Условие Фано: что это такое и как применяется в ЕГЭ 2026

Что такое условие Фано и зачем оно нужно

Представь, что ты передаёшь сообщение по рации, используя азбуку Морзе. Если одна буква кодируется как «точка», а другая как «точка-тире», возникает проблема: получив «точку-тире», ты не поймёшь, это одна буква или две. Условие Фано решает именно эту проблему.

Условие Фано — это правило, которое гласит: никакое кодовое слово не является началом другого кодового слова. Это означает, что любое сообщение, закодированное с использованием таких кодов, можно расшифровать без ошибок и неоднозначностей.

Зачем это нужно на практике? Условие Фано используется везде, где важна точная передача информации: в архиваторах файлов, при передаче данных по интернету, в штрих-кодах и даже в телефонных номерах. Без этого условия компьютер не смог бы однозначно прочитать сжатый файл, а мобильная связь давала бы сбои.

История: Роберт Фано и теория информации

Роберт Марио Фано (1917–2016) — итальяно-американский учёный в области информатики, профессор факультетов электротехники и компьютерных наук в Массачусетском технологическом институте, действительный член Национальной академии наук США.

Родился в богатой еврейской семье. Отец, Джино Фано, был профессором геометрии Туринского университета. После принятия в Италии антиеврейских законов в 1939 году эмигрировал в США.

Фано известен по работам в области теории информации, он независимо от Клода Шеннона изобрел ранний алгоритм сжатия информации и вывел неравенство Фано. В 1949 году Роберт Фано опубликовал отчет, в котором независимо от Клода Шеннона описан Алгоритм Шеннона — Фано.

В 1976 году Фано получил награду имени Шеннона за работы в области теории информации. Его вклад в развитие компьютерных наук сложно переоценить: работы Фано легли в основу современных методов сжатия данных.

Основное определение и формулировки

Обычная формулировка: Никакое кодовое слово не может быть началом другого кодового слова.

Математическая формулировка: Для любых двух различных кодовых слов K_i и K_j из кодовой таблицы выполняется условие: K_i не является префиксом K_j.

Разберём на примере:

Буква	Код (удовлетворяет условию Фано)	Код (НЕ удовлетворяет условию Фано)
А	0	0
Б	10	01
В	110	010
Г	111	0101

В первом столбце никакой код не является началом другого. Во втором столбце код «0» является началом всех остальных кодов — условие Фано нарушено!

Теория кодирования: равномерные и неравномерные коды

В теории информации существует два основных типа кодов:

Равномерные коды — все кодовые слова имеют одинаковую длину.

Пример: кодировка ASCII использует 8 бит для каждого символа. Буква «А» — 01000001, буква «Z» — 01011010. Каждый символ занимает ровно 8 бит.

Неравномерные коды — кодовые слова имеют разную длину.

В задачах ЕГЭ необходимо закодировать последовательность букв с использованием неравномерного двоичного кода, который должен соответствовать условию Фано.

Преимущества неравномерного кодирования:

• Экономия места: частые символы кодируются короткими кодами (1–2 бита), редкие — длинными (3–5 бит)
• Эффективность: в среднем сообщение занимает меньше места, чем при равномерном кодировании
• Практичность: используется во всех современных архиваторах (ZIP, RAR, 7z)

Характеристика	Равномерный код	Неравномерный код
Длина кодовых слов	Одинаковая	Разная
Простота декодирования	Очень простая	Требует условия Фано
Эффективность сжатия	Низкая	Высокая
Примеры	ASCII, UTF-32	Коды Хаффмана, Шеннона-Фано

Префиксные и постфиксные коды

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

Пример префиксного кода:

• А: 0
• Б: 10
• В: 110
• Г: 111

Когда декодер читает последовательность слева направо, он сразу понимает, где заканчивается одна буква и начинается другая. Например, последовательность 0110111 читается однозначно: 0-110-111 = А-В-Г.

Постфиксный код — код, в котором ни одно кодовое слово не является концом (постфиксом) другого. Такие коды удовлетворяют обратному условию Фано.

