Каталог: Задание №4. Кодирование информации и условие Фано

Банк задач: 237 Формат ЕГЭ 2026 Базовый (1 балл) 2-4 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №4

Тема кодификатора Префиксные однозначно декодируемые коды, прямое условие Фано и двоичные деревья

Сложность и баллы Базовый (1 балл)

Рекомендуемое время 2-4 мин

Инструменты решения Двоичное дерево, Прямое условие Фано, Неравенство Крафта

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

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

Тип 1: Минимальная длина кода для одной новой буквы

Найти кодовое слово минимальной длины с наименьшим числовым значением при равенстве длин.

Тип 2: Кодирование нескольких оставшихся букв

Требуется закодировать 2-3 оставшиеся буквы так, чтобы суммарная длина сообщения была минимальна.

Тип 3: Неравномерная частота букв в слове

Часто встречающиеся буквы слова ставятся на короткие ветки (длина 1-2), редкие — на более глубокие.

Теоретический фундамент и алгоритмы

1. Прямое условие Фано:

Прямое условие Фано: никакое кодовое слово не может быть началом (префиксом) другого кодового слова.

Следствие: код является префиксным, что гарантирует однозначное декодирование сообщения слева направо без разделителей между буквами!

2. Построение двоичного дерева:

                 [ Корень ]
                /          \
              0              1
            /   \          /   \
          00     01      10     11
         /  \   /  \    /  \   /  \
       000 001 010 011 100 101 110 111

Корень дерева — пустая строка. Из каждого узла выходят две ветки: левая — 0, правая — 1.
Каждая буква алфавита должна быть листом дерева (тупиком).
Главное правило Фано: если узлу назначена буква, из него НЕЛЬЗЯ продолжать ветки дальше! Всё поддерево под этой буквой блокируется.
Свободные ветки наименьшей глубины — кандидаты для новых букв.

3. Пошаговый разбор реальной задачи:

Условие: По каналу связи передаются сообщения, содержащие буквы А, Б, В, Г, Д, Е. Для передачи используется код, удовлетворяющий условию Фано: А: 00, Б: 010, В: 011, Г: 10. Какое кодовое слово наименьшей длины можно назначить для буквы Д, если известно, что код буквы Е также должен быть закодирован?

Отмечаем на дереве занятые узлы:
- Ветка 00 $\implies$ занята буквой А (закрыта).
- Ветка 010 $\implies$ занята буквой Б.
- Ветка 011 $\implies$ занята буквой В. Вся ветка 0... полностью закрыта!
- Ветка 10 $\implies$ занята буквой Г.
Смотрим на оставшуюся свободную ветку 11:
- Если мы отдадим 11 букве Д целиком, то для буквы Е не останется ни одной свободной ветки!
- Поэтому расщепляем узел 11 на два листа: 110 и 111.
Назначаем: букве Д = 110 (наименьшее числовое значение), букве Е = 111.

Ответ: 110

Лайфхаки и фишки для ускорения

Совет

При вопросе 'с наименьшим числовым значением' среди кодов равной длины выбирайте тот, у которого нули идут раньше (например, 100 меньше 101 и 110).

Совет

Для проверки достаточности свободных веток используйте неравенство Крафта: \sum 2^{-l_i} \le 1.

Частые ошибки и экзаменационные ловушки

Ошибка: Продолжить растить ветку из занятого узла буквы
Если букве А присвоен код '01', назначить букве Б код '010'. Код '01' является префиксом '010' — Фано нарушено!

Правильно: Назначенная буква закрывает всю ветку под собой навсегда.

Ошибка: Забыть про оставшиеся буквы алфавита
Отдать последний свободный узел длины 2 и не оставить места для остальных 2 букв.

Правильно: Свободных листьев дерева на финальном этапе должно хватать на ВСЕ оставшиеся буквы алфавита!

ГРОБ №4: Минимизация суммарной длины слова со сложной частотностью букв

Дано слово 'АНАНАСЫ'. Требуется минимизировать суммарную длину закодированного слова в битах.

Алгоритм решения: Посчитайте частоту каждой буквы: буква А встречается 3 раза, Н — 2 раза, С — 1 раз, Ы — 1 раз. Букву А ставьте на самую короткую ветку (длины 1-2), чтобы максимизировать экономию бит!

Практические задачи из банка КИМ (Всего: 237)

Решать в песочнице СмартКИМ

Задача #9072 №4 ЕГЭ