74. Сжатие информации. Метод Хаффмана.

Сжатие сокращает объем пространства, требуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи ин¬формации по каналу установленной ширины пропускания. Рассматривается обратимое сжатие или сжатие без наличия помех, где первоначальный текст может быть в точности восстановлен из сжатого состояния. Необратимое или ущербное сжатие используется для цифровой записи аналоговых сигналов, таких как человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов, записанных на естественных и на искусственных языках, поскольку в этом случае ошибки обычно недопустимы. Существует много веских причин осуществлять сжатие данных, так как более быстрая передача данных и сокращение пространства для их хранения позволяют сберечь значительные средства и зачастую улуч¬шить показатели ЭВМ. Существуют два основных способа проведения сжатия: статистический и словарный. Лучшие статистические методы применяют кодиро¬вание Хаффмана, лучшие словарные – метод Зива-Лемпела. В статистическом сжатии каждому символу присваивается код, основанный на вероятности его появления в тексте. Высоковероятные символы получают короткие коды, и наоборот. В словарном методе группы последовательных символов или «фраз» заменяются кодом. Замененная фраза может быть найдена в некотором «словаре». Метод Хаффмана. В этом методе при сжатии данных каждому символу присваивается оптимальный префиксный код, основанный на вероятности его появления в тексте. Префиксные коды – это коды, в которых никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину. Алгоритм Хаффмана можно разделить на два этапа: 1) определение вероятности появления символов в файле; 2) нахождение оптимального префиксного кода. На первом этапе необходимо прочитать файл полностью и подсчитать вероятности появления символов в файле (иногда подсчитывают, сколько раз встречается каждый символ). Если при этом учитываются все 256 сим¬волов, то не будет разницы в сжатии текстового или файла иного формата. Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x, который имеет вероятность появления, равную сумме вероятностей появле¬ния символов a и b. Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего сим¬вола, и эти два новых кода принимаются как коды заменяемых сим¬волов. Например, код символа a будет соответствовать коду x с до¬бавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

Huffman(C)

1. n ←|c|

2. Q ←C

3. For i=q to n-1 do

4. Выделить память для нового узла z

5. x ←min(Q); z^.left ←x

6. y ←min(Q); z^.Right ←y

7. z^.f ←x^.f+y^.f

8. Insertt(Q,z)

9. End for

10. Return min(Q)

75. Исчерпывающий перебор. Задачи коммивояжера. Задача о назначениях.

Исчерпывающий перебор – генерация всех вариантов из области определения задачи, выбор тех, которые удовлетворяют ограничениям и последующий поиск нужного варианта решения.

Задача коммивояжера: найти кратчайший путь по заданным n городам, чтобы каждый город посещался только один раз и конечным пунктом оказался город, с которого начали движение. Зададим граф, вершины – города, ребра между ними – пути, вес графа – расстояние от города до города. Обход: V₁ – V₂ - …… - V₁. Пример:

Обходы: a -> b -> c -> d -> a = 18 (2 + 8 + 1 +8); a -> b -> d -> c -> a = 11; a -> c -> d -> b -> a = 11; a -> c -> b -> d -> a = 23; a -> d -> c -> b -> a = 18; a -> d -> c -> b -> a = 23. Выч. сложность O(n!) - n кол-во «городов».

Задача о назначениях: Имеется n работников, которые должны выполнить n заданий, стоимость выполнения заданий разными работниками различна. Необходимо распределить все задания так, чтобы они были выполнены с наименьшей стоимостью. Один работник не может выполнять две работы. Пример:

	Задание 1	Задание 2	Задание 3	Задание 4
Работник 1	9	2	7	8
Работник 2	6	4	3	7
Работник 3	5	8	1	8
Работник 4	7	6	9	4

Переборы вариантов: (выбранная последовательность заданий для 4 работников = полученная стоимость) 1, 2, 3, 4 = 9+4+1+4 = 18; 1,2,4,3 = 9+4+8+9 = 30; 1,3,2,4 = 9+3+8+4 = 24; 1,3,4,2 = 26; 1,4,2,3 = 33; и т.д. Сложность алгоритма = O(n!) .

76. Поиск с возвратом: алгоритм, применение метода к задаче нахождения гамильтонова цикла в графе. Рассмотрим задачу нахождения путей, проходящих ровно один раз через каждую вершину (а не через каждое ребро) графа. Путь с таким свойством называется гамильтоновым путем, а цикл – гамильтоновым циклом. Очевидным алгоритмом нахождения гамильтонова пути в графе является полный перебор всех возможностей: генерируем все n! различных последовательностей вершин и для каждой проверяем, определяет ли она гамильтонов путь. Такие действия потребуют по крайней мере n! шагов. Алгоритм с возвратом: Строим наше решение последовательно, начиная с пустой последовательности, т.е. последовательности длины 0. Имея некоторое частичное решение < xj,..., xi >, стараемся найти такое допустимое значение xi+1,относительно которого мы не можем сразу заключить, что < xj,..., xi, xi+1 > можно расширить до некоторого решения (а может быть < xj,...,xi,xi+1 > уже является решением). Если такое предполагаемое, но еще не использованное значение xi+i существует, то мы добавляем его к нашему частичному решению и продолжаем процесс для последовательности < xj,..., xi, xi+1 > . Если его не существует, то мы возвращаемся к частичному решению < xj,..., xi _j > и продолжаем наш процесс, отыскивая новое, еще не использованное допустимое значение xi . Пример:

Двигаемся: 1->2->3->4->5->6 , т.к. невозможно 6->1 (нет общего ребра), 6->5->4->6->5, но опять нету 5->1, поэтому 5->4->3->… и т.д. В результате получится путь: 1->2->4->6->5->3->1. Алгоритм:

Алгоритм GamiltonCycle(G) 1. for all vϵV do dop[v] <- true 2. x[1] <- v₀ 3. dop [v₀] <- false 4. Gamilton(2)

Gamilton (k) 1. for y <- List (X[k-1]) do 2. if (y = x₀) and (k = n+1) 3.then x[k] <- v₀; return x 4. else if dop[y] then 5 x[k] <- y 6. dop[y] <- false 7. Gamilton (k+1) 8.dop[y] <- true 9. end if 10 end if 11 end for