Аннотация:
Факультатив “Продвинутые алгоритмы и структуры данных” направлен на изучение подходов к решению задач из различных областей (математический анализ, дискретный анализ, теория графов, теория комбинаторных игр и др.) Лекционный материал состоит из описания алгоритмов и структур данных для решения различных алгоритмических задач, доказательств их асимптотических временных и пространственных сложностей(где необходимо), также включает разбор некоторых деталей реализации

Программа учебной дисциплины
«Продвинутые алгоритмы и структуры данных»

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

РазработчикКрахмалев Денис Сергеевич
Число кредитов6
Контактная работа (час.)120
Самостоятельная работа (час.)108
Курс, Образовательная программаКурс не указан,ОП не указана
Формат изучения дисциплиныБез использования онлайн курса


1. Цель, результаты освоения дисциплины и пререквизиты
Цели:
  1. Дать слушателям представление о ходе работы алгоритмов для решения задач из различных областей программирования
  2. Научиться использовать инструменты для их асимптотической оценки
  3. Уметь реализовать эти алгоритмы вне зависимости от языка программирования
Планируемые результаты обучения (ПРО):
  1. Знать и уметь реализовывать основные алгоритмы сортировки
  2. Знать и уметь реализовывать деревья поиска
  3. Знать и уметь реализовывать хеш-таблицы для хранения разных типов данных
  4. Освоить базовые понятия теории графов, уметь решать задачи на этту тему
  5. Знать и уметь реализовывать основные алгоритмы поиска кратчайших путей в графе
  6. Освоить понятие динамического программирования и уметь решать смежные задачи
  7. Знать и уметь реализовывать основные алгоритмы поиска максимального потока в графе и построения остовного дерева
  8. Знать и уметь реализовывать основные алгоритмы для поиска подстроки в строке
  9. Знать и уметь реализовывать основные суффиксные структуры данных
  10. Уметь программно решать геометрические задачи
  11. Знать и уметь реализовывать основные алгоритмы длинной арифметики
  12. Освоить теорию комбинаторных игр
2. Содержание учебной дисциплины
Тема (раздел дисциплины)Объем в часахПланируемые результаты обучения (ПРО), подлежащие контролюФормы контроля
лк
см/пр
onl/cр
1. Базовые алгоритмы и структуры данных 4
  1. Знать и уметь реализовывать основные алгоритмы сортировки
1.
0
2
2. Сортировки и порядковые статистики8
  1. Знать и уметь реализовывать основные алгоритмы сортировки
1.
0
4
3. Хеш-таблицы4
  1. Знать и уметь реализовывать хеш-таблицы для хранения разных типов данных
1.
0
2
4. Деревья поиска8
  1. Знать и уметь реализовывать деревья поиска
1.
0
4
5. Теория графов8
  1. Освоить базовые понятия теории графов, уметь решать задачи на этту тему
1.
0
4
6. Поиск путей в графе6
  1. Знать и уметь реализовывать основные алгоритмы поиска кратчайших путей в графе
1.
0
3
7. Динамическое программирование4
  1. Освоить понятие динамического программирования и уметь решать смежные задачи
1.
0
2
8. Остовные деревья. Поиск максимального потока в графе8
  1. Знать и уметь реализовывать основные алгоритмы поиска максимального потока в графе и построения остовного дерева
2.
0
4
9. Задачи LCA и RMQ4
  1. Знать и уметь реализовывать основные алгоритмы поиска максимального потока в графе и построения остовного дерева
2.
0
2
10. Строки. Поиск подстроки в строке6
  1. Знать и уметь реализовывать основные алгоритмы для поиска подстроки в строке
2.
0
3
11. Суффиксные структуры на строках8
  1. Знать и уметь реализовывать основные суффиксные структуры данных
2.
0
4
12. Геометрия8
  1. Уметь программно решать геометрические задачи
2.
0
4
13. Длинная арифметика2
  1. Знать и уметь реализовывать основные алгоритмы длинной арифметики
2.
0
1
14. Теория комбинаторных игр4
  1. Освоить теорию комбинаторных игр
2.
0
2
Часов по видам учебных занятий:82
0
41
Итого часов:123

