Рекомендации ФИПИ по самостоятельной подготовке к ЕГЭ по информатике (2026)

Текст документа

Текст извлечён из официального PDF ФИПИ автоматически: формулы, таблицы и рисунки могут отображаться неточно — сверяйтесь с документом выше.

Федеральная служба по надзору в сфере образования и науки ФГБНУ «Федеральный институт педагогических измерений»

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ обучающимся по организации самостоятельной подготовки к ЕГЭ 2026 года ИНФОРМАТИКА

Москва, 2026

Автор-составитель: С.С. Крылов

Методические рекомендации предназначены для обучающихся 11 класса, планирующих сдавать ЕГЭ 2026 г. по информатике. Они содержат советы разработчиков контрольных измерительных материалов ЕГЭ и полезную информацию для организации индивидуальной подготовки к ЕГЭ. В пособии описаны структура и содержание контрольных измерительных материалов ЕГЭ 2026 г., приведён индивидуальный план подготовки к экзамену, указаны темы, на освоение/повторение которых целесообразно обратить особое внимание. Даны рекомендации по выполнению разных типов заданий, работе с открытым банком заданий ЕГЭ и другими дополнительными материалами, полезные ссылки на информационные материалы ФИПИ.

Дорогие друзья! Скоро вам предстоит сдать единый государственный экзамен (ЕГЭ) по информатике. Ваша основная задача – показать хорошую подготовку, благодаря которой сможете поступить в выбранный вами вуз. Данные рекомендации помогут вам в подготовке к экзамену. В 2026 г., как и в 2025 г., вариант КИМ ЕГЭ по информатике состоит как из заданий, для выполнения которых необходим компьютер, так и из заданий в традиционной форме. В табл. 1 представлено распределение заданий ЕГЭ 2026 г. по разделам курса информатики с учётом обновлённого кодификатора проверяемых требований к результатам освоения основной образовательной программы среднего общего образования и элементов содержания для проведения ЕГЭ по информатике и содержания федеральной образовательной программы среднего общего образования. Таблица 1 Номер раздела 1

Название раздела

Номер Что проверяется задания Цифровая 13 Умение использовать маску подсети грамотность 22 Умение строить математические модели для решения практических задач. Знание архитектуры современных компьютеров, многопроцессорных систем Теоретические 1 Умения представлять и считывать данные основы в разных типах информационных моделей информатики (схемы, карты, таблицы, графики и формулы) 2 Умение строить таблицы истинности и логические схемы 4 Умения кодировать и декодировать информацию 7 Умение определять объём памяти, необходимый для хранения графической и звуковой информации 8 Знание основных понятий и методов, используемых при измерении количества информации 11 Умение подсчитывать информационный объём сообщения 14 Знание позиционных систем счисления 15 Знание основных понятий и законов математической логики 19 Умение анализировать алгоритм логической игры 20 Умение найти выигрышную стратегию игры 21 Умения построить дерево игры по заданному алгоритму и найти выигрышную стратегию Алгоритмы и 5 Формальное исполнение простого алгоритма, записанного на естественном языке, или программирование умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд, или умение восстанавливать 3

Номер раздела

Название раздела

Номер задания

Информационные технологии

Что проверяется исходные данные линейного алгоритма по результатам его работы Умение определять возможные результаты работы простейших алгоритмов управления исполнителями и вычислительные алгоритмы Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд Умение вычислять рекуррентные выражения Умения составить алгоритм обработки числовой последовательности и записать его в виде простой программы (10–15 строк) на языке программирования Умение анализировать ход исполнения алгоритма Умение создавать собственные программы (10–20 строк) для обработки символьной информации Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации Умение обрабатывать целочисленную информацию с использованием сортировки Умение искать информацию в реляционных базах данных Умение обрабатывать числовую информацию в электронных таблицах Умение осуществлять информационный поиск средствами текстового процессора Умение использовать электронные таблицы для обработки целочисленных данных Умение выполнять последовательность решения задач анализа данных: сбор первичных данных, очистка и оценка качества данных, выбор и построение модели, преобразование данных, визуализация данных, интерпретация результатов

