Алфавитное и равномерное кодирование.

ДИСКРЕТНАЯ МАТЕМАТИКА

 

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 

к лабораторным и самостоятельной работам

 

 

для студентов специальности

«Системы и методы принятия решений»

дневной формы обучения

 

 

Утверждено на заседании кафедры ИСПР Протокол № 1 от 31.08.2011г.

 

 

 

 

 

Краматорск 2011

 

 

Лабораторная работа №1

 

Алфавитное и равномерное кодирование.

(Алгоритмы Фано и Хаффмана).

Цель работы: изучить алгоритмы кодирования информации посредством методов Фано и Хаффмена.

 

Задание.

1. Для заданных распределений вероятностей появления букв построить заданный код и рассчитать среднюю длину кодирования.

№ варианта	Раcпределение вероятностей	Метод кодирования
	Р={0,1;0,6;0,09;0,08;0,07;0,06}	Метод Фано
	Р={0,5;0,3;0,1;0,03;0,02;0,01;0,04}	Метод Хаффмена
	Р={0,2;0,2;0,19;0,12;0,11;0,09;0,09}	Метод Хаффмена
	Р={0,4;0,4;0,1;0,03;0,03;0,02;0,02}	Метод Фано
	Р={0,4;0,18;0,1;0,1;0,07;0,06;0,05;0,04}	Метод Хаффмена
	Р={0,2;0,3;0,2;0,1;0,1;0,05;0,05}	Метод Фано
	Р={0,2;0,2;0,19;0,12;0,11;0,09;0,09}	Метод Фано
	Р={0,25;0,2;0,15;0,15;0,15;0,1}	Метод Хаффмена
	Р={0,4;0,18;0,1;0,1;0,07;0,06;0,05;0,04}	Метод Фано
	Р={0,6;0,1;0,06;0,08;0,07;0,09}	Метод Хаффмена
	Р={0,2;0,25;0,35;0,05;0,15}	Метод Фано
	Р={0,2;0,3;0,2;0,1;0,1;0,05;0,05}	Метод Хаффмена
	Р={0,35;0,14;0,19;0,17;0,15}	Метод Фано
	Р={0,22;0,17;0,21;0,05;0,2;0,15}	Метод Фано
	Р={0,02;0,35;0,31;0,13;0,19}	Метод Хаффмена
	Р={0,16;0,23;0,11;0,28;0,22}	Метод Хаффмена
	Р={0,38;0,08;0,27;0,18;0,09}	Метод Фано
	Р={0,14;0,36;0,19;0,24;0,07}	Метод Хаффмена
	Р={0,41;0,16;0,07;0,3;0,06}	Метод Фано
	Р={0,26;0,12;0,06;0,19;0,08;0,15;0,14}	Метод Хаффмена

 

2. Написать программу, которая осуществляет кодирование Вашей фамилии, имени и отчества методом Фано или Хаффмена в зависимости от варианта.

 

Лабораторная работа №2

Самокорректирующиеся коды. Коды Хемминга.

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

Задание.

Обнаружить и исправить ошибку в представленном коде, декодировать сообщение.

