Принцип работы

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

Шаг1

Строим бор из образцов. Построение выполняется за время  , где   — суммарная длина образцов.

Б ор (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на ребрах

Бор для набора образцов {he, she, his, hers}:

Шаг 2. Превращаем бор в автомат. Узлы бора становятся состояниями автомата; корень — начальное состояние. Узлы бора, в которых заканчиваются образцы, становятся терминалами. Для переходов по автомату заведём в узлах несколько функций.

Билет 5

Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s.Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы.

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

Любая вершина орграфа сильно связана сама с собой.

Алгоритм Косарайю — алгоритм поиска компонент сильной связности в орграфе. Чтобы найти компоненты сильной связности, сначала выполняется поиск в глубину (DFS) на обращении исходного графа (ребра инвертированы), вычисляя вектор обратного порядка обхода. Затем мы используем обращение этого вектора, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берем вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты.

2.

Суффиксное дерево — бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w.

Реализация алгоритма Укконена

Этот алгоритм строит суффиксное дерево для данной строки длины   за время  , где   — размер алфавита (если его считать константой, то асимптотика получается  ).

Входными данными для алгоритма являются строка   и её длина  , которые передаются в виде глобальных переменных.

Основная функция —  , она строит суффиксное дерево. Дерево хранится в виде массива структур  , где   — корень суффиксного дерева.

В целях простоты кода рёбра хранятся в тех же самых структурах: для каждой вершины в её структуре   записаны данные о ребре, входящем в неё из предка. Итого, в каждой   хранятся:  , определяющие метку   ребра в предка,   — вершина-предок,   — суффиксная ссылка,   — список исходящих рёбер.

Билет 6

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.

Алгоритм

Пусть вершины графа   пронумерованы от 1 до n и введено обозначение   для длины кратчайшего пути от i до j, который кроме самих вершин i , j проходит только через вершины  . Очевидно, что   — длина (вес) ребра  , если таковое существует (в противном случае его длина может быть обозначена как  ).

Существует два варианта значения  :

Кратчайший путь между   не проходит через вершину  , тогда 

Существует более короткий путь между  , проходящий через  , тогда он сначала идёт от i до k, а потом от k до j. В этом случае, очевидно, 

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для   имеет вид:

 — длина ребра 

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения     для k от 1 до n. Полученные значения   являются длинами кратчайших путей между вершинами i, j.

Сложность алгоритма

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

Построение матрицы достижимости

Алгоритм Флойда-Уоршелла может быть использован для нахождения замыкания отношения   по транзитивности. Для этого в качестве W[0] используется бинарная матрица смежности графа,  ; оператор minзаменяется дизъюнкцией, сложение заменяется конъюнкцией:

for k = 1 to n

for i = 1 to n

for j = 1 to n

W[i][j] = W[i][j] or (W[i][k] and W[k][j])

После выполнения алгоритма матрица W является матрицей достижимости.

Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до  , где   — длина битовой маски (в модели вычислений RAM). На практике, ещё бо́льшего ускорения можно достичь, используя такие специализированные наборы микропроцессорных команд, как SSE.

2.Система непересекающихся множеств позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трех операций {Union, Find, MakeSet}. Система непересекающихся множеств очень удобна для хранения компонент связности в графах. К примеру, Алгоритму Краскала необходима подобная структура данных для эффективной реализации.

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

.

Каждому классу   назначается представитель  . Соответствующая система непересекающихся множествподдерживает следующие операции:

MakeSet( ): создает для элемента   новый класс. Назначает этот же элемент представителем созданного класса.

Union( ,  ): объединяет оба класса, принадлежащие представителям   и  , и назначает   представителем нового класса.

Find( ): определяет для   класс к которому принадлежит элемент, и возвращает его представителя.

Алгоритмическая реализация. Тривиальная реализация сохраняет принадлежность элементов из   и представителей   в индексном массиве. На практике же, чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Find. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.

Union( ,  ): Вешает корень более низкого дерева под корень более высокого дерева. Если при этом   становится ребенком  , оба узла меняются местами.

Find( ): проходит путь от   до корня дерева и возвращает его (корень в данном случае является представителем).

Для ускорения операций Union и Find используются следующие эвристики.

Union-By-Size

Во время операции Union(r, s) корень более низкого дерева вешается под корень более высокого дерева. Благодаря этому подходу сохраняется балансировка дерева. Глубина каждого поддерева T не может превысить величину  . При использовании этой эвристики worst-case-время операции Find уменьшается с   до  . Для эффективной реализации предлагается сохранять в корне количество узлов в дереве.

Сжатие путей

Используется чтобы ускорить операцию Find( ). При каждом новом поиске, все элементы находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция Find будет работать в среднем α(n), где α - функция, обратная функции Аккермана. Это позволяет значительно ускорить работу, так как α для всех применяемых на практике значений принимает значение, меньшее 5.

Билет 7

Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм награфах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательноговеса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPFдля устранения кольцевых маршрутов.

Примеры

Вариант 1. Дана сеть автомобильных дорог, соединяющих города Московской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Москва до каждого города области (если двигаться можно только по дорогам).

Дан взвешенный ориентированный^[1] граф   без петель и дуг отрицательного веса^[2]. Найти кратчайшие пути от некоторой вершины   графа   до всех остальных вершин этого графа.

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.