Билет 1 — демоверсия ЕГЭ-2026; остальные билеты — задания в формате экзамена (открытый сборник или тренировочные по образцу). Это тренировочные материалы, а не официальные КИМ. Ответы пересчитаны и сверены.
По каналу связи передаются сообщения, содержащие буквы из набора: В, Е, О, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано (никакое кодовое слово не является началом другого) — это обеспечивает однозначную расшифровку.
Кодовые слова для некоторых букв известны: О — 1111, Р — 110. Для трёх оставшихся букв В, Е и Т кодовые слова неизвестны.
Вопрос. Какое количество двоичных знаков потребуется для кодирования слова ТЕТЕРЕВ, если известно, что оно закодировано минимально возможным количеством знаков?
Не знаешь, как решать?
Потренируйся на дереве кода: расставляй коды по свободным местам и строй дерево по кодам.
Дано. Выпишем все буквы и известные коды (неизвестные оставим пустыми):
буква
В
Е
О
Р
Т
код
1111
110
Коды нужны для букв В, Е, Т.
2Шаг 2
Подход. Снова условие Фано. Занятые коды занимают часть двоичного дерева; чтобы сократить слово, самые частые буквы слова нужно закодировать самыми короткими из свободных кодов, а редкие — более длинными.
3Шаг 3
В слове ТЕТЕРЕВ буквы встречаются так: Е — 3 раза, Т — 2 раза, Р — 1 раз, В — 1 раз (буква О не встречается).
4Шаг 4
Заданные коды занимают ветку «1»: Р = 110 (длина 3), О = 1111. Свободны короткие коды «0» и «10», а также длинный 1110 — они показаны пунктиром.
Минимально: Е = 0 (1 бит — самая частая буква), Т = 10 (2 бита), В = 1110 (4 бита). Р остаётся 110 (3 бита).
Назначили Е=0, Т=10, В=1110 (добавленные коды — фиолетовые).
заданный коддобавленный код
6Шаг 6
Сумма для слова: 3⋅1+2⋅2+1⋅3+1⋅4=14.
Итог слова ТЕТЕРЕВ: 3⋅1+2⋅2+1⋅3+1⋅4=14.
заданный коддобавленный код
7Шаг 7
Почему это минимум. Свободных «верхних» кодов ровно три: 0 (1 бит), 10 (2 бита) и 1110 (4 бита). Любой другой свободный код лежит внутри одной из этих веток и потому только длиннее (например, 000 вместо 0 — уже 3 бита). Букв без кода тоже три — В, Е, Т, — значит занять нужно именно эти три кода. Осталось распределить их по частоте: если поменять два кода местами, у более частой буквы код станет длиннее и сумма вырастет. Поэтому самый короткий код — самой частой букве: Е (3 раза) = 0, Т (2 раза) = 10, В (1 раз) = 1110. Буква Р всегда 3 бита (110), а О в слове ТЕТЕРЕВ не встречается. Если же уйти в более глубокую ветку — например, взять вместо 0 коды 000, 001, 010, — выйдет 3⋅3+2⋅3+1⋅3=18, плюс Р = 3, всего 21>14. Другой расклад даёт больше 14.
8Шаг 8
Почему нельзя дорастить заданный код. Новые буквы нельзя повесить и под уже известные коды Р = 110 или О = 1111. Если продлить такой код, он перестанет быть листом: встретив строку «110» (или «1111»), приёмник не поймёт, это буква Р (или О) или начало более длинного кода. Поэтому новые буквы ставятся только в свободные ветки 0, 10 и 1110.
Правильный ответ этого билета: 14
Проверка: минимальное кодирование даёт 3⋅1+2⋅2+1⋅3+1⋅4=14. Совпадает с опубликованным ответом источника.
Теория и другие билеты
Разбор с нуля, типовые ошибки, частые вопросы и все билеты задания 4 — на странице задания.