Задание 4 ЕГЭ информатика

1. Введение

Задание №4 проверяет умение работать с неравномерным двоичным кодом, удовлетворяющим условию Фано.

При решении задания необходимо уметь:

• определять длину кодового слова;
• проверять условие Фано;
• строить двоичное дерево;
• находить свободные кодовые слова;
• достраивать коды для всех символов алфавита;
• находить минимальный код или минимальную длину сообщения;
• учитывать частоту повторения букв в слове.

Алфавит — набор символов, которые могут встречаться в сообщении.

Кодовое слово — последовательность нулей и единиц, соответствующая одному символу.

Например:

• А → 0;
• Б → 10;
• В → 110;
• Г → 111.

2. Неравномерный двоичный код

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

Например:

• А → 00;
• Б → 01;
• В → 10;
• Г → 11.

Длина каждого кода равна 2 битам.

В неравномерном коде кодовые слова могут иметь разную длину.

Например:

• А → 0 — 1 бит;
• Б → 10 — 2 бита;
• В → 110 — 3 бита;
• Г → 111 — 3 бита.

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

Однако коды необходимо подобрать так, чтобы сообщение можно было однозначно расшифровать.

3. Условие Фано

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

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

Удачный пример

• А → 0;
• Б → 10;
• В → 110;
• Г → 111.

Условие Фано выполняется:

• код 0 не является началом других кодов;
• код 10 не является началом кодов 110 и 111;
• коды 110 и 111 не являются началом друг друга.

Неудачный пример

• А → 0;
• Б → 01;
• В → 1.

Код 0 является началом кода 01, поэтому условие Фано нарушено.

Последовательность 01 можно расшифровать двумя способами:

• Б → 01;
• АВ → 0 1.

Однозначная расшифровка невозможна.

Ещё один неудачный пример

• А → 10;
• Б → 101;
• В → 11.

Код 10 является началом кода 101. Следовательно, условие Фано не выполняется.

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

4. Как строить дерево Фано

Дерево Фано показывает:

• какие коды уже заняты;
• какие продолжения использовать нельзя;
• где можно разместить новые символы;
• хватит ли свободных ветвей для всего алфавита.

В дереве:

• ветвь 0 обычно направляют влево;
• ветвь 1 — вправо;
• путь от корня до буквы образует её код;
• буквы размещаются только в конечных вершинах — листьях.

Рассмотрим пример:

• Л → 00;
• М → 01;
• Н → 11;
• коды букв П и Р неизвестны.

Шаг 1. Наносим известные коды

Начинаем с корня и двигаемся по цифрам каждого кода:

Например:

• 00 — два перехода по ветви 0;
• 01 — сначала 0, затем 1;
• 11 — два перехода по ветви 1.

Вершины с буквами продолжать нельзя. Поэтому использовать коды, начинающиеся с 00, 01 или 11, уже невозможно.

Например, после кода Л → 00 запрещены:

• 000;
• 001;
• 0001;
• любые другие продолжения 00.

Иначе 00 станет началом другого кода, и условие Фано нарушится.

Шаг 2. Считаем оставшиеся буквы

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

Но нам необходимо закодировать две буквы:

• П;
• Р.

Нельзя сразу назначить:

П → 10

Тогда 10 станет листом, а продолжения 100 и 101 использовать будет нельзя. Для буквы Р места не останется.

Перед использованием свободной вершины всегда считайте, сколько символов алфавита ещё осталось закодировать.

Шаг 3. Делим свободную вершину

Поскольку внутри ветви 10 нужно разместить две буквы, разделяем её на две новые ветви:

• 100;
• 101.

Получаем полный код:

• Л → 00;
• М → 01;
• Н → 11;
• П → 100;
• Р → 101.

Все символы находятся в листьях, поэтому условие Фано выполняется.

Шаг 4. Выбираем требуемый вариант

Буквы П и Р можно поменять местами:

• П → 100, Р → 101;
• П → 101, Р → 100.

Оба варианта допустимы.

Если требуется найти код буквы П с наименьшим числовым значением, выбираем:

П → 100

поскольку двоичное число 100 меньше 101.

Краткий алгоритм построения дерева

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

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

5. Основные прототипы задания

Прототип 1. Найти код с наименьшим числовым значением

Даны коды нескольких букв. Для остальных букв коды неизвестны. Требуется найти минимально возможный код определённой буквы.

Алгоритм:

1. Построить дерево по известным кодам.
2. Найти свободные ветви.
3. Посчитать все незакодированные символы.
4. Достроить коды для всего алфавита.
5. Выбрать минимальный допустимый код нужной буквы.

Главная ошибка — дать требуемой букве короткий код, но не оставить места для остальных символов.

Прототип 2. Найти минимальную сумму длин кодов

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

Например, если получены коды длиной 2, 3, 4 и 4 бита, то:

2 + 3 + 4 + 4 = 13 бит

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

Прототип 3. Найти минимальную длину закодированного слова

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

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

Например, в слове КАЗАЧКА:

• А встречается 3 раза;
• К — 2 раза;
• З — 1 раз;
• Ч — 1 раз.

Самый короткий доступный код выгоднее дать букве А, следующий по длине — букве К.

Общая длина сообщения вычисляется по формуле:

L = n₁ · l₁ + n₂ · l₂ + ... + nₖ · lₖ

где:

• n — количество повторений буквы;
• l — длина её кода.

Чем чаще буква встречается в слове, тем выгоднее дать ей более короткий код.

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

Прототип 4. В слове используются не все символы алфавита

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

Например, алфавит содержит 12 символов. Коды первых 8 символов известны, а подобрать требуется коды для 9-го, 10-го и 11-го символов.

Нельзя забывать про 12-й символ. Для него тоже необходимо оставить допустимый код, даже если:

• он не встречается в слове;
• его код не спрашивают;
• его длина напрямую не влияет на ответ.

Иначе будет закодирован не весь алфавит, поэтому решение окажется неправильным.

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

видео разбор задания

Практическая часть, задания с реального ЕГЭ

Практическое задание №1

Источник: Основная волна 2023

Условие

По каналу связи передаются шифрованные сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется неравномерный двоичный код. Для шести букв используются кодовые слова:

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?

В ответе запишите суммарную длину кодовых слов для букв А и Б.

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

Решение

После нанесения известных кодов единственной свободной остаётся вершина 101.

Нужно закодировать две буквы — А и Б. Назначить одной из них код 101 нельзя: он станет листом, поэтому продолжить его и закодировать вторую букву уже не получится.

Разделим вершину 101:

• А → 1010;
• Б → 1011.

Буквы можно поменять местами — длина кодов не изменится.

Суммарная длина:

4 + 4 = 8 бит

Ответ: 8.

Практическое задание №2

Источник: Открытый банк заданий ФИПИ

Условие

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код.

Для кодирования букв используются кодовые слова:

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

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

Решение

Построим дерево по известным кодам.

После заполнения известных ветвей свободной остаётся вершина 111.

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

У → 111

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

Ответ: 111.

Практическое задание №3

Источник: Основная волна 19.06.2024

Условие

По каналу связи передаются сообщения, содержащие только буквы Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано.

Кодовые слова для некоторых букв известны:

• Б → 1001;
• К → 11.

Для трёх оставшихся букв Л, Н и О кодовые слова неизвестны.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОКОЛ?

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

Решение

В слове КОЛОКОЛ:

• О встречается 3 раза;
• К — 2 раза;
• Л — 2 раза.

Код буквы К уже известен: 11, его длина равна 2 битам.

После построения дерева оставшимся буквам можно назначить коды длиной 1, 3 и 4 бита. Самый короткий код отдаём наиболее частой букве:

• О → 0;
• Л → 101;
• Н → 1000.

Буква Н в слове не встречается, но ей всё равно необходимо назначить код.

Длина слова:

2 · 2 + 3 · 1 + 2 · 3 = 4 + 3 + 6 = 13 бит

Ответ: 13.

Практическое задание №4

Источник: Основная волна 11.06.2025

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано.

Кодовые слова для некоторых букв известны:

Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв?

В ответе запишите суммарную длину кодовых слов для букв А, Б, В, Г.

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

Решение

Ветвь 1 полностью занята кодами:

• Е → 10;
• Д → 11.

В ветви 0 свободны вершины 000 и 010. Но необходимо закодировать четыре буквы: А, Б, В и Г.

Если занять вершины 000 и 010, места хватит только для двух букв. Поэтому каждую свободную вершину разделим ещё на две ветви:

• А → 0000;
• Б → 0001;
• В → 0100;
• Г → 0101.

Все четыре новых кода имеют длину 4 бита.

Суммарная длина:

4 + 4 + 4 + 4 = 16 бит

Ответ: 16.

Практическое задание №5

Источник: Основная волна 18.06.2026

Условие

По каналу связи передаются сообщения, содержащие только буквы из набора: А, Д, К, Н, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано.

Кодовые слова для некоторых букв известны:

• Р → 0101;
• Н → 011.

Для трёх оставшихся букв А, К и Д кодовые слова неизвестны.

Какое количество двоичных знаков потребуется для кодирования слова КАНАДКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

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

Решение

В слове КАНАДКА:

• А встречается 3 раза;
• К — 2 раза;
• Н — 1 раз;
• Д — 1 раз.

Код буквы Н уже известен: 011, его длина равна 3 битам.

После построения дерева буквам А, К и Д можно назначить коды длиной 1, 2 и 4 бита. Более короткие коды отдаём более частым буквам:

• А → 1;
• К → 00;
• Д → 0100.

Код буквы Р уже задан: 0101. Буква Р в слове не встречается, поэтому её код не влияет на длину сообщения.

Длина слова:

3 · 1 + 2 · 2 + 1 · 3 + 1 · 4 = 3 + 4 + 3 + 4 = 14 бит

Ответ: 14.