Алгебра

Вот содержание:

элементарные алгоритмы

●     Функция Эйлера и её вычисление

●     Бинарное возведение в степень за O (log N)

●     Алгоритм Евклида нахождения НОД (наибольшего общего делителя)

●     Решето Эратосфена

●     Расширенный алгоритм Евклида

●     Числа Фибоначчи и их быстрое вычисление

●     Обратный элемент в кольце по модулю

●     Код Грея

●     Длинная арифметика

●     Дискретное логарифмирование по модулю M алгоритмом baby-step-giant-step Шэнкса за O (sqrt(M) log M)

●     Диофантовы уравнения с двумя неизвестными: AX+BY=C

●     Модульное линейное уравнение первого порядка: AX=B

●     Китайская теорема об остатках. Алгоритм Гарнера

●     Нахождение степени делителя факториала

●     Троичная сбалансированная система счисления

●     Вычисление факториала N! по модулю P за O (P log N)

●     Перебор всех подмасок данной маски. Оценка 3N

для суммарного количества подмасок всех масок

●     Первообразный корень. Алгоритм нахождения

●     Дискретное извлечение корня

●     Решето Эратосфена с линейным временем работы

сложные алгоритмы

●     Тест BPSW на простоту чисел за O (log N)

●     Эффективные алгоритмы факторизации: Полларда p-1, Полларда p, Бента, Полларда Монте-Карло, Ферма

●     Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел

Графы

элементарные алгоритмы

●     Поиск в ширину

●     Поиск в глубину

●     Топологическая сортировка

●     Поиск компонент связности

компоненты сильной связности, мосты и т.д.

●     Поиск компонент сильной связности, построение конденсации графа за O (N + M)

●     Поиск мостов за O (N + M)

●     Поиск точек сочленения за O (N + M)●     Поиск мостов в режиме онлайн за O(1) в среднем

кратчайшие пути из одной вершины

●     Алгоритм Дейкстры нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N2

 + M)

●     Алгоритм Дейкстры для разреженного графа нахождения кратчайших путей от заданной вершины до всех

остальных вершин за O (M log N)

●     Алгоритм Форда-Беллмана нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N M)

●     Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N M)

кратчайшие пути между всеми парами вершин

●     Нахождение кратчайших путей между всеми парами вершин графа методом Флойда-Уоршелла за O (n

3

)

●     Подсчёт количества путей фиксированной длины между всеми парами вершин, нахождение кратчайших

путей фиксированной длины за O (n

3

 log k)

минимальный остов

●     Минимальное остовное дерево. Алгоритм Прима за O (n

2

) и за O (m log n)

●     Минимальное остовное дерево. Алгоритм Крускала за O (M log N + N2

)

●     Минимальное остовное дерево. Алгоритм Крускала со структурой данных 'система непересекающихся множеств' за O 

(M log N)

●     Матричная теорема Кирхгофа. Нахождение количества остовных деревьев за O (N3

)

●     Код Прюфера. Формула Кэли. Количество способов сделать граф связным

циклы

●     Нахождение отрицательного цикла в графе за 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 M2

)

●     Метод Проталкивания предпотока нахождения максимального потока за O (N4

)

●     Модификация метода Проталкивания предпотока за O (N3

)

●     Поток с ограничениями

●     Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей за O (N3

 M)

●     Задача о назначениях. Решение с помощью min-cost-flow за O (N5

)

●     Задача о назначениях. Венгерский алгоритм (алгоритм Куна) за O (N4

)

●     Нахождение минимального разреза алгоритмом Штор-Вагнера за O(N3

)

●     Поток минимальной стоимости, циркуляция минимальной стоимости. Алгоритм удаления циклов отрицательного веса

●     Алгоритм Диница нахождения максимального потока

паросочетания и связанные с ними задачи

●     Алгоритм Куна нахождения наибольшего паросочетания за O (N M)

●     Проверка графа на двудольность и разбиение на две доли за O (M)

●     Нахождение наибольшего по весу вершинно-взвешенного паросочетания за O (N3

)●     Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах за O (N3

)

●     Покрытие путями ориентированного ациклического графа

●     Матрица Татта. Рандомизированный алгоритм для поиска максимального паросочетания в произвольном графе

связность

●     Рёберная связность. Свойства и нахождение

●     Вершинная связность. Свойства и нахождение

●     Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин

К-ые пути

обратные задачи

●     Обратная задача SSSP (inverse-SSSP - обратная задача кратчайших путей из одной вершины) за O (M)

●     Обратная задача MST (inverse-MST - обратная задача минимального остова) за O (N M2

)

разное

●     Покраска рёбер дерева (структуры данных) - решение за O (log N)

●     Задача 2-SAT (2-CNF). Решение за O (N + M)

●     Heavy-light декомпозиция

Геометрия

элементарные алгоритмы

●     Длина объединения отрезков на прямой за O (N log N)