На основании табл. 1 можно составить индивидуальный план подготовки к экзамену, учитывая ваш текущий уровень освоения учебного материала. Рекомендуем вам прорешать тренировочный вариант ЕГЭ, например демонстрационный вариант КИМ этого года или прошлых лет, открытые варианты и задания из открытого банка заданий ЕГЭ, размещённого на официальном сайте ФГБНУ «ФИПИ» <www.fipi.ru>. Также можно воспользоваться различными сборниками вариантов, при этом следует обращать внимание на соответствие структуры и тематики заданий этих вариантов официальному демонстрационному варианту КИМ. Если выполнение заданий по какой-либо теме вызвало затруднения, то на изучение/повторение соответствующей темы следует отвести больше времени. Не следует изначально планировать себе слишком жёсткий график, который вы вряд ли сможете соблюдать, – будьте реалистом.

В графах «Пройдено» и «Необходимо изучить/повторить» табл. 2 отметьте не только прохождение соответствующего учебного материала, но и параграфы учебников или других учебных материалов, которые соответствуют нужной теме. Так вы сформируете индивидуальный план подготовки к экзамену. Таблица 2 №

Проверяемые элементы Пройдено содержания 1. Цифровая грамотность 1.1 Умение использовать маску подсети 1.2 Умение планировать последовательно и параллельно выполняемые процессы 2. Теоретические основы информатики 2.1 Умения представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы) 2.2 Умение строить таблицы истинности и логические схемы 2.3 Умения кодировать и декодировать информацию 2.4 Умение определять объём памяти, необходимый для хранения графической и звуковой информации 2.5 Знание основных понятий и методов, используемых при измерении количества информации 2.6 Умение подсчитывать информационный объём сообщения 2.7 Знание позиционных систем счисления 2.8 Знание основных понятий и законов математической логики 2.9 Умение анализировать алгоритм логической игры 2.10 Умение найти выигрышную стратегию игры 2.11 Умения построить дерево игры по заданному алгоритму и найти выигрышную стратегию 3. Алгоритмы и программирование исполнение 3.1 Формальное простого алгоритма, записанного на естественном

Необходимо изучить/повторить

Период времени

Проверяемые элементы содержания языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд, или умение восстанавливать исходные данные линейного алгоритма по результатам его работы 3.2 Умение определять возможные результаты работы простейших алгоритмов управления исполнителями и вычислительные алгоритмы 3.3 Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд вычислять 3.4 Умение рекуррентные выражения 3.5 Умения составить алгоритм обработки числовой последовательности и записать его в виде простой программы (10–15 строк) на языке программирования 3.6 Умение анализировать ход исполнения алгоритма 3.7 Умение создавать собственные программы (10–20 строк) для обработки символьной информации 3.8 Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации обрабатывать 3.9 Умение целочисленную информацию с использованием сортировки 4. Информационные технологии 4.1 Умение находить информацию в реляционных базах данных обрабатывать 4.2 Умение числовую информацию в электронных таблицах осуществлять 4.3 Умение информационный поиск средствами текстового процессора использовать 4.4 Умение электронные таблицы для обработки целочисленных данных

Пройдено

Необходимо изучить/повторить

Период времени

Проверяемые элементы содержания Умение выполнять последовательность решения задач анализа данных: сбор первичных данных, очистка и оценка качества данных, выбор и построение модели, преобразование данных, визуализация данных, интерпретация результатов

Пройдено

Необходимо изучить/повторить

Период времени

Рассмотрим подробнее выполнение заданий экзаменационной работы, сгруппированных по разделам курса, и типичные ошибки, допущенные участниками ЕГЭ прошлых лет, в табл. 3. Таблица 3 Номер задания 13

Рекомендации по выполнению

Типичные ошибки и рекомендации по их предотвращению

1. Цифровая грамотность

Рекомендуется повторить правила Необходимо различать понятия формирования сетевых адресов «чётное двоичное число» и «двоичное с использованием маски подсети. число с чётным количеством Также для выполнения этого единичных разрядов». задания необходимо свободно Так, например, число 11102 чётное, но оперировать с числами, количество его единичных разрядов записанными в двоичной равно трём, т.е. нечётно и шестнадцатеричной системах счисления Для выполнения задания следует по- Необходимо учитывать, что самая строить модель в виде графа или длинная по количеству процессов таблицы, наглядно показывающую цепочка может не быть самой длинной порядок и продолжительность по продолжительности выполнения. выполнения процессов Игнорирование этого факта приводит к ошибочному решению

2. Теоретические основы информатики

Это довольно простое задание; для Как и в большинстве простых заданий, его выполнения требуется основные ошибки происходят из-за понимание того, что наличие ребра торопливости и невнимательности между вершинами A и Б графа означает, что на пересечении соответствующих строки и столбца в таблице стоит ненулевое значение, равное длине дороги из A в Б. Справедливо и обратное утверждение: если на пересечении строки и столбца в таблице стоит ненулевое значение, то соответствующие вершины графа соединены ребром

Номер Рекомендации по выполнению задания 2 Необходимо повторить темы «Логические значения, операции и выражения», «Таблицы истинности» (особенно таблицы истинности для конъюнкции и дизъюнкции)

Наиболее простой, хоть и не самый быстрый, переборный способ решения: последовательным прибавлением единицы перебираются все возможные кодовые слова, пока не встретится подходящее, удовлетворяющее условию Фано

В случае изображения с заданной глубиной цвета необходимо определить информационный объём (количество бит), отводимых под один пиксель; далее объём изображения вычисляется произведением информационного объёма пикселя на ширину и высоту изображения в пикселях. Если известен объём изображения, но неизвестна глубина цвета, решается обратная задача. Для того чтобы верно определить информационный объём пикселя, нужно владеть алфавитным подходом к измерению количества информации, т.е. знать, сколько цветов можно закодировать двоичным словом с длиной N. Для звуковых файлов используется аналогичный подход

Типичные ошибки и рекомендации по их предотвращению Игнорирование прямо указанного в условии задания требования, что заполненная таблица истинности не должна содержать одинаковые строки. Это приводит к внешне правдоподобному, но на самом деле неверному решению Из-за невнимательного чтения условия задания экзаменуемые иногда не замечают, что требуется найти кодовое слово минимальной длины с максимальным (минимальным) числовым значением. Кроме того, если в задании указано, что несколько букв остались без кодовых слов, то кодовое слово для указанной буквы должно быть подобрано таким образом, чтобы осталась возможность найти кодовые слова, удовлетворяющие условию Фано, и для других букв. Так, например, если нужно закодировать буквы А, Б, В, Г и букву A закодируем как 1, то буквы Б, В, Г уже никак не получится закодировать с соблюдением условия Фано, поэтому длину кодового слова для А придётся увеличить Если вычисления получаются слишком громоздкими, значит, вы неправильно решаете задачу. Удобно выделить во всех множителях степени двойки, тогда умножение сведётся к сложению показателей степеней, а деление – к вычитанию

Номер Рекомендации по выполнению задания 8 Для выполнения этого задания необходимо овладеть алфавитным подходом к измерению количества информации и операциями с числами в различных системах счисления 11 Для выполнения этого задания также необходимо овладеть алфавитным подходом к измерению количества информации и повторить единицы измерения количества информации 14

19–21

Следует повторить определение позиционной системы счисления, а также потренироваться в решении аналогичных задач в десятичной системе счисления. Начать выполнение задания следует с перевода всех используемых чисел в одну систему счисления (в ту из используемых, у которой наименьшее основание) Необходимо также повторить свойства импликации и, если эта операция содержится в выражении, избавиться от неё, заменив на комбинацию отрицания и дизъюнкции Эта группа заданий объединена общей частью условия, в которой сформулированы правила игры, приведённой в задании 19. У этого задания довольно длинное условие. Внимательно прочитайте его, убедитесь, что вам полностью понятны правила логической игры. Задание 19 из этой группы обычно самое простое, и выполнить его нетрудно; для выполнения задания 20 может потребоваться анализ возможных ходов игроков с помощью дерева игры. Для выполнения задания 21, если его решение не следует из результатов выполнения задания 20, следует построить на черновике полное или неполное дерево игры в виде схемы или таблицы

Типичные ошибки и рекомендации по их предотвращению При использовании способа решения при помощи системы счисления с основанием N следует помнить, что слова в списке нумеруются с единицы, поэтому числу 0 будет соответствовать первое слово Необходимо учитывать, что в заданиях этой линии для кодирования слов обычно отводится одинаковое и минимально возможное целое число байт, а для кодирования символов – одинаковое и минимально возможное целое количество бит Основные ошибки связаны с невнимательностью при выполнении арифметических действий в недесятичных системах счисления, например вычитание единицы в ситуации типа: 10100002 – 1

Важно понимать, что выражение должно быть тождественно истинно, т.е. истинно при любых допустимых значениях переменных x и у, а не только при некоторых наборах значений При выполнении заданий рассмотрены не все возможные ходы проигрывающего игрока, которые он может сделать при игре выигрывающего игрока по выигрышной стратегии

Номер задания 5

Рекомендации по выполнению

Типичные ошибки и рекомендации по их предотвращению

3. Алгоритмы и программирование

В заданиях этой линии, как правило, Как и в других заданиях базового требуется произвести простой уровня сложности, ошибки вызваны анализ небольшого алгоритма, недостаточной внимательностью записанного на естественном языке. и отсутствием или поверхностностью Для этого достаточно определить самостоятельной проверки поматематическую или логическую лученного ответа закономерность, связывающую исходные данные и результат выполнения алгоритма. Для выявления такой закономерности может потребоваться несколько раз выполнить алгоритм с исходными данными. После получения ответа необходимо его проверить – действительно ли он отвечает описанию алгоритма, и, если, например, нужно было найти некоторое максимальное значение, полезно убедиться, что не подходит следующее в порядке возрастания допустимое значение. Поскольку во многих заданиях этой линии используется обработка двоичных чисел, рекомендуется повторить, как выполняются арифметические операции в двоичной системе счисления, в том числе умножение числа на 2 Для успешного выполнения этого Необходимо обратить особое внимазадания следует прежде всего на ос- ние на вопрос задания, чтобы понять, нове анализа алгоритма определить учитываются ли точки на границах тип, размеры и взаимное располо- фигур, нужно ли искать площадь или жение фигур, после чего выполнить периметр необходимые простые расчёты Как обычно, для выполнения Для выполнения этого задания не задания на анализ алгоритма нужно рекомендуется писать программу на найти закономерность, связывающую Python или другом языке высокого исходные данные и результат уровня, поскольку это, скорее всего, работы алгоритма, для чего нужно займёт много времени и может выполнить несколько шагов породить ошибки. алгоритма и проанализировать Намного проще выполнить несколько результат. тактов программы МТ вручную, что В демонстрационном варианте КИМ позволит понять логику этого года приведён новый тип взаимодействия внешней памяти алгоритмического исполнителя – (лента МТ) с внутренней памятью МТ со своей системой команд. (состояния МТ) и разобраться, какой Чтобы успешно выполнять задания простой алгоритм записан на языке для нового исполнителя, команд МТ необходимо потренироваться в 10

Номер задания

Рекомендации по выполнению выполнении, составлении и анализе программ МТ. Важно понимать роль состояний в командах МТ как разновидности внутренней памяти МТ Для успешного выполнения этого задания следует сначала проанализировать заданное рекурсивное выражение на предмет его упрощения и наиболее эффективного способа организации вычислений. Так, например, следует учитывать, что для вычисления значения выражения вида N!/(N – 1)! нет необходимости писать рекурсивную программу вычисления факториала. Следует заметить, что при больших значениях N такая программа либо будет работать крайне долго, либо аварийно завершится из-за ограничений на выделяемые ей ресурсы в зависимости от используемой среды программирования Для успешного выполнения этого задания рекомендуется организовать ввод последовательности из файла с последующим сохранением её в массиве, далее, двигаясь по массиву, при первом проходе определить условия отбора пар или троек элементов, а при втором проходе подсчитать количество пар (троек, отдельных элементов), удовлетворяющих этому условию

Один из распространённых способов выполнения этого задания – выписать последовательность рекуррентных формул, определяющих, сколькими способами можно получить текущее число из ближайших предшественников, одновременно производя вычисления по этим формулам. «Ближайших» в данном случае означает тех, из которых текущее число получается в резуль-

Типичные ошибки и рекомендации по их предотвращению

Если написанная вами программа работает слишком долго или выдаёт сообщения о превышении допустимого количества рекурсивных вызовов, то необходимо критически проанализировать своё решение и найти более эффективный способ вычисления выражения из условия, упростив его. При выполнении этого задания также крайне важно верно сформулировать условие завершения (продолжения) рекурсивного спуска и действий, выполняемых при каждом рекурсивном вызове

Распространённая техническая ошибка – некорректный ввод из файла, что может привести к неполному или повторному вводу входных данных. Содержательными ошибками могут оказаться неверные формулировки условий в операторах ветвления и циклах, например замена строгого равенства на нестрогое и наоборот, ошибки индексации, ошибки инициализации переменных, неверно выбранные знаки неравенства («больше» вместо «меньше» и наоборот) Не стоит пытаться перечислить все пути в явном виде: это слишком трудоёмко и, скорее всего, в итоге приведёт к ошибке. Распространённая ошибка – экзаменуемые в процессе рекуррентных вычислений забывают о том, что траектория обязана содержать указанные в условии числа или не содержать их

Номер задания

Рекомендации по выполнению

Типичные ошибки и рекомендации по их предотвращению

тате применения программы, состоящей из одной команды. Когда текущее число сравняется с заданным, количество таких способов и станет искомым числом программ Для успешного выполнения этого за- Важно правильно рассмотреть все воздания требуется написать алгоритм, можные комбинации текущего состореализующий простейший конечный яния автомата и встреченной буквы автомат с сумматором. Состояние автомата и значение сумматора изменяются в зависимости от встреченной буквы и текущего состояния В этом задании требуется написать При отладке программы следует циклы перебора некоторого коли- уделять особое внимание корректчества целых чисел и разложения ности выделения простых множителей этих чисел на простые множители с последующей обработкой. Для выполнения заданий такого типа важно уметь применять операции деления нацело и нахождения остатка Для выполнения этого задания нуж- При отладке программы следует удено уметь организовывать лять особое внимание верному выбору сортировку целочисленных входных направления сортировки и обработке данных. Это можно делать как её результатов с помощью самостоятельно реализуемого алгоритма сортировки (например, пузырькового), так и с помощью стандартных библиотечных процедур. Для выполнения данного задания можно также использовать редактор электронных таблиц со встроенной функцией сортировки

4. Информационные технологии

Сначала следует уяснить структуру Типичная ошибка происходит при отрассматриваемой базы данных, боре строк для решения: включение взаимосвязь полей её таблиц. Затем лишних или пропуск нужных нужно выделить необходимую информацию (строки) с помощью фильтров или формул с условиями, а потом надо суммировать требуемые числовые значения Для выполнения задания нужно ис- Неверное использование логических пользовать логическую функцию функций с условием, в котором логические функции (И, ИЛИ, НЕ) применяются к результатам вычисления значений операций отношения (больше, меньше, равно, не равно)

Номер Рекомендации по выполнению задания 10 Для выполнения задания требуется открыть заданный файл в текстовом редакторе, сформулировать и выполнить поисковый запрос 18 Для выполнения этого задания нужно с помощью формул электронной таблицы смоделировать возможные действия Робота и выбрать оптимальный в смысле выполнения условия задания вариант 27 Для выполнения этого задания нужно с помощью электронной таблицы построить график, дающий представление о кластеризации звёзд; сформулировать математические условия для группировки точек по кластерам; вычислить координаты центра каждого кластера и остальные необходимые по условию значения

Типичные ошибки и рекомендации по их предотвращению Учёт не соответствующих условию задания словоформ или, напротив, пропуск соответствующих Неверное моделирование движения Робота и/или суммирование его «добычи»

Неверное формулирование условий для группировки точек по кластерам

Рекомендуется следующая последовательность действий при подготовке к экзамену. 1. Провести самодиагностику, прорешав демонстрационный вариант КИМ и самостоятельно проверив ответы, для чего воспользоваться эталонными ответами и критериями оценивания. Если есть возможность работать в паре или группой, желательно всегда организовывать взаимную проверку развёрнутых ответов. Цели – выявить собственные пробелы в знаниях и темы, вызвавшие затруднения, зафиксировать исходный уровень подготовки. 2. Заполнить индивидуальный план подготовки к экзамену и следовать ему. 3. Выполнять задания не обязательно в порядке нумерации разделов 1–4. Напротив, лучше выполнить сначала задания разделов 2–4, а затем раздела 1. 4. При повторении каждой темы сначала выполнять задания по линиям, не менее чем по три-четыре задания каждого типа, встречающегося в линии, затем выполнять задания группами, относящимися к данной теме. После того как ошибки в выполнении заданий по данной теме сведены к минимуму, можно переходить к проработке следующей темы. 5. После завершения повторения всех тем следует решить ещё как минимум один вариант КИМ и сравнить результаты (см. п. 1). Также снова следует выявить темы и линии заданий, вызвавшие затруднения, и дополнительно их проработать.

Разбор новых моделей заданий ЕГЭ 2026 г. и упражнения для самостоятельной подготовки В демонстрационном варианте КИМ ЕГЭ 2026 г. приведена новая модель задания 12. Рассмотрим пример выполнения этого задания и приведём варианты условий для самостоятельного решения. Пример задания 12 (демо 2026 г.) Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a0, a1, …, an–1}), включая специальный пустой символ a0. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний: Q = {q0, q1, …, qn–1}. В начальный момент времени головка находится в начальном состоянии q0. На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может изменить символ в текущей ячейке и/или переместиться в ячейку справа или слева от текущей. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Программа работы исполнителя МТ задаётся в табличном виде.

q0 q1 … qn–1

a0 команда команда … команда

a1 команда команда … команда

… … … … …

an–1 команда команда … команда

В первой строке перечислены все возможные символы в текущей ячейке ленты; в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» не возможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов: «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно; «N» – отсутствие сдвига; «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды. Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3. Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «λ». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z». Программа λ q0 λ, L, q0 q1 λ, S, q1

Z X, L, q1 X, L, q1

заменяет на ленте все символы «Z» на «X» и останавливает в первой ячейке слева от последовательности символов «X». Возможное начальное состояние исполнителя: … λ λ Z Z Z

исполнителя

▲ q0

Конечное состояние исполнителя после завершения выполнения программы: … λ λ X X X X λ λ ▲ q1

Выполните задание. На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя: λ 1 q0 λ, L, q1 q1 λ, S, q1 0, S, q1

0 1, L, q1

После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности. Решение Рассмотрим фрагмент таблицы команд, соответствующий стартовому состоянию. λ q0 λ, L, q1 По условию в начальный момент времени головка находится в ближайшей ячейке справа от последовательности символов. Эта ячейка также по условию содержит пустой символ «λ», поэтому из начального состояния q0 головка МТ сдвигается влево (команда L), и МТ переходит в состояние q1. Заметим, что больше нигде в программе состояние q0 не встречается. Далее, исходя из условия, МТ может встретить в текущей ячейке либо символ «1», либо символ «0». Рассмотрим фрагмент таблицы команд, относящийся к этим двум случаям. 1 0 q1 0, S, q1 1, L, q1 15

Если встречен символ «1», то МТ заменяет его на «0» и останавливается (команда S). Если встречен символ «0», то МТ заменяет его на «1» и сдвигается влево. Это происходит циклически до тех пор, пока не будет встречен символ «1» или «λ». Рассмотрим фрагмент таблицы команд для случая символа «λ» и текущего состояния q1. λ q1 λ, S, q1 Видно, что в этом случае МТ останавливается. Заметим, что эта команда может выполниться только в случае, если на ленте изначально не было ни одного символа «1», иначе бы раньше выполнилась команда 1 q1 0, S, q1 По условию после завершения работы программы на ленте осталось ровно 343 нуля. Найдём максимальное исходное число нулей. Предположим, что изначально вся лента была заполнена нулями, тогда их было ровно 1000, после выполнения программы они превратились бы в 1000 единиц, что не соответствует условию. Итак, нулей было меньше 1000 и программа завершилась, как только была встречена первая единица. При этом справа от этой первой встреченной единицы после завершения программы могут находиться только единицы (или пустой символ, если единица была самым правым символом). Таким образом, где-то слева от этой единицы остались 342 нуля, в 343-й ноль превратилась сама единица. Очевидно, что максимальное число нулей в исходном состоянии имело место при отсутствии других единиц слева от первой встреченной. Таким образом, максимум исходных нулей достигается, когда в исходной последовательности была всего одна единица, находившаяся на 343-м месте слева. Поэтому максимально возможное исходное число нулей равно: 1000 – 1 = 999. Исходная конфигурация ленты: … 0 … 0 342 нуля

… 0 657 нулей

λ ▲ q0

Финальная конфигурация ленты: … 0 … 0 343 нуля

… 1 657 единиц

▲ q1

Ответ: 999.

Примеры заданий линии 12 для самостоятельного решения Пример 1*. Выполните задание. На ленте в соседних ячейках записана последовательность из 2000 символов, включающая 1000 нулей и 1000 единиц, расположенных подряд в произвольном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя: λ 1 q0 λ, L, q1 q1 λ, S, q1 0, S, q1

0 1, L, q1

Определите максимально возможное число нулей на ленте после завершения работы программы. Ответ: 1001. Пример 2. Выполните задание. На ленте в соседних ячейках записана последовательность из 400 символов, включающая 200 нулей и 200 единиц, расположенных подряд в произвольном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа работы исполнителя: λ 1 q0 λ, R, q1 q1 λ, S, q1 0, R, q1

0 1, S, q1

Определите максимально возможное число нулей на ленте после завершения работы программы. Ответ: 399. Пример 3. Выполните задание. На ленте в соседних ячейках записана последовательность из 400 символов, включающая 200 нулей и 200 единиц, расположенных подряд в произвольном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа работы исполнителя: λ 1 q0 λ, R, q1 q1 λ, S, q1 0, R, q1

0 1, S, q1

Определите минимально возможное число нулей на ленте после завершения работы программы. Ответ: 199. Здесь и далее описание МТ в условии задания опущено для экономии места, поскольку оно идентично приведённому в задании демонстрационного варианта. *

Пример 4. Выполните задание. На ленте в соседних ячейках записана последовательность из 2000 символов, включающая 1000 нулей и 1000 единиц, расположенных подряд в произвольном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя: λ 1 q0 λ, L, q1 q1 λ, S, q1 0, S, q1

0 1, L, q1

Определите минимально возможное число нулей на ленте после завершения работы программы. Ответ:

1. Пример

5. Выполните задание. На ленте в соседних ячейках записано в двоичной системе счисления число 257 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от записи числа. Программа работы исполнителя: λ 1 q0 λ, L, q1 q1 λ, S, q1 0, L, q1

0 1, L, q1

Определите десятичное число, двоичная запись которого на ленте является результатом работы программы. Ответ: 254. Пример 6. Выполните задание. На ленте в соседних ячейках записано в двоичной системе счисления число 321 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от записи числа. Программа работы исполнителя: λ 1 q0 λ, L, q1 q1 λ, S, q1 0, L, q1

0 1, L, q1

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

Пример 7. Выполните задание. На ленте в соседних ячейках записано в двоичной системе счисления число 128 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от записи числа. Программа работы исполнителя: λ 1 q0 λ, L, q1 q1 λ, S, q1 0, S, q1

0 1, L, q1

Определите десятичное число, двоичная запись которого на ленте является результатом работы программы. Ответ: 127. Пример 8. Выполните задание. На ленте в соседних ячейках записано в двоичной системе счисления число 150 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от записи числа. Программа работы исполнителя: λ 1 q0 λ, L, q1 q1 λ, S, q1 0, S, q1

0 0, L, q1

Определите десятичное число, двоичная запись которого на ленте является результатом работы программы. Ответ: 148. Пример 9. Выполните задание. На ленте в соседних ячейках записано в двоичной системе счисления число 99 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от записи числа. Программа работы исполнителя: λ 1 q0 λ, R, q1 q1 λ, S, q1 0, S, q1

0 1, R, q1

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

Пример 10. Выполните задание. На ленте в соседних ячейках записано в двоичной системе счисления число 99 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от записи числа. Программа работы исполнителя: λ 1 q0 λ, R, q1 q1 λ, S, q1 0, R, q1

0 1, S, q1

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

19. Пример

11. Выполните задание. На ленте в соседних ячейках записано в двоичной системе счисления число 121 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от записи числа. Программа работы исполнителя: λ 1 q0 λ, R, q1 q1 λ, S, q1 1, R, q1

0 1, S, q1

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