6. Варианты заданий

1. Написать процедуры построения -, -кодов Элиаса для заданного натурального числа.

2. Запрограммировать процедуру кодирования и декодирования последовательности нулей и единиц методом кодирования длин серий.

3. Написать процедуру кодирования и декодирования последовательности символов заданным побуквенным префиксным кодом.

4. Запрограммировать процедуру, которая определяет является ли заданная схема побуквенного кодирования префиксной.

5. Для заданного набора длин кодовых слов написать процедуру построения побуквенного префиксного кода.

6. Написать процедуру кодирования текста на русском языке кодом Хаффмена. Определить степень сжатия этого кода.

7. Написать процедуру кодирования текста на русском языке кодом Фано. Определить степень сжатия этого кода. Сравнить средние длины кодовых слов кода Хаффмена и кода Фано.

8. Написать процедуру кодирования текста на русском языке кодом Шеннона. Определить степень сжатия этого кода. Сравнить средние длины кодовых слов кода Хаффмена и кода Шеннона.

9. Написать процедуру кодирования текста на русском языке кодом Гилберта-Мура. Определить степень сжатия этого кода. Сравнить средние длины кодовых слов кода Хаффмена и кода Гилберта-Мура.

10. Графически изобразить кодовое дерево заданного префиксного кода.

Рекомендуемая литература

1. Вирт Н. Алгоритмы и структуры данных. – М.: , 1989.

2. Кнут Д. Искусство программирования для ЭВМ, сортировка и поиск. – М.: Мир, 1978.

3. Ахо А., Ульман Дж., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. – М. Мир, 1979.

4. Марченко А.И., Марченко Л.А. Программирование в среде Turbo PASCAL 7.0. Базовый курс. Киев: «ВЕК+», 2003.

5. Березин Б.И., Березин С.Б. Начальный курс С и С++. М: «Диалог-МИФИ», 2001

Приложение А

Псевдокод для записи алгоритмов

Для записи алгоритма будем использовать специальный язык – псевдокод. Алгоритм на псевдокоде записывается на естественном языке с использованием двух конструкций: ветвления и повтора. В круглых скобках будем писать комментарии. В треугольных скобках будем описывать действия, алгоритм выполнения которых не требует детализации, например, <обнулить массив>.

: = Операция присваивания значений.

Операция обмена значениями.

Конструкции ветвления.

1. IF (условие) Если выполняется условие,

<действие> то выполнить действие

FI FI указывает на конец этих действий.

2. IF (условие)

<действия 1>

ELSE <действия 2> Действия 2 выполняются,

FI если неверно условие.

3. IF (условие1)

<действия1>

ELSEIF (условие2) Действия 2 выполняются,

<действия2> если неверно условие1 и верно условие 2

…FI

Конструкции повтора.

1. Цикл с предусловием.

DO (условие) Действия повторяются

<действия> пока условие истинно.

OD OD указывает на конец цикла.

2. Цикл с постусловием.

DO <действия>

OD (условие выполнения)

3. Цикл с параметром.

DO (i=1, 2, ... n) Действия выполняются для значений

<действия> параметра из списка

OD

4. Бесконечный цикл.

DO

<действия>

OD

5. Принудительный выход из цикла.

DO

...IF (условие) OD Если условие истинно, то выйти из цикла.

OD

Елена Викторовна Курапова

Елена Павловна Мачикина