●     Знаковая площадь треугольника и предикат 'По часовой стрелке'

●     Проверка двух отрезков на пересечение

●     Нахождение уравнения прямой для отрезка

●     Нахождение точки пересечения двух прямых

●     Нахождение точки пересечения двух отрезков

●     Нахождение площади простого многоугольника за O (N)

●     Теорема Пика. Нахождение площади решётчатого многоугольника за O (1)

●     Задача о покрытии отрезков точками

●     Центры тяжести многоугольников и многогранников

более сложные алгоритмы

●     Пересечение окружности и прямой

●     Пересечение двух окружностей

●     Построение выпуклой оболочки алгоритмом Грэхэма-Эндрю за O (N log N)

●     Нахождение площади объединения треугольников. Метод вертикальной декомпозиции

●     Проверка точки на принадлежность выпуклому многоугольнику за O (log N)

●     Нахождение вписанной окружности в выпуклом многоугольнике с помощью тернарного поиска за O (N log

2

 C)

●     Нахождение вписанной окружности в выпуклом многоугольнике методом сжатия сторон за O (N log N)

●     Диаграмма Вороного в двумерном случае, её свойства, применение. Простейший алгоритм построения за O(N4

)

●     Нахождение всех граней, внешней грани планарного графа за O (N log N)

●     Нахождение пары ближайших точек алгоритмом разделяй-и-властвуй за O (N log N)

●     Преобразование геометрической инверсии

●     Поиск общих касательных к двум окружностям

●     Поиск пары пересекающихся отрезков алгоритмом заметающей прямой за O (N log N)Строки

●     Z-фунция строки и её вычисление за O (N)

●     Префикс-функция, её вычисление и применения. Алгоритм Кнута-Морриса-Пратта

●     Алгоритмы хэширования в задачах на строки

●     Алгоритм Рабина-Карпа поиска подстроки в строке за O (N)

●     Разбор выражений за O (N). Обратная польская нотация

●     Суффиксный массив. Построение за O (N log N) и применения

●     Суффиксный автомат. Построение за O (N) и применения

●     Нахождение всех подпалиндромов за O (N)

●     Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига за O (N) времени и O (1) памяти

●     Алгоритм Ахо-Корасик

●     Суффиксное дерево. Алгоритм Укконена

●     Поиск всех тандемных повторов в строке алгоритмом Мейна-Лоренца (разделяй-и-властвуй) за O (N log N)

●     Поиск подстроки в строке с помощью Z- или Префикс-функции. Алгоритм Кнута-Морриса-Пратта

●     Решение задачи "сжатие строки"

●     Определение количества различных подстрок за O (N2

 log N)

Структуры данных

●     Sqrt-декомпозиция

● Дерево Фенвика

●     Система непересекающихся множеств

●     Дерево отрезков

●     Декартово дерево (treap, дерамида)

●     Модификация стека и очереди для извлечения минимума за O (1)

●     Рандомизированная куча

Алгоритмы на последовательностях

●     Задача RMQ (Range Minimum Query - минимум на отрезке)

●     Нахождение наидлиннейшей возрастающей подпоследовательности за O (N2

) и O (N log N)

●     K-ая порядковая статистика за O (N)

●     Нахождение наидлиннейшей возрастающей подпоследовательности за O (N2

) и O (N log N)

Динамика

●     Динамика по профилю. Задача "паркет"

●     Нахождение наибольшей нулевой подматрицы за O (N M)

Линейная алгебра

●     Метод Гаусса решения системы линейных уравнений за O (N3

)●     Нахождение ранга матрицы за O (N3

)

●     Вычисление определителя матрицы методом Гаусса за O (N3

)

●     Вычисление определителя методом Краута за O (N3

)

Численные методы

●     Интегрирование по формуле Симпсона

●     Поиск корней методом Ньютона (касательных)

●     Тернарный поиск

Комбинаторика

●     Биномиальные коэффициенты

●     Числа Каталана

●     Ожерелья

● Расстановка слонов на шахматной доске

●     Правильные скобочные последовательности. Нахождение лексикографически следующей, K-ой, определение номера

●     Количество помеченных графов, связных помеченных графов, помеченных графов с K компонентами связности

●     Генерация сочетаний из N элементов

●     Лемма Бернсайда. Теорема Пойа

●     Принцип включений-исключений

Теория игр

●     Игры на произвольных графах. Метод ретроспективного анализа за O (M)

●     Теория Шпрага-Гранди. Ним

Расписания

●     Задача Джонсона с одним станком

●     Задача Джонсона с двумя станками

●     Оптимальный выбор заданий при известных временах завершения и длительностях выполнения

Разное

●     Задача Иосифа

●     Игра Пятнашки: существование решения

●     Дерево Штерна-Броко. Ряд Фарея

●     Поиск подотрезка массива с максимальной/минимальной суммой за O(N)