Пример постфиксного кода:

• А: 0
• Б: 01
• В: 011
• Г: 111

Декодирование постфиксного кода ведётся справа налево (с конца сообщения).

Прямое условие Фано: определение и примеры

Прямое условие Фано гарантирует, что закодированное сообщение можно однозначно декодировать с начала.

Формулировка: Ни одно кодовое слово не является началом другого кодового слова.

Пример 1. Проверка кода

Дан код: К — 0, Л — 10, М — 110, Н — 111

Проверяем:

• 0 не начинает 10, 110, 111
• 10 не начинает 0, 110, 111
• 110 не начинает другие
• 111 не начинает другие

Вывод: код удовлетворяет прямому условию Фано.

Пример 2. Декодирование

Сообщение: 011011110

Декодируем слева направо, используя код из примера 1:

• 0 — буква К
• 110 — буква М
• 111 — буква Н
• 10 — буква Л
• 0 — буква К

Результат: КМНЛК

Пример 3. Код НЕ удовлетворяет условию

Дан код: А — 0, Б — 01, В — 10

Код А (0) является началом кода Б (01). Условие Фано нарушено!

Попробуем декодировать: 010

• Вариант 1: 0-10 = А-В
• Вариант 2: 01-0 = Б-А

Два разных результата! Декодирование неоднозначно.

Обратное условие Фано: определение и примеры

Обратное условие Фано гласит: никакое кодовое слово не является окончанием другого кодового слова. Гарантируется, что закодированное сообщение можно однозначно декодировать с конца.

Формулировка: Ни одно кодовое слово не заканчивается другим кодовым словом.

Пример 1. Проверка кода на обратное условие

Дан код: А — 00, Б — 01, В — 10, Г — 110

Проверяем справа налево:

• 00 не является концом других
• 01 не является концом других
• 10 является концом 110

Вывод: код НЕ удовлетворяет обратному условию Фано (10 — это конец 110).

Пример 2. Правильный код для обратного условия

Дан код: А — 00, Б — 01, В — 10, Г — 11

Проверяем:

• 00 не заканчивает другие коды
• 01 не заканчивает другие коды
• 10 не заканчивает другие коды
• 11 не заканчивает другие коды

Вывод: код удовлетворяет обратному условию Фано.

Дерево Фано: построение и применение

Дерево Фано – это наглядный и эффективный метод для решения задач, связанных с созданием неравномерных двоичных кодов. Это бинарное дерево, в котором каждый переход влево обозначается 0, а вправо — 1 (или наоборот).

Правила построения дерева Фано:

1. Корень дерева — начальная точка
2. Из каждого узла отходят две ветви: левая (0) и правая (1)
3. Листья дерева — это кодируемые символы
4. Путь от корня до листа образует код символа

Пример построения:

Нужно закодировать буквы А, Б, В, Г. Известны коды: А — 00, Б — 01, В — 10. Найти код для Г.

Строим дерево:

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

Из дерева видно, что для буквы Г остаётся код 11.

Применение дерева Фано:

• Визуализация кода: дерево показывает структуру кодов
• Проверка условия: если два символа в одном узле — условие нарушено
• Поиск кратчайших кодов: незаполненные ветви указывают на свободные коды
• Декодирование: идём по дереву согласно битам сообщения

Декодирование с помощью дерева:

Дано сообщение: 001011

Движемся по дереву:

• 0 → 0 → достигли листа [А]
• 1 → 0 → достигли листа [В]
• 1 → 1 → достигли листа [Г]

Результат: АВГ

Алгоритм проверки кода на условие Фано

Существует чёткий алгоритм, который позволяет быстро проверить любой код на соответствие условию Фано.

Алгоритм для прямого условия Фано:

1. Запиши все кодовые слова в столбик
2. Для каждого кодового слова проверь: не начинаются ли им другие слова
3. Если найдёшь хотя бы одну пару, где одно слово начинается с другого — условие НЕ выполнено
4. Если таких пар нет — условие выполнено

Пример проверки:

