Что такое условие Фано простыми словами?

Никакой код буквы не должен быть **началом** (префиксом) кода другой буквы. Если код буквы А = 01, то ни одна другая буква не может иметь код, начинающийся на 01 — например, 010 или 0111. Это гарантирует, что последовательность битов разбирается однозначно слева направо без разделителей.

Чем обратное условие Фано отличается от прямого?

**Прямое условие Фано** — никакой код не является началом другого. **Обратное** — никакой код не является **окончанием** другого (суффиксом). Обратное условие нужно, когда сообщение читается справа налево. На ЕГЭ чаще встречается прямое, но и обратное бывает — читай условие внимательно.

Как быстро проверить, выполняется ли условие Фано?

Построй **бинарное дерево**: 0 — налево, 1 — направо. Каждый код — путь от корня. Условие Фано выполнено, если **все буквы находятся в листьях** дерева, а не в промежуточных узлах. Если какая-то буква оказалась во внутренней вершине, через которую проходит путь к другой букве, — условие нарушено.

Что такое алгоритм Хаффмана и зачем он на ЕГЭ?

Алгоритм Хаффмана строит **оптимальный префиксный код**: чем чаще буква встречается, тем короче её код. На ЕГЭ прямого задания «построй код Хаффмана» почти нет, но идея помогает в задачах «сделай код минимальной суммарной длины» — обычно достаточно вручную собрать дерево снизу вверх по частотам.

Какой код искать — наименьший или наибольший?

Читай задание **дословно**. Часто просят «кратчайший возможный код» для оставшейся буквы при условии, что код удовлетворяет Фано. Иногда наоборот — «наибольший по длине». Иногда — «наименьшее двоичное число такой-то длины». Подмена одного на другое — частая причина потери балла.

Сколько времени отводить на задание 4?

**3-5 минут**. Задание на 1 балл, и при отработанной технике дерева оно решается быстро. Если застрял на 7-й минуте — пропусти и вернись. Всего на экзамене 235 минут, и тратить их стоит там, где больше вес: [26 и 27 задания](/blog/zadanie-27-ege-informatika) по 2 балла каждое.

Можно ли решать задание 4 в уме или нужен черновик?

Обязательно нужен черновик. Рисуй дерево или таблицу кодов: держать префиксы в голове — верный путь к ошибке. На КЕГЭ черновик выдаётся, используй его. См. [чек-лист, что взять на КЕГЭ](/blog/chek-list-dlya-kege-chto-vzyat).

Где тренировать задание 4?

Банк ФИПИ, сайт Полякова, сборники Крылова. Для интерактивной тренировки с автопроверкой и разбором ошибок подойдёт TuteMe — задачи на Фано и Хаффмана генерируются с разной сложностью, после ошибки показывается визуализация дерева кодов.

Задание 4 ЕГЭ по информатике — неравномерные коды, условие Фано, Хаффман

О чём задание 4

Задание 4 ЕГЭ по информатике — про неравномерные двоичные коды. Тебе дают несколько букв с их кодами (или частотами), и нужно либо достроить код для оставшейся буквы, либо посчитать длину закодированного сообщения, либо восстановить исходный текст по цепочке битов.

Задание стоит 1 первичный балл, решается за 3-5 минут и почти никогда не меняется в формулировке. Если разобраться с двумя идеями — условием Фано и построением дерева кодов — ты будешь решать его почти на автомате.

Зачем вообще нужны неравномерные коды

В равномерном коде все буквы кодируются одинаковым числом битов. Например, 8 букв — по 3 бита каждая. Просто, но неэффективно: буквы «О», «Е», «А» в русском встречаются в десятки раз чаще, чем «Щ», «Ъ», «Ф», и отводить всем одинаковое место — расточительно.

Неравномерный код даёт коротким буквам — короткий код, редким — длинный. Среднее количество битов на букву падает, сообщение сжимается. На этой идее работает архиватор ZIP, кодек JPEG, сжатие текста gzip — всё через потомков кода Хаффмана 1952 года.

Но появляется проблема: если коды разной длины, как понять, где кончается одна буква и начинается следующая? В равномерном коде ты режешь поток по 3 бита. В неравномерном — нужно правило, чтобы разбор был однозначным. Это правило называется условием Фано.

