Задачі з теорії кодування
Задача 1.Методом Шеннона-Фано закодувати задані символи
Нехай задані початкові символи:
A (частота в тексті 50)
B (частота в тексті 39)
C (частота в тексті 18)
D (частота в тексті 49)
E (частота в тексті 35)
F (частота в тексті 24)
Кодове дерево:
Отриманий код: A - 11, B - 101, C - 100, D - 00, E - 011, F - 010.
Задача 2. Привести таблицю, що показує процес перебору наборів довжини 4 згідно з алгоритмом Грея
Стовпець it показує номер поточної ітерації, а стовпець kit — номер компонента, що підлягає відновленню.
|
X1 |
X2 |
X3 |
X4 |
It |
Kit |
|
0 |
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
0 |
1 |
2 |
2 |
|
0 |
0 |
1 |
1 |
3 |
1 |
|
0 |
0 |
1 |
0 |
4 |
3 |
|
0 |
1 |
1 |
0 |
5 |
1 |
|
0 |
1 |
1 |
1 |
6 |
2 |
|
0 |
1 |
0 |
1 |
7 |
1 |
|
0 |
1 |
0 |
0 |
8 |
4 |
|
1 |
1 |
0 |
0 |
9 |
1 |
|
1 |
1 |
0 |
1 |
10 |
2 |
|
1 |
1 |
1 |
1 |
11 |
1 |
|
1 |
1 |
1 |
0 |
12 |
3 |
|
1 |
0 |
1 |
0 |
13 |
1 |
|
1 |
0 |
1 |
1 |
14 |
2 |
|
1 |
0 |
0 |
1 |
15 |
1 |
|
1 |
0 |
0 |
0 |
16 |
- |
Задачі для самостійної роботи студентів
Задача 1: Скласти таблицю, що показує процес перебору наборів довжини 5 згідно з алгоритмом Грея, попередньо розробити програму.
Задача 2. Записати своє прізвище, ім’я, по батькові. Зжати рядок алгоритмом Шеннона – Фано.
Контрольні питання
В чому полягає робота архіватора?
В чому суть методів кодування Хаффамана та Шеннона-Фано?
В чому переваги коду Грея?
Список рекомендованої літератури
Дискретная математика для программистов / Ф.А. Новиков - Спб: Питер, 2001.
Виленкин Н.Я. Комбинаторика. - М.: Наука, 1969.
Холл М. Комбинаторика. - М.: Мир,1970.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Енергія, 1980.
Столл Р. Множества. Логика. Аксиоматические теории. - М.: Наука, 1968.
Яблонский С.В. Введение в дискретную математику. - М.: Наука, 1979.
Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975.
Липский В. Комбинаторика для программистов. - М.: Мир, 1988.
Кнут Д. Искусство программирования / т.1, 2, 3 /. - М.: Мир, 1976 - 1978.
Форд Л., Потоки в сетях - М.:Мир,1966
Цой С., Цхай С.М. Прикладная теория графов - Алма-Ата. 1971
Андерсон, Джеймс А. Дискретная математика и комбинаторика. - Пер. с англ. — М. : Издатель- Издательский дом "Вильямс", 2004. — 960 с.
Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие/ Б. Н. Иванов. — М.: Лаборатория Базовых Знаний, 2003. — 288 с: ил. - серия "Технический университет"
Плотников А.Д. Дискретная математика: учеб. пособие /А.Д. Плотников. — М.: Новое знание, 2005. — 288 с.
"Комп'ютерна дискретна математика": підручник\ М. Ф. Бондаренко Н. В. Білоус А. Г. Руткас. - Харків: "Компанія СМІТ, 2004. - 480 с.
Зміст
Лабораторна робота №1...........................................................................................................3
Лабораторна робота №2...........................................................................................................9
Лабораторна робота №3...........................................................................................................13
Лабораторна робота №4...........................................................................................................24
Лабораторна робота №5...........................................................................................................30
Лабораторна робота №6...........................................................................................................38
Лабораторна робота №7...........................................................................................................48
Лабораторна робота №8...........................................................................................................52
Список рекомендованої літератури........................................................................................55