Коды: 0, 10, 110, 111

Проверяемый код	Начинается ли им другой код?	Результат
0	Нет (10, 110, 111 не начинаются с 0)
10	Нет (0, 110, 111 не начинаются с 10)
110	Нет
111	Нет

Вывод: условие Фано выполнено.

Упрощённый метод (для ЕГЭ):

• Отсортируй коды по длине (от короткого к длинному)
• Короткий код не должен быть началом длинного
• Проверяй последовательно: сравнивай каждый код только с теми, что длиннее

Связь с алгоритмами Шеннона-Фано и Хаффмана

Условие Фано лежит в основе двух важнейших алгоритмов сжатия данных.

Алгоритм Шеннона-Фано

Алгоритм Шеннона-Фано — алгоритм префиксного неоднородного кодирования. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано — префиксные, то есть никакое кодовое слово не является префиксом любого другого.

Принцип работы:

1. Подсчитай частоту каждого символа в сообщении
2. Отсортируй символы по убыванию частоты
3. Раздели список на две группы с примерно равной суммой частот
4. Первой группе присвой код 0, второй — 1
5. Повторяй деление для каждой группы

Алгоритм Хаффмана

Алгоритм кодирования Хаффмана был разработан через несколько лет после алгоритма Шеннона - Фано. Он также имеет свойство префиксности, а, помимо этого, обладает доказанной минимальной избыточностью.

Принцип работы:

1. Каждый символ — отдельный узел с весом (частотой)
2. Выбери два узла с наименьшим весом
3. Объедини их в новый узел, вес которого равен сумме весов
4. Повторяй, пока не останется один корневой узел
5. Присвой рёбрам коды (0 и 1)

Характеристика	Шеннона-Фано	Хаффмана
Условие Фано	Выполняется	Выполняется
Оптимальность	Не всегда оптимален	Всегда оптимален
Сложность построения	Простая	Средняя
Применение	Учебные цели	ZIP, PNG, MP3

Если построить все возможные коды Шеннона — Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, то есть оптимальные коды.

Практические примеры из жизни

1. Телефонные номера

Система телефонных номеров построена с учётом условия Фано! Номера разных городов не могут начинаться друг с друга. Например:

• Москва: +7 495 xxx-xx-xx
• Санкт-Петербург: +7 812 xxx-xx-xx
• Екатеринбург: +7 343 xxx-xx-xx

Коды 495, 812, 343 не являются началами друг друга, поэтому телефонная станция сразу понимает, куда направлять звонок.

2. Системы передачи данных

При передаче данных по интернету используются коды, удовлетворяющие условию Фано. Это позволяет:

• Декодировать данные «на лету» без задержек
• Не хранить всё сообщение целиком перед декодированием
• Избежать ошибок при восстановлении информации

3. Штрих-коды и QR-коды

Внутренняя структура QR-кодов использует префиксное кодирование. Сканер считывает код последовательно и сразу определяет границы блоков данных.

4. Архиваторы файлов

Форматы ZIP, RAR, 7-Zip используют алгоритм Хаффмана, который строит коды, удовлетворяющие условию Фано. Благодаря этому:

• Файлы сжимаются эффективно (экономия 50–90% места)
• Распаковка происходит быстро
• Данные восстанавливаются без потерь

5. Азбука Морзе

Интересный факт: классическая азбука Морзе НЕ удовлетворяет условию Фано! Например, буква E (точка) является началом буквы I (две точки). Поэтому в азбуке Морзе используются паузы для разделения букв.

Задание №4 ЕГЭ по информатике: типы задач

Задание №4 из ЕГЭ по информатике 2025 года направлено на проверку знаний в области кодирования и декодирования информации с использованием неравномерных двоичных кодов. Оно относится к базовому уровню сложности, и выполнение задачи обычно занимает около 2 минут.

Типы задач:

Тип 1. Найти кратчайшее кодовое слово

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

Пример: Известны коды К — 01, Л — 001, М — 000. Найти кратчайший код для буквы Н.

