МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

РЫБИНСКАЯ ГОСУДАРСТВЕННАЯ АВИАЦИОННАЯ

ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ ИМЕНИ П. А. СОЛОВЬЕВА

КАФЕДРА МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ЭЛЕКТРОННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДСТВ

В.Н.Пинаев лабораторный практикум по курсу "структуры и алгоритмы обработки данных в эвм"

части I–II

РЫБИНСК

2002 

ББК 32. 973–01

П–32

УДК 681.3

Пинаев В.Н. Лабораторный практикум по курсу "Структуры и алгоритмы обработки данных"/РГАТА. Рыбинск, 2002 г. – 23 с.

Лабораторный практикум содержит описание четырех лабораторных работ по курсу "Структуры и алгоритмы обработки данных в ЭВМ". Каждая работа снабжена теоретическим материалом, разобранными примерами и контрольными вопросами. Некоторые примеры иллюстрируются фрагментами описаний структур и алгоритмов на языке ПАСКАЛЬ.

Практикум предназначен для студентов направления 552800 Информатика и вычислительная техника и специальности 220400 Программное обеспечение вычислительных вычислительной техники и автоматизированных систем.

© Пинаев В.Н., 2002

© Рыбинская государственная авиационная технологическая академия им. П. А. Соловьева, 2002

Лабораторная работа №1 мера информации

Начальные определения

В толковом словаре по вычислительным системам¹ приводится следующее определение:

“Энтропия (entropy) – мера количества информации, вырабатываемой источником, попадающей к получателю в пересчете на символ (секунду и т.п.). Понятие энтропии в теории информации введено К.Э. Шенноном в 1948 году и позднее развито другими исследователями. … Энтропия (в зависимости от выбранного основания логарифма, используемого в основной формуле) измеряется в битах, натах или Хартли. Термин «энтропия» взят по аналогии с энтропией в термодинамике, где она определяется выражением, имеющим ту же форму (с точностью до множителя) и знака”.

Мы интерпретируем информацию как неопределенность, которую необходимо устранить, чтобы получить эту информацию.

Формула Шеннона имеет вид:

.

В частном случае при p₁=p₂=…=p_n=1/n формула Шеннона носит название формулы Хартли и имеет вид:

.

Здесь n – количество состояний системы, p_i – вероятность перехрда системы в i-oe состояние.

Задание к лабораторной работе

1. Изучить теоретическую часть.

2. Составить программу, которая по заданному текстовому файлу определяет меру информативности в пересчете на один символ. Имя входного файла вводится с клавиатуры. Сформировать таблицу, в которой указать все встречающиеся символы, их коды, частоту встречаемости в абсолютном и относительном выражении. Таблицу и результирующий ответ вывести на экран и в выходной файл. Дополнительно программа должна выводить сведения об авторе работы².

Контрольные вопросы и задания

1. Как сформировать тестовый входной файл, чтобы итоговый результат был равен некоторому наперед заданному целому положительному числу? Какое максимальное значение может иметь мера информативности на один символ входного текста?

2. Каким типом целесообразно задавать диапазон индексов массива, где хранятся частоты встречаемых символов?

Лабораторная работа №2 коды хаффмана

Мера информативности (энтропия) была определена в лабораторной работе №1. На основе этого определения можно сформулировать алгоритм, позволяющий построить так называемый код Хаффмана.

Рассмотрим построение кода Хаффмана на примере.

Пусть имеется текст «Во поле береза стояла»³. Составим таблицу частот символов этого текста.

Символ, Si

В

п

о

л

е

б

р

з

а

с

т

я

Частота, Ci

1

1

3

2

3

3

1

1

1

2

1

1

1

Pi=Ci/n

1/21

1/21

3/21

2/21

3/21

3/21

1/21

1/21

1/21

2/21

1/21

1/21

1/21

Pi*Log2Pi

H=3,522572

n=	21
1	1	3	2	3	3	1	1	1	2	1	1	1
0,047619	0,047619	0,142857	0,095238	0,142857	0,142857	0,047619	0,047619	0,047619	0,095238	0,047619	0,047619	0,047619
-4,39232	-4,39232	-2,80735	-3,39232	-2,80735	-2,80735	-4,39232	-4,39232	-4,39232	-3,39232	-4,39232	-4,39232	-4,39232
-0,20916	-0,20916	-0,40105	-0,32308	-0,40105	-0,40105	-0,20916	-0,20916	-0,20916	-0,32308	-0,20916	-0,20916	-0,20916	3,522572
													73,974