Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Шпора по информатике.docx
Скачиваний:
4
Добавлен:
01.03.2025
Размер:
383 Кб
Скачать
☆

Метод потенциалов

Обобщение метода предоплаты. Самый точный Введём для каждого состояния структуры данных величину  — потенциал (функция из множества состояний структуры в действительные числа). Изначально потенциал равен , а после выполнения 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) — сумма потоков из источника  . В дальнейшем мы докажем, что она равна сумме потоков в сток  .

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

Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.