Сколько баллов дают за задание 12 ЕГЭ по информатике?

До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.

Сколько времени тратить на задание 12?

Примерное время выполнения по спецификации ФИПИ — 6 минут; на весь экзамен отводится 235 минут.

Где потренироваться на задании 12?

В тренажёре «Ранга» по этому номеру сейчас 38 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Задание 12: Исполнитель МТ (машина Тьюринга)

Теория к заданию № 12 ЕГЭ-2027 по информатике: коротко правило, приём решения по шагам, два разобранных примера из банка «Ранга» и ошибки, на которых теряют балл.

Что проверяет задание 12

Что проверяет: Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд. В КИМ-2027 здесь — исполнитель МТ: головка на бесконечной ленте, программа задана таблицей состояний.
Баллы: до 1 балл из 29 первичных
Уровень: повышенный
Время: около 6 минут (примерное время по спецификации ФИПИ; на весь экзамен — 235 минут)
Формат: краткий ответ; решается и без программы

Правило и теория

Лента разбита на ячейки, в каждой — один символ алфавита, в том числе пустой символ λ. Головка видит одну ячейку.
Команда в таблице для пары (состояние q, символ a): записать символ, сдвинуть головку (L — влево, R — вправо, N — на месте) и перейти в новое состояние.
Работа начинается в состоянии q0 и заканчивается при переходе в состояние останова (обычно обозначено в условии).
Удобно моделировать МТ словарём в Python: prog[(q, a)] = (b, move, q2); ленту — словарём «позиция → символ» с λ по умолчанию.
Многие программы реализуют арифметику над записью числа: инверсия цифр, прибавление 1, сдвиг — узнай действие, и ответ получится без трассировки.

Приём решения по шагам

Перепиши таблицу программы и начальное положение головки.
Выполни 3–5 тактов вручную и пойми, что делает программа (например, инвертирует разряды справа налево).
Выполни программу до останова (вручную или симуляцией) и прочитай результат на ленте.
Переведи результат в требуемую форму (десятичное число, количество символов и т. п.).

Два разобранных примера из банка «Ранга»

Сначала реши сам — потом раскрой ответ и разбор. Ответы взяты из банка, по которому работает тренажёр, и проверены.

Пример 1

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя, включая специальный пустой символ λ. На каждом такте головка находится в одном из состояний q0, q1, …; в начальный момент — в состоянии q0. Программа задаётся таблицей: на пересечении строки состояния и столбца символа записана команда из трёх элементов через запятую: записываемый в текущую ячейку символ, сдвиг («L» — влево, «R» — вправо, «S» — остановка после выполнения команды) и новое состояние. Сдвиг происходит после записи символа. Программа работы исполнителя (прочерк — пара «состояние – символ» невозможна): состояние | λ | 0 | 1 q0 | λ, L, q1 | — | — q1 | λ, S, q1 | 1, L, q1 | 0, L, q1 На ленте в соседних ячейках записано двоичное представление числа 2025 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Определи результат выполнения программы. В ответе запиши получившееся на ленте число в десятичной системе счисления.

Показать ответ и разбор

Ответ: 22

2025 = 11111101001₂. Головка идёт справа налево и меняет каждую цифру на противоположную, на пустой ячейке слева останавливается: все разряды инвертированы. Значение: (2^k − 1) − N, где k — число разрядов. На ленте остаётся 00000010110₂ = 22. Ответ: 22.

Карточка банка «Ранга» informatics-12-0 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Пример 2

Исполнитель МТ — читающая и записывающая головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке ровно один символ, пустой символ обозначен «λ». За один такт головка, находясь в состоянии qi и обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, сдвигается влево (L), вправо (R) или останавливается (S) и переходит в новое состояние. Сдвиг выполняется после записи. В начальный момент головка в состоянии q0. На ленте в соседних ячейках записано двоичное представление числа 2482 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Программа работы исполнителя — в таблице на рисунке (строки — состояния, столбцы — символ в текущей ячейке; в клетке — записываемый символ, сдвиг, новое состояние): q0: λ → λ, L, q1 q1: λ → 1, L, q2; 0 → 0, L, q1; 1 → 1, L, q1 q2: λ → λ, S, q2 Определи результат выполнения программы. В ответе запиши получившееся число в десятичной системе счисления.

Таблица программы исполнителя МТ: состояния q0, q1, q2, символы λ, 0, 1.

Показать ответ и разбор

Ответ: 6578

2482 = 100110110010₂ (12 цифр). Программа проходит число справа налево, не меняя цифр, и дописывает слева единицу. На ленте после остановки: 1100110110010 (пустые ячейки не считаются), это 6578 в десятичной системе. Ответ: 6578.

Карточка банка «Ранга» informatics-12-30 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

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

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

Тренироваться: 38 заданий этого номера

Тренажёр «Ранга»: условие, проверка ответа сразу и разбор по шагам. Первое задание — без регистрации, дальше — в кабинете ученика.

Решать задание 12

Кабинет ученика · Разбор задания 12: 10 примеров

Частые вопросы о задании 12

Сколько баллов дают за задание 12 ЕГЭ по информатике?: До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.
Сколько времени тратить на задание 12?: Примерное время выполнения по спецификации ФИПИ — 6 минут; на весь экзамен отводится 235 минут.
Что проверяет задание 12?: Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд. В КИМ-2027 здесь — исполнитель МТ: головка на бесконечной ленте, программа задана таблицей состояний.
Где потренироваться на задании 12?: В тренажёре «Ранга» по этому номеру сейчас 38 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Источник: ФИПИ — демоверсии, спецификации, кодификаторы ЕГЭ, архив материалов 2027 года (проект спецификации и демоверсии КИМ ЕГЭ-2027 ФИПИ по информатике (опубликован как проект; 27 заданий, 29 первичных баллов, экзамен на компьютере)).

Тексты теории — авторские материалы «Ранга». Примеры — авторские тренировочные задания в формате ЕГЭ, не официальные задания ФИПИ. Мы не обещаем конкретных баллов: результат зависит от твоей работы.