16 Вопрос. Алгоритм Хаффмана.

Жадный алгоритм (англ.Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская что конечное решение также окажется оптимальным.

Алгоритм Хаффмана (англ. Huffman) — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. Коды Хаффмана широко используются при сжатия информации (в типичной ситуации выигрыш может составить от 20% до 90% в зависимости от тина файла). Алгоритм Хаффмана находит оптимальные префиксы (коды символов), исходя из частоты использования этих символов в сжимаемом тексте, с помощью жадного выбора.

17 Вопрос. Поиск элемента в двоичном дереве поиска.

Поиск элемента в дереве. Операция заключается в прохождении узлов дерева в одном из рассмотренных выше порядке. При прохождении дерева поиска достаточно пройти только то поддерево, которое возможно содержит искомый элемент;

В двоичном дереве каждая вершина имеет не более двух потомков, обозначенных как левый ( left) и правый ( right). Кроме того, на данные, хранимые в вершинах дерева, вводится следующее правило упорядочения: значения вершин левого поддерева всегда меньше, а значения вершин правого поддерева - больше значения в текущей вершине.

struct btree {

int val;

btree *left,*right; };

Свойства двоичного дерева позволяют применить в нем алгоритм поиска, аналогичный двоичному поиску в массиве. Каждое сравнение искомого значения и значения в вершине позволяет выбрать для следующего шага правое или левое поддерево. Алгоритмы включения и исключения вершин дерева не должны нарушать указанное свойство: при включении вершины дерева поиск места ее размещения производится путем аналогичных сравнений. Эти алгоритмы являются линейно рекурсивными или циклическими.

18 Вопрос. Балансировка деревьев.

Б.Д. – это алгоритм перестроения дерева таким образом, что при добавлении узла на новый уровень дерева, предыдущий уровень уже будет заполненный.

Идеально сбалансированное дерево, в котором все уровни полностью заполнены.

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

У любого дерева, которое состоит из левых дочерних узлов, называется главной лозой дерева.

19 Вопрос. Алгоритмы представления графа.

Представление графа в виде массива

Первое из описываемых представлений графа основано на следующих соображениях. Структуру графа можно описать, сопоставив каждой вершине множество дуг, выходящих из нее, причем каждая дуга, выходящая из вершины u, идентифицируется своим концом— номером вершины, в которую эта дуга входит. Таким образом, граф представляется массивом, в котором каждому номеру вершины и в диапазоне от 0 до N сопоставлено множество целых чисел — номеров вершин, в которые входят дуги, исходящие из выбранной вершины u.

Представление графа в виде матрицы смежности

Еще один распространенный способ представления графа — это представление в виде матрицы смежности размером N * N (рис.1). B этой матрице в элементе с индексами (i,j) записывается информация о дугах, ведущих из вершины с номером i в вершину с номером j. В важном частном случае простого графа, т. е. графа, в котором каждая упорядоченная пара вершин соединена не более чем одной дугой, и отсутствуют дуги вида (u, u), элементы матрицы могут принимать значения 0 или 1 в зависимости от того, существует ли соответствующая дуга. Ясно, что такое представление самым тесным образом связано с представлением, описанным выше в определении класса setGraph.

Представление в виде матрицы смежности будем называть М-графом. Удобно связывать с матрицей смежности информацию о нагрузке на дуги. В этом случае элементом матрицы будет либо значение нагрузки на соответствующую дугу, либо некоторое стандартное значение, говорящее об отсутствии дуги.

Рис.1. граф и его представление в виде матрицы смежности

Если, например, граф моделирует транспортную сеть, в которой нагрузка на дугу представляет расстояние между пунктами, соединенными этой дугой, то признаком отсутствия дуги удобно сделать значение 0 или, напротив, максимально возможное целое, смотря по тому, что окажется более удобным в используемом алгоритме. В общем виде, если тип нагрузки представлен значениями класса W, то представление графа будет содержать двумерный массив значений класса W. Мы для простоты не будем интересоваться нагрузкой на дуги графа, таким образом, элементами матрицы, представляющей М-граф, могут быть просто логические значения.

Представление графа в виде связанного списка

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

Рис.2. Граф и его представление в виде связанных списков

Представление графа в виде списка дуг

Иногда используются и другие представления графов, например, для случая очень разреженных графов, когда при большом количестве N вершин графа число дуг существенно меньше NXN, например, порядка N. Одним из таких представлений является представление в виде списка дуг, когда все дуги графа собраны в единый список, в каждом элементе которого записана информация об обоих концах дуги, а также, возможно, о нагрузке на дугу (рис.3).

Рис.3. Граф и его представление в виде списка дуг