Вариант	Закодированное сообщение
	1 1 1 0 1 0- 0 1 0 1 0 0 0 0 0-0 1 0 0 1 1 1-1 1 0 1 0 1 1 1 1- 0 0 0 0 0 1
	1 0 1 0 0 1 1-0 0 0 1 1 1 0-1 1 1 0 1 0-1 0 0 0 0 0 1-1 1 0 0 1 0 0 0 0-1 1 0 0 1 1 0 0 1- -0 1 0 1 1 0 0 0 1 0-1 1 0 1 0 1 1 1 1-0 0 1 0 0 0
	1 1 1 1 1 1 1 0 1-1 0 0 0 1 0 1-0 1 0 0 1 0 0 1 1-1 1 1 0 0 1 1 1 1 1-0 0 1 0 0 0 0 1 1 0 1 1 1 0 0-1 1 1 0 0 1-0 1 1 0 1 0 1-0 0 0 0 0 1
	0 1 0 0 0 1 0 1 1-0 1 1 0 0 1 1 0 1-0 1 0 1 1 1 1 1 1-1 0 1 0 0 0 1 0 1 1-0 0 1 0 0 1 0 1 1 1 0 1 0-0 0 0 0 0 1-0 1 1 1 0 1 0 0 0-0 0 0 0 1 0-1 0 1 1 0 1 1-0 1 1 0 1 1 0 1 1- 1 1 1 0 0 1-1 0 1 0 0 1 1-0 0 1 0 0 0
	1 0 1 1 1 1 0-1 0 1 0 1 0 0-0 0 1 0 1 1 1-1 0 1 1 0 0 0-1 0 1 1 1 0 0 0 0-1 1 0 0 0 0- 0 0 0 1 1 1 0-1 1 1 0 0 1-0 1 0 1 0 1 1 0 0 -1 0 0 0 1 1 1-1 0 0 1 1 0 1 0 0-0 0 0 0 1 0
	0 1 0 1 0 1 0 0 1-0 0 0 1 0 1 1-0 0 1 0 1 1 1-0 0 1 0 0 0-1 0 0 0 0 0 1-0 0 0 0 1 0
	1 0 0 1 0 1 0-0 1 0 0 0 0 1-0 1 1 1 1 0 0 0 0 1-0 1 0 0 1 1 1-1 0 1 0 0 1 1 0 0 1- 0 0 1 0 1 1 1-1 1 1 0 1 0-0 0 0 0 0 1
	1 0 1 1 0 1 1-1 0 1 0 1 1 1-0 1 1 0 1 0 1-1 1 0 1 0 1 0 1 0-1 1 1 0 0 1-1 0 0 0 1 1 1- 0 0 0 0 0 1
	0 0 1 1 1 1 0 1 0 1-0 0 0 1 1 0 0 1 0 0-0 0 1 1 1 1 1-1 1 1 0 1 0-0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1-0 1 0 0 1 1 1-0 1 0 1 0 1 0 0 1-0 0 0 0 1 0
	1 0 0 1 0 1 0-1 0 1 0 0 0 1-1 0 0 0 0 0 1-1 1 1 1 1 0 0 1 1 1-1 0 1 0 0 1 1- 0 0 0 1 0 1 1-0 0 1 1 1 0 0 1 1 1-1 0 0 1 0 0 0 0 0-1 1 1 0 0 1-0 0 0 1 1 0 1 1 1 0- 0 0 1 0 0 0
	0 1 1 0 1 0 1-1 0 1 1 0 0 0-0 1 1 1 1 1 0 1 1-0 0 0 1 1 1 0-0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1-0 0 1 1 1 1 1-1 0 0 1 1 1 0 0 0-0 0 1 0 0 0
	0 1 1 0 1 1 1 0 0-0 0 1 0 0 0-1 1 1 1 0 1 1 0 0-1 0 1 0 1 1 1-0 1 0 0 0 1 0 1 1- 0 1 1 1 1 0 0 1 1 1 0-0 0 1 1 1 0 0 1 1 0-1 0 0 1 1 0 1 0 0-0 1 1 1 1 1 0 0 0 0- 0 0 0 0 0 1
	1 1 0 0 0 0-0 1 1 0 1 0 1-1 1 1 0 1 0-0 0 0 0 1 0
	1 0 0 0 0 1 0-0 0 0 1 1 1 0-1 1 1 0 1 0-1 0 0 0 0 0 1-1 1 0 0 1 0 0 0 0-1 1 0 0 1 1 0 0 1- -0 1 0 1 1 0 0 0 1 0-1 1 0 1 0 1 1 1 1-0 0 1 0 0 0
	1 1 1 1 1 1 1 0 1-1 0 0 0 1 0 1-0 1 0 0 1 0 0 1 1-1 1 1 0 0 1 1 1 1 1-0 0 1 0 0 0- 1 1 1 0 1 0- 0 1 0 1 0 0 0 0 0-0 1 0 0 1 1 1-1 1 0 1 0 1 1 1 1- 0 0 0 0 0 1
	0 1 1 0 0 0 1 0 0-1 1 1 0 0 1-0 1 0 0 1 1 1-0 0 0 0 0 1-1 1 1 1 1 0 1 1 1 0-0 0 1 0 1 0 0
	0 0 0 1 1 1 0-1 1 1 0 1 0-0 0 1 0 1 1 1-1 1 0 0 1 1 1 0 0-0 0 0 0 1 0
	1 0 1 0 0 1 1-0 0 1 0 0 0-1 0 1 1 0 1 1-1 0 1 0 1 0 0-1 0 0 1 1 0 0 0 1-0 1 1 1 1 0 1 0 0 0- 0 0 0 0 1 0

