Задание 12: Формальные исполнители. Машина Тьюринга

• Тема: Формальные исполнители. Машина Тьюринга (Редактор, Робот, Чертёжник, МТ).
• Ответ: строка или число.
• Балл: 1. Время: 6 мин. Сложность: повышенный.

Общая информация

Задание 12 проверяет умение выполнять алгоритмы для различных формальных исполнителей.

Задания: N12.Машина Тьюринга

Типы исполнителей

1. Редактор

Работает с буквенно-цифровыми последовательностями (строками).

2. Робот

Работает с шахматным полем или сеткой. Может перемещаться по клеткам и выполнять действия.

3. Чертёжник

Применяет алгоритмы на координатной плоскости. Похож на Черепаху, но с другими командами.

4. Машина Тьюринга (МТ)

Работает с лентой, считывает и записывает символы, перемещается по ленте.

Исполнитель «Редактор»

Основные команды

1. Заменить (v, w)

   • Заменяет первое левое вхождение строки v на последовательность w
   • Если вхождения нет, строка не меняется
   • Поиск идёт слева направо

2. Обнаружено (v)

   • Проверяет наличие подстроки v в строке
   • Возвращает "правда" или "ложь"
   • Строка остаётся неизменной

Дополнительные команды (могут встречаться)

• Удалить (v) - удаляет первое вхождение v
• Вставить (v, позиция) - вставляет v в указанную позицию
• Найти (v) - возвращает позицию первого вхождения v

Алгоритм решения

Шаг 1: Анализ задачи

1. Определить тип исполнителя (Редактор, Робот, Чертёжник, МТ)
2. Выписать все команды и их описание
3. Зафиксировать начальное состояние (исходная строка, позиция и т.д.)

Шаг 2: Выполнение алгоритма

1. Составить таблицу трассировки:

   Шаг	Команда	Состояние строки	Примечание
   0	-	Исходная строка	Начальное состояние
   1	Заменить(...)	Новая строка	Результат замены
   2	Обнаружено(...)	Та же строка	Проверка условия
   ...	...	...	...

2. Выполнять команды строго по порядку:

   • После каждой команды фиксировать новое состояние
   • Учитывать условия (если есть)
   • Выполнять циклы полностью

3. Особое внимание:

   • Команда "Заменить" ищет первое левое вхождение
   • После замены поиск следующего вхождения начинается с начала строки (или с позиции после замены, в зависимости от формулировки)
   • Условия проверяются перед выполнением зависящих от них команд

Шаг 3: Проверка результата

1. Проверить выполнение всех команд
2. Проверить правильность замен - убедиться, что заменено первое вхождение
3. Записать ответ в требуемом формате

Пример решения (Редактор)

Задача: Исполнитель Редактор получает на вход строку и выполняет следующий алгоритм:

НАЧАЛО
ПОКА нашлось (111)
  заменить (111, 2)
  заменить (222, 1)
КОНЕЦ ПОКА
КОНЕЦ

Определите, какая строка получится в результате применения этого алгоритма к строке, состоящей из 100 единиц.

Решение:

1. Начальное состояние: строка из 100 единиц: 111...1 (100 раз)

2. Трассировка:

   • Шаг 1: Найдено "111" → заменяем на "2": 2 + 111...1 (97 единиц)
   • Шаг 2: Найдено "111" → заменяем на "2": 22 + 111...1 (94 единицы)
   • Шаг 3: Найдено "111" → заменяем на "2": 222 + 111...1 (91 единица)
   • Шаг 4: Найдено "222" → заменяем на "1": 1 + 111...1 (91 единица)
   • Шаг 5: Найдено "111" → заменяем на "2": 12 + 111...1 (88 единиц)
   • ... (процесс продолжается)

3. Анализ:

   • Каждые 3 единицы заменяются на "2"
   • "222" заменяется на "1"
   • Процесс цикличен: 111 → 2, 222 → 1

4. Результат: После всех замен останется строка, которая зависит от остатка от деления 100 на 3.

5. Ответ: (требуется полный расчёт)

Особенности работы с Редактором

Поиск вхождений

• "Первое левое вхождение" означает, что поиск идёт слева направо
• После замены поиск может начинаться:
  • С начала строки (в большинстве задач)
  • С позиции после замены (уточняется в условии)

Циклы

• ПОКА условие - выполняется, пока условие истинно
• ПОВТОРИ n раз - выполняется ровно n раз
• Важно отслеживать, когда условие цикла становится ложным

Условия

• ЕСЛИ условие ТО команды - выполняется только при истинном условии
• ЕСЛИ условие ТО ... ИНАЧЕ ... - выбор между двумя вариантами

Типичные ошибки

1. Неправильный поиск вхождений - нужно искать первое левое вхождение, а не все
2. Ошибки в циклах - не учитывается момент выхода из цикла
3. Пропуск шагов - не все команды выполняются
4. Неправильная интерпретация команд - важно внимательно читать описание
5. Ошибки при множественных заменах - нужно отслеживать все изменения строки

Полезные советы

1. Составляйте таблицу трассировки - это помогает не пропустить шаги
2. Внимательно читайте описание команд - особенно про поиск вхождений
3. Отслеживайте циклы - фиксируйте состояние после каждой итерации
4. Проверяйте условия - перед выполнением зависящих команд проверяйте условие
5. Используйте обратный ход - если нужно восстановить исходные данные
6. Проверяйте результат - выполняйте алгоритм повторно для проверки

Остальные исполнители - подробно

1) Робот

Исполнитель Робот работает в клетчатом поле/лабиринте. Обычно требуется довести Робота до клетки, закрасить нужные клетки или проанализировать работу алгоритма.

Таблица команд Робота

Алгоритм решения задач на Робота

1. Перепишите стартовую позицию Робота и направление (если задано).
2. Выпишите команды и условия цикла (ПОКА, ЕСЛИ).
3. Выполняйте команды пошагово в таблице трассировки: шаг, клетка, проверка условия, действие.
4. Каждый раз проверяйте, не идёт ли команда движения в стену.
5. В конце запишите позицию/число закрашенных клеток/полученный маршрут (что спрашивает задача).

Шаблон таблицы:

2) Чертёжник

Чертёжник работает на координатной плоскости. Основная идея: каждая команда добавляет вектор смещения к текущей точке.

Таблица команд Чертёжника

Алгоритм решения задач на Чертёжника

1. Выпишите все векторы смещения из условия.
2. Для каждого блока Повтори k посчитайте суммарный вектор блока и умножьте на k.
3. Сложите все смещения по x и по y отдельно.
4. Если по условию возврат в стартовую точку, составьте систему:
   • сумма по x = 0
   • сумма по y = 0
5. Найдите неизвестные параметры (n, a, b) и подставьте в ответ.

Шаблон таблицы:

3) Машина Тьюринга

Машина Тьюринга (МТ) работает с лентой из ячеек. На каждом шаге выбирается команда по паре (текущее состояние, текущий символ).

Таблица команд МТ

Примечание: в разных сборниках обозначения могут отличаться, но логика одинаковая.

Алгоритм решения задач на МТ

1. Запишите начальную ленту, позицию головки и начальное состояние.
2. На каждом шаге ищите в таблице команд нужную ячейку:
   • строка - текущее состояние;
   • столбец - текущий символ.
3. Выполняйте команду в фиксированном порядке:
   • записать символ;
   • сдвинуть головку;
   • перейти в новое состояние.
4. Ведите трассировку до команды останова.
5. Снимите ответ: итоговая лента, позиция головки или нужный фрагмент (по условию).

Шаблон таблицы трассировки:

Составлено: Лилия С.
Источники: КИМ ЕГЭ 2026, открытый банк ФИПИ, спецификация ЕГЭ по информатике

Удачи на экзамене! 🎓