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