roadMap.md

На проработку

Теория чисел

• Числа Фибоначчи
• Дискретное логарифмирование
• Китайская теорема об остатках, Алгоритм Гарнера
• Нахождение степени делителя факториала
• Первообразный корень. Дискретное извлечение корня
• Быстрое преобразование Фурье - умножение двух полиномов или длинных чисел за O(NlogN)

Графовые алгоритмы

• Поиск в глубину (+ рекурсивный)

мосты, точки сочленения, компоненты связности

• Поиск мостов в реижме онлайн
• Поиск точек сочленения

кратчайшие пути

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

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

• Минимальное остовное дерево. Алгоритм Крускала с DSU
• Минимальное остовное дерево. Алгоритм Прима
• Нахождение количества остовных деревьев( Матричная теорема Кирхгофа)
• Код Прюфера. Формула Кэли. Количество способов сделать граф связным

наименьший общий предок (LCA)

• Наименьший общий предок. Нахождение с препроцессингом
• Наименьший общий предок. Метод двоичного подъёма
• Наименьший общий предок. Алгоритм Фарах-Колтона и Бендера
• Задача RMQ (Range Minimum Query - минимум на отрезке)

потоки

• Нахождение максимального потока. Алгоритм Эдмондса-Карпа
• Нахождение максимального потока. Метод Проталкивания предпотока
• Поток с ограничениями
• Задача о назначениях. Решение с помощью min-cost-flow, Венгерский алгоритм
• Нахождение минимального разреза алгоритмом Штор-Вагнера
• Поток минимальной стоимости, циркуляция минимальной стоимости. Алгоритм удаления циклов отрицательного веса

паросочетания

• Нахождения наибольшего паросочетания. Алгоритм Куна
• Нахождения наибольшего паросочетания. Алгоритм Эдмондса
• Нахождения наибольшего паросочетания. Матрица Татта.
• Проверка графа на двудольность и разбиение на две доли
• Нахождение наибольшего по весу вершинно-взвешенного паросочетания
• Покрытие путями ориентированного ациклического графа

связность

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

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

• Обратная задача SSSP (inverse-SSSP - обратная задача кратчайших путей из одной вершины)
• Обратная задача MST (inverse-MST - обратная задача минимального остова)

разное

• Покраска рёбер дерева (структуры данных)
• Heavy-light декомпозиция
• Поиск максимальной клики, распознавание клики размером k

Строковые алгоритмы

• Алгоритм Кнута-Морриса-Пратта
• Алгоритмы хэширования в задачах на строки
• Алгоритм Рабина-Карпа поиска подстроки в строке
• Разбор выражений за O (N). Обратная польская нотация
• Суффиксный массив.
• Суффиксный автомат.
• Алгоритм Ахо-Корасик
• Суффиксное дерево. Алгоритм Укконена
• Поиск всех тандемных повторов в строке алгоритмом Мейна-Лоренца (разделяй-и-властвуй)
• Редакционное растояние. Алгоритмы: Хэмминга, Дамеруа-Левенштейна, Джаро-Винклера

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

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

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

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

Динамика

• Нахождение наибольшей нулевой подматрицы

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

• Метод Гаусса решения системы линейных уравнений
• Нахождение ранга матрицы
• Вычисление определителя матрицы методом Гаусса

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

• Интегрирование по формуле Симпсона
• Поиск корней методом Ньютона (касательных)
• Тернарный поиск

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

• Биномиальные коэффициенты
• Числа Каталана
• Ожерелья
• Расстановка слонов на шахматной доске
• Количество помеченных графов, связных помеченных графов, помеченных графов с K компонентами связности
• Генерация сочетаний из N элементов
• Лемма Бернсайда. Теорема Пойа
• Принцип включений-исключений

Теория игр

• Игры на произвольных графах. Метод ретроспективного анализа
• Теория Шпрага-Гранди. Ним

Расписания

• Задача Джонсона с одним станком
• Задача Джонсона с двумя станками
• Оптимальный выбор заданий при известных временах завершения и длительностях выполнения

Разное

• Игра Пятнашки: существование решения
• Дерево Штерна-Броко. Ряд Фарея
• Поиск подотрезка массива с максимальной/минимальной суммой