ЕГЭ по информатике: Задания 5, 12, 23 — исполнители

Три задания ЕГЭ по информатике проверяют умение исполнять и анализировать алгоритмы для формальных исполнителей. В задании 5 алгоритм строит по натуральному числу N новое число R, преобразуя его двоичную запись, — нужно найти R или, наоборот, исходное N, при котором результат удовлетворяет условию. В задании 12 по спецификации 2026 года требуется исполнить алгоритм для исполнителя с фиксированным набором команд; в демонстрационном варианте 2026 года это исполнитель МТ — машина Тьюринга с лентой, головкой, состояниями и программой, записанной таблицей. В задании 23 нужно посчитать количество программ исполнителя, переводящих одно число в другое, с ограничениями на траекторию. Элементы кодификатора — 3.3 (исполнение и анализ алгоритмов), 3.1 (машина Тьюринга как модель вычислений) и 3.16 (динамическое программирование).

В заданиях типа 5 материал учит видеть арифметику за действиями с двоичной записью: дописать справа цифру — значит умножить на 2 и прибавить эту цифру. Отсюда простые формулы вроде R = 4N + 2b, которые позволяют быстро найти граничное N без перебора. Для машины Тьюринга разбираются программы инверсии слова и прибавления единицы к двоичному числу: результат на ленте, число тактов, роль пустого символа λ и команды остановки. Для задания 23 — табличный метод: число программ из каждого числа, правило произведения для обязательной точки траектории, обнуление для запрещённой точки и рекурсивное решение на Python.

Все ответы вычислены программами: алгоритмы задания 5 выполнены для всех N, программы МТ — на симуляторе, количества программ задания 23 проверены и динамикой, и полным перечислением программ.

Письменная работа предлагает вывести формулу для R, составить программу МТ, выписать ленту по тактам, построить таблицу количества программ и написать функцию подсчёта с запрещённой точкой. На устном экзамене нужно решить по задаче каждого типа и объяснить метод. Карточки собирают определения и приёмы.

Главная цель — научиться быстро исполнять алгоритмы разных исполнителей вручную и проверять себя короткой программой: преобразование двоичной записи числа в задании 5, машину Тьюринга в задании 12 и подсчёт числа программ динамикой в задании 23, включая обязательные и запрещённые промежуточные значения. Порядок работы с материалом такой: сначала пройдите тест и прочитайте объяснения к ошибкам, затем повторите карточки, после этого выполните письменную работу, сверяясь с ключевыми пунктами, и в конце проверьте себя на устном экзамене, где задачи нужно решать без подсказок и объяснять ход рассуждения.

• Выполнять алгоритмы над двоичной записью числа и выражать результат формулой
• Находить граничное исходное значение N без полного перебора
• Исполнять программу машины Тьюринга и считать такты
• Считать число программ исполнителя табличным методом
• Учитывать обязательные и запрещённые числа траектории

Кодификатор ЕГЭ 2026 по информатике: 3.3 — определение результатов работы алгоритмов и исходных данных по результату; 3.1 — машина Тьюринга; 3.16 — динамическое программирование, подсчёт количества вариантов. Спецификация 2026: задания 5, 12, 23.