Задание 12. Исполнение алгоритма для исполнителя с фиксированным набором команд: ЕГЭ по информатике

Задание 12 ЕГЭ по информатике проверяет умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд. В демоверсии используется исполнитель МТ — машина Тьюринга с головкой, лентой и таблицей переходов. Ученик должен проследить работу программы по тактам, изменить состояние…

Что нужно знать

Исполнитель МТ имеет бесконечную ленту, разделённую на ячейки; в каждой ячейке ровно один символ из алфавита A, включая пустой символ λ (a0).
Головка МТ находится в одном из состояний Q = {q0, q1, …, qn–1}; начальное состояние обычно q0.
За один такт головка читает текущий символ, заменяет его согласно программе, перемещается на соседнюю ячейку (L — влево, R — вправо, S — остаётся на месте) и переходит в новое состояние.
Программа задаётся таблицей: строки — состояния, столбцы — символы; на пересечении указана команда вида «новый символ, направление, новое состояние».
Если в программе для пары (состояние, символ) нет команды, исполнитель останавливается (или поведение не определено — в демо всегда есть команда).
В демоверсии программа заменяет все символы Z на X и останавливается в первой ячейке слева от последовательности X.

Термины и понятия

Исполнитель МТ: абстрактная машина Тьюринга, работающая на бесконечной ленте с головкой.
Лента: бесконечная последовательность ячеек, в каждой хранится символ из алфавита.
Головка: устройство, которое читает и записывает символ в текущей ячейке и может перемещаться влево или вправо.
Состояние: внутреннее состояние исполнителя (q0, q1, …), определяющее, какую строку программы использовать.
Такт (шаг): один цикл работы исполнителя, включающий чтение, замену, перемещение и смену состояния.
Команда: тройка (новый символ, направление, новое состояние), записанная в ячейке таблицы программы.
Направление L: перемещение головки на одну ячейку влево.
Направление R: перемещение головки на одну ячейку вправо.

Частые ошибки

Путают направления L и R: L — влево, R — вправо. Ошибка приводит к неверному положению головки.
Неверно читают таблицу: берут команду из другой строки или столбца. Нужно внимательно сопоставлять текущее состояние и символ.
Забывают заменить символ в текущей ячейке перед перемещением. Команда включает и замену, и движение.
Неправильно определяют момент остановки: если для пары (состояние, символ) нет команды, исполнитель останавливается, но в демо всегда есть команда.

Как пройти тему

В курсе «Информатика» тема «Задание 12. Исполнение алгоритма для исполнителя с фиксированным набором команд» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Задание 11. Кодирование изображений и звука
Следующая тема: Задание 13. Анализ хода исполнения алгоритма

Все темы: ЕГЭ по информатике