- •2.Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
- •2.Префикс-функция. Определение
- •Постановка задачи
- •Построение матрица достижимости
- •Принцип работы
- •Сложность алгоритма
- •2.Дека́ртово де́рево — это двоичное дерево, в узлах которого хранятся:
- •Оценка сложности
- •Дерево отрезков. Построение
- •Билет 11
- •Билет 12
- •Метод потенциалов
- •Определения
Метод потенциалов
Обобщение
метода предоплаты. Самый точный
Введём
для каждого состояния структуры данных
величину
—
потенциал (функция из множества состояний
структуры в действительные числа).
Изначально потенциал равен
,
а после выполнения i-ой
операции —
.
Стоимость i-ой
операции обозначим
.
Если удалось придумать такую Ф, что
Ф(Dn)
>= Ф(D0),
то суммарная учетная стоимость даст
верхнюю оценку для реальной стоимости
n
операций.
Сумма ai >= сумма ti
2.
Наименьший общий предок вершин u и v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т.е. являющаяся предком обоих вершин. Общепринятое сокращение — LCA
Самый простой, наивный алгоритм для нахождения наименьшего общего предка — вычислить глубину вершин u и v и постепенно подниматься из каждой вершины вверх по дереву, пока не будет найдена общая вершина:
Процедура LCA(u, v):
h1 := depth(u) // depth(x) = глубина вершины x
h2 := depth(v)
while h1 ≠ h2:
if h1 > h2:
u := parent(u)
h1 := h1 - 1
else:
v := parent(v)
h2 := h2 - 1
while u ≠ v:
u := parent(u) // parent(x) = непосредственный предок вершины x
v := parent(v)
return u
Наименьшим
общим предком (least common ancestor) двух
узлов
и
в
корневом дереве
называется
узел
,
который среди всех узлов, являющихся
предками как узла
,
так и
,
имеет наибольшую глубину.
Постановка задачи LCA
Пусть
дано корневое дерево
.
На вход подаются запросы вида
,
для каждого запроса требуется найти их
наименьшего общего предка.
Алгоритм
Препроцессинг
Для каждой вершины определим глубину с помощью следующей рекурсивной формулы:
Ясно, что глубина вершины элементарным образом поддерживается во время обхода в глубину.
Запустим обход в глубину из корня, который будет вычислять значения следующих величин:
Cписок
глубин посещенных вершин
.
Глубина текущей вершины добавляется в
конец списка при входе в данную вершину,
а также после каждого возвращения из
её сына.
Список
посещений узлов
,
строящийся аналогично предыдущему,
только добавляется не глубина а сама
вершина.
З
начение
функции
,
возвращающей любой индекс в списке
глубин
,
по которому была записана глубина
вершины
(например
на момент входа в вершину).
Постановка задачи RMQ
Пример построенного дерева для массива А
Дан
массив
.
Поступают запросы вида
,
на каждый запрос требуется найти минимум
в массиве
,
начиная с позиции
и
заканчивая позицией
.
Алгоритм
Декартово дерево (англ. сartesian tree) по неявному ключу на массиве — это бинарное дерево, допускающее следующее рекурсивное построение:
Корнем
дерева является элемент массива, имеющий
минимальное значение
,
скажем
.
Если минимальных элементов несколько,
можно взять любой.
Левым
поддеревом является декартово дерево
на массиве
.
Правым
поддеревом является декартово дерево
на массиве
.
Здесь и далее будет также использоваться для обозначения соответствующей вершины дерева.
Построим
декартово дерево на массиве
.
Тогда
=
.
БИЛЕТ 14
Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного деревавзвешенного связного неориентированного графа. Формулировка
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
Оценка
До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом общее время работы алгоритма Крускала можно принять за O(E * log(E)).
2. Д ерево ключевых слов (или "бор") (keyword tree, trie) для множества шаблонов P - это дерево с корнем K, такое что: 1. Каждое ребро e в K отмечено одним символом. 2. Всякие два ребра, исходящие из одной вершины, имеют разные метки. Определим метку вершины v как конкатенацию меток ребер, составляющих путь из корня в v, и обозначим ее L (v). 3. Для каждого шаблона Pi из множества P есть вершина v, такая что L (v) = Pi. 4. Метка каждой вершины-листа является шаблоном из множества P.
Пример дерева ключевых слов (бора)
Дерево ключевых слов для P = {he, she, his, hers}: Бор - хороший способ хранения словаря строк.
Построение бора
Начинаем с дерева из одной вершины (корня); добавляем шаблоны Pi один за другим: Следуем из корня по ребрам, отмеченным буквами из Pi, пока возможно. Если Pi заканчивается в v, сохраняем идентификатор Pi (например, i) в v. Если ребра, отмеченного очередной буквой Pi нет, то создаем новые ребра и вершины для всех оставшихся символов Pi. Это занимает, очевидно, O (|P1| + ... + |Pk|) = O (n) времени.
Поиск строки в бору
Поиск строки S в бору: начинаем в корне, идем по ребрам, отмеченным символами S, пока возможно. Если с последним символом S мы приходим в вершину с сохраненным идентификатором, то S - слово из словаря. Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет. Ясно, что это занимает O (|S|) времени. Таким образом, бор - это эффективный способ хранить словарь и искать в нем слова. Теперь перейдем от бора к автомату (automaton), чтобы добиться поиска шаблонов в тексте за линейное время.
Билет 15
В теории
графов транспортная
сеть — ориентированный
граф
,
в котором каждое ребро
имеет
неотрицательную пропускную
способность
и поток
.
Выделяются две вершины: источник S и сток t такие,
что любая другая вершина сети лежит на
пути из S в t.
Транспортная сеть может быть использована
для моделирования, например, дорожного
трафика.
Целочисленная транспортная сеть — транспортная сеть, все пропускные способности ребер которой — целые числа.
Транспортная
сеть (flow
network) — ориентированный граф
в
котором
каждому
ребру
приписана
неотрицательная пропускная способность
.
Если
,
то
.
выделены две вершины: источник (source) S и сток (sink) t, такие, что любая другая вершина сети лежит на пути из S в t.
Поток (flow) —
функция
со
следующими свойствами для любых
вершин
и
:
Ограничение
пропускной способности (capacity
constraints). Поток не может превысить
пропускную способность:
Антисимметричность (skew
symmetry). Поток из
в
должен
быть противоположным потоку из
в
:
Сохранение
потока (flow
conservation):
для
всех
,
кроме источника и стока.
Величина
потока (value
of flow) — сумма потоков из источника
.
В дальнейшем мы докажем, что она равна
сумме потоков в сток
.
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.
