Задание 4 ЕГЭ по информатике: условие Фано
Четвёртое задание ЕГЭ по информатике про неравномерные двоичные коды. Обычно часть букв уже закодирована, и нужно подобрать коды для остальных так, чтобы сообщение однозначно декодировалось, а сумма длин была наименьшей. Работает одна идея: условие Фано и дерево кодов.
Для 10–11 классов. Нумерация по проекту демоверсии ФИПИ на 2027 год.
Условие Фано и дерево
Условие Фано: ни одно кодовое слово не является началом другого. Тогда сообщение читается однозначно. Удобно представить коды как дерево: от корня идут ветки 0 и 1, каждый код это путь до листа. Код не может стоять на пути к другому коду.
Если коды 0, 10 и 110 заняты, свободной остаётся только ветка 111. От неё можно получить 1110 и 1111, или длиннее.
Разбор задач
Два оставшихся кода
Для букв А, Б, В использованы коды 0, 10, 110. Найдите наименьшую сумму длин кодов для букв Г и Д.
Свободна только ветка 111.
Делим её на 1110 и 1111, сумма длин 4 + 4 = 8.
Ответ: 8
Кратчайший код
Коды: А 00, Б 01, В 100, Г 101. Какой кратчайший код можно дать букве Д?
Ветка 0 занята целиком (00 и 01), ветка 10 тоже.
Свободна ветка 11, её длина 2.
Ответ: 11
Декодирование
Коды: А 00, Б 01, В 10, Г 11. Расшифруйте сообщение 0110.
Коды равной длины, делим по два: 01 и 10.
Б и В.
Ответ: БВ
Проверь себя
- Коды 1, 01, 001. Наименьшая длина кода ещё одной буквы? Ответ: 3 (000).
- Можно ли использовать коды 0 и 01 одновременно? Ответ: нет, 0 начало 01.
Где теряют балл
- Проверка только в одну сторону. Новый код не должен быть началом старых, и старые не должны быть началом нового.
- Неоптимальное деление. Делите самую короткую свободную ветку, а не длинную.
Как тренироваться
Рисуйте дерево для каждой задачи, через пять-шесть задач оно будет строиться в голове. Количество информации и коды в статье количество информации: задачи. Все номера экзамена в статье ЕГЭ по информатике по номерам.
Разберём на занятии
Готовим к ОГЭ и ЕГЭ на живых занятиях в мини-группе до шести человек или один на один, с пробниками в формате экзамена и разбором каждой ошибки.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Что такое обратное условие Фано?
Ни один код не является окончанием другого. Оно тоже гарантирует однозначность, но в задании обычно используют прямое.
Сколько баллов?
Один первичный балл.