Утверждена
Академическим советом ОП
Протокол №_____ от _______._______.20_______

1. Дать слушателям представление о ходе работы алгоритмов для решения задач из различных областей программирования
2. Научиться использовать инструменты для их асимптотической оценки
3. Уметь реализовать эти алгоритмы вне зависимости от языка программирования

1. Знать и уметь реализовывать основные алгоритмы сортировки
2. Знать и уметь реализовывать деревья поиска
3. Знать и уметь реализовывать хеш-таблицы для хранения разных типов данных
4. Освоить базовые понятия теории графов, уметь решать задачи на этту тему
5. Знать и уметь реализовывать основные алгоритмы поиска кратчайших путей в графе
6. Освоить понятие динамического программирования и уметь решать смежные задачи
7. Знать и уметь реализовывать основные алгоритмы поиска максимального потока в графе и построения остовного дерева
8. Знать и уметь реализовывать основные алгоритмы для поиска подстроки в строке
9. Знать и уметь реализовывать основные суффиксные структуры данных
10. Уметь программно решать геометрические задачи
11. Знать и уметь реализовывать основные алгоритмы длинной арифметики
12. Освоить теорию комбинаторных игр

1. Базовые алгоритмы и структуры данных
   Определение алгоритма. Примеры простых алгоритмов: вычисление числа Фибоначчи, проверка числа на простоту, быстрое возведение в степень. Определение структуры данных, абстрактного типа данных (интерфейса). Динамический массив. Двусвязный и односвязный список. Стек. Очередь. Дек. Хранение стека, очереди и дека в массиве. Циклическая очередь в массиве. Хранение стека, очереди и дека в списке. Массив. Линейный поиск. Бинарный поиск. Поддержка минимума в стеке. Асимптотические обозначения, работа с ними. Асимптотика простых алгоритмов Амортизационный анализ. Амортизированное (учетное) время добавления элемента в динамический массив. Оценка амортизированной сложности: метод потенциалов, метод бухучёта Представление очереди в виде двух стеков. Время извлечения элемента. Поддержка минимума в очереди. Двоичная куча. АТД “Очередь с приоритетом”. Персистентный стек. Формулировка задачи. Устойчивость, локальность. Квадратичные сортировки: сортировка вставками, выбором. Сортировка слиянием. Сортировка с помощью кучи. Слияние K отсортированных массивов с помощью кучи.
2. Сортировки и порядковые статистики
   TimSort Быстрая сортировка. Выбор опорного элемента. Доказательство среднего времени работы. Интроспективная сортировка + современные варианты Нижняя оценка времени работы для сортировок сравнением. Сортировка подсчетом. Карманная сортировка. Поразрядная сортировка. MSD, LSD. Сортировка строк. Binary QuickSort. Поиск k-ой порядковой статистики за линейное время. Интерполяционная сортировка (до 2 порядка) Внешние сортировки Сортировочные сети Сети Бэтчера, битонический сортировщик Мастер-теорема(основная теорема об оценках) с доказательством
3. Хеш-таблицы
   Хеш-функции. Остаток от деления, мультипликативная. Полиномиальная. Ее использование для строк. Метод Горнера для уменьшения количества операций умножения при ее вычислении. Хеш-таблицы. Понятие коллизии. Метод цепочек (открытое хеширование). Метод прямой адресации (закрытое хеширование). Линейное пробирование. Проблема кластеризации. Квадратичное пробирование. Двойное хеширование. Фильтры Блума
4. Деревья поиска
   Определение дерева, дерева с корнем. Высота дерева, родительские, дочерние узлы, листья. Количество ребер. Обходы в глубину. pre-order, post-order и in-order для бинарных деревьев. Обход в ширину. Дерево поиска. Поиск ключа, вставка, удаление. Необходимость балансировки. Три типа самобалансирующихся деревьев. АВЛ-дерево. Вращения. Сплей-дерево. Операция Splay. Поиск, вставка, удаление в сплей-дереве. Декартово дерево. Оценка средней высоты декартового дерева при случайных приоритетах (без доказательства). Построение за O(n), если ключи упорядочены. Декартово дерево по неявному ключу. Интерфейс быстрого массива: Доступ к элементу в позиции i, Вставка элемента в позицию i, Удаление элемента из позиции i, Конкатенация двух массивов, разделение массива на два. Нерезидентные деревья Красно-черное дерево. B-деревья. K-D-дерево