Тип 2. Найти длину закодированного сообщения

Даны коды для части букв. Нужно найти минимальную длину кодирования заданного слова.

Пример: Известны коды А — 110, Б — 01. Какова минимальная длина слова ДЕЛЕНИЕ?

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

Дана закодированная последовательность и таблица кодов. Нужно её декодировать.

Пример: Дано сообщение 01100111 и коды: А — 0, Б — 110, В — 111. Декодировать.

Тип 4. Подсчёт суммарной длины кодов

Даны коды для части букв. Нужно найти минимальную суммарную длину кодов для оставшихся букв.

Тип 5. Проверка на условие Фано

Дана таблица кодов. Нужно определить, выполняется ли условие Фано (прямое или обратное).

Тип 6. Коды с обратным условием Фано

Те же типы задач, но проверяется обратное условие (декодирование справа налево).

Решение задач ЕГЭ: примеры с пошаговым разбором

Задача 1. Найти кратчайшее кодовое слово

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

Решение:

Шаг 1. Рисуем дерево Фано и отмечаем известные коды:

          (корень)
         /        \
        0          1
       / \        / \
      0   1      0   1
    [А] /|\    [?] [Б]
       0 1 ?
      [В]

Шаг 2. Смотрим, какие короткие коды свободны:

• 0 — занят (начало кода А)
• 1 — занят (начало кода Б)
• 00 — занят (код А)
• 01 — занят (начало кода В)
• 10 — свободен!
• 11 — занят (код Б)

Шаг 3. Проверяем условие Фано для кода 10:

• 10 не является началом 00, 11, 010
• 00, 11, 010 не являются началом 10

Ответ: 10

Задача 2. Длина закодированного сообщения

Для кодирования используется неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды: К — 0, Л — 10, М — 110, Н — 111. Какое количество двоичных знаков потребуется для кодирования слова КЛМН?

Решение:

Шаг 1. Заменяем каждую букву её кодом:

• К → 0 (1 бит)
• Л → 10 (2 бита)
• М → 110 (3 бита)
• Н → 111 (3 бита)

Шаг 2. Складываем длины: 1 + 2 + 3 + 3 = 9

Ответ: 9

Задача 3. Найти минимальное количество знаков

Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова некоторых букв известны: А — 110, Б — 01, И — 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ДЕЛЕНИЕ?

Решение:

Шаг 1. Анализируем слово: Д-Е-Л-Е-Н-И-Е (7 букв, из них И — 1 раз, остальные неизвестны)

Шаг 2. Строим дерево и находим свободные коды:

          (корень)
         /        \
        0          1
       / \        / \
      0   1      0   1
     /|\  [Б]   [?] [А]
    0 ? ?
  [И] ? ?

Шаг 3. Минимальные свободные коды:

• 001 (3 бита)
• 10 (2 бита)
• 111 (3 бита)

Шаг 4. Распределяем коды для оставшихся 4 букв (Д, Е, Л, Н):

• Самый короткий (10) — для Е (встречается 3 раза)
• Остальные — для Д, Л, Н (по разу)

Шаг 5. Считаем длину ДЕЛЕНИЕ:

• Д — 001 (3)
• Е — 10 (2)
• Л — 111 (3)
• Е — 10 (2)
• Н — 100 (3)
• И — 000 (3)
• Е — 10 (2)

Итого: 3 + 2 + 3 + 2 + 3 + 3 + 2 = 18

Ответ: 18

Задача 4. Декодирование последовательности

Дана кодовая таблица: А — 0, Б — 10, В — 110, Г — 111. Декодируйте сообщение: 0110111100

Решение:

Читаем слева направо, сверяясь с таблицей:

• 0 — А
• 110 — В
• 111 — Г
• 10 — Б
• 0 — А

Ответ: АВГБА

Задача 5. Обратное условие Фано

Дан код: А — 00, Б — 10, В — 01, Г — 110. Выполняется ли обратное условие Фано?

Решение:

Проверяем, не заканчивается ли один код другим:

• 00 не заканчивает другие
• 10 заканчивает 110

