5. Методы поиска

Делятся на методы поиска среди упорядоченных и неупорядоченных данных.

Среди неупорядоченных:

1. последовательный поиск

2. быстрый последовательный поиск

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

Быстрый последовательный поиск. Организуется цикл не со счётчиком, а цикл с условием совпадения ключей. Условие повторения — несовпадение ключей. При такой организации число сравнений в среднем N/2 .

Поиск в самоорганизующемся массиве данных. Массив данных неупорядоченный. Если нашли нужный элемент, помещаем его в начало, а остальные сдвигаем на одну позицию. Как только снова потребовался поиск, снова сравниваются все подряд. Нашли — ставим на первое место, остальные сдвигаем.

25 17 83 22 64

17: 17 25 83 22 64

64: 64 17 25 83 22

83: 83 64 17 25 22

17: 17 83 64 25 22

6. Методы поиска среди упорядоченных данных

Метод бинарного поиска

Сверяется со средним элементом (n/2). Если искомый ключ меньше среднего, ищем в левой половине, если больше — в правой. Количество сравнений log(N,2).

Однородный бинарный поиск

Используется переменная H (ширина отрезка). Позиция будет вычисляться по формуле i = +- H. H=H/2 . Число элементов массива должно быть степенью двойки.

Метод Фибоначчи

0 1 1 2 3 5 8 13 21 34 …

Сравнение как в бинарном поиске, но по числам Фибоначчи. Если массив из 34, сравниваем с 21 элементом. Если < 21 , то сравниваем с 13. Если меньше 13, то с 8 и т.д.

Если элемент оказался больше, следующая позиция вычисляется: 21 + 8 (F_i+F_i-2)

Число сравнений log(N,2) . Если элемент ближе к правой части массива, то нужно брать метод Фибоначчи.

Интерполяционный поиск

Реализована идея поиска по словарю. Для поиска используется формула i = Л+(П-Л)/(Кп-Кл) * (К-Кл)

Сначала Л=0, П=длина массива, Кп — ключ в правой позиции, Кл — ключ в левой позиции, К — искомый ключ.

log(N*log(N,2),2)

Поиск со вставкой по дереву

Сравнение с ключом-корнем дерева, если меньше, то left, больше — right и т.д.

log(N,2) для сбалансированных деревьев. Для вырожденного случая число сравнений N.

Для случайных величин 2*ln(N) = 1.4*log(N,2)

Цифровой поиск со вставкой по дереву

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

Поиск по бору

Сбалансированное двухпоточное слияние

Есть 4 файла F1..F4 , файлы хранятся на дисках.

Двухфазное слияние

Фаза слияния и фаза перезаписи.

Многофазное слияние с фиббоначиевым разбиением

2. Семестр 2

1. Алгоритмы на графах

Граф — упорядоченная пара G = (V,E)

V — вершины

E — рёбра

Вершины, соединённые общим ребром — смежные.

Взвешенный граф

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

Ациклический граф — граф без циклов.

Сильносвязный граф — граф, у которого из каждой вершины есть путь в любую другую вершину этого графа.

2. Представление графов

1. Матрицы смежности

Матрица, число строк и столбцов равно количеству вершин в графе. На пересечении ставится 0 (если вершины не связаны) или 1 (если вершины связаны).

Матрица весов — вместо 0 и 1 записывается вес ребра.

2. Матрицы инцидентности

Число строк — количество вершин. Число столбцов — количество рёбер (дуг)

Плотный граф — граф, близкий к полному. У которого каждая вершина связана с большинством оставшихся.

Разреженный — каждая вершина связана с небольшим количеством оставшихся вершин.

Список примыканий (МП1)

Дерево — связный граф без циклов.

Ребро — неупорядоченная пара вершин, соединённых между собой

Степень вершины — число инцидентных ей рёбер.

Порядок графа — число его вершин. Записывается |V|

Размер графа — число рёбер. Записывается |E|

Кратные рёбра, концевые вершины совпадают

Петля — ребро, вершины которого совпадают

Мультиграф — граф с кратными рёбрами

Псевдограф — мультиграф с петлями

Простой граф — без петель

Орграф — граф, все рёбра которого являются дугами.

Смешанный граф — граф, часть рёбер которого является ориентированными.

Нагруженный граф — каждому ребру соответствует вес

Сеть — взвешенный орграф.

Маршрут — последовательность вершин и рёбер, в которой каждая, кроме последующей, соединена ребром со следующей

Путь — маршрут в орграфе.

Длина маршрута — число составляющих его рёбер для невзвешенного или сумма весов для взвешенного

Цикл — цепь, в которой первая и последняя вершина совпадают

Эйлеров цикл — цикл, проходящий по каждому ребру в неориентированном мультиграфе ровно 1 раз.

Гамильтонов цикл — содержит каждую вершину один раз.

Контур — цикл в орграфе

Простой путь — в котором рёбра не повторяются.

Ациклический граф — граф без циклов

Связный граф — в котором для любой вершины существует путь из одной вершины в другую.

Компоненты связности — такое подмножество вершин, для любых двух … из которого существует путь из одной в другую и нет пути в остальные.

Разреженный — число рёбер много меньше квадрата его порядка.

Матрица смежности (примыканий) — элемент i,j содержит число рёбер, идущих из одной вершины в другую.

Списки примыканий — способ представления графов в виде списков, число которых равно количеству узлов.