По каналу связи передаются сообщения, содержащие только заглавные буквы русского алфавита. Для передачи используется двоичный код, допускающий однозначное декодирование. Укажите минимальную возможную длину закодированной последовательности АТТЕСТАТ

Минимальная длина закодированной последовательности слова АТТЕСТАТ в двоичном коде с уникальным декодированием равна 14 бит. Как это получилось (пошагово): - Подсчитываем частоты букв в слове АТТЕСТАТ: А встречается 2 раза, Т — 4 раза, Е — 1 раз, С — 1 раз. Путиков веса: w(Т)=4, w(А)=2, w(Е)=1, w(С)=1. - Чтобы минимизировать суммарную длину кодирования L = 4·lТ + 2·lА + 1·lЕ + 1·lС при условии уникодируемого двоичного кода, применяем алгоритм Хаффмана. Шаги Хаффмана: объединяем две наименьшие частоты 1 и 1 -> вес 2; затем 2 и 2 -> вес 4; затем 4 и 4 -> вес 8. В итоге получаем кодовые длины: lТ = 1, lА = 2, lЕ = 3, lС = 3. - Вычисляем общую длину: L = 4*1 + 2*2 + 1*3 + 1*3 = 4 + 4 + 3 + 3 = 14 бит. - Пример допустимого кодирования: Т=0, А=10, Е=110, С=111. Тогда АТТЕСТАТ кодируется как 10 0 0 110 111 0 10 0, что даёт 14 бит. Почему это минимально: - Для двоичного UD-кода частоты букв должны удовлетворять ограничению Крафта: сумма 2^{-l_i} ≤ 1. Для данного распределения частот любые сокращения длин для Е и С ниже 3 бит нарушили бы это неравенство; увеличение длин для других букв только увеличит общую длину. Код Хаффмана даёт оптимальные целевые длины для заданных весов, следовательно 14 бит — минимально возможное значение. Ответ: 14 бит.