Ответ: Нет, обратное условие Фано НЕ выполняется.

Задача 6. Суммарная длина кодов

Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Д — 00, Е — 10, Ж — 110, З — 111. Известно, что есть ещё 4 буквы: А, Б, В, Г. Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв А, Б, В, Г.

Решение:

Шаг 1. Строим дерево и находим свободные позиции:

          (корень)
         /        \
        0          1
       / \        / \
      0   1      0   1
    [Д] [?]   [Е]/|\
                0 1 ?
              [Ж][З]?

Шаг 2. Свободные коды:

• 01 (2 бита)
• 1110 (4 бита)
• 1111 (4 бита)
• Можем добавить ещё ветки от 01: 010 и 011 (по 3 бита)

Шаг 3. Минимальный вариант для 4 букв:

• 010 (3)
• 011 (3)
• 1110 (4)
• 1111 (4)

Сумма: 3 + 3 + 4 + 4 = 14

Ответ: 14

Задача 7. Сложная задача на оптимизацию

По каналу связи передаются сообщения, содержащие только цифры 2, 3, 4, 5 и четыре знака арифметических действий +, -, *, /. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для цифр известны: 2 — 00, 3 — 01, 4 — 10, 5 — 11. Какое наименьшее количество двоичных знаков требуется для кодирования четырёх знаков арифметических действий? В ответе запишите суммарную длину кодовых слов.

Решение:

Шаг 1. Все коды длины 2 заняты (00, 01, 10, 11). Нужны коды длины 3.

Шаг 2. Но коды длины 3 нарушат условие Фано! Например, 000 начинается с 00.

Шаг 3. Используем другую стратегию — смешанные коды:

• Переназначаем: 2 — 000, 3 — 001, 4 — 01, 5 — 1
• Свободные: 00 (занято), 10, 110, 111

Стоп! Мы не можем менять заданные коды.

Шаг 4. Правильное решение: раз все 2-битные коды заняты, для операций используем 3-битные, но они должны начинаться с комбинаций, которые ещё не использованы как начала:

Невозможно! Все 2-битные варианты заняты.

Значит, минимум — 4 бита для каждого знака: 000, 001... Нет, это тоже нарушит!

Правильное решение: Система уже заняла все коды длины 2. Для добавления новых символов нужно использовать коды, которые НЕ начинаются ни с одного из занятых. Но это невозможно при текущей структуре!

Задача некорректна в изначальной постановке. Обычно в таких задачах часть кодов неизвестна, и мы строим оптимальное дерево.

Частые ошибки при решении задач

Ошибка 1. Путать прямое и обратное условие

Всегда читай условие: если не указано явно, по умолчанию проверяется прямое условие (префиксы).

Ошибка 2. Забывать проверять ВСЕ пары кодов

Недостаточно проверить, что короткие коды не начинают длинные. Нужно проверить каждую пару!

Пример: Коды 10, 01, 101. Код 10 является началом 101 — условие нарушено!

Ошибка 3. Не учитывать минимальность кода

Если задача требует «кратчайшее кодовое слово», нужно найти именно минимальное, а не любое подходящее.

Ошибка 4. Неправильно строить дерево Фано

Запомни: левая ветвь — 0, правая — 1 (или наоборот, но единообразно).

Ошибка 5. Пропускать проверку самого короткого кода

Даже если код состоит из одного бита (0 или 1), его нужно проверить на условие Фано!

Ошибка 6. Неверное декодирование

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

Ошибка 7. Считать, что условие Фано — единственное для однозначности

Условие Фано является достаточным, но не необходимым для однозначной декодируемости: есть однозначно декодируемые коды, не являющиеся префиксными. Однако для ЕГЭ это не критично — в заданиях используются именно префиксные коды.

Советы по подготовке к ЕГЭ

1. Тренируй построение дерева Фано

Рисуй дерево для каждой задачи — это визуализирует структуру кодов и помогает не ошибиться.

2. Запомни стандартные проверки