Краткие теоретические сведения.

Каждое слово сообщения A при равномерном кодировании допускает разложение вида A =A_i1,A_i2 ,A_i3,…A_in, и имеет единственное такое разложение. Если ограничиться бинарным кодированием, то A_i = a₁ a₂ a₃…..a_m номера слов в словаре, записанные в двоичной системе (a_i принимает значения 0 или1). Необходимо отметить, что каждый двоичный номер слова может быть однозначно записан и десятеричным числом.

Пусть S”(I) – подмножество всех слов, допускающих разложение указанного вида. Рассмотрим следующую схему кодирования:

A₁® B₁

A₂® B₂

A₃® B₃ (2.1)

….

A_s® B_s,

где B_i = b₁ b₂ b₃ …b_l – элементарные двоичные коды, имеющие одинаковую длину l = m + k, при этом такие, чтобы по коду, полученному на выходе канала связи (помеха может изменить 0 на 1 или наоборот, но не может добавить или убрать элемент b_i) однозначно восстановить код на входе канала и из него получить исходное сообщение.

 

Построение самокорректирующихся кодов было осуществлено Хеммингом. Рассмотрим случай, когда источник помех может внести не более одного инвертирования в элементарный код B_i (р =1). Вариантов получения элементарного кода B_i будет l +1 (правильный и l штук с инвертированием b_i на каждой позиции). Для того, чтобы дополнительных разрядов в коде B_i хватило для кодирования l +1 случаев, необходимо выполнение следующего условия:

2 ^m ≤ 2 ^l / (l + 1) (2.2)

Из этих соображений выбираем l как наименьшее целое число, удовлетворяющее неравенству (2).

Дальнейшее построение будет состоять из трех этапов:

1. Построение кодов Хемминга (описание алгоритма кодирования).

2. Обнаружение ошибок в кодах Хемминга.

3. Декодирование.

 

Построение кодов Хемминга (описание алгоритма кодирования)

В множестве натуральных чисел {1,2,3,…, l }выделим следующие подмножества:

1, 3, 5, 7, 9 ….(содержатся все числа, у которых при переводе в двоичную запись в последнем разряде 1);

2, 3, 6, 7, 10 ….(содержатся все числа, у которых при переводе в двоичную запись в предпоследнем разряде 1);

..........

2^k–1, 2^k–1 +1, ….(содержатся все числа, у которых при переводе в двоичную запись в k –ом, считая справа, разряде 1).

Наименьшие члены этих подмножеств являются степенями 2: 1 = 2⁰; 2 = 2¹;

4 = 2²;…., причем 2^k–1 ≤ l, а 2^k+1 ³ l +1.

Члены b_i набора b₁ b₂ b₃ …b_l, у которых индекс i принадлежит множеству {1, 2, 4,… 2^k–1}, называются контрольными членами, остальные – информационными. Таким образом, контрольных членов будет k, а информационных l – k = m. Сформулируем правило построения набора …b_l по набору a₁ a₂ a₃…..a_m.

Сначала определяются информационные члены:

b₃ = a₁

b₅ = a₂

b₆ = a₃

.....

Таким образом, набор информационных членов, расположенных в естественном порядке, совпадает с набором a₁ a₂ a₃…..a_m. Затем определяются контрольные члены,

b₁ = b₃+ b₅ + b₇ + … (mod 2),

b₂ = b₃+ b₆ + b₇ + … (mod 2), (2.3)

b₄= b₃+ b₆ + b₇ + … (mod 2),

.............

 