5. Теория графов
   Ориентированный граф, неориентированный граф, псевдограф. Обход в глубину. Цвета вершин. Времена входа и выхода. Лемма о белых путях. Проверка связности неориентированного графа. Поиск цикла в неориентированном и ориентированном графе. Топологическая сортировка. Связность в неор. графе, компоненты связности. Слабая и сильная связность в ор. графе. Компоненты слабой, сильной связности. Нахождение компонент сильной связности. Алгоритм Косарайю с доказательством корректности. Алгоритм Тарьяна с доказательством корректности. Компоненты реберной двусвязности. Мосты. Поиск мостов. Компоненты вершинной двусвязности. Точки сочленения. Поиск точек сочленения. Волновой алгоритм. Обход в ширину (применение очереди в волновом алгоритме). Критерий существования Эйлерова пути и цикла в ориентированном и неориентированном графе. Поиск эйлерова пути и цикла. Гамма-алгоритм. Доказательство корректности Алгоритм Дейкстры. Доказательство корректности. Оценка времени работы. Дерево кратчайших путей. Потенциалы. Условие применимости алгоритма Дейкстры для измененных длин ребер. Потенциал π(v) = ρ(v, t). Двусторонний алгоритм Дейкстры.
6. Поиск путей в графе
   Алгоритм Флойда. Доказательство. Восстановление пути. Нахождение цикла отрицательного веса. Алгоритм Форда-Беллмана. Хранение в матрице: Dvk равно длине кратчайшего пути до вершины v за ровно k ребер (не более k ребер). Доказательство корректности. Оценка времени работы. Восстановление пути. Детектирование цикла отрицательного веса. Поиск самого цикла. Нахождение кратчайших путей с учетом циклов отрицательного веса. Алгоритм Джонсона. Добавление фиктивного корня и фиктивных ребер для запуска алгоритма Форда-Беллмана. Алгоритм Йена Алгоритм Левита, поиск цикла минимального веса. Алгоритм A*. Условие монотонности на эвристику. Допустимость эвристики. Примеры эвристик.
7. Динамическое программирование
   Общая идея жадных алгоритмов. Задача о рюкзаке. Динамическое программирование. Восходящее ДП. Нисходящее ДП, кэширование результатов. Вычисление чисел Фибоначчи. Нахождение наибольшей возрастающей подпоследовательности за O(N2) и за O(N log N) Расстояние Левенштейна. Восстановление редакционного пути Задача Коммивояжёра. Метод ветвей и границ Естественные алгоритмы. Алгоритм муравьиной колонии. Алгоритм роя пчёл (два варианта) Количество способов разложить число N на слагаемые. Количество способов разложить число N на различные слагаемые. Нахождение наибольшей общей подпоследовательности. Методы восстановления ответа в задачах динамического программирования.
8. Остовные деревья. Поиск максимального потока в графе
   Остовное дерево. Построение с помощью обхода в глубину и в ширину. Определение минимального остовного дерева. Теорема о разрезе. Доказательство. Алгоритм Прима. Аналогия с алгоритмом Дейкстры. Алгоритм Крускала. Доказательство. Оценка времени работы. Система непересекающихся множеств. Эвристика ранга с доказательством оценки времени работы. Эвристика сжатия пути без доказательства. Алгоритм Борувки. Доказательство. Оценка времени работы. Приближение решения задачи коммивояжера с помощью минимального остовного дерева. Алгоритм двух китайцев для ориентированного графа Упражнение: мин.остов за eloglogv (комбинация Прима и Борувки) Определение сети. Определение потока. Физический смысл. Аналогия с законами Кирхгофа. Определение разреза. Понятия потока через разрез. Доказательство факта, что поток через любой разрез одинаковый. Понятие остаточной сети. Понятие дополняющего пути. Необходимость отсутствия дополняющего пути для максимальности потока. Теорема Форда-Фалкерсона. Алгоритм Форда-Фалкерсона. Поиск минимального разреза. Пример целочисленной сети, в котором алгоритм работает долго. Алгоритм Эдмондса-Карпа. Доказательство, что кратчайшее расстояние в остаточной сети не уменьшается. Общая оценка времени работы алгоритма Эдмондса-Карпа. Алгоритм проталкивания предпотока Алгоритм Малхотры — Кумара — Махешвари Слоистая сеть. Алгоритм Диница. Оценка времени работы. Паросочетания. Паросочетание в двудольном графе. Максимальное паросочетание. Чередующие пути. Увеличивающие пути. Теорема Бержа. Сведение поиска максимального паросочетания к поиску максимального потока. Алгоритм Куна.
9. Задачи LCA и RMQ
   RSQ и RMQ. Sparse-table. Дерево отрезков. Обработка запросов от листьев. Обработка запросов от корня. Изменение значения в массиве, обновление дерева отрезков. Множественные операции. LCA. Метод двоичного подъема. Сведение LCA к задаче RMQ. Сведение RMQ к задаче LCA.
