Автор работы: Пользователь скрыл имя, 21 Января 2011 в 21:37, контрольная работа
Измерение информации
Системы счисления
Представление информации в памяти ЭВМ
Кодирование сообщений
Проектирование конечного автомата
Решение:
Построим для
данного алфавита равномерный код
| 0
1 2 3 4 5 6 7 8 |
a
b c d e f g h i |
0000
0001 0010 0011 0100 0101 0110 0111 1000 |
№ 16. Построить
код Шеннона – Фано.
| Символ | Частота встречаемости |
| a
b c d e f g h i |
P(a)=7/31=0,225806
P(b)=6/31=0,193548 P(c)=4/31=0,120329 P(d)=3/31=0,096774 P(e)=2/31=0,064516 P(f)=3/31=0,096774 P(g)=3/31=0,096774 P(h)=2/31=0,064516 P(i)=1/31=0,032258 |
Сортируем последовательность
по убыванию вероятности появления
| Символ | Частота встречаемости | Разряды | Кодовая комбинация | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | |||
| a | 0,225806 | 0 | 0 | 00 | ||||
| b | 0,193548 | 0 | 1 | 01 | ||||
| c | 0,120329 | 1 | 0 | 0 | 100 | |||
| d | 0,096774 | 1 | 0 | 1 | 101 | |||
| f | 0,096774 | 1 | 1 | 0 | 110 | |||
| g | 0,096774 | 1 | 1 | 1 | 0 | 1110 | ||
| e | 0,064516 | 1 | 1 | 1 | 1 | 0 | 11110 | |
| h | 0,064516 | 1 | 1 | 1 | 1 | 1 | 0 | 111110 |
| i | 0,032258 | 1 | 1 | 1 | 1 | 1 | 1 | 111111 |
Разбиваем последовательность на 2 по возможности равновероятные группы
Точно
пополам поделить не возможно. Есть
два варианта разбиения:
a,b,c (0,544)/d,f,g,e,h,i(0,42) и a,b (0,42) / c,d,f,g,e,h,i (0,55).
Остановимся на втором варианте.
В идеальном случае отношение этих вероятностей должно быть равным единице. Для первого варианта разбиения отношение меньшей вероятности к большей равно 0,55/0,42 = 1,31. Для второго варианта разбиения это отношение равно 0,42/0,55= 0,76.
Первому разряду кода символов первой группы присваивается значение 0, первому разряду кода символов второй группы - 1.
Далее для каждой из 2х групп выполняем шаги 1)-3)
№ 17. Построить код Хаффмана.
Строим кодовое дерево
| 1 | ||||||||||||||||
| 0 | ||||||||||||||||
| 0,645 | 1 | 1 | ||||||||||||||
| 0,226 | ||||||||||||||||
| 0 | 0,355 | 1 | ||||||||||||||
| 0 | 1 | |||||||||||||||
| 0,419 | 0 | 0,194 | 0,161 | 0,097 | ||||||||||||
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |||||||||
| 0,226 | 0,194 | 0,129 | 0,097 | 0,097 | 0,097 | 0,065 | 0,065 | 0,032 | ||||||||
| a | b | c | d | f | g | e | h | i | ||||||||
| a
b c d e f g h i |
000
001 010 100 111 101 110 0110 0111 |
№ 18. Найти избыточность
равномерного кода и кода Хаффмана
№ 19. Закодировать
первые два символа сообщения
кодом Хаффмана и построить для
полученного двоичного
Проектирование
конечного автомата
№ 20. Для заданного конечного автомата построить:
Автомат: Телевизор
Машина Поста
№ 21. Решить данную
задачу с помощью эмулятора Машины
Поста. Решение предоставить в виде
файла Фамилия_номер_варианта.
Задача:
На ленте машины
Поста расположен массив из 2*N отмеченных
секций. Составить программу, по которой
машина Поста раздвинет на расстояние
в 1 секцию две половины данного массива.
Каретка находится над
крайней правой меткой
массива
Распознавание
образов
№ 22. Построить классы объектов для распознавания:
Объекты: легковые
автомобили
№ 23. Построить
граф перехода конечного автомата распознавателя
(распознающую грамматику) и синтаксическую
диаграмму (порождающую грамматику) для
алфавита и соответствующего ему языка
Алфавит и язык:
V ={a, b, c}; L = {сac, cbc, ca}
Информационное
моделирование
№ 24. Разработать
информационную модель объекта
Результаты предоставить
в виде компьютерной презентации.
Объект моделирования: Снегопад