Условие Фано: строгое определение

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

Пример кодов, удовлетворяющих Фано:

Буква	Код
А	0
Б	10
В	110
Г	111

Проверяем: код «А» = 0. Начинается ли код Б, В или Г с 0? Нет, все они с 1. Код Б = 10. Начинается ли В или Г с 10? В = 110, Г = 111 — нет. Код В = 110 не является началом кода Г = 111 (отличаются в последнем бите). Всё чисто.

Пример, нарушающий Фано:

Буква	Код
А	0
Б	01
В	10

Код А = 0 является началом кода Б = 01. Если в потоке идёт 01, непонятно: это «Б» одной буквой или «А» + начало какой-то другой буквы. Декодирование неоднозначно — значит, такой код на приёмной стороне не используют.

Обратное условие Фано

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

Как проверять условие Фано через дерево

Самый надёжный способ — построить бинарное дерево кодов:

корень — пустой код
ребро налево — бит 0
ребро направо — бит 1
путь от корня до вершины — код этой вершины

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

Пример для кодов А=0, Б=10, В=110, Г=111:

          (корень)
         /        \
        0(А)      1
                 / \
                0(Б) 1
                    / \
                   0(В) 1(Г)

А, Б, В, Г — все в листьях. Отлично, Фано выполнено.

Типы задач

Тип 1. Подобрать код для новой буквы

Дано: коды нескольких букв, условие Фано выполнено. Нужно добавить ещё одну букву и выбрать для неё кратчайший (или наоборот, наименьший по значению) код, при котором Фано сохранится.

Техника: строй дерево для известных букв. В тех местах, где ещё есть «свободные» пути (не ведущие к существующим буквам), можно повесить новую букву. Выбирай место с минимальной глубиной — это даст кратчайший код.

Тип 2. Посчитать длину сообщения

Дано: коды всех букв + частоты их появления (или сам текст). Нужно посчитать, сколько битов займёт закодированное сообщение.

Формула: длина = Σ (частота буквы × длина её кода).

Тип 3. Декодировать сообщение

Дано: коды букв + битовая последовательность. Нужно восстановить исходный текст.

Техника: иди по дереву от корня. Каждый 0 — налево, каждый 1 — направо. Добрался до листа — выписал букву и вернулся к корню. Повторяй до конца строки.

Тип 4. Минимальная длина при заданных частотах

Дано: частоты букв. Нужно найти минимальную возможную суммарную длину закодированного сообщения при условии Фано. Здесь работает алгоритм Хаффмана.

Алгоритм Хаффмана — пошагово

Хаффман строит дерево снизу вверх по частотам:

Выпиши все буквы и их частоты.
Выбери две буквы с наименьшими частотами.
Объедини их в новый узел, его частота = сумма частот детей.
Убери исходные две буквы из списка, добавь туда новый узел.
Повторяй шаги 2-4, пока не останется один узел — это корень.
Пройди по дереву: левое ребро — 0, правое — 1. Прочитай коды.

Пошаговый разбор на 5 буквах

Буквы с частотами: А=12, Б=3, В=5, Г=8, Д=4.

Шаг 1. Выбираем две минимальные: Б=3 и Д=4. Объединяем в узел (БД)=7.

Остаётся: А=12, В=5, Г=8, (БД)=7.

Шаг 2. Две минимальные: В=5 и (БД)=7. Объединяем в (В·БД)=12.

Остаётся: А=12, Г=8, (В·БД)=12.

Шаг 3. Две минимальные: Г=8 и А=12. Объединяем в (ГА)=20.

Остаётся: (В·БД)=12, (ГА)=20.

Шаг 4. Объединяем последние два: (В·БД·ГА)=32. Это корень.

Теперь проходим по дереву и выписываем коды (конкретное назначение 0/1 может отличаться, важна длина):

Буква	Частота	Длина кода	Пример кода
А	12	2	11
Г	8	2	10
В	5	2	00
Д	4	3	011
Б	3	3	010

Частые буквы (А, Г) получили длину 2, редкие (Б, Д) — длину 3. Это и есть принцип Хаффмана.