10. Строки. Поиск подстроки в строке
    Понятие префикс, суффикс, подстрока. Понятие собственных префикса и суффикса. Постановка задачи поиска подстроки в строке. Тривиальный алгоритм поиска подстроки в строке. Префикс-функция. Тривиальный алгоритм нахождения. Линейный алгоритм нахождения. Доказательство времени работы Подсчет префикс-функции для строки q$t, где q — образец, а t — текст. Алгоритм Кнута-Морриса-Пратта. Поточная обработка текста без хранения префикс-функции для всей строки q$t. Z-функция. Тривиальный алгоритм нахождения. Линейный поиск Z-функции. Доказательство времени работы Применение для поиска подстроки в строке (КМП-2). Хранение Z-функции только для образца, а не для всей строки q$t. Построение строки по z-функции Построение Префикс-функции строки при известной z-функции Структура данных Бор. Построение, оценка времени построения и объема памяти. Алгоритм Ахо-Корасик. Суффиксная ссылка. Построение бора. Построение суффиксной ссылки. Оценка времени работы. Ситуации, когда один образец является суффиксом другого. «Длинные» суффиксные ссылки, то есть ссылки, идущие в следующую терминальную вершину, которая является суффиксом текущей. Построение автомата переходов. Построение переходов по буквам с учетом перемещения по суффиксным ссылкам. Кэширование переходов. Бор с суффиксными ссылками для одного шаблона. Аналогия с префикс-функцией.
11. Суффиксные структуры на строках
    Суффиксный массив. Построение за O(n^2 log n). Поиск подстроки в тексте с использованием суффиксного массива. Построение суффиксного массива за O(n log n) с помощью удвоения префикса, по которому происходит цифровая сортировка. Алгоритм Касаи. Доказательство времени работы. Суффиксное дерево. Сжатое суффиксное дерево. Хранение сжатого суффиксного дерева. Тривиальное построение сжатого суффиксного дерева. Линейность числа вершин и ребер. Алгоритм Итальяно Обновление дерева при добавлении одного символа в конец строки. Два случая: создание нового листа и проход вдоль ребра. Эвристика листа. Добавление бесконечного числа символов на ребро при добавлении листа. Суффиксная ссылка. Инвариант: для всех внутренних вершин вычислена суффиксная ссылка. Доказательство факта, что суффиксная ссылка ведет всегда в вершину. Переход к суффиксу меньшего размера и подсчет суффиксной ссылки для вновь созданной вершины. Быстрый спуск, обоснование его допустимости. Алгоритм Укконена. Потенциалы для доказательства времени работы. Потенциал по длине слова, соответствующего вершине. Потенциал по количеству промежуточных вершин от корня. Доказательство асимптотики
12. Геометрия
    Введение. Точка, вектор, отрезок. Скалярное произведение, векторное произведение. Прямая, плоскость. Выпуклая оболочка 2D. Алгоритм Джарвиса. Алгоритм Грэхема. Метод в 2D «Разделяй и властвуй» за O(n log n). Упражнение: Чан в 2Д Выпуклая оболочка 3D. Заворачивание подарка за O(n^2). Метод в 3D «Разделяй и властвуй» за O(n log n) Алгоритм Чана Сумма Минковского двух выпуклых многоугольников за O(m + n). Сканирующая прямая. Проверка факта пересечения какой-либо пары отрезков из множества за O(n log n). Триангуляция Делоне. Сведение к поиску выпуклой оболочки в 3D. ЕМОД - Евклидово минимальное остовное дерево. Достаточность использования ребер триангуляции Делоне. O(V log V). Диаграмма Вороного. Эквивалентность триангуляции Делоне. Построение диаграммы Вороного по схеме: Выпуклая оболочка 3D –> Триангуляция Делоне –> Диаграмма Вороного. O(n log n). Алгоритм Форчуна.
13. Длинная арифметика
    Длинная арифметика. Умножение. Алгоритм Карацубы. Деление. Преобразование Фурье. Дискретное преобразование Фурье. Быстрое преобразование Фурье.
14. Теория комбинаторных игр
    Математические игры. Игра с камнями. Есть N камней, игрок может брать от 1 до K камней. Побеждает игрок, взявший последний камень. Модификация: проигрывает игрок, который взял последний камень. Игра в монеты за круглым столом. Игроки по очереди кладут круглые монеты на круглый стол так, чтобы они не пересекались. Игрок, который не может сделать ход, проигрывает. Метод симметричной стратегии. Игры на графе. Выигрышные и проигрышные вершины. Классификация игр. Нормальные и ненормальные игры. Нормальной называют игру, в которой листья проигрышные. Сведение ненормальной игры к нормальной. Справедливые и несправедливые игры. Справедливые, когда каждый игрок из одной позиции может делать такие же ходы, как и противник. Пример не справедливой игры: шахматы, шашки. Случайные/детерминированные. Выигрышная и проигрышная стратегия. Определение оптимальной стратегии с учетом количества ходов. Поиск оптимальной стратегии в ациклических графах. Min-Max. Теорема Шпрага-Гранди. Эквивалентности игр. Игра Ним. Теорема Шпрага-Гранди II Ретро-анализ. Нахождение хода в оптимальной стратегии во время ретро-анализа Минимакс. Оценка состояния игры эвристикой. Альфа-бета отсечение

• 1, Не блокирующее, Экзамен (устный)
  
• 2, Не блокирующее, Экзамен (устный)