12 января 2019. Графы

1. Алгоритмы Прима, Крускала, Борувки и их применения.

2. Продвинутые применения СНМ.

19 января 2019. Геометрия

1. Выпуклая оболочка, 2 алгоритмы построения (за \(O(n \log n)\) и за \(O(n \cdot ans)\)

2. Проверка на принадлежность точки прямоугольнику с помощью пускания прямой, подсчёта площади и подсчёта углов за \(O(n)\), а так же для выпуклого многоугольника за \(O(n \log n)\)

3. Выпуклый многоугольник: Построение касательной, пересечение с прямой, за \(O(\log n)\)

4. Нахождение 2 самых дальних точек за \(O(n \log n)\), нахождение 2 ближайших точек за \(O(n \log n)\)

5. Вероятностные алгоритмы: Монте-Карло, построение мин. покрывающей окружности за \(O(n)\)

2 февраля 2019. Кучи деревьев

1. Биномиальная куча

2. Splay-дерево

9 февраля 2019. Теория вероятностей и линейная алгебра

1. Вероятность, математическое ожидание, линейность математического ожидания

2. Вероятностные алгоритмы: случайная перестановка за \(O(n)\), \(k\)-я порядковая статистика за \(O(n)\), сортировка случайно сгенерированного массива за \(O(n)\)

3. Алгоритмы с маленькой вероятностью ошибки: нахождение отрезке массива числа, которое встречается хотя-бы половину от длины отрезка раз, проверка что произведение чисел в 2 массивах равно без длинной арифметики за \(O(n)\).

4. Алгоритм Гаусса

5. Матрица, возведение матрицы в степень, нахождение \(n\)-го числа, заданного рекурентой за \(O(\log n)\), нахождение числа путей длины \(k\) между каждой парой вершин графа за \(O(n^3 \log k)\)

16 февраля — 2 марта 2019. Потоки

1. Определение сети, потока, величины потока, пропускной способности ребра, разреза, величины разреза, остаточной сети, увеличивающего пути

2. Основные свойства потока: величина разреза равна величине потока, связь величины потка и существования увеличивающего пути, Теорема Форда-Фалкирсона (максимальный разрез равен минимальному потоку)

3. Алгоритм Форда-Фалкирсона, алгоритм Эдмондса-Карпа, их асимптотики, масштабирование потока, изменение асимптотик этих алгоритмов при добавлении масштабирования

4. Алгоритм Диница, его асимптотика

5. Алгоритм проталкивания предпотока*

6. Доказательство корректности поиска потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости

7. Алгоритмы поиска потока минимальной стоимости с помощью Форда-Беллмана, ускорение его при помощи очереди, использование потенциалов Джонсона при поиске потока минимальной стоимости

8. Венгерский алгоритм

9 марта 2019. Симплекс

1. Симплекс метод*

16 марта 2019. Сложные графы

1. Поиск паросочетания в произвольном графе

2. Алгоритм 2 китайцев поиска минимального остовного дерева в ориентированном графе

3. Построение дерева доминаторов

23 марта 2019. Неточные решения NP-полных задач

1. Алгоритм отжига, генетический алгоритм

20 апреля 2019. Матроиды

1. Определение матроида, 3 аксиомы, примеры матроида, база матроида, 2 варианта эквивалентной замены 3-й аксиомы

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

27 апреля 2019. Алгоритмы во внешней памяти

1. Общие представления, время работы простейших алгоритмов: разворота массива, merge 2 массивов, сортировки массива, задачи Join.

2. Задача list-ranking, решение за \(O\left(\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B} \log n\right)\) и \(O\left(\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}\right)\)

3. Алгоритм списка с возможностью перехода к \(k\)-му следующему элементу за \(O\left(\frac{k}{B}\right)\), алгоритм \(B\)-дерева.

4. Heap во внешней памятью со всеми операциями за \(O\left(\frac{1}{B}\log_{\frac{M}{B}}\frac{N}{B}\right)\)*

5. BFS во внешней памяти за \(O\left(Sort(E) + \frac{Scan(E)}{\sqrt{\frac{E}{VB}}} + V \cdot\sqrt{\frac{E}{VB}}\right) = O\left(Sort(E) + \sqrt{\frac{VE}{B}}\right)\)*

11 мая 2019. Link-cut

1. Алгоритм Link-cut, доказательство асимптотики \(O(n \log^2 n)\).