Алгоритмы и структуры данных


Первый семестр.
1. Введение.
Вычисление чисел Фибоначчи (с рекурсией и без). Сортировка вставками. Время работы алгоритма. Скорость роста функций (логарифм, полином, экспонента). Анализ времени работы алгоритмов.
2. Числовые алгоритмы.
Элементарная арифметика: сложение, умножение, деление. Арифметика сравнений: сложение, умножение, возведение в степень, алгоритм Евклида, расширенный алгоритм Евклида, деление. Проверка чисел на простоту. Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA. Универсальное хеширование.
3. Рекуррентные соотношения.
Умножение чисел (простой рекурсивный алгоритм, улучшенный алгоритм). Рекуррентные соотношения.
4. Элементарные структуры данных.
Список и массив (массив и список как структуры данных, поддерживающие основные словарные операции; сравнение по времени и по памаяти). Расширяющийся массив (почему массив нужно увеличивать не на константу, а в константу раз). Стек и очередь.
5. Более сложные структуры данных.
Хеш-таблица (хеширование с открытой адресацией, хеширование со списками, хеш-функции для чисел и строк). Корневое дерево (бинарное дерево, дерево с произвольным ветвлением, представление "левый ребёнок — правый сосед"). Двоичное дерево поиска (все операции выполняются за время, пропорциональное высоте). АВЛ- дерево (как поддерживать дерево сбалансированным при вставке и удалении). Очередь с приоритетами (структура данных, позволяющая удалять, вставлять и находить минимум/максимум; сравнение реализаций массивом, отсортированным массивом, кучей).
6. Алгоритмы сортировки.
Сортировка слиянием. Сортировка с помощью кучи. Нижняя оценка $\Omega(n \log n)$ для сортировки. Быстрая сортировка. Сортировка подсчётом и цифровая сортировка. Порядковые статистики (нахождение за линейное в среднем и худшем случае время).
7. Декомпозиция графов.
Графы и способы их представления: способы использования графов; способы представления графов: список рёбер, матрица смежности, списки смежности; плюсы и минусы каждого из подходов. Поиск в глубину в неориентированных графах: обход вершин, достижимых из данной; рёбра дерева и обратные рёбра; время работы поиска в глубину. Связность неориентированных графов: выделение компонент связности неориентированного графа. Поиск в глубину в ориентированных графах: типы рёбер: ребро дерева, прямое, обратное, пересекающее. Ориентированные ациклические графы: в графе есть цикл тогда и только тогда, когда поиск в глубину находит обратное ребро; топологическая сортировка вершин - в порядке уменьшения post-значений; наличие стока и истока в ациклическом графе.
8. Пути в графах.
Расстояния в графе: определение расстояния между двумя вершинами. Поиск в ширину: обход вершин графа в порядке увеличения расстояний от исходной вершины; дерево кратчайших путей; доказательство корректности; оценка на время работы; сравнение с поиском в глубину. Алгоритм Дейкстры: адаптация поиска в ширину введением дополнительных вершин; установка будильников; алгоритм Дейкстры; альтернативный взгляд на алгоритм: последовательное расширение множества вершин, до которых расстояние уже посчитано; время работы алгоритма при различных реализациях очереди с приоритетами. Кратчайшие пути при наличии рёбер отрицательного веса: вызов update для всех ребер графа; алгоритм Беллмана-Форда; определение наличия цикла отрицательного веса в графе. Кратчайшие пути в ациклических ориентированных графах: достаточно перебирать вершины в порядке топологиечской сортировки и вызывать update для всех соседей.
9. Максимальный поток.
Определение сети и потока; задача линейного программирования. Метод Форда-Фалкерсона: определение остаточной сети; $c_f(u,v)$ может превосходить $c(u,v)$, остаточное ребро не обязано быть ребром исходной сети; определение дополняющего пути и разреза и их пропускных способностей; теорема о максимальном потоке и минимальном разрезе; метод Форда-Фалкерсона. Алгоритм Эдмондса-Карпа: дополнение вдоль кратчайшего пути в остаточной сети; доказательство верхней оценки $O(VE)$: расстояние в отсаточной сети до каждой вершины не убывают, каждое ребро может стать критическим $O(V)$ раз. Алгоритм проталкивания предпотока: определения предпотока, высотной функции для предпотока; операции поднятия вершины и проталкивания предпотока; доказательство корректности алгоритма: в течение работы алгоритма в остаточной сети нет пути из изстока в сток; оценка времени работы: оценка количества подъёмов, а также насыщающих и ненасыщающих проталкиваний.
10. Жадные алгоритмы.
Задача о выборе заявок. Минимальное покрывающее дерево. Коды Хаффмена. Покрытие множествами. Вершинное покрытие.
11. Динамическое программирование.
Ещё раз о кратчайших путях в ациклических ориентированных графах: нахождение расстояний в порядке топологической сортировки вершин. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом. Стоимость редактирования: граф на подзадачах, нахождение кратчайшего пути в данном графе. Задача о рюкзаке: рюкзак с повторениями и без, ленивые вычисления. Перемножение нескольких матриц: представление порядка перемножения в виде дерева, оценка на количество порядков. Независимые множества в деревьях Кратчайшие пути: кратчайшие пути для всех вершин графа, задача о коммивояжере.
12. Поиск подстроки в строке.
Простейший $O(mn)$ алгоритм. Нахождение подстроки при помощи конечного автомата: общие идеи; примеры для строчек ${\tt abcd}$ и ${\tt ababc}$. Алгоритм Кнута-Морриса-Пратта: $l(X)$ — самое длинное начало $X$, являющееся одновременно и его концом и не совпадающее с $X$; вычисление $l$ для всех префиксов заданной строки за линейное время; пример для строки ${\tt ababababca}$.
13. Поиск подстроки в строке.
Построение суффиксного дерева и массива за линейное время.
Второй семестр.
14. Базовые геометрические алгоритмы.
15. Быстрое преобразование Фурье.
Быстрое вычисление значений многочлена в точках: два способа задания многочленов — коэффициентами и значениями в точках; вычисление значений многочлена в точках методом "разделяй и властвуй"; дискретное преобразование Фурье; быстрое преобразование Фурье. Интерполяция: интерполяция в терминах матриц; матрица Вандермонда; интерполяция как домножение на обратную матрицу.
16. Вероятностные алгоритмы.
Проверка результата перемножения матриц. Проверка равенства длинных строк. Проверка равенства многочленов. Проверка эквивалентности ветвящихся программ.
17. Вероятностные алгоритмы.
Вероятностный алгоритм для нахождения минимального сечения. Нахождение кратчайших расстояний между всеми парами вершин графа. Минимальное покрывающее дерево.
18. Алгоритмы, обрабатывающие вход по мере поступления.
Алгоритмы для задачи кэширования и задачи о покрытии множествами.
19. NP-полные задачи.
Введение: во многих задачах решение ищется среди экспоненциального большого множества кандидатов. Задача пропозициональной выполнимости: задача поиска; алгоритм, задающий задачу поиска. Задача о коммивояжере: оптимизационные задачи и задачи поиска; сравнение с задачей о нахождении покрывающего дерева. Задачи о независимом множестве, вершинном покрытии и клике, длиннейший путь. Задача о рюкзаке и сумме подмножества: задача об унарном рюкзаке; задача о сумме подмножества как более просто формулирующася задача. Сложные и простые задачи: сравнение нескольких пар задач, которые формулируются похоже, но имеют разную сложность; простые задачи просты по многим различным причинам, в то время как сложные задачи сложны по одной и той же причине.
20. Точные алгоритмы для NP-полных задач.
$2^{\omega n/3}$ алгоритм для задачи о максимальном разрезе, основанный на быстром умножении матриц. $3^{n/2}$ алгоритм для задачи 3-выполнимости, основанный на локальном поиске. $2^{n/2}$ алгоритм для задачи о сумме подмножества, основанный на бинарном поиске.
21. Точные алгоритмы для NP-полных задач.
Алгоритмы, основанные на применении формулы включений-исключений.
22. Приближенные алгоритмы для NP-полных задач.
2-приближенный алгоритм для задачи о вершинном покрытии: на каждом шаге выбирается непокрытое ребро и оба его конца помещаются в множество. Задача о коммивояжере в метрическом пространстве: определение и доказательство NP-полноты. 2- и 3/2-приближенные алгоритмы для задачи о коммивояжере в метрическом пространстве. Неприближаемость задачи о коммивояжере в общем случае.
23. Приближенные алгоритмы для NP-полных задач.
Алгоритмы, основанные на решении задачи полуопределённого программирования.
Литература
  • Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, 2006.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, Cambridge, second edition, 2001.
  • А. Шень. Программирование: теоремы и задачи. М., МЦНМО, 2-е издание, 2004.
  • R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
Ссылки