Билет 1 — демоверсия ЕГЭ-2026; остальные билеты — задания в формате экзамена (открытый сборник или тренировочные по образцу). Это тренировочные материалы, а не официальные КИМ. Ответы пересчитаны и сверены.
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Е — 10, Д — 11, Ж — 010, З — 011.
Вопрос. Укажите минимальную суммарную длину кодовых слов для оставшихся четырёх букв (А, Б, В, Г), при которой условие Фано будет выполняться. В ответе запишите целое число.
Разбор задачи
Задание 4 ЕГЭ по информатике — это кодирование и условие Фано. Для части букв коды уже известны, а для остальных их нужно подобрать так, чтобы сообщения расшифровывались однозначно.
Однозначность обеспечивает условие Фано: ни один код не должен быть началом другого. Коды удобно изображать двоичным деревом, а минимальную суммарную длину ищут, размещая буквы в самых коротких свободных ветках.
Что важно знать
Задание базового уровня — оценивается в 1 балл
Новый код нельзя «доращивать» из уже заданного — иначе код перестанет быть листом
Чем чаще буква в слове, тем короче должен быть её код
Не знаешь, как решать?
Потренируйся на дереве кода: расставляй коды по свободным местам и строй дерево по кодам.
По каналу передают сообщения из букв А, Б, В, Г, Д, Е, Ж, З. Каждой букве соответствует кодовое слово — строка из 0 и 1. Коды идут подряд без разделителей, поэтому приёмник должен однозначно понимать, где заканчивается код одной буквы и начинается код другой.
2. Условие Фано
Условие Фано: никакое кодовое слово не является началом (префиксом) другого. Если условие нарушено, расшифровка неоднозначна: при кодах 0 и 01 непонятно, является ли 01 «0» и «1» или сразу «01».
3. Дерево кода
Коды удобно изображать двоичным деревом: от корня отходят ребро «0» (влево) и «1» (вправо). Каждый код — путь от корня до листа. Условие Фано означает, что занятые коды не «висят» друг над другом.
4. Что ищем
Часть кодов задана. Нужно добавить коды для оставшихся букв так, чтобы условие Фано выполнялось для всех букв сразу, а суммарная длина добавленных кодов была минимальной.
5. Пример: кодирование по двоичному дереву
Дано. Четыре буквы с кодами:
А — 0
Б — 10
В — 110
Г — 111
Разбираем по дереву. От корня идут два ребра: 0 — влево, 1 — вправо. Код буквы — это путь от корня до её листа: А = 0, Б = 10, В = 110, Г = 111. Каждый код стоит в листе, выше него никаких кодов нет, поэтому ни один код не является началом другого — условие Фано выполнено.
А=0, Б=10, В=110, Г=111: каждый код — лист дерева, поэтому ни один не является началом другого.
Решение
открыто шагов: 8 из 8
1Шаг 1
Дано. Выпишем все буквы и известные коды (неизвестные оставим пустыми):
буква
А
Б
В
Г
Д
Е
Ж
З
код
11
10
010
011
Коды нужны для букв А, Б, В, Г.
2Шаг 2
Подход. Задача на условие Фано: ни один код не должен быть началом другого. Собираем занятые коды, отмечаем их листьями двоичного дерева (влево «0», вправо «1») и размещаем оставшиеся буквы только в свободных местах; затем суммируем длины новых кодов.
Ветка «1» занята целиком: коды 10 и 11 — оба листья, дальше места нет. В ветке «0» заняты только листья 010 (Ж) и 011 (З); ветка «00» свободна целиком. Внутри «00» осталось два уровня — ровно четыре свободных листа.
В ветке 00 свободны четыре листа (пунктир) — как раз под А, Б, В, Г.
заданный кодсвободная ветка
5Шаг 5
Оставшиеся 4 буквы (А, Б, В, Г) размещаются в свободной ветке 00. Минимальные коды: 0000, 0001, 0010, 0011.
Разместили А=0000, Б=0001, В=0010, Г=0011 (добавленные коды — фиолетовые).
заданный коддобавленный код
6Шаг 6
Суммарная длина: 4⋅4=16.
Итог: 4 новых кода по 4 бита → 4⋅4=16.
заданный коддобавленный код
7Шаг 7
Почему это минимум. Свободное место есть только внутри ветки 00, и туда нужно уложить четыре буквы. Если занять короткий узел — 00, 000 или 001, — он «закроет» все свои продолжения: например, код 000 запрещает коды 0000 и 0001, а код 00 запрещает всю ветку целиком. После такого выбора свободных листьев останется не больше трёх, и четвёртую букву кодировать будет нечем. Значит, все четыре кода обязаны стоять на 4-м уровне — это ровно 0000, 0001, 0010, 0011. Другого размещения четырёх букв нет, поэтому 16 — единственная и минимальная возможная сумма. Другие ветки занять нельзя: правая часть дерева занята кодами 10 и 11, а любая ветка 11… (в том числе 111) начинается с кода Д = 11 и нарушила бы условие Фано. А если уйти глубже? Можно увести буквы дальше от корня — например, взять коды 000, 0010, 00110, 00111. Условие Фано при этом выполняется, но коды длиннее: 3+4+5+5=17, а не 16. Чем глубже ветка, тем больше сумма, поэтому 16 — минимум.
Тот же принцип, но буквы уведены глубже: 3+4+5+5=17 бит (>16).
заданный кодболее длинный вариант
8Шаг 8
Почему нельзя подвесить буквы под Д или под любую другую существующую ветку, где уже есть буква? По длине такой вариант был бы даже равен нашему — те же 16 бит: коды 1100, 1101, 1110, 1111 имеют по 4 бита. Но так делать нельзя: код 11 уже занят буквой Д и обязан быть листом. Если продлить его до 1100…1111, то, встретив в сообщении «11», приёмник не поймёт, это уже буква Д или только начало нового кода. Доращивать заданный код запрещено — буква Д перестала бы быть листом.
Так нельзя: под кодом 11 появились продолжения, значит 11 больше не лист — строка «11» не читается однозначно как Д.
заданный коддобавленный коднельзя: код должен быть листом
Правильный ответ этого билета: 16
Проверка:4 буквы по 4 бита → 4⋅4=16. Совпадает с эталоном демоверсии.
Проверка
Типовые ошибки и проверка
Проверяют только «коды не равны», а нужно «ни один код не является началом другого».
Не следят, что новые коды не должны быть префиксами старых (и наоборот).
«Втискивают» буквы в слишком короткие ветки, где места не хватает.
Отвечают числом букв вместо суммарной длины кодов.
Проверка: выпишите все коды и убедитесь, что ни один не является началом другого; сложите длины новых кодов.
Режимы
Сейчас открыт режим обучения: теория, разбор и ответ видны. Скоро появится режим проверки —
только условие и поле ответа, без подсказок.
Умение применять условие Фано и строить коды минимальной суммарной длины: по известным кодам части букв подобрать коды для остальных так, чтобы расшифровка была однозначной.
Что такое условие Фано?
Это требование к кодам: никакое кодовое слово не является началом (префиксом) другого. Если его нарушить, приёмник не сможет однозначно разбить поток нулей и единиц на отдельные буквы.
Почему нельзя продолжить уже известный код?
Заданный код должен оставаться листом дерева. Если дописать к нему биты, встретив исходный код, приёмник не поймёт, это буква или начало более длинного кода. Поэтому новые буквы ставят только в свободные ветки.
Как найти минимальную суммарную длину кодов?
Свободные места — это листья двоичного дерева, которых хватает всем оставшимся буквам. Нужно занять самые короткие свободные листья: чем меньше сумма длин, тем лучше. Частые буквы кодируют коротко, редкие — длиннее.
Сколько баллов даёт задание 4?
Задание относится к базовому уровню сложности и даёт 1 первичный балл.