Просьба уточнить количество часов контактной работы. В разделе "Общие сведения" указано 120, по таблице получается 82
Просьба уточнить количество часов самостоятельной работы. В разделе "Общие сведения" указано 108, по таблице получается 41.
Содержание разделов дисциплины:
  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. Строки. Поиск подстроки в строке
    Понятие префикс, суффикс, подстрока. Понятие собственных префикса и суффикса. Постановка задачи поиска подстроки в строке. Тривиальный алгоритм поиска подстроки в строке. Префикс-функция. Тривиальный алгоритм нахождения. Линейный алгоритм нахождения. Доказательство времени работы Подсчет префикс-функции для строки qt,гдеqобразец,аtтекст.АлгоритмКнутаМоррисаПратта.Поточнаяобработкатекстабезхраненияпрефиксфункциидлявсейстрокиqt. 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 Ретро-анализ. Нахождение хода в оптимальной стратегии во время ретро-анализа Минимакс. Оценка состояния игры эвристикой. Альфа-бета отсечение
3. Оценивание

Формула округления: Стандартное арифметическое округление
Шкала оценки: Десятибалльная
Вид формулы оценивания: Линейная
Формула оценивания:

Окончательная оценка = Экз1


4. Примеры оценочных средств

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


5. Ресурсы
5.1. Рекомендуемая основная литература
п/пНаименование
1Роберт Седжвик Algorithms in C++
2Дональд Кнут The Art of Computer Programming
3Bernhard von Stengel Lecture Notes on Game Theory
4Муртаф Б Современное линейное программирование
5Новиков И. А. Дискретная математика для программистов
6Кормен Томас Х., Лейзерсон Чарльз И., Ривест Рональд Л., Штайн Клиффорд Алгоритмы. Построение и анализ

5.2. Рекомендуемая дополнительная литература
Не требуется

5.3. Программное обеспечение
п/пНаименованиеУсловия доступа/скачивания
1Microsoft Windows 7 Professional RUS
Microsoft Windows 8.1 Professional RUS
Microsoft Windows 10
Из внутренней сети университета (договор)
2Microsoft Office Professional Plus 2010Из внутренней сети университета (договор)

5.4. Профессиональные базы данных, информационные справочные системы, интернет-ресурсы (электронные образовательные ресурсы)
п/пНаименованиеУсловия доступа/скачивания
Профессиональные базы данных, информационно-справочные системы
1Электронно-библиотечная система ЮрайтURL: https://biblio-online.ru/
Интернет-ресурсы (электронные образовательные ресурсы)
1Открытое образованиеURL: https://openedu.ru/

5.5. Материально-техническое обеспечение дисциплины
Учебные аудитории для лекционных по дисциплине обеспечивают использование и демонстрацию тематических иллюстраций, соответствующих программе дисциплины в составе:
- ПЭВМ с доступом в Интернет (операционная система, офисные программы, антивирусные программы);
- мультимедийный проектор с дистанционным управлением.
Учебные аудитории для семинарских и самостоятельных занятий по дисциплине оснащены ПЭВМ, с возможностью подключения к сети Интернет и доступом к электронной информационно-образовательной среде НИУ ВШЭ.

6. Особенности организации обучения для лиц с ограниченными возможностями здоровья и инвалидов
В случае необходимости, обучающимся из числа лиц с ограниченными возможностями здоровья (по заявлению обучающегося) а для инвалидов также в соответствии с индивидуальной программой реабилитации инвалида, могут предлагаться следующие варианты восприятия учебной информации с учетом их индивидуальных психофизических особенностей, в том числе с применением электронного обучения и дистанционных технологий:
6.1.1. для лиц с нарушениями зрения: в печатной форме увеличенным шрифтом; в форме электронного документа; в форме аудиофайла (перевод учебных материалов в аудиоформат); в печатной форме на языке Брайля; индивидуальные консультации с привлечением тифлосурдопереводчика; индивидуальные задания и консультации.
6.1.2. для лиц с нарушениями слуха: в печатной форме; в форме электронного документа; видеоматериалы с субтитрами; индивидуальные консультации с привлечением сурдопереводчика; индивидуальные задания и консультации.
6.1.3. для лиц с нарушениями опорно-двигательного аппарата: в печатной форме; в форме электронного документа; в форме аудиофайла; индивидуальные задания и консультации.