Tinkoff Generation

Алгоритмы. 3 курс. План занятий второго полугодия

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)\).