• Все коды одинаковой длины → условие выполнено автоматически
• Есть код длины 1 → все остальные должны начинаться с другого бита
• Проверяй пары: короткий код не должен быть началом длинного

3. Отрабатывай скорость

На задание №4 отводится около 2 минут. Тренируй решение на время: ты должен за 1 минуту строить дерево и за 1 минуту находить ответ.

4. Используй шпаргалку по типам задач

Составь себе таблицу с алгоритмами для каждого типа задач (см. раздел «Типы задач»).

5. Прорешай все задачи из открытого банка ФИПИ

На сайте ФИПИ выложены реальные задачи прошлых лет. Прорешай их все — многие задачи повторяются с небольшими изменениями.

6. Проверяй ответ через декодирование

Нашёл код для буквы? Проверь: попробуй декодировать какую-нибудь последовательность с этим кодом. Если получается однозначно — всё верно.

7. Учи обратное условие Фано

Хоть оно встречается реже, в вариантах ЕГЭ оно появляется. Не игнорируй эту тему!

8. Пользуйся онлайн-тренажёрами

Сайты вроде «Решу ЕГЭ» (inf-ege.sdamgia.ru) предлагают тысячи задач с автоматической проверкой.

Применение в современных технологиях

1. Сжатие данных

Все современные архиваторы (ZIP, RAR, 7-Zip, gzip) используют алгоритм Хаффмана или его модификации. Благодаря условию Фано файлы сжимаются без потерь и быстро распаковываются.

Типичное сжатие:

• Текстовые файлы: 60–80%
• Изображения BMP: 80–95%
• Исполняемые файлы: 30–50%

2. Форматы изображений

Формат PNG использует комбинацию алгоритмов, включая кодирование Хаффмана. JPEG тоже применяет префиксное кодирование на этапе сжатия.

3. Видео- и аудиокодеки

MP3, AAC, H.264, H.265 — все используют энтропийное кодирование с условием Фано. Это позволяет:

• Уменьшить размер файла в 10–20 раз
• Сохранить приемлемое качество
• Воспроизводить медиа «на лету»

4. Мобильная связь и Wi-Fi

Протоколы передачи данных используют префиксные коды для эффективной упаковки информации в пакеты. Это экономит трафик и ускоряет соединение.

5. Облачные хранилища

Google Drive, Яндекс.Диск, Dropbox сжимают файлы перед загрузкой на сервер. Это экономит место и ускоряет синхронизацию.

6. Системы штрих-кодирования

EAN-13, QR-коды используют префиксное кодирование для разделения блоков данных (тип товара, производитель, контрольная сумма).

7. Криптография

Некоторые криптографические алгоритмы используют префиксные коды для эффективного представления ключей и зашифрованных данных.

8. Искусственный интеллект

Нейронные сети для обработки текста (GPT, BERT) используют токенизацию — разбиение текста на фрагменты. Эффективное кодирование токенов основано на принципах условия Фано.

Заключение и выводы

Условие Фано — это фундаментальный принцип теории информации, который обеспечивает однозначное декодирование сообщений. Ты узнал, что:

• Прямое условие Фано требует, чтобы ни один код не был началом другого
• Обратное условие Фано требует, чтобы ни один код не был концом другого
• Дерево Фано — удобный инструмент для визуализации и проверки кодов
• Алгоритмы Шеннона-Фано и Хаффмана строят коды, удовлетворяющие условию Фано
• В ЕГЭ по информатике задание №4 проверяет понимание этих принципов

Условие Фано используется повсюду: от архиваторов и кодеков до телефонии и облачных хранилищ. Понимание этого принципа даёт тебе ключ к пониманию того, как компьютеры эффективно хранят и передают информацию.

Ключевые моменты для запоминания:

1. Условие Фано = никакой код не начинает другой
2. Дерево Фано — лучший способ решения задач
3. Проверяй ВСЕ пары кодов, а не только короткие с длинными
4. Для ЕГЭ важны оба условия: прямое и обратное
5. Практика — единственный путь к уверенному решению за 2 минуты

Удачи на ЕГЭ!