значения которых 0 или 1 и помещаются на соответствующих местах в элементарных кодах B_i. По сути, создается кодовый словарь для схемы кодирования (1), в котором для каждого элементарного кода выполняются следующие условия (суммирование по mod 2):

b₁ + b₃+ b₅ + b₇ +…= 0,

b₂ + b₃+ b₆ + b₇ + … = 0, (2.4)

b₄ + b₃+ b₆ + b₇ + … = 0,

.............

(количество единиц в позициях элементарного кода, определяемых индексами, четно).

 

Обнаружение ошибок в кодах Хемминга

Ошибка на выходе из канала связи может быть обнаружена и исправлена так (для построенного кода – не больше одной в каждом элементарном коде). Номер позиции S (записанный в двоичной системе), в которой произошла ошибка, определяется так:

S = S_k… S₂ S₁ ,

где S_i определяется по формулам (4) для элементарного кода, полученного на выходе канала связи. Если ошибки нет, то S_i = 0 и общий результат S = 0.

 

Пример 1: Пусть на вход канала связи поступил элементарный код 0110011 (т.е закодировано **1*011 (поз. 3,5,6,7– информационные, а контрольные члены заменены *)). На выходе получено 0110001 (искажен 6–й член элементарного кода). Вычислим S.

S₁ = b₁ + b₃+ b₅ + b₇ = 0 + 1 + 0 + 1 = 0 (mod 2),

S₂ = b₂ + b₃+ b₆ + b₇ = 1 + 1 + 0 + 1 = 1 (mod 2),

S₃ = b₄ + b₅ + b₆ + b₇ = 0 + 0 + 0 + 1 = 1 (mod 2).

S = 1 1 0 = 6 (в десятичной системе).

Пример 2: Пусть на выходе получено 0111011 (искажен 4–й (контрольный) член элементарного кода).

S₁ = b₁ + b₃+ b₅ + b₇ = 0 + 1 + 0 + 1 = 0 (mod 2),

S₂ = b₂ + b₃+ b₆ + b₇ = 1 + 1 + 1 + 1 = 0 (mod 2),

S₃ = b₄+ b₅ + b₆ + b₇ = 1 + 0 + 1 + 1 = 1 (mod 2).

S = S₃ S₂ S₁= 1 0 0 = 4 (в десятичной системе).

Тогда восстановленное сообщение имеет вид: 0110011, а исходное сообщение – 1011 (удалены контрольные члены, выделенные цветом)

Декодирование

После получения закодированного сообщения происходит его разбивка на элементарные коды, вычисление для каждого кода S и в случае его неравенства 0 – корректировка соответствующего информационного члена (если S указывает на контрольный член, то корректировка не нужна). После удаления всех контрольных членов получаем исходное сообщение.

 

Примечание: Рассмотрено построение кодов Хемминга для бинарного кодирования и допустимом числе ошибок в элементарных кодах не более одной. Существует теория для построения таких кодов для равномерного кодирования любой арности и числе ошибок не более 2, 3,… и. д.

Лабораторная работа №3

Формальные грамматики и языки|речь|.

(Цепочки. Классификация грамматик по Хомскому).

 

Цель работы: закрепить понятия « алфавит», «цепочка», «формальная грамматика» и «формальный язык», «выводимость цепочек», «эквивалентная грамматика»;сформировать умения и навыки распознавания типов формальных языков и грамматик по классификации Хомского, построения эквивалентных грамматик.

 

Задание.

1.Определить к какому типу по Хомскому относится данная грамматика, какой язык она порождает, каков тип языка.

2.Указать максимально возможный номер типа грамматики и языка.

 

Вариант	Задание

 

Тип 0

Любая порождающая грамматика является грамматикой типа 0. На вид правил грамматик этого типа не накладывается никаких дополнительных ограничений. Класс языков типа 0 совпадает с классом рекурсивно перечислимых языков.

Тип 1

Грамматика G = 〈 T, N, P, S 〉 называется неукорачивающей, если правая часть каждого правила из P не короче левой части (т. е. для любого правила α → β P выполняется неравенство | α | ≤ | β |). В виде исключения в неукорачивающей грамматике допускается наличие правила S → l, при условии, что S (начальный символ, аксиома) не встречается в правых частях

