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

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н — 1111, З — 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны.
Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

1. Определим частоты букв в слове КАЗАЧКА: буква А встречается 3 раза, К — 2 раза, З и Ч — по 1 разу.

2. Для минимизации длины сообщения более частым буквам назначаются более короткие кодовые слова при соблюдении условия Фано.
l(К)=1,l(А)=2,l(З)=3,l(Ч)=3

3. Суммарное количество двоичных знаков вычисляется с учётом числа вхождений каждой буквы.
L=2⋅1+3⋅2+1⋅3+1⋅3=14