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

По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, М, О, Т, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Ч — 00, М — 01, А — 11. Для трёх оставшихся букв К, О и Т кодовые слова неизвестны.
Какое количество двоичных знаков требуется для кодирования слова КОТОМКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

1. Кодовые слова 00, 01 и 11 занимают три ветви двоичного дерева. Чтобы условие Фано выполнялось, неизвестные слова могут располагаться только в ветви 10.

2. Для трёх кодовых слов в ветви 10 минимально возможные длины — 3, 4 и 4. Более короткое слово длины 3 выгоднее назначить букве, которая встречается чаще всего.

3. Буквы К и О встречаются в слове КОТОМКА по два раза, поэтому одной из них можно назначить длину 3, а другой — длину 4. Букве Т назначается длина 4. Для М и А длина кодового слова равна 2.

4. Суммарное количество двоичных знаков равно:
2⋅3+2⋅4+1⋅4+1⋅2+1⋅2=22