Суммарная длина сообщения: 12·2 + 8·2 + 5·2 + 4·3 + 3·3 = 24 + 16 + 10 + 12 + 9 = 71 бит.

Пример задачи «под ЕГЭ»

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

Решение. Строим дерево:

Свободная вершина одна — та, что соответствует пути 111. Всё, что короче (0, 10, 11, 110), либо уже занято, либо является префиксом занятых кодов.

Ответ: 111.

Проверка: 111 не начинается ни с одного из 0, 10, 110. И сам не является началом ни одного из них. Фано выполнено.

Пример посложнее: наименьший код

Условие. Буквам А, Б, В, Г, Д сопоставлены двоичные коды: А = 11, Б = 00, В = 01. Найди наименьший (как двоичное число) код для Д длины не более 4 бит, при котором сохраняется условие Фано.

Решение. Занятые «поддеревья»: все пути, начинающиеся с 11, 00, 01. Свободны пути, начинающиеся с 10. Значит, код Д должен начинаться с 10, его длина от 2 до 4.

10 — длина 2, само двоичное число 10₂ = 2. Проверим: не является ли 10 префиксом уже существующих (11, 00, 01)? Нет. Они — префиксом 10? Тоже нет. Подходит.
Более короткого (1 бит) нельзя: 0 — префикс для 00, 01; 1 — префикс для 11.

Ответ: 10.

Типичные ошибки

1. Забыл проверить оба направления. Условие Фано двустороннее: новый код не должен быть префиксом существующих и существующие не должны быть префиксом нового. Проверяй и то, и то.

2. Путаница «кратчайший» vs «наименьший по значению». Код 001 короче, чем 1111, но как число 001 = 1, а 1111 = 15. «Кратчайший» — про длину, «наименьший» — про значение. Выбирай по условию. Разбор похожих ловушек — в материале про типичные ошибки на ЕГЭ.

3. Ошибка в подсчёте длины. Всегда перемножай частоту на длину именно этой буквы и суммируй. Легко случайно умножить на длину другой.

4. Неправильно прочитал условие про направление. Если сказано «обратное условие Фано» — работай с суффиксами, а не префиксами. Это разные задачи.

5. Начал строить дерево сверху, а не снизу (для Хаффмана). Хаффман — всегда снизу вверх от самых редких. Сверху строить нельзя, получится неоптимально.

Связь с другими заданиями

Префиксные коды встречаются не только в задании 4. В задании 1 анализируют таблицы и графы — там тоже иногда пользуются деревом. Принципы кодирования помогают в заданиях на системы счисления и информационный объём. Если проседаешь в теории кодов в целом — начни с подготовки с нуля, а потом возвращайся к заданию 4.

Тайминг и тактика

На задание 4 отводи 3-5 минут. Алгоритм действий:

Прочитай условие дважды. Уточни: прямое или обратное Фано, «кратчайший» или «наименьший», что именно ищется.
Выпиши известные коды столбиком.
Нарисуй дерево (или таблицу свободных префиксов).
Найди подходящий код.
Проверь: не префикс ли он для существующих и наоборот.
Если задача на длину сообщения — посчитай сумму частот на длины.

Если через 7 минут решения нет — пропусти и вернись позже. 1 балл не стоит того, чтобы потерять 10 минут на 2-балльное задание 27.

Как тренироваться

За 2 недели до экзамена прорешай:

20-30 задач из банка ФИПИ на задание 4 (фильтр по номеру).
Сборник Полякова — раздел «Кодирование и декодирование».
3-5 пробников целиком, чтобы потренировать задание 4 в потоке.

Отличный способ тренировки — самому кодировать короткие слова кодом Хаффмана. Возьми слово, посчитай частоты букв, построй дерево, закодируй, раскодируй обратно. Через 10 таких упражнений алгоритм запоминается намертво.

Для полной подготовки по всем заданиям посмотри план на 3 месяца или на 6 месяцев, там задание 4 встроено в расписание.

Итого

Задание 4 — про одно правило (условие Фано) и один инструмент (бинарное дерево кодов). Освоил — решаешь за 3 минуты. Не освоил — теряешь балл на пустом месте. Рисуй дерево, проверяй оба направления, не путай «кратчайший» с «наименьшим» — и балл твой.