правил. Грамматикой типа 1 будем называть неукорачивающую грамматику. Тип 1 в некоторых источниках определяют с помощью так называемых контекстно-зависимых грамматик.

Грамматика G = 〈 T, N, P, S 〉 называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид α → β, где α = ξ₁ A ξ₂, β = ξ₁γξ₂, A N, γ (T N)⁺, ξ₁, ξ₂ (T N)^*.

В виде исключения в КЗ-грамматике допускается наличие правила с пустой правой частью S → l, при условии, что S (начальный символ) не встречается в правых частях правил. Цепочку ξ₁ называют левым контекстом, цепочку ξ₂ называют правым контекстом. Язык, порождаемый контекстно-зависимой грамматикой, называется контекстно-

зависимым языком.

Тип 2

Грамматика G = 〈 T, N, P, S 〉 называется контекстно-свободной (КС), если каждое правило из Р имеет вид A → β, где A N, β (T N)^*. Заметим, что в КС-грамматиках допускаются правила с пустыми правыми частями. Язык, порождаемый контекстно-свободной грамматикой, называется контекстно-свободным языком.

Грамматикой типа 2 будем называть контекстно-свободную грамматику. КС-грамматика может являться неукорачивающей, т.е. удовлетворять ограничениям неукорачивающей грамматики.

Тип 3

Грамматика G = 〈 T, N, P, S 〉 называется праволинейной, если каждое правило из Р имеет вид A → wB либо A → w, где A, B N, w T *.

Грамматика G = 〈 T, N, P, S 〉 называется леволинейной, если каждое правило из Р имеет вид A → Bw либо A → w, где A, B N, w T *.

Леволинейные и праволинейные грамматики определяют один и тот же класс языков. Такие языки называются регулярными. Право- и леволинейные грамматики также будем называть регулярными.

Регулярная грамматика является грамматикой типа 3.

Автоматной грамматикой называется праволинейная (леволинейная) грамматика, такая, что каждое правило с непустой правой частью имеет вид: A → a либо A → aB (для леволинейной, соответственно, A → a либо A → Ba), где A, B N, a T. 4)

 

Лабораторная работа №4

Построение разных|различных| типов конечных автоматов

(Детерминированные и недетерминированные конечные автоматы).

 

Цель работы: изучить основные понятия конечных автоматов, научиться преобразовывать недетерминированный конечный автомат в эквивалентный ему детерминированный конечный автомат.

 

Задание

По недетерминированному конечному автомату, диаграмма которого представлена в индивидуальном задании, построить детерминированный конечный автомат, распознающий тот же язык.

В ходе выполнения задания должны быть выполнены и описаны следующие подзадачи:

 

1. Записать параметры заданного НКА в виде:

К *={ Q, A, q ₀, g*, F }, (4.1)

 

где А ={ а ₁, а ₂,..., а_n } – входной алфавит;

Q ={ q ₀, q ₁, q ₂,..., q_m } – множество состояний автомата;

q ₀ – начальное состояние автомата, q ₀Î Q;

g* – функция переходов недетерминированного конечного автомата, является отображением типа Q x А ®[2 ^Q \Æ]. Напомним, что для любого множества М через 2 ^М обозначается множество всех подмножеств из М; символ Æ обозначает пустое множество. Совокупность g *(q_i,а_j) – это всегда непустое подмножество состояний автомата, в любое из которых он может перейти из состояния q_i под воздействием буквы а_j, здесь q_i Î Q, а_j Î А.

F –множество допускающих состояний, F Í Q.

 

2. Построить таблицу переходов для заданного НКА

3. Преобразовать НКА в КА.

4.Проверить состояния полученного КА на достижимость и эквивалентность

5. Записать параметры заданного КА в виде:

К ={ Q, A, q ₀, g, F }, (4.2)

 

где А ={ а ₁, а ₂,..., а_n } – входной алфавит;

Q ={ q ₀, q ₁, q ₂,..., q_m } – множество состояний автомата;

