Зачем это в ЕГЭ. Задание 4 проверяет умение анализировать кодовые деревья и декодировать сообщения (1 первичный балл). Встречается в 70% реальных вариантов ФИПИ. Проверяет понимание принципов Фано и работы с бинарными деревьями.
Главная идея. Кодовое дерево — граф, где буквы расположены в листьях, а путь от корня задаёт их код. Для декодирования идём по веткам, пока не найдём букву. Ключ — чёткое следование по ветвям (0 — лево, 1 — право).
Алгоритм (чеклист).
1. Постройте дерево по заданным кодам или условию.
2. Для декодирования разбейте битовую строку на части, соответствующие кодам букв.
3. Для каждой части начните с корня, двигайтесь по ветвям согласно битам (0 — лево, 1 — право).
4. Остановитесь, достигнув листа — это искомая буква.
5. Проверьте, что все биты использованы и декодирование завершено.
Опоры (кратко).
- Условие Фано: ни один код не является началом другого.
- Формула длины кода: , где — вероятность, — длина кода.
- Бинарное дерево: каждый узел имеет не более двух потомков.
Пример 1 (дерево по кодам).
Шаг 1. Даны коды: А — 0, Б — 10, В — 110, Г — 111.
Шаг 2. Строим дерево: корень → 0 (А), правая ветвь → 1 → 0 (Б), 1 → 0 (В), 1 (Г).
Шаг 3. Декодируем "010110": 0→А, 10→Б, 110→В.
Шаг 4. Результат: АБВ.
Пример 2 (оптимальные коды).
Шаг 1. Даны частоты: А — 40%, Б — 30%, В — 20%, Г — 10%.
Шаг 2. Строим коды Хаффмана: А — 0, Б — 10, В — 110, Г — 111.
Шаг 3. Средняя длина: бит.
Типичные ошибки.
1. Путаница 0/1 при движении по дереву — всегда проверяйте соответствие битов и ветвей.
2. Неполное декодирование — остались неиспользованные биты в строке.
3. Нарушение Фано — код одной буквы является началом другой.
4. Неправильное построение дерева — буквы должны быть только в листьях.
Дальше. Переходите к анализу более сложных деревьев с неравномерным распределением вероятностей.