ЕГЭ · ЗАДАНИЕ 4
Кодирование и условие Фано · №31212
Передаются буквы Д, Е, К, О, Т, Л. Известны коды Д = 00, Т = 11. Для Е, К, Л и О коды неизвестны. Найдите минимальную длину кодирования слова КОТЕЛОК.
| Символ | Кодовое слово |
|---|---|
| Д | 00 |
| Т | 11 |
| Е | ? |
| К | ? |
| Л | ? |
| О | ? |
Кодируемое слово: КОТЕЛОК
Напоминание: ни одно кодовое слово не должно быть началом другого кодового слова.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 20
1. Найдём частоты
В КОТЕЛОК буквы К и О встречаются по два раза, Т, Е и Л — по одному. На Т = 11 заранее приходится 2 бита.
2. Построим допустимый код
Ветви 00 и 11 заняты. Разделим каждую из свободных ветвей 01 и 10 на две:
| Буква | Код | Частота | Битов |
|---|---|---|---|
| К | 010 | 2 | 6 |
| О | 011 | 2 | 6 |
| Е | 100 | 1 | 3 |
| Л | 101 | 1 | 3 |
| Т | 11 | 1 | 2 |
| Д | 00 | 0 | 0 |
3. Докажем минимальность
Однобитовые коды невозможны: они стали бы началом Д или Т. Если неизвестным буквам не давать двухбитовый код, каждой нужно минимум 3 бита: 6 × 3 + 2 = 20.
Если одной частой букве отдать код длины 2, остальные три нужно разместить под другой свободной ветвью. Их минимальные длины — 3, 4 и 4. Даже при выгодном распределении получим 2 × 2 + 2 × 3 + 4 + 4 + 2 = 20. Обе двухбитовые ветви занять нельзя: ещё двум буквам не останется места.
Ответ: 20 бит. Не прибавляйте код Д: он должен быть в алфавите, но в слове этой буквы нет.
Самопроверка. Закройте разбор и повторите расчёт без подсказки.