q ₀ – начальное состояние автомата, q ₀Î Q;

g – функция переходов конечного автомата, представляющая собой отображение типа Q x А ® Q (если g (q_i,а_j)= q_k, то автомат из состояния q_i под воздействием буквы а_j должен перейти в состояние q_k);

F – множество допускающих состояний, F Í Q.

 

6. Построить диаграмму состояний полученного КА.

7. Проверить, допускает ли полученный КА цепочки, которые были допущены НКА.

8. Составить программу, реализующую работу полученного КА.

Индивидуальные задания

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

Вариант 16

Вариант 17

Вариант 18

Вариант 19

Вариант 20

 

Лабораторная работа №5

Задание

Разработать программное средство, реализующее следующие функции:

а) ввод произвольной формальной грамматики и проверка ее на принадлежность к классу КС-грамматик;

б) построение МП-автомата по КС-грамматике;

Продемонстрировать разбор некоторой входной строки с помощью по-

строенного автомата для случаев:

а) входная строка принадлежит языку исходной КС-грамматики и допускается МП-автоматом;

б) входная строка не принадлежит языку исходной КС-грамматики и не

принимается МП-автоматом.

Индивидуальные варианты заданий представлены в таблице 5.1.

 

Таблица 5.1 - Варианты заданий для лабораторной работы №5

Вариант	Задание
	G=({S, A, B, D, E}, {a, b, c, e}, P, S), где P: 1) S→AB | l; 2) A→Aa | S | a; 3) B→bD | bS | b; 4) D→ccD; 5) E→eE |e.
	G=({E, T, F, G, H}, {+, -, *, /, n, m, h}, P, E), где P:1) E→T | E+T | E-T | l; 2) T→F | F*T | F/T | l; 3) F→G | Fn | n;4) G→Gm; 5) H→Hh | h.
	G=({E, T, F, G, H}, {+, -, *, /, n, m, h}, P, E), где P:1) E→T | E+T | E-T | l; 2) T→F | F*T | F/T | l; 3) F→G | Fn | n; 4) G→Gm; 5) H→Hh | h.
	G=({R, T, F, G, K}, {m, i, j, k, ^, ~, ⊥}, P, R), где P:1) R→R~T⊥ | R^T⊥ | l; 2) T→F | Fi | Fj | Gk | l; 3) G→GkG; 4) K→Ki | Km | m.
	G=({S, X, Y, Z, K}, {x, y, z, k, #, $}, P, S), где P: 1) S→X | Y | Z; 2) X→x#X | x#Y | l; 3) Y→Yy$ |Yz$ | $ | l; 4) Z→Zz$;5) K→Kk$ | k$.
	G=({S, L, M, P, N}, {n, m, l, p, @, ⊥}, V, S), где V: 1) S→@nL | @mM | P; 2) L→M | Ll⊥ | Lm⊥ | l; 3) M→L | Mm | mm; 4) N→pN@ | @; 5) P→nmP.
	G=({X, Y, Z, K, L}, {a, b, l, =, <, >, ∧, ∨, }, V, X), где V:1) X→Y | Y=Y | Y<Y | Y>Y | K; 2) Y→Y∧Z | Y∨ Z | l; 3) Z→ a | b| l;4) K→ K; 5) L→ l | a | b.
	G=({Q, A, B, C, D}, {0, 1, -}, P, Q), где P: 1) Q→01A | 01B | A; 2) A→ 0B1 | B | 1 | l; 3) B→BA0 | B1 | C | l; 4) C→0C11; 5) D→ - D1 | -0 | -1.
	G=({R, T, U, W, V}, {0, 1, +, -, *, /}, P, R), где P: 1) R→T1T | T1U | W | l; 2) T→U | T01 | T10 | l; 3) U→+U | +0 | +1 4) W→W-W | W+W; 5) V→*0 | /1.
	G=({S, R, T, F, E}, {a, b, k, {, [, }, ], ⊥}, P, S), где P: 1) S→{R | [ R; 2) R→Ra} | Ra] | a | T | F | l; 3) F→{F} | bb; 4) T→[T]; 5) E→k⊥.
	G=({Y, K, M, L, S}, {a, b, *, /, ^}, P, Y), где P: 1) Y→KS | KM; 2) K→K* | K/ | S; 3) S→Sa/ | Sb/ | l; 4) M→*M*; 5) L→L^ | ^a.
	G=({S, B, A }, {a, b,x,{,}}, P, S), где P: 1)S → aA{xx};2)A → bA | cBx | l;3)B → bSc
	G=({S, B, A }, {a, b,}, P, S), где P: 1)S → aSB | bA; 2) A → aS | cA | l; 3)B → bB | d
	G=({S, B, A,}, {a, b,}, P, S), где P: 1)S → cA | B | d; 2) A → abA | c | l; 3)B → bSc | aAb
	G=({S, B, A }, {a, b,{,}}, P, S), где P: 1)S → bABCb | d; 2)A → aA | cB | l; 3)B → Sc 4)C → a {bb}
	G=({S, B, A, }, {a, b,{}}, P, S), где P: 1) S → aAb | cC; 2)A → a { bab };3)B → cAc | aB | l;4)C→Bb
	G=({S, B, A, }, {a, b,{}}, P, S), где P: 1)S → aSB | bAf | l; 2)A → bAc | cS;3)B → cB | d

