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

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

1. В слове КАРАВАН буква А встречается три раза, а буквы К, Р, В и Н — по одному разу. Поэтому наиболее короткое доступное кодовое слово выгодно назначить букве А.

2. С учётом условия Фано и известных кодов Р = 1 и К = 0000 можно, например, построить кодовые слова: А = 01, В = 001, Н = 00010, Д = 00011, К = 0000, Р = 1. Ни одно кодовое слово не является началом другого.

3. Длина кодирования слова КАРАВАН вычисляется по количеству вхождений букв: 3⋅l(А)+l(К)+l(Р)+l(В)+l(Н)=3⋅2+4+1+3+5=19.