Асимптотика, инструменты и merge-sort ------------------------------------- - Асимптотика, обозначения O, Theta, Omega, o, w; их свойства, использование в контексте памяти и времени алгоритма - Мастер-теорема - Экспоненциальные рекурренты - merge-sort с линейной доппамятью, merge. Стабильность merge-sort Бинарный поиск, простые структуры данных, Куча ---------------------------------------------- - Связный список - Простые структуры данных: вектор (расширение за O(1)) - Простые структуры данных: stack, queue, deque, реализации через LinkedList и на массиве - Бинарный поиск: поиск элемента в массиве - Бинарный поиск: lower_bound - Бинарный поиск: пример задачи на бинпоиск по ответу - Бинарная куча: min(), add(), extractMin(), decreaseKey() - Бинарная куча: построение за O(n) (д-во O(n) на практике) - Бинарная куча: heap sort (как получить O(1) памяти на практике) На практике: min на очереди Быстрая сортировка, квадратичные сортировки ------------------------------------------- - Квадратичные сортировки: Selection sort - Квадратичные сортировки: Bubble sort - Квадратичные сортировки: Insertion sort - Quicksort с делением на три части (x). - Вероятность в алгоритмах: Probabilistic vs Randomized - Доказательство quicksort через оценку на число сравнений - Доказательство quicksort через рекуренты и интеграл - (*) IntroSort, TimSort - Порядковая статистика через одноветочный quicksort Сортировки, нижняя оценка, median of medians, разное ---------------------------------------------------- - Нижняя оценка числа сравнений в сортировке через сравнения, детерминированные алгоритмы - Детерминированный алгоритм поиска порядковой статистики (median of medians). - count_sort, в том числе стабильно. Сортировка пар чисел, digit sort. - (*) merge sort без рекурсии и аллокация памяти только один раз - жадность: выполнить все задачи к дедлайнам. (*) На практике: больше жадных примеров. Динамическое программирование ----------------------------- Динамическое программирование, введение Прыжки по полоске на 3-5 шагов, числа фибоначчи. Концепция динамики вперёд/назад/лениво Путь на матрице восстановление ответа с массивом предков и без Рюкзак без стоимостей (subset sum). Восстановление ответа. Наибольшая возрастающая подпоследовательность за O(n^2) Редакционное расстояние за O(n^2) На практике: рюкзак со стоимостями На практике: наибольшая общая подпоследовательность На практике: наибольшая возрастающая подпоследовательность за O(n log n) Динамическое программирование 2 ------------------------------- Задача НОП Алгоритм Хиршберга (в контексте НОП) Коды Хаффмана Упорядоченные беспрефиксные коды (дп за куб) Динамика по подмножествам: гамильтонов путь за O(2^n n) На практике: эффективный перебор подмножеств На практике: хроматическое число графа На практике: Set Cover через динамическое программирование Графы, DFS ---------- Хранение графа: матрица смежности, списки смежности, мульти-список смежности Поиск в глубину Применения DFS: компоненты связности, поиск пути, двудольность Классификация рёбер (в неор. графе, в ор. графе) Поиск цикла в неорграфе (обратное ребро) Поиск цикла в ор графе (пометки вершин в три цвета) Топологическая сортировка через времена выхода Мосты SCC, 2-SAT, Euler ----------------- Компоненты сильной связности (алгоритм Kosaraju) 2-SAT Эйлеров цикл в неориентированном графе и сведение эйлерова пути Топологическая сортировка через очередь Bfs, Dijkstra, A-star --------------------- Bfs Dijkstra (за O(V^2 + E) и за O(E log V)) A-star ((*) д-во что если верна консистентность, то A-star эквив. Дейкстре). На практике: 0-1 bfs, 0-k bfs (*) На практике: A-star (если h(v) <= dist(v, t) то найдём верный путь). Bellman-Ford, Floyd-Warshall ---------------------------- Алгоритм Bellman-Ford Проверка существования отр. цикла Восстановление пути (если нет отр. цикла) Алгоритм Floyd-Warshall Проверка существования отр. цикла Проблема переполнения MST, DSU -------- Лемма о разрезе (о ребре) Алгоритм Прима (O(V^2), или O(E log V)) Алгоритм Крускала Снм: реализация на списках (small to large) Снм: древесная реализация. Эвристика сжатия путей и рангов. Доказательство оценки log(n) для ранговой эвристики (*) Доказательство оценки log(n) для сжатия путей Строки ------ Z-функция pi-функция Применения к поиску подстроки в строке Бор Ахо-Корасик ----------- Алгоритм КМП (версия без замыкания до автомата). Ахо-Корасик (версия без замыкания до автомата). Построение суфссылок за линейное от суммарный длины строк время. На практике: замыкание Ахо-Корасика до автомата