Задание 13. Анализ хода исполнения алгоритма: ЕГЭ по информатике

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

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

Машина Тьюринга (МТ) — абстрактный исполнитель, работающий на бесконечной ленте, разбитой на ячейки, с головкой, которая может читать и записывать символы, а также сдвигаться влево (L) или вправо (R) или останавливаться…
Таблица команд МТ: строки соответствуют состояниям головки (q0, q1, q2, ...), столбцы — символам алфавита (включая пустой символ λ). В клетке на пересечении строки и столбца записана команда, выполняемая, если головка…
Команда состоит из трёх элементов через запятую: 1) символ, который записывается в текущую ячейку (может совпадать с уже записанным); 2) направление сдвига: L (влево), R (вправо), S (остановка); 3) новое состояние…
Сдвиг головки происходит после записи символа в текущую ячейку. То есть сначала выполняется запись, затем сдвиг, затем смена состояния.
Если пара «символ–состояние» отсутствует в таблице (пустая клетка), это означает, что такая ситуация невозможна при правильной работе программы, и выполнение не должно до неё дойти.
Начальная конфигурация: на ленте записано некоторое количество символов (например, 'Z' или '1'), все остальные ячейки заполнены пустым символом λ. Головка находится в определённом состоянии (обычно q0) и обозревает…

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

Машина Тьюринга (МТ): абстрактная вычислительная машина, состоящая из бесконечной ленты, головки и управляющего устройства, работающая по…
Состояние: внутреннее состояние головки МТ, обозначаемое q0, q1, q2 и т.д.
Алфавит: набор допустимых символов на ленте, включая пустой символ λ.
Пустой символ (λ): обозначает отсутствие символа в ячейке.
Команда: тройка (записываемый символ, направление сдвига, новое состояние).
Сдвиг L: перемещение головки на одну ячейку влево.
Сдвиг R: перемещение головки на одну ячейку вправо.
Сдвиг S: остановка выполнения программы.

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

Путают строки и столбцы таблицы: считают, что строки — символы, а столбцы — состояния. В результате выбирают неверную команду.
Неправильно понимают направление сдвига: L — влево, R — вправо, но иногда путают из-за зеркального восприятия. Или забывают, что сдвиг происходит после записи, и меняют состояние до сдвига.
Ошибаются при переводе двоичного числа в десятичное: например, читают число справа налево или неверно определяют разряды.
Пропускают шаг изменения переменных (запись символа) и сразу переходят к сдвигу, теряя информацию.

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

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

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

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

← Предыдущая тема: Задание 12. Исполнение алгоритма для исполнителя с фиксированным набором команд
Следующая тема: Задание 14. Позиционные системы счисления

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