Информатик
Главная › ЕГЭ по информатике › Задание 4
ЕГЭ по информатике · задание №4

Условие Фано: учимся строить двоичные деревья

Превращаем нули и единицы в пути. Находим свободные ветви, подбираем короткие коды и понимаем, как получить минимальную сумму длин. Сначала строим вместе, затем пробуем сами.

Построить своё деревоРазобраться с нуля
Сначала смысл

Задание 4 ЕГЭ: кодовые слова и условие Фано

Буквам назначают последовательности из нулей и единиц: например, А → 00, Б → 01, В → 1. Длины кодов могут различаться. В этих задачах нужно дополнить кодовую таблицу так, чтобы сообщение можно было однозначно читать слева направо.

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

У слов 01 и 010 конфликт: прочитав 01, ещё нельзя понять, закончилась буква или нужно читать следующий 0. А 010 и 011 совместимы: ни одно целиком не стоит в начале другого.

Пара кодовПроверкаРезультат
0 и 010 — начало 01Конфликт
00 и 001100 — начало 0011Конфликт
010 и 011Общий участок 01 разрешён; целые коды различаютсяМожно
1000 и 1001Различаются последним битомМожно
01 и 01Одинаковый код для разных буквНельзя

Дерево помогает увидеть все эти отношения сразу. Готовые кодовые слова отмечаем буквами в конечных вершинах — листьях. Общие начала слов остаются внутренними вершинами.

Построим с нуля

Как строить двоичное дерево по кодам

  1. Нарисуй корень. Это старт до чтения битов. У корня пока нет кода и нет буквы.
  2. Договорись о направлениях: ребро 0 идёт налево, ребро 1 — направо. На каждом шаге читай ровно один бит.
  3. Для А = 00 пройди из корня 0 → 0. В конце поставь А. Длина 2 — это два ребра, а не количество нарисованных вершин.
  4. Для C = 010 вернись к корню, пройди 0 → 1 → 0. Начальную ветвь 0 используй ту же самую. Поставь C только в конце пути.
  5. Для D = 011 снова начни от корня. Путь 0 → 1 уже существует; добавь правое ребро 1 и подпиши D.
  6. Проверь листья. Из вершины с готовой буквой больше не проводи ветви: любой код ниже неё нарушит условие Фано.
Дерево для A = 00, C = 010, D = 011Налево — 0, направо — 1. A = 00; C = 010; D = 011. Свободные ветви: 1.00110100A010C011D01ветвь0ветвь1свободностарткорень
Пути C и D разделяют общий участок 01. Вершина 01 — развилка, а не готовый код. Ветка 1 пока свободна.
Не рисуй отдельное дерево для каждой буквыВсе пути начинаются в одном корне. Одинаковые первые биты проходят через одни и те же вершины. Если путь уже дошёл до готовой буквы, продолжать его нельзя.

Четыре состояния вершины

СостояниеПример в дереве вышеМожно назначить новую букву?
Готовый лист00, 010, 011Нет: код уже занят
Развилка над готовыми кодами0, 01Нет: новый код станет началом существующего
Потомок готового листа000 под A = 00Нет: существующий код станет началом нового
Свободная ветвь1 и её продолженияДа, с учётом остальных новых букв

«Вершина не подписана» ещё не значит «свободна». Сначала проверь, нет ли готовой буквы выше по пути и нет ли уже назначенных букв ниже.

Построй сам

Интерактивный тренажёр двоичного дерева

Выбери режим. Проходи путь кнопками 0 и 1 либо введи код вручную, затем закрепи за ним букву. В дереве можно выбирать вершины мышью или клавишами Tab и Enter. На узком экране прокрути схему в сторону.

Попробуй ошибиться осознанноВ первом режиме закрепи A = 00. Затем проверь C = 001 и C = 0: тренажёр объяснит два разных конфликта. После этого исправь C на 010.
Тип 1 · один неизвестный код

Как найти кратчайшее кодовое слово

Известны коды девяти букв. Подбери для B кратчайшее кодовое слово, сохранив условие Фано. Среди кратчайших выбери код с наименьшим числовым значением.
БукваКодБукваКод
A00F1001
B?S1100
C010X1010
D011Y1101
E1011Z111

Шаг 1. Построй известные пути

Начни с короткого A = 00: вся область под 00 сразу закрыта. Затем добавь C = 010 и D = 011. В правой половине дерева разложи коды 1001, 1010, 1011, 1100, 1101 и 111.

Шаг 2. Ищи свободную вершину по уровням сверху вниз

ДлинаКандидатыПочему не подходят
10, 1Оба являются началами готовых кодов
200, 01, 10, 1100 занят; остальные ведут к готовым кодам
3000, 001Находятся под готовым A = 00
3010, 011, 111Уже заняты буквами C, D и Z
3100, 101, 110Являются началами готовых четырёхбитных кодов
41000Свободен: нет готового кода ни выше, ни ниже

Шаг 3. Закрепи B = 1000 и проверь оба направления

Ни один известный код не является началом 1000. Само 1000 тоже не является началом известного кода. Соседний F = 1001 не мешает: общая развилка 100 разрешена.

Решение: кратчайший код B = 1000Налево — 0, направо — 1. A = 00; C = 010; D = 011; E = 1011; F = 1001; S = 1100; X = 1010; Y = 1101; Z = 111; B = 1000.00110010011001011100A010C011D01ветвь0ветвь1000B1001F100ветвь1010X1011E101ветвь10ветвь1100S1101Y110ветвь111Z11ветвь1ветвьстарткорень
Зелёный лист B = 1000 дополняет дерево. Внутренние вершины 10 и 100 нельзя было брать готовыми кодами.
Ответ: 1000Сначала минимизируем длину, затем сравниваем числовое значение среди кодов этой длины. Здесь на длине 4 свободен только 1000.

Если кратчайших вариантов несколько

Пусть известны только 00 и 11. Код длины 1 невозможен, а на длине 2 свободны 01 и 10. Выбираем 01: при равной длине он меньше 10. Проверять удобно слева направо: 00, 01, 10, 11.

Не превращай строку 01 в 1: ведущий ноль — часть пути, поэтому эти два кода находятся в разных вершинах.

Тип 2 · несколько неизвестных кодов

Как получить минимальную суммарную длину

Заданы А = 000, Б = 001, В = 01 и Г = 11. Нужно назначить коды четырём буквам Д, Е, Ж и З. Найди наименьшую сумму длин этих четырёх кодовых слов.
Известные коды и свободная ветвь 10Налево — 0, направо — 1. А = 000; Б = 001; В = 01; Г = 11. Свободные ветви: 10.01010011000А001Б00ветвь01В0ветвь10свободно11Г1ветвьстарткорень
Левая половина занята кодами 000, 001 и 01; справа занят 11. Новые коды могут начинаться только с 10.

Шаг 1. Найди область для всех новых букв

Любой новый код начинается с 10. Но если сразу закрепить 10 за одной буквой, остальные три уже не поместятся: вся оставшаяся свободная область окажется под готовым листом.

Шаг 2. Преврати одну свободную ветвь в четыре листа

  1. Раскрой 10 в две дочерние вершины: 100 и 101.
  2. Раскрой 100: получатся 1000 и 1001.
  3. Раскрой 101: получатся 1010 и 1011.
  4. Назначь четырём листьям Д, Е, Ж и З в любом порядке. Каждая буква получила по 4 бита.
Четыре новых листа с суммой длин 16Налево — 0, направо — 1. А = 000; Б = 001; В = 01; Г = 11; Д = 1000; Е = 1001; Ж = 1010; З = 1011.01010010011011000А001Б00ветвь01В0ветвь1000Д1001Е100ветвь1010Ж1011З101ветвь10ветвь11Г1ветвьстарткорень
Сбалансированное заполнение: 1000, 1001, 1010, 1011. Новые коды находятся на одном уровне.
4 + 4 + 4 + 4 = 16
Ответ: 16Складываем длины только четырёх новых кодов. Длины уже заданных А, Б, В и Г в ответ не включаем.
Разберёмся, почему

Почему короткий код для одной буквы может ухудшить сумму

Можно закрепить Д = 100 и разместить остальные три буквы глубже в соседней ветви. Условие Фано не запрещает такое дерево. Например:

БукваКодДлина
Д1003
Е10104
Ж101105
З101115
Допустимое дерево с суммой длин 17Налево — 0, направо — 1. А = 000; Б = 001; В = 01; Г = 11; Д = 100; Е = 1010; Ж = 10110; З = 10111.01010000111011000А001Б00ветвь01В0ветвь100Д1010Е10110Ж10111З1011ветвь101ветвь10ветвь11Г1ветвьстарткорень
Этот вариант тоже правильный по Фано. Но длины 3, 4, 5 и 5 дают сумму 17 — больше оптимальных 16.

3 + 4 + 5 + 5 = 17. Выиграли один бит на первой букве, но потеряли по одному биту на двух других.

Короткое доказательство минимума 16

Ветка 10 должна разойтись и налево, и направо. Если все четыре кода отправить в одну её половину, у всех появится лишний общий бит: его можно убрать и уменьшить сумму.

  • Две буквы в 100 и две в 101. В каждой половине два разных кода требуют хотя бы ещё по одному биту. Итого все четыре имеют длину не меньше 4: сумма минимум 16, и наш вариант её достигает.
  • Одна буква в одной половине и три в другой. Первую выгоднее сделать кодом длины 3. Для трёх остальных кратчайшие добавочные пути внутри соседней половины имеют длины 1, 2, 2: один дочерний лист и два в другой дочерней ветви. Полные длины получаются 4, 5, 5. Сумма минимум 17.

Распределение 3 + 1 симметрично. Других распределений четырёх букв по двум используемым половинам нет. Поэтому сумма меньше 16 невозможна.

Проверь это рукамиВ третьем режиме тренажёра сначала построй вариант 100, 1010, 10110, 10111 и посмотри на 17. Затем начни заново и построй четыре кода длины 4. Цель — сравнивать сумму, сохраняя место для всех букв.

Здесь минимизируется сумма длин четырёх кодов, каждый учитывается один раз. Если условие спрашивает длину конкретного сообщения, учитывай число повторений каждой буквы: код длины 3, встречающийся 5 раз, даст 15 бит.

Самостоятельная проверка

Десять упражнений по деревьям и кодам

После ошибки измени ответ и проверь снова. В кодах сохраняй начальные нули.

Решено: 0 из 10

1. Длина пути

Сколько рёбер нужно пройти от корня для кода 0101?

2. Общий префикс

Могут ли одновременно быть кодами двух букв 010 и 011? Ответь «да» или «нет».

3. Продолжение готового кода

Есть A = 00. Можно ли назначить другой букве код 001? Ответь «да» или «нет».

4. Код над готовым листом

Есть C = 010. Можно ли назначить другой букве код 01? Ответь «да» или «нет».

5. Выбор при равной длине

Заданы только коды 00 и 11. Найди кратчайший новый код; при равенстве длин выбери наименьшее числовое значение. Сохрани ведущий ноль.

6. Первый разбор

Какой кратчайший код нужно назначить B в первом полном примере?

7. Оставшаяся область

Известны 000, 001, 01 и 11. С каких двух битов начинаются все новые коды?

8. Считаем сумму

Четырём новым буквам назначены коды 1000, 1001, 1010 и 1011. Какова сумма длин только новых кодов?

9. Допустимый, но более длинный вариант

Чему равна сумма длин кодов 100, 1010, 10110 и 10111?

10. Читаем сообщение по дереву

Даны A = 00, B = 01, C = 1. Расшифруй сообщение 00011 латинскими буквами без пробелов.

Видеоразбор

Видео по заданию №4

Видео скоро выйдет.

Алгоритм решения задания 4

  1. Выпиши известные коды, не теряя ведущие нули.
  2. Построй единое дерево: 0 влево, 1 вправо; буква ставится только в конце своего пути.
  3. Закрой продолжения готовых листьев. Не назначай буквы вершинам над ними.
  4. Если нужна одна буква, ищи свободный код по уровням от коротких к длинным.
  5. Если нужны несколько букв, оставь достаточно свободных листьев и сравни суммарную длину всего нового набора.
  6. Проверь все новые коды друг с другом и с известными: нет совпадений и ни один не является началом другого.
  7. Запиши то, что спрашивается: само кодовое слово, его длину, сумму длин или длину сообщения.

Частые вопросы о двоичных деревьях

Почему нельзя взять любую вершину без буквы?

Она может быть развилкой над уже готовым кодом или находиться ниже готового листа. Оба случая нарушают условие Фано. Свободна только область без готовых кодов на пути сверху и в продолжениях снизу.

Общий префикс у двух кодов всегда запрещён?

Нет. У 1000 и 1001 есть общий участок 100 — это разрешено. Запрещено, когда один целый код является началом другого, как 100 и 1001.

Можно ли продолжить готовый лист ещё двумя ветвями?

Только если снять с него букву. Известные коды менять нельзя, поэтому под готовым кодом из условия новые буквы не размещаем.

Минимальная сумма всегда получается у кодов одной длины?

Нет. Всё зависит от свободных ветвей и числа букв. Для трёх букв в одной свободной области кратчайшие добавочные пути могут быть 0, 10 и 11: их длины различаются. В примере с четырьмя буквами под 10 оптимальны четыре пути одинаковой длины.

Можно ли перепутать 01 и 1?

Нет: это разные пути и разная длина. В поле ответа вводи код целиком, включая все начальные нули.

Как декодировать сообщение по дереву?

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

Закрепи двоичные коды в учебнике

Теорию кодирования и полный разбор задания 4 ЕГЭ можно найти в учебнике на сайте. После тренажёра переходи к самостоятельным задачам в практике.

Открыть учебникПерейти к практике