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

С фибоначчиевым распределением.

Многофазное слияние.

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

Методы внешней сортировки.

Поиск по дереву.

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

Фибоначчиев поиск.

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

Бинарный поиск (методом деления отрезка пополам).

Ищем путем сравнения ос средним. Если текущий ключ меньше 64-го элемента, то далее берем середину либо левого, либо правого отрезка. Тогда ключ считается либо не найденным, либо найденным. i=(L+R)/2. Если X<Ai, то è нет è l=I иначе è R=i. Трудоемкость log₂N.

Модификация предыдущего метода, используется H – длина отрезка. H=H/2. Если X<Ai, то è нет è l=I i=i+H иначе è R=i i=i-H. Трудоемкость log₂N.

Сложение, вычитание – «короткие операции»; деление, умножение – «длинные операции».

Поиск берется с конца, берется последнее число Фибоначчи, не превышающее длины массива. А1… А2… А3… А5… А8… А13… А21… А34. Сравниваем до тех пор, пока не попадем в ситуацию, когда X больше первого. В правом фрагменте берем позицию элементов A_Fi+Fi-2. Если организовать рекурсивно, то массив передается в функцию. Трудоемкость log₂N.

Поиск по словарю.

Л – левая позиция интервала.

П – правая позиция интервала.

Значения ключей от 1 – до 1000.

К_л – 1

К_п – 1000

r = Л + (П-Л)/(К_п - К_л) * (К - К_л). Данная формула предполагает, что ключи распределены равномерно. Трудоемкость log₂log₂N.

Каждый узел содержит по три поля минимум, есть left, right и корень. Если сравниваются слова – лексикографическое сравнение.

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

2. Сбалансированное многопоточное слияние.

3. Многофазное слияние.

4. С фибоначчиевым распределением.

Этап	F1	F2	F3	F4	Примечание
Исходное состояние	-	-	-
1. Разбиение   2. Слияние   3. Слияние.   4. Слияние			-     Сливаются	-	Распределение с сортировкой.

Добавляется распределение на 3 этапе. Далее, снова слияние.

Граф представляет собой сеть. Узлы и дуги. С помощью графов, можно подсчитывать статистику. Граф представляет собой совокупность двух понятий: G=(V,E) – множество вершин и ребер. Есть понятие порядок графа – число вершин. Вершины могут быть смежными, если соединены ребром. Ребро является инцидентным. Тест по теории графов(!!!). Если ребро направленно – называется дугой. Если есть – то граф ориентированный. Если есть и то, и то – смешанный граф.

Мультиграф – несколько ребер между вершинами. Псевдограф.

Взвешенный граф – каждому ребру соответствует вес, какое-то числовое значение.

Цикл – путь, у которого начальная и конечная точка совпадают.

Путь. Маршрут – неориентированный граф.

V – множество вершин.

Е – множество пар, ребер.

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

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

Порядок графа – число вершин.

Размер графа – число ребер.

Инцидентными являются ребро и узлы, соединенные с ним.

Смежными или соседними являются ребра (вершины), соединенные общей вершиной (ребром).

Кратными называются ребра, концевые вершины которых совпадают.

Петля – ребро, вершины (концы) которого совпадают.

Дата добавления: 2014-01-05