Билет 12

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

Операции

makeHeap

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

insert

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей.

getMin

Возвращает указатель  . Реальное время работы —  .

merge

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы —  . Амортизированное время работы также  , поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется,  .

extractMin

Первая рассматриваемая операция, в ходе которой меняется структура кучи. 

consolidate

Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более   вершин.

delete

Удаление вершины реализуется через уменьшение ее ключа до   и последующим извлечением минимума. Амортизированное время работы:  .

2.

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

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0:   для всех  . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Неформальное описание

Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

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

Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью  .

Для каждого ребра на найденном пути увеличиваем поток на  , а в противоположном ему — уменьшаем на  .

Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

Возвращаемся на шаг 2.

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

На каждом шаге алгоритм добавлет поток увеличивающего пути к уже имеющемуся потоку. Если пропускные способности всех рёбер — целые числа, легко доказать по индукции, что и потоки через все рёбра всегда будут целыми. Следовательно, на каждом шаге алгоритм увеличивает поток по крайней мере на единицу, следовательно, он сойдётся не более чем за O(f) шагов, где f — максимальный поток в графе. Можно выполнить каждый шаг за время O(E), где E— число рёбер в графе, тогда общее время работы алгоритма ограничено O(E*f).

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

Билет 13

Амортизационная стоимость (анализ)

Амортизационный анализ — метод подсчета времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае. Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Это оценка среднего времени выполнения операций для худшего случая. Средняя амортизационная стоимость операций — величина , находящаяся по формуле: , где  - время выполнения операций  совершённых над структурой данных. Амортизационный анализ использует следующие методы: 1. Метод усреднения (метод группового анализа). 2. Метод потенциалов. 3. Метод предоплаты (метод бухгалтерского учета). Метод усреднения В методе усреднения амортизационная стоимость операций определяется напрямую по формуле, указанной выше: суммарная стоимость всех операций алгоритма делится на их количество.

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

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