Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

Задачи и дополнения

1. Доказать, что всякий оптимальный код является

2. Закодировать двоичным кодом Хаффмена множество сообщений, имеющих вероятности:

p1 = 0,25; p2 = 0,2; p3 = p4 = p5 = 0,15; p6 = 0,1.

Построить соответствующее кодовое дерево.

3. Основываясь на алгоритме Хаффмена, найти способ непосредственного построения кодового дерева оптимального кода.

Указание. Построение дерева надо начинать не с корня, а с концевых вершин.

4. В некоторых случаях результаты двоичного кодирования по методу Фано те же, что и по методу Хаффмена, в том смысле, что длины соответствующих кодовых слов для обоих методов совпадают. Так, например, обстоит дело для множества сообщений с вероятностями:

p1 = 1/4; р2 = p3 = р4 = р5 = 1/8; p6 = p7 = p8 = p9 = 1/16.

На самом деле справедливо следующее утверждение: если pi = 2-ni (т. е. если вероятности являются степенями двойки), то длины соответствующих кодовых слов в кодах Фано и Хаффмена одинаковы и равны ni.

5. Не всегда полный код является оптимальным для данного множества сообщений, Можно доказать, однако, что всякий полный код является оптимальным для некоторого множества сообщений с подходящим образом подобранными вероятностями. Так, если кодовые слова полного кода с основанием d имеют длины n1, n2, ..., nN, то он оптимален для множества сообщений с вероятностями d-n1, d-n2, ..., d-nN.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru