Как решать задание 4 ЕГЭ по информатике (условие Фано, кодирование)?
Задание 4 про кодовые слова и условие Фано вообще не понимаю. Просят найти минимальную длину кода для буквы или проверить, можно ли однозначно декодировать. Как разобраться с условием Фано на ЕГЭ?
2 ответа
Задание 4 — про префиксные коды и условие Фано.
Условие Фано: ни одно кодовое слово не является началом (префиксом) другого. Если выполнено — код декодируется однозначно слева направо.
Типовой вопрос: даны коды нескольких букв, нужно найти минимальную длину кода для оставшейся буквы так, чтобы условие Фано сохранялось.
Метод — двоичное дерево. Каждый код = путь в дереве (0 — влево, 1 — вправо). Кодовое слово занимает узел, и тогда все его потомки запрещены (иначе нарушится префиксность).
Алгоритм:
- Размести данные коды в дереве.
- Найди свободные узлы минимальной глубины для новой буквы.
- Минимальная длина — это глубина ближайшего свободного узла.
Пример: коды А=0, Б=10, В=110. Тогда 0, 10, 110 заняли свои ветки; свободен узел на глубине 3 — это 111. Значит, минимальная длина нового кода = 3.
Частая ошибка: забыть, что обратное условие (постфиксное) тоже бывает в задании, и что «минимальная длина» — это именно длина, а не сам код. Также не путай: если код-слово короткое, оно блокирует длинные слова с тем же началом.
Чтобы не рисовать дерево, держи в голове правило: кодовое слово длины L «съедает» долю 1/2^L всех возможных кодов (неравенство Крафта). Сумма таких долей по всем буквам не должна превышать 1.
Но для ЕГЭ дерево нагляднее: рисуешь занятые ветки, ищешь первую свободную развилку — её глубина и есть ответ. Главное — помнить, что занятый узел закрывает всё, что ниже него.