Условие
Четыре сообщения имеют вероятности 1/2,1/8,1/8,1/4. Постройте двоичный префиксный код и найдите энтропию и среднюю длину.
Решение по шагам
Объединим два наименьших веса 1/8+1/8=1/4, затем получившийся 1/4 с исходным 1/4 в 1/2, затем два веса 1/2 в корень. Код для сообщений в указанном порядке можно выбрать 0,110,111,10.
Ни одно кодовое слово не является началом другого. Длины 1,3,3,2 дают EL=(1/2)·1+(1/8)·3+(1/8)·3+(1/4)·2=7/4 бита. Энтропия H=−Σp log₂p также 7/4: все вероятности имеют вид 2⁻ˡ, поэтому нижняя граница достигнута.
Проверка результата
Сумма Крафта 1/2+1/8+1/8+1/4=1. Код однозначно читается, например 011010 разбивается на 0|110|10.
Типичная ошибка
Назначить четыре слова одинаковой длины 2: это допустимо, но средняя длина 2 хуже оптимальной 1,75.
Что даёт этот метод
Частые сообщения кодируются короче; алгоритм Хаффмана оптимизирует среднюю длину.
Дальше по теме
Университетские задачи по вероятности.
Следующие разборы
- МГУ, вероятность: два мешка и три шара без возвращения
- МГУ: полный разбор итогового варианта по вероятности, 2025
Условие адаптировано из открытого источника: Борис Демешев, msu_probability_spring_2025, HA5Q3. Решение, объяснение и проверка изложены редакцией damirock.com; это не официальный ключ преподавателя. CC0 1.0. Вёрстка и обозначения адаптированы; числовые предпосылки указаны в условии.