e-maxx :: algo
Вас приветствует книга, собранная по материалам сайта e-maxx.ru/algo (по состоянию на 20 Sep 2010 18:56).
В этой книге Вы найдёте описание, реализации и доказательства множества алгоритмов, от известных всем до
тех, которые являются уделом лучших олимпиадников и специалистов по Computer Science. В конце приведены ссылки
на тематическую литературу, которую можно скачать с моего сайта, а также немного информации обо мне.
Приятного чтения!
Оглавление
Алгебра
элементарные алгоритмы
● Функция Эйлера и её вычисление
● Бинарное возведение в степень за O (log N)
● Алгоритм Евклида нахождения НОД (наибольшего общего делителя)
● Решето Эратосфена
● Расширенный алгоритм Евклида
● Числа Фибоначчи и их быстрое вычисление
● Обратный элемент в кольце по модулю
● Код Грея
● Длинная арифметика
● Дискретное логарифмирование по модулю M алгоритмом baby-step-giant-step Шэнкса за O (sqrt(M) log M)
● Диофантовы уравнения с двумя неизвестными: AX+BY=C
● Модульное линейное уравнение первого порядка: AX=B
● Китайская теорема об остатках. Алгоритм Гарнера
● Нахождение степени делителя факториала
● Троичная сбалансированная система счисления
● Вычисление факториала N! по модулю P за O (P log N)
● Перебор всех подмасок данной маски. Оценка 3
N
для суммарного количества подмасок всех масок
● Первообразный корень. Алгоритм нахождения
● Дискретное извлечение корня
сложные алгоритмы
● Тест BPSW на простоту чисел за O (log N)
● Эффективные алгоритмы факторизации: Полларда p-1, Полларда p, Бента, Полларда Монте-Карло, Ферма
● Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел
Графы
элементарные алгоритмы
● Поиск в ширину
● Поиск в глубину
● Топологическая сортировка за O (N + M)
● Поиск компонент связности за O (N + M)
компоненты сильной связности, мосты и т.д.
● Поиск компонент сильной связности, построение конденсации графа за O (N + M)
● Поиск мостов за O (N + M)
● Поиск точек сочленения за O (N + M)
кратчайшие пути из одной вершины
● Алгоритм Дейкстры нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N
2
+ M)
● Алгоритм Дейкстры для разреженного графа нахождения кратчайших путей от заданной вершины до всех
остальных вершин за O (M log N)
● Алгоритм Форда-Беллмана нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N M)
● Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N M)
кратчайшие пути между всеми парами вершин
● Нахождение кратчайших путей между всеми парами вершин графа методом Флойда-Уоршелла за O (n
3
)
● Подсчёт количества путей фиксированной длины между всеми парами вершин, нахождение кратчайших
путей фиксированной длины за O (n
3
log k)
минимальный остов
● Минимальное остовное дерево. Алгоритм Прима за O (N M) и за O (M log N + N
2
)
● Минимальное остовное дерево. Алгоритм Крускала за O (M log N + N
2
)
● Минимальное остовное дерево. Алгоритм Крускала со структурой данных 'система непересекающихся множеств' за O
(M log N)
● Матричная теорема Кирхгофа. Нахождение количества остовных деревьев за O (N
3
)
циклы
● Нахождение отрицательного цикла в графе за O (N M)
● Нахождение Эйлерова пути или Эйлерова цикла за O (M)
● Проверка графа на ацикличность и нахождение цикла за O (M)
наименьший общий предок (LCA)
● Наименьший общий предок. Нахождение за O (sqrt (N)) и O (log N) с препроцессингом O (N)
● Наименьший общий предок. Нахождение за O (log N) с препроцессингом O (N log N) (метод двоичного подъёма)
● Наименьший общий предок. Нахождение за O (1) с препроцессингом O (N) (алгоритм Фарах-Колтона и Бендера)
● Задача RMQ (Range Minimum Query - минимум на отрезке). Решение за O (1) с препроцессингом O (N)
● Наименьший общий предок. Нахождение за O (1) в режиме оффлайн (алгоритм Тарьяна)
потоки и связанные с ними задачи
● Алгоритм Эдмондса-Карпа нахождения максимального потока за O (N M
2
)
● Метод Проталкивания предпотока нахождения максимального потока за O (N
4
)
● Модификация метода Проталкивания предпотока за O (N
3
)
● Поток с ограничениями
● Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей за O (N
3
M)
● Задача о назначениях. Решение с помощью min-cost-flow за O (N
5
)
● Задача о назначениях. Венгерский алгоритм (алгоритм Куна) за O (N
4
)
● Нахождение минимального разреза алгоритмом Штор-Вагнера за O(N
3
)
● Поток минимальной стоимости, циркуляция минимальной стоимости. Алгоритм удаления циклов отрицательного веса
● Алгоритм Диница нахождения максимального потока
паросочетания и связанные с ними задачи
● Алгоритм Куна нахождения наибольшего паросочетания за O (N M)
● Проверка графа на двудольность и разбиение на две доли за O (M)
● Нахождение наибольшего по весу вершинно-взвешенного паросочетания за O (N
3
)
● Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах за O (N
3
)
● Покрытие путями ориентированного ациклического графа
● Матрица Татта. Рандомизированный алгоритм для проверки существования совершенного паросочетания в
произвольном графе
связность
● Рёберная связность. Свойства и нахождение
● Вершинная связность. Свойства и нахождение
● Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин
К-ые пути
● Нахождение K-го кратчайшего пути без циклов с помощью бинарного поиска за O (N
2
K log W)
