1. Графы - база
1. dfs
2. bfs
3. ford-bellman, реализация с очередью
4. floyd
5. поиск отрицательного цикла
6. MST (Прим, Краскал)
2. Игры
1. Динамическое программирование, игры на ацикличных графах
2. Ретроанализ, игры на графах с циклами
3. Функция Гранди
4. Функция Смита
3. Перебор
1. Метод ветвей и границ. Отсечение по ответу.
2. Iterative Deepening. dfs vs bfs.
4. Приближенные методы
1. Локальные оптимизации
2. Генетический алгоритм
3. Отжиг
5. Вероятностыне алгоритмы
1. Las-Vegas
2. Monte-Karlo
3. Каргер-Штейн
6. Коммивояжер
1. MST x 2, MST x 3/2
2. Nearest
3. Локальные оптимизации для Коммивояжера
7. Двудольные графы
1. Паросочетание, контролирующее множество, независимое множество
2. Лемма о дополняющем пути
3. Лемма Холла
4. Алгоритм Куна
5. Алгоритм Хопкрофта-Карпа
6. Раскраска ребер двудольного графа
7. Покрытие ацикличного графа min числом цепей.
8. Теорема Дилворта.
8. Раскраски
1. Теорема Брукса
2. Теорема Визинга
3. Алгоритм раскраски вершин планарного графа в 6 цветов.
9. Потоки
1. Поток, разрез.
2. Теорема Форда-Фалкерсона.
3. Алгоритм Эдмондса.
4. Алгоритм Масштабирования потока.
5. Алгоритм Диница.
6. Вершинные поток и разрез. Поток и разрез (реберные и вершинные) в неорграфе.
7. MinCost поток. Отсутствие отрицательных циклов.
8. Лемма о дополняющем пути для MinCost потока.
9. Дейкстра с потенциалами.
10. Задача о назначениях, транспортная задача.
11. [L,R] потоки.
12. Алгоритм Штор-Вагнера
10. Декартовы деревья
1. Дерево по явному ключу. Операции Split и Merge.
2. K-th, Add(L, R), GetSum(L, R),
3. Дерево по неявному ключу. Reverse(L, R), Insert(i), Delete(i).
4. Построение за O(N) дерева по неявному ключу.
11. RSQ, RMQ, Деревья отрезков
1. RSQ: Неменяющийся массив
2. RMQ: Неменяющийся массив, Sparse table
3. RSQ: Меняющийся массив, дерево Фенвика.
4. RSQ, RMQ: Меняющийся массив, дерево отрезков.
5. Прибавление и присваивание на отрезке.
6. RSQ и RMQ на неменяющейся матрице
7. RSQ и RMQ на меняющейся матрице, двумерные деревья отрезков и Фенвика.
8. Квадродерево на матрице.
12. 2D-запросы и деревья
1. 2D дерево отрезков
2. КД-дерево
3. Дерево отрезков декартовых деревьев.
13. LCA, Функции на путях дерева
1. Разбиение дерева через LCA, Offline и Online задачи.
2. Offline поиск LCA.
3. 2 метода Online поиска LCA.
4. Веса ребер дерева не меняется, RSQ и RMQ
5. Веса ребер дерева меняется, RSQ и RMQ
6. Покрытие дерева путями, сведение запроса на пути к 2D запросу.
14. Численные методы
1. Бинарный поиск
2. Троичный поиск
3. Градиентный спуск
4. Усовершенствованные поиски
5. Поиск вещественных корней многочлена
15. Теория чисел
1. Решето Эратосфена
2. Тест Ферма, тест Миллера-Рабина.
3. Эвристика Полларда
16. Cтроки
1. Полиномиальный хэш
2. Хэштаблицы со списками и с открытой адресацией.
3. Коллизии у полиномиальных хэшей и хэш-таблицы
4. Задачи: Поиск слов в тексте, наибольшая общая подстрока, наибольший подпалиндром.
5. Суффиксный массив хэшами
6. Суффиксный массив цифровой сортировкой
7. LCP для суффиксного массива. Алгоритм Касаи.
8. Бор. Суф.дерево. Способы хранения бора.
9. Сжатый бор, сжатое суффиксное дерево, получение из суф.массив
10. Алгоритм Укконена.
11. Алгоритм Ахо-Корасика.
17. Паросочетания в произвольном графе
1. Лемма Татта-Берджа
2. Теорема о дополняющем чередующемся пути.
3. Алгоритм Эдмондса
4. Рандомизированный алгоритм
18. Матроиды
1. Определение. Алгоритм Радо-Эдмондса.
2. Графовый матроид.
3. Трансверсальный матроид (паросочетания).
4. Векторный матроид.
19. Планарные графы
1. Теоерема Эйлера
2. Укладка в R³, на сфере
3. Док-во того, что K_3,3 и K₅ не планарны. Теорема Куратовского.
4. Алгоритм Демукрона.
5. Алгоритм разбиение графа на грани. Выделение внешних граней.
20. 2-SAT
1. Формулировка 2-SAT, 3-SAT.
2. Жадное решение за O(VE), док-во.
3. Решение за O(E).
21. Нейрон
1. Задача классификации. Что такое нейрон. Разделение на >= 1 и <= t.
2. Обучение Нейрона с помощью Л.П.
3. Обучение Нейрона с помощью Градиентного спуска.
4. Решение задачи "Кто автор этого стиха? Пушкин или Лермонтов?"
5. Реализация Simplex метода.