4 задание ЕГЭ по информатике: условие Фано и декодирование

Кому: выпускнику · Обновлено 2026-10-25

Раздел: Информатика · Тема: Разборы заданий по номерам · Задание 4

В 4 задании ЕГЭ по информатике нужно работать с неравномерным двоичным кодом: расшифровать сообщение или подобрать кодовое слово так, чтобы выполнялось условие Фано (никакое кодовое слово не является началом другого). Решается оно за несколько минут вручную по дереву кодов или короткой программой на Python. Ниже: теория, пошаговый алгоритм, шаблон кода и частые ошибки.

Решить задание в тренажёре

Что проверяют в задании 4 по информатике

Задание относится к базовому уровню и посвящено теме «Кодирование и декодирование, условие Фано». Ответ в нём записывается как последовательность: чаще всего это буквы подряд или число, например длина кодового слова. Точную формулировку и оформление ответа на текущий год смотри в демоверсии и кодификаторе на сайте ФИПИ (fipi.ru): именно они задают актуальный формат.

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

• Расшифровать строку из нулей и единиц по заданной таблице кодов.
• Подобрать кодовое слово для ещё одной буквы так, чтобы условие Фано сохранилось (часто нужно кратчайшее или с минимальной суммой длин).
• Определить, какой из предложенных наборов кодов удовлетворяет условию Фано, или найти, какое слово нужно изменить.

Теория: условие Фано и неравномерный код

В равномерном коде все кодовые слова одной длины, и строку просто режут на одинаковые блоки. В неравномерном буквы кодируются словами разной длины, поэтому без дополнительного правила возможна неоднозначность. Например, если А = 0, Б = 01, В = 1, то строка 01 читается и как АВ, и как Б.

Условие Фано (прямое условие): ни одно кодовое слово не является началом (префиксом) другого кодового слова. Если оно выполнено, любое сообщение декодируется единственным способом, причём читать можно слева направо без возвратов. Код называют префиксным.

Полезно представлять код как двоичное дерево. Из корня каждый символ 0 уводит влево, а 1 вправо. Кодовые слова должны стоять в листьях: если слово стоит в промежуточной вершине, оно является началом других слов, и условие нарушено.

4 задание ЕГЭ по информатике: разбор декодирования по шагам

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

• Выпиши таблицу кодов и отсортируй слова по длине: короткие проверяй первыми.
• Ставь указатель в начало строки и читай символы по одному, накапливая текущий фрагмент.
• Когда фрагмент совпал с кодовым словом, запиши букву и начни накапливать заново.
• Дойдя до конца строки, проверь, что остатка нет и число букв совпало с указанным в условии (если оно дано).
• Запиши буквы подряд без пробелов и запятых, как требует условие.

Как подобрать кодовое слово: поиск по дереву

Если нужно добавить слово для новой буквы, нарисуй дерево по имеющимся кодам. Свободное слово можно выбрать только там, где ветка ещё не занята и не является продолжением чужого листа.

Пример рассуждения: у букв коды 0, 10, 110. Слово 111 свободно: оно не начинается ни с одного из имеющихся слов, и ни одно из них не начинается с него. Слова длиннее, например 1110, тоже допустимы, но если просят кратчайшее, берём минимальную длину.

Быстрая проверка допустимости длин даёт неравенство Крафта: сумма 2 в степени минус длина слова по всем словам не должна превышать 1. Для длин 1, 3, 3, 4, 4 получаем 1/2 + 1/8 + 1/8 + 1/16 + 1/16 = 7/8, то есть место для ещё одного слова есть. Это необходимое условие, но не достаточное: после него всё равно проверяй префиксы напрямую.

4 задание ЕГЭ по информатике на Python: шаблон

Задание можно решать и кодом: это удобно для самопроверки и для случаев, когда вариантов много. Идея шаблона проста. Для проверки условия Фано перебери все пары различных слов и убедись, что одно не начинается с другого. Для декодирования двигайся по строке и сравнивай накопленный фрагмент со словарём кодов.

Шаблон проверки в виде текста: функция fano(words) возвращает True, если для любых двух слов a и b из набора при a != b выражение b.startswith(a) ложно. Для декодирования заведи словарь вида {'0': 'Е', '111': 'Ж'}, пустую строку cur и список res; для каждого символа ch строки добавляй его к cur, и если cur есть в словаре, добавляй букву в res и обнуляй cur.

Для поиска кратчайшего свободного слова перебирай кандидатов по возрастанию длины (все двоичные строки длины 1, затем 2, затем 3 и так далее) и возвращай первый, который проходит проверку fano вместе с исходным набором. Не забывай, что на самом экзамене нужен только ответ, а программа служит помощником и способом проверить ручное решение.

Типичные ошибки и как себя проверить

Большинство потерь в этом задании связаны с невнимательностью, а не со сложной теорией. Вот что стоит держать под контролем.

• Проверяют только слова «в одну сторону»: нужно смотреть обе пары, a как начало b и b как начало a.
• Забывают, что слово не должно совпадать с уже занятым: два одинаковых кода нарушают однозначность.
• При декодировании берут первую подходящую букву по длинному слову, не проверив короткие. Начинай всегда с накопления символов и сравнения с каждым словом.
• Не сверяют число букв с числом из условия. Это самая дешёвая проверка: если букв вышло больше или меньше, где-то ошибка в разбиении.
• Пишут ответ с пробелами, запятыми или строчными буквами, хотя требуется слитная запись заглавными.
• Путают «кратчайшее слово» и «слово минимальной суммарной длины набора». Перечитай, о чём именно спрашивают.

Как тренироваться по заданию 4

Начни с 5–6 заданий на декодирование и добейся того, чтобы они решались без ошибок за пару минут. Затем переходи к задачам на подбор слова и проверку условия Фано. Решай вручную, а потом перепроверяй кодом по шаблону: расхождение сразу покажет, где ошибка.

Подходящие задачи есть на странице заданий по информатике, а в тренажёре «Ранга» можно ввести ответ и сразу увидеть проверку. Общий порядок подготовки к предмету с нуля описан в отдельной статье блога. Актуальные демоверсии и спецификацию сверяй на fipi.ru, чтобы не опираться на устаревшие форматы.

Материал — разъяснение «Ранг». Официальные правила экзамена, расписание, шкалы баллов и перечни заданий публикуют ФИПИ (fipi.ru) и Рособрнадзор (obrnadzor.gov.ru). Мы не обещаем конкретных баллов: результат зависит от твоей работы.