ДИСКРЕТНАЯ МАТЕМАТИКА

 

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 

к лабораторным и самостоятельной работам

 

 

для студентов специальности

«Системы и методы принятия решений»

дневной формы обучения

 

 

Утверждено на заседании кафедры ИСПР Протокол № 1 от 31.08.2011г.

 

 

 

 

 

Краматорск 2011

 

 

Лабораторная работа №1

 

Алфавитное и равномерное кодирование.

(Алгоритмы Фано и Хаффмана).

Цель работы: изучить алгоритмы кодирования информации посредством методов Фано и Хаффмена.

 

Задание.

1. Для заданных распределений вероятностей появления букв построить заданный код и рассчитать среднюю длину кодирования.

№ варианта	Раcпределение вероятностей	Метод кодирования
	Р={0,1;0,6;0,09;0,08;0,07;0,06}	Метод Фано
	Р={0,5;0,3;0,1;0,03;0,02;0,01;0,04}	Метод Хаффмена
	Р={0,2;0,2;0,19;0,12;0,11;0,09;0,09}	Метод Хаффмена
	Р={0,4;0,4;0,1;0,03;0,03;0,02;0,02}	Метод Фано
	Р={0,4;0,18;0,1;0,1;0,07;0,06;0,05;0,04}	Метод Хаффмена
	Р={0,2;0,3;0,2;0,1;0,1;0,05;0,05}	Метод Фано
	Р={0,2;0,2;0,19;0,12;0,11;0,09;0,09}	Метод Фано
	Р={0,25;0,2;0,15;0,15;0,15;0,1}	Метод Хаффмена
	Р={0,4;0,18;0,1;0,1;0,07;0,06;0,05;0,04}	Метод Фано
	Р={0,6;0,1;0,06;0,08;0,07;0,09}	Метод Хаффмена
	Р={0,2;0,25;0,35;0,05;0,15}	Метод Фано
	Р={0,2;0,3;0,2;0,1;0,1;0,05;0,05}	Метод Хаффмена
	Р={0,35;0,14;0,19;0,17;0,15}	Метод Фано
	Р={0,22;0,17;0,21;0,05;0,2;0,15}	Метод Фано
	Р={0,02;0,35;0,31;0,13;0,19}	Метод Хаффмена
	Р={0,16;0,23;0,11;0,28;0,22}	Метод Хаффмена
	Р={0,38;0,08;0,27;0,18;0,09}	Метод Фано
	Р={0,14;0,36;0,19;0,24;0,07}	Метод Хаффмена
	Р={0,41;0,16;0,07;0,3;0,06}	Метод Фано
	Р={0,26;0,12;0,06;0,19;0,08;0,15;0,14}	Метод Хаффмена

 

2. Написать программу, которая осуществляет кодирование Вашей фамилии, имени и отчества методом Фано или Хаффмена в зависимости от варианта.