По каналу связи передаются сообщения, содержащие только буквы алфавита: А, Б, В, Г, Д, Е, М, Т, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 01, В — 11. Для остальных букв А, Д, Е, М, Т, И, К кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова МАТЕМАТИКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков? Примечание: условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.

В слове МАТЕМАТИКА частоты букв такие: А — 3 раза, М — 2, Т — 2, Е — 1, И — 1, К — 1. Кодовые слова Б — 01 и В — 11 резервируют эти ветви, поэтому все шесть букв слова должны иметь коды под ветвями 00 и 10.

Для частот 3, 2, 2, 1, 1, 1 оптимальные длины двоичного префиксного кода без ограничений равны 2, 3, 3, 3, 4, 4. Но здесь каждая такая длина должна увеличиться как минимум на 1: коды могут занимать лишь половину двоичного дерева (ветви 00 и 10). Получаются длины 3, 4, 4, 4, 5, 5.

Минимальная общая длина: 3 × 3 + 2 × 4 + 2 × 4 + 1 × 4 + 1 × 5 + 1 × 5 = 37.

Ответ: 37 двоичных знаков.