Алгоритмы и структуры данных пилотный поток 2019/2020

Лектор: Глеб Олегович Евстропов

План учебной дисциплины

План учебной дисциплины, только лучше

Важные ссылки
Текущая успеваемость html-версия	Google.Classroom инвайт: hhp3okt	Запись на консультации

Формула выставления итоговой оценки

2, 5 модули: 0.3 · О_{контесты} + 0.25 · O_листки + 0.15 · O_КР + 0.3 · O_экз + O_бонус

3, 4 модули: 0.325 · Оконтесты + 0.3 · Oлистки + 0.075 · OКР + 0.3 · Oэкз + Oбонус

• О_{контесты} вычисляется по формуле:

  Оконтесты = 10 · (	КК + ДК	+	БЗ		), где:
  	ОЗ - поправка		ОЗ

  • КК — баллы за короткие контесты
  • ДК — баллы за длинные контесты (исключая бонусные задачи)
  • БЗ — баллы за бонусные задачи в длинных контестах
  • ОЗ — общее число задач во всех контестах (исключая бонусные задачи)
  • Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

  Виды контестов:

  • Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
  • Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
• О_листки вычисляется по формуле:

  Олистки = 10 ·	количество решённых задач
  	количество обязательных задач - поправка

  Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно во время присутственных часов, на консультациях ассистентам. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке.

• В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О_КР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
• За экзамен студент получает оценку от 0 до 10, эта оценка будет являться О_экз.
• Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).

Лекции и семинары

2 модуль

Дата Семинар Листочек Лекция 29 октября Понятие асимптотического времени работы алгоритма. Сильно-, слабо- и псевдополиномиальное время работы. Обозначения O, o, Ω, ω 64726976 Знакомство со структурой курса и системой выставления оценок.Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность 31 октября Совместное решение задач по теории вероятностей 652e676f Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства 5 ноября Совместное решение задач на мат. ожидание 6f676c65 Модель вычислений, описание RAM-модели. Три основных способа доказательства корректности на примере квадратичных сортировок. 7 ноября Короткий контест №1 12 ноября Разговор про тестирование не было Сортировки сравнения, схема доказательства времени работы по индукции, невозможность сортировки быстрее n log n. 14 ноября Сортировки и порядковые статистики 2e636f6d Сортировки, использующие значения элементов. Сортировка подсчётом, поразрядная сортировка, корзинная сортировка.Сортировка случайных чисел за линейное время. Модель вычислений во внешней памяти. Сортировка сравнениями во внешней памяти 19 ноября Сортировки и порядковые статистики (2) 2f6f7065 Элементарные структуры данных, двоичная куча. 21 ноября Короткий контест №2 26 ноября Разбор домашнего задания №1 k-ичная куча, амортизационный анализ методом кредитов и методом потенциалов. Словарь с доступом по значению через сливаемые массивы,очередь с минимумом, дек с минимумом, динамический массив 28 ноября Непростые задачи на простые структуры 6e3f6964 Биномиальные кучи и фибоначчиевы кучи 3 декабря Задачи на кучи 3d315935 Хеширование, вводная лекция. Полиномиальный хеш. 5 декабря Контрольная работа №1 10 декабря Разбор домашнего задания №2 Хеш-таблицы, стратегии масштабирования, фильтры Блума. 12 декабря Хеши и хеш-таблицы 42756a31 Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево. 17 декабря Деревья поиска 53643279 2-3 дерево, B-дерево 19 декабря Бонусный контест №1

3 модуль

Дата Семинар Листочек Лекция 14 января Самобалансирующиеся деревья Тарьяна-Слейтора 374d6b47 Запросы на отрезках, префиксные суммы, разреженные таблицы, дерево отрезков, групповые модификации 16 января Запросы на отрезках 4f503751 Задачи LCA и LA, метод четырёх русских 21 января Короткий контест №3 23 января Двумерные запросы на отрезках и подобное 34597662 Понятие персистентной структуры данных, персистентное декартово дерево 28 января Персистентные структуры данных. 55493345 Перебор и динамическое программирование с примерами. Подотрезки, подмножества, поддеревья, ацкиличные графы, meet-in-the-middle 30 января Динамическое программирование. 57426b4b Классические приёмы задач динамического программирования. Замена параметра, битовые операции, эффективное использование памяти 4 февраля Занятий не будет 6 февраля Продвинутое динамическое программирование и перебор 56522020 Эффективный перебор, асимптотические и неасимптотические оптимизации. 11 февраля Ещё немного переборов и динамического программирования тык Эффективный перебор в играх с нулевой суммой. Альфа-бета отсечение 13 февраля Разбор домашнего задания №4 Теория графов, основные задачи на обход в глубину. 18 февраля Контрольная работа №2 20 февраля Задачи на графы тыц Мосты и точки сочленения, компоненты рёберной и вершинной двусвязности. 25 февраля Задачи на графы №2 тук Кратчайшие пути в графах 27 февраля Разбор домашнего задания №5 Минимальный остов. Прим, Краскал, Борувка, критерии оптимальности 3 марта Короткий контест №4 5 марта Задачи на кратчайшие пути и остовы тыщ Система непересекающихся множеств. Оценки log* и обратная функция Аккермана 10 марта Разговор про оптимизации кода не было Графы во внешней памяти. Задача о ранжировании списка 12 марта Разбор домашнего задания №6 Задача о максимальном паросочетании в двудольных графах. 17 марта Короткий контест №5 19 марта Бонсуный контест №2

4 модуль

Дата Семинар Листочек Лекция 7 апреля Разбор домашнего задания №7 Введение в потоки, две постановки задачи и декомпозиция 9 апреля Короткий контест с подвохом №6 14 апреля Задачи на паросочетания. тыщ Теорема Форда-Фалкерсона, приёма масштабирования, Эдмондс-Карп и Диниц. 16 апреля Задачи на потоки. тыщ Диниц+масштабирование, первая теорема Карзанова, паросочетание за O(m sqrt n), стоимостные потоки. записи доски 21 апреля Сложные задачи на потоки. тыщ Корректность жадного алгоритма стоимостного потока + задача о назначениях. Постановка основных строковых задач. 23 марта Короткий контест №7 28 апреля Ещё немного задач на потоки и стоимостные потоки. тыщ Задача поиска шаблона в тексте, префикс-функция и z-функция. Автомат префикс-функции. 30 апреля Задачи на строковые алгоритмы. тыщ Алгоритм Бойера-Мура. Бор, Ахо-Корасик. 7 мая Короткий контест №8 12 мая Задачи на Ахо-Корасик тыщ Сжатый бор, алгоритм Укконена построения суффиксного дерева. 14 мая Задачи на Укконена + определения и примеры из автоматов и языков тыщ Выразительная эквивалетность РВ, ДКА, НКА, eps-НКА, лемма о накачке, иерархия языков 19 мая Разбор домашнего задания №8 Минимизация ДКА 21 мая Короткий контест №9 26 мая Задачи на автоматы, языки и машину Тьюринга тыщ Проблема P ? NP, теорема Кука-Левина, NP-полнота некоторых задач. 28 мая Задачи на строковые алгоритмы и автоматы тыщ Простое ТЧ, расширенный Евклид, факторизация, линейное решето, дискретное логарифмирование 2 июня Задачи на сводимости и NP-полноту тыщ Ро-метод Полларда, тест на простоту Миллера-Рабина 4 июня Бонусный контест №3 9 июня Задачи на ТЧ тыц Шифрование с открытым ключом, схема RSA, цифровая подпись.

5 модуль

Дата Семинар Листочек Лекция 1 сентября Алгоритм Карацубы, метод деревьев рекурсии, мастер-теорема ъъъ Быстрое преобразование Фурье 4 сентября Задачи на Фурье ффт Численные методы оптимизации 8 сентября Задачи на численные методы оптимизации тык Численные методы интегрирования, метод 11 сентября Задачи на Монте-Карло и методы интегрирования тыц Эвристические методы оптимизации 15 сентября Основные примитивы вычислительной геометрии и работа с ними тут ¯\_(ツ)_/¯ 18 сентября Разбор домашнего задания №11 Быстрые методы вычислительной геометрии 22 сентября Задачи по вычислительной геометрии там Быстрый поиск пересечения отрезков, трёхмерная выпулкая оболочка, k-d дерево 25 сентября Короткий контест №10 29 сентября Задачи на многомерную геометрию ъуъ Введение в линейное программирование, постановка задачи, двойственная задача 2 октября Разговор про MapReduce эхх Симплекс-метод 6 октября Бонусный контест №4 9 октября Разбор домашнего задания №12 Приближённые алгоритмы, константные приближения, дерандомизация 13 октября Задачи на приближённые и вероятностные алгоритмы ... Стриминговые алгоритмы, задача о тяжёлых элементах, порядковые статистики и сумма в окне 18 октября Последний семинар ( FFF Стриминговые алгоритмы, подсчёт количества различных элементах, линейные наброски для оценки количества элементов с ключом X

Листки

Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации sheets.google.com

Листки в электронном виде отправляются в систему Google Classroom (инвайт: hhp3okt). Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения отправляются ровно один раз — нельзя отправить что-то, а потом через неделю прислать исправленную версию (небольшие исправления и уточнения разрешаются, если сделаны в течение нескольких часов после отправки листка и строго до дедлайна).

Общие предположения, которыми можно пользоваться в задачах

• Если в задаче говорится про запросы, то по умолчанию online
• Если не оговорено иное, можно использовать столько же памяти, сколько времени
• Если не оговорено иное, то можно ожидаемое амортизированное время с хешами

Список листков

№	Дедлайн	Темы	Листок	Пояснения
2 модуль
1	Полночь с 25 на 26 ноября	Вероятности и математическое ожидание	тык
2	Полночь с 9 на 10 декабря	Сортировки, простые структуры данных и кучи	тук	В пятой задаче медиана массива чётной длины — левый из двух возможных элементов Во второй задаче можно считать, что запросы даны заранее и нужно ответить на все сразу
3	Полночь с 21 на 22 декабря	Хеши и деревья поиска	тыц	Если не оговорено иное, то можно ожидаемое амортизированное время с хешами Во второй задаче числа целые В восьмой задаче можно считать, что TreeNode хранит Left, Right, Parent В первой задаче все строки непустые
3 модуль
4	Полночь с 12 на 13 февраля	Структуры данных	бац
5	Полночь с 26 на 27 февраля	Динамическое программирование, перебор и метод meet-in-the-middle	бах	Во второй задаче алфавит произвольный
6	Полночь с 11 на 12 марта	Обходы графов и кратчайшие расстояния	бам	В седьмой задаче отрицательных весов не бывает
7	Полночь с 30 на 31 марта	Остовы, графы и СНМ	бум
4 модуль
8	Полночь с 18 на 19 мая	Потоки и паросочетания	бац	В первой в процессе размещения домино разрешается уходить в минус Во втором пункте одиннадцатой задачи имеется в виду рёберное покрытие В третьей под k понимается количество коробок и финальных мест под коробки. Пустые клетки поля в k не учитываются. Считать, что k > 0.
9	Полночь с 27 на 28 мая	Строки и регулярные языки	бах	Если это явно не указано, то алфавит нельзя считать константным В десятой задаче звёздочка означает любую строку В десятой задаче вопросиков: разрешены только буквы английского алфавита и звёздочки. Знаки вопроса (джокеры, означающие один любой символ) не разрешены
10	Полночь с 10 на 11 июня	Классы сложности и теоретико-числовые алгоритмы	бан
5 модуль
11	Полночь с 17 на 18 сентября	Численные методы оптимизации и БПФ	бар	В четвёртой задаче все точки различны. Добавлять нужно точки только с целочисленными координатами Во второй задаче расстояние евклидово В третьей можно менять на любые вещественные числа В девятой задаче нужно найти целую часть Суперсходимость и сходимость могут быть только на каком-то интервале. В этом случае надо указать, как мы в этот интервал попадём
12	Полночь с 5 на 6 октября	Методы оптимизации и вычислительная геометрия	тык	В 10 задаче под словами дан многогранник имеются в виду вершины и грани
13	Полночь с 20 на 21 октября	Линейное программирование и приближённые задачи	:-(	В 4 задаче положительные рёбра

Короткие контесты

Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

№	Дата	Ссылка	Дорешивать
2 модуль
1	7 ноября 2019	15290	полночь с 27 на 28 декабря
2	21 ноября 2019	15816	полночь с 27 на 28 декабря
3 модуль
3	21 января 2020	16928	полночь с 20 на 21 июня
4	3 марта 2020	17435	полночь с 20 на 21 июня
5	17 марта 2020	17611	полночь с 20 на 21 июня
4 модуль
6	9 апреля 2020	17927	не предусмотрено
7	23 апреля 2020	18158	полночь с 20 на 21 июня
8	7 мая 2020	18262	полночь с 20 на 21 июня
9	21 мая 2020	18478	полночь с 20 на 21 июня
5 модуль
10	25 сентября 2020	20084	полночь с 21 на 22 октября

Длинные контесты

Дедлайн	Темы	Ссылка
2 модуль
полночь с 9 на 10 декабря	Cортировки, порядковые статистики, простые структуры данных	15815
полночь с 22 на 23 декабря	Хеши и деревья поиска	16271
3 модуль
Полночь с 17 на 18 февраля	Структуры данных, запросы на отрезках	17022
Полночь с 31 марта на 1 апреля	Динамика, перебор, графы	17506
4 модуль
Полночь с 24 на 25 мая	Графы, паросочетания, потоки	18261
Полночь с 14 на 15 июня	Строки, языки, ТЧ	18261
5 модуль
Полночь с 10 на 11 октября	Фурье, численные методы, вычислительная геометрия	19905
Полночь с 21 на 22 октября	Приближённые и вероятностные алгоритмы, линейные задачи	20843

Экзамены

Правила экзамена 2 модуль

1. Состоит из письменного теста и устной части.
2. За тест ставится оценка от 1 до 8.
3. На устную часть приглашаются те, кто написал тест на 4 и выше.
4. У тех, кто идёт на устную часть, оценка понижается на 1.
5. На устной части вы последовательно увеличиваете свою оценку на 1, отвечая на теоретические вопросы и задачи.
6. За экзамен можно два раза перетянуть билет.
7. Три неправильных подхода к снаряду приводят к форсированному перетягиванию билета в счёт одной попытки.
8. Если попытки кончились, то экзамен для студента завершается.

Правила экзамена (3, 4, 5 модули)

Правила экзамена

Дата и время

Модуль	Дата	Время, аудитория		Программа
2 модуль	28 декабря (суббота)	Письменная часть	11:00-12:30, ауд. R401	тык
		Устная часть	14:00-17:00, ауд. R401
3-4 модуль	23 июня	Устная часть (дистанционно)	Не выходя из дома	туц
5 модуль	24 октября	Устная часть (дистанционно)	Не выходя из дома	TBD

Ссылки на материалы

Основные источники:

1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
2. neerc.ifmo.ru

Изученные темы:

2 модуль

1. Виды задач, сильно-, слабо-, и псевдополиномиальность: https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/algorithms.pdf
2. Ликбез по теории вероятностей
   1. Кормен, приложение В "Комбинаторика и теория вероятности", c 1235
   2. Памятка по основным определениям
3. Индикаторная случайная величина: Кормен, раздел 5.2, с 144.
4. Методы решения рекуррентных соотношений: Кормен, гл. 4, разделы 4.3-4.5 (со стр. 108)
5. Модель вычислений во внешней памяти, сортировка слиянием во внешней памяти: https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_во_внешней_памяти._Базовые_конструкции
6. Двоичная куча, сортировки, порядковые статистики
   1. Кормен, часть 2 "Сортировка и порядковая статистика" с. 173
   2. https://neerc.ifmo.ru/wiki/index.php?title=Двоичная_куча
7. Невозможность сортировки быстрее n log n: Кормен, начало главы "Сортировка за линейное время", стр. 220
8. Фибоначчиевы кучи
   1. Кормен, гл. 19, с 542
   2. https://neerc.ifmo.ru/wiki/index.php?title=Фибоначчиева_куча
9. Биномиальные кучи: https://neerc.ifmo.ru/wiki/index.php?title=Биномиальная_куча
10. Хеширование и хеш-таблицы
    1. Кормен, гл. 11, с. 285
    2. http://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий
11. Фильтр Блума: http://neerc.ifmo.ru/wiki/index.php?title=Фильтр_Блума
12. Амортизационный анализ: Кормен, гл. 17, с 487
13. Бинарные деревья поиска: Кормен, гл. 12, c 319
14. Декартово дерево
    1. https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево
    2. https://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево_по_неявному_ключу
15. B-деревья
    1. Кормен, гл.18, стр. 521
    2. http://neerc.ifmo.ru/wiki/index.php?title=B-дерево
16. 2-3-деревья: http://neerc.ifmo.ru/wiki/index.php?title=2-3_дерево
17. Стек и очередь с минимумом: https://e-maxx.ru/algo/stacks_for_minima
18. Дек на 3 стеках: https://neerc.ifmo.ru/wiki/index.php?title=Дек

3 модуль

1. Cплей деревья:
   1. визуализатор: https://www.cs.usfca.edu/~galles/visualization/SplayTree.html
   2. http://neerc.ifmo.ru/wiki/index.php?title=Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
   3. https://en.wikipedia.org/wiki/Splay_tree
   4. https://habr.com/ru/company/JetBrains-education/blog/210296/
   5. оригинальная статья: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
2. Деревья отрезков:
   1. https://e-maxx.ru/algo/segment_tree - одномерное, с propagation меток, двухмерное, персистентное
   2. про дерево отрезков снизу вверх: https://codeforces.com/blog/entry/1256
   3. сортированный массив/дерево отрезков/декартово дерево в каждой вершине двухмерного дерева, предподсчёт переходов, приёмы со сжатием координат и сканирующей прямой - см. задачи с семинаров
3. Разреженные таблицы: https://neerc.ifmo.ru/wiki/index.php?title=Решение_RMQ_с_помощью_разреженной_таблицы
4. LCA:
   1. https://e-maxx.ru/algo/ - раздел из 5 статей с различными методами
   2. https://neerc.ifmo.ru/wiki/index.php?title=Сведение_задачи_RMQ_к_задаче_LCA
   3. https://neerc.ifmo.ru/wiki/index.php?title=Сведение_задачи_LCA_к_задаче_RMQ
5. LA: https://neerc.ifmo.ru/wiki/index.php?title=Level_Ancestor_problem
6. Персистентное декартово дерево по неявному ключу: https://habr.com/ru/post/240519/
7. Персистентный стек: https://neerc.ifmo.ru/wiki/index.php?title=Персистентный_стек
8. Персистентная очередь:
   1. через персистентный массив/c помощью LA - см. задачи с семинаров
   2. асимптотчески оптимальная: https://habr.com/ru/post/241231/, http://codeforces.com/blog/entry/15685
9. СНМ: https://e-maxx.ru/algo/dsu
10. ДП:
    1. Кормен, глава 15, с. 392
    2. http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование
    3. http://neerc.ifmo.ru/wiki/index.php?title=Динамика_по_поддеревьям
    4. http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_рюкзаке
    5. по графам, по поддеревьям, по подотрезкам, по подмножествам, вперёд/назад/ленивая, рюкзак и т.д. - см. задачи с семинаров и практических занятий
11. Meet-in-the-middle:
    1. https://neerc.ifmo.ru/wiki/index.php?title=Meet-in-the-middle - несколько примеров
    2. алгоритм Шэнкса baby-step-giant-step: https://e-maxx.ru/algo/discrete_log
12. Перебор:
    1. перебор подмасок данной маски: https://e-maxx.ru/algo/all_submasks
    2. генерация сочетаний: https://e-maxx.ru/algo/generating_combinations
    3. оптимизации при поиске вершинного покрытия: https://informatics.mccme.ru/mod/statements/view3.php?chapterid=2530 - см. разбор, https://habr.com/ru/company/hsespb/blog/456130/
    4. битовые трюки и оптимизации: https://codeforces.com/blog/entry/21858, http://acm.math.spbu.ru/~sk1/mm/lections/2014-08-20-bits.pdf
13. Метод ветвей и границ: https://en.wikipedia.org/wiki/Branch_and_bound
14. Альфа-бета отсечение:
    1. визуализация хода работы в лучшем случае http://josquin.cs.depaul.edu/~rburke/courses/w08/gam376/notes/BestCase.html
    2. https://en.wikipedia.org/wiki/Alpha–beta_pruning - тут хороший псевдокод и есть длинная подробная визуализация
    3. классическая статья Дональда Кнута: https://pdfs.semanticscholar.org/dce2/6118156e5bc287bca2465a62e75af39c7e85.pdf
15. Элементарные алгоритмы на графах (bfs, dfs, топологическая сортировка, мосты, точки сочленения, компоненты сильной связности) см. на https://e-maxx.ru/algo/
16. 2-sat через компоненты сильной связности: https://e-maxx.ru/algo/2_sat
17. Остовы:
    1. http://neerc.ifmo.ru/wiki/index.php?title=Остовные_деревья:_определения,_лемма_о_безопасном_ребре
    2. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Борувки
    3. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Прима
    4. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Краскала
    5. критерии оптимальности остовного дерева: см. задачи 1-2 семинара №26
18. Эйлеров цикл/путь:
    1. http://neerc.ifmo.ru/wiki/index.php?title=Эйлеровость_графов
    2. http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_построения_Эйлерова_цикла
19. Кратчайшие пути:
    1. http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Флойда
    2. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Дейкстры
    3. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Форда-Беллмана
    4. http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Джонсона
    5. http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A*
    6. http://neerc.ifmo.ru/wiki/index.php?title=Эвристики_для_поиска_кратчайших_путей
20. Паросочетания:
    1. http://neerc.ifmo.ru/wiki/index.php?title=Паросочетания:_основные_определения,_теорема_о_максимальном_паросочетании_и_дополняющих_цепях
    2. http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Холла
    3. https://e-maxx.ru/algo/kuhn_matching - алгоритм Куна
    4. Теорема Кёнига: http://neerc.ifmo.ru/wiki/index.php?title=Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольных_графах
    5. Покрытие непересекающимися путями ациклического орграфа: https://e-maxx.ru/algo/path_cover
    6. https://ru.wikipedia.org/wiki/Теорема_Дилуорса
    7. https://ru.wikipedia.org/wiki/Алгоритм_Хопкрофта_—_Карпа

4 модуль

1. Поток:
   1. https://neerc.ifmo.ru/wiki/index.php?title=Определение_сети,_потока
   2. https://neerc.ifmo.ru/wiki/index.php?title=Разрез,_лемма_о_потоке_через_разрез
   3. https://neerc.ifmo.ru/wiki/index.php?title=Теорема_Форда-Фалкерсона
   4. http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину
   5. http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Эдмондса-Карпа
   6. http://neerc.ifmo.ru/wiki/index.php?title=Схема_алгоритма_Диница
   7. http://neerc.ifmo.ru/wiki/index.php?title=Теоремы_Карзанова_о_числе_итераций_алгоритма_Диница_в_сети_с_целочисленными_пропускными_способностями
   8. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_масштабирования_потока
   9. http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_декомпозиции
   10. http://neerc.ifmo.ru/wiki/index.php?title=Циркуляция_потока
   11. https://e-maxx.ru/algo/flow_with_limits - поток с ограничениями
2. Стоимостной поток:
   1. http://neerc.ifmo.ru/wiki/index.php?title=Поток_минимальной_стоимости
   2. https://e-maxx.ru/algo/min_cost_flow
   3. http://neerc.ifmo.ru/wiki/index.php?title=Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости
   4. http://neerc.ifmo.ru/wiki/index.php?title=Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости
3. Элементарные алгоритмы на строках:
   1. https://e-maxx.ru/algo/prefix_function
   2. https://neerc.ifmo.ru/wiki/index.php?title=Префикс-функция
   3. https://neerc.ifmo.ru/wiki/index.php?title=Z-функция
   4. http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Манакера
4. Ахо-Корасик:
   1. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Ахо-Корасик
   2. https://e-maxx.ru/algo/aho_corasick
5. Суффиксное дерево:
   1. http://yury.name/internet/01ianote.pdf
   2. https://neerc.ifmo.ru/wiki/index.php?title=Сжатое_суффиксное_дерево
   3. https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Укконена
6. ДКА, НКА, РВ:
   1. https://neerc.ifmo.ru/wiki/index.php?title=Детерминированные_конечные_автоматы
   2. https://neerc.ifmo.ru/wiki/index.php?title=Недетерминированные_конечные_автоматы
   3. https://neerc.ifmo.ru/wiki/index.php?title=Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона
   4. https://neerc.ifmo.ru/wiki/index.php?title=Прямое_произведение_ДКА
   5. https://neerc.ifmo.ru/wiki/index.php?title=Регулярные_языки:_два_определения_и_их_эквивалентность
   6. https://neerc.ifmo.ru/wiki/index.php?title=Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков)
   7. https://neerc.ifmo.ru/wiki/index.php?title=Доказательство_нерегулярности_языков:_лемма_о_разрастании
   8. https://neerc.ifmo.ru/wiki/index.php?title=Минимизация_ДКА,_алгоритм_Хопкрофта_(сложность_O(n_log_n))
   9. И.А. Волкова, А.А. Вылиток, Т.В. Руденко "Формальные грамматики и языки. Элементы теории трансляции"
7. Машина Тьюринга:
   1. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. "Машина Тьюринга и алгоритмы Маркова. Решение задач"
   2. https://ru.wikipedia.org/wiki/Тезис_Чёрча_—_Тьюринга
   3. https://ru.wikipedia.org/wiki/Проблема_остановки
8. Классы задач, NP-полнота:
   1. Кормен, гл. 34, c. 1096
   2. http://ru.discrete-mathematics.org/fall2015/3/complexity/lecture-2-p-np.pdf
   3. http://ru.discrete-mathematics.org/fall2015/3/complexity/lecture-3-4-np-complete.pdf
   4. https://en.wikipedia.org/wiki/L_(complexity), https://en.wikipedia.org/wiki/P_(complexity), https://en.wikipedia.org/wiki/NP_(complexity), https://en.wikipedia.org/wiki/EXPTIME, https://en.wikipedia.org/wiki/PSPACE
   5. https://neerc.ifmo.ru/wiki/index.php?title=Теорема_Кука
   6. https://neerc.ifmo.ru/wiki/index.php?title=Сведение_относительно_класса_функций._Сведение_по_Карпу._Трудные_и_полные_задачи
9. Элементы алгебры, Ро-метод Полларда, тест на простоту Миллера-Рабина, RSA:
   1. Кормен, гл. 31, c. 968
   2. https://e-maxx.ru/algo/, раздел "Алгебра"

5 модуль

1. Алгоритм Карацубы: https://ru.wikipedia.org/wiki/Алгоритм_Карацубы
2. Основная теорема о рекуррентных соотношениях (Master Theorem), метод Штрассена:
   1. Кормен, гл. 4, стр 90
   2. https://ru.wikipedia.org/wiki/Основная_теорема_о_рекуррентных_соотношениях
3. Быстрое преобразование Фурье:
   1. Кормен, гл. 30, стр. 940
   2. https://e-maxx.ru/algo/fft_multiply
   3. Ньютоновские схемы для быстрого деления и извлечения корня: https://arxiv.org/pdf/1004.3412.pdf
4. Про IEEE 754: https://neerc.ifmo.ru/wiki/index.php?title=Представление_вещественных_чисел
5. Приближённые алгоритмы:
   1. Кормен, гл. 35, стр. 1157
   2. 3/2 TSP: https://ru.wikipedia.org/wiki/Алгоритм_Кристофидеса, есть в презентации https://compsciclub.ru/media/courses/2017-autumn/spb-tsp/materials/20171126_tsp_csclub.pdf
   3. дерандомизация: https://ru.wikipedia.org/wiki/Метод_условных_вероятностей
   4. MAXSAT: https://en.wikipedia.org/wiki/Maximum_satisfiability_problem, предпоследний раздел https://www.mccme.ru/ium/postscript/s12/gasnikov-12.pdf
   5. MAXCUT: начало http://web.cs.iastate.edu/~pavan/633/lec14.pdf
6. Генетические алгоритмы: https://ru.wikipedia.org/wiki/Генетический_алгоритм
7. Алгоритм Каргера-Штайна: https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Каргера_для_нахождения_минимального_разреза
8. Быстрая геометрия:
   1. работа с примитивами, выпуклая оболочка, проверка принадлежности точек выпуклому многоугольнику, построение касательных к выпуклому многоугольнику, поиск двух ближайших точеки, поиск любых двух пересекающихся отрезков, алгоритмы пересечения полуплоскостей: см. задачи с семинаров + в разделе "Геометрия" https://e-maxx.ru/algo/
   2. поиск наиболее удалённых точек https://neerc.ifmo.ru/wiki/index.php?title=Диаметр_множества_точек_(вращающиеся_калиперы)
   3. минимальная накрывающая окружность: https://ru.wikipedia.org/wiki/Задача_о_наименьшей_окружности, https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек
   4. триангуляция методом отрезания ушей https://neerc.ifmo.ru/wiki/index.php?title=Триангуляция_полигонов_(ушная_%2B_монотонная)
9. Задача Point location:
   1. соответствующий раздел http://www.csun.edu/~ctoth/Handbook/chap38.pdf
   2. классическая статья Тарьяна: ftp://ftp.cs.princeton.edu/techreports/1985/005.pdf
   3. глава 2 в http://inis.jinr.ru/sl/vol1/CMC/Preparata,Sheimos,Vychislitelnaya%20geometriya,%201989.pdf
   4. глава 6 книги "Computational Geometry - Algorithms and Applications", 3rd Ed. de Berg et all.
10. k-d деревья: https://neerc.ifmo.ru/wiki/index.php?title=К-d_деревья_и_перечисление_точек_в_произвольном_прямоугольнике_(статика)
11. Выпуклая оболочка:
    1. глава 3 http://inis.jinr.ru/sl/vol1/CMC/Preparata,Sheimos,Vychislitelnaya%20geometriya,%201989.pdf
    2. глава 11 книги "Computational Geometry - Algorithms and Applications", 3rd Ed. de Berg et all.
12. Численные методы интегрирования. Метод Монте-Карло:
    1. Самарский, Гулин "Численные методы", глава 4 http://samarskii.ru/books/book1989.pdf
    2. https://ru.wikipedia.org/wiki/Численное_интегрирование - обзорная статья
    3. https://ru.wikipedia.org/wiki/Метод_Монте-Карло
13. Численные методы оптимизации. Троичный поиск, градиентный и покоординатный спуск, метод Ньютона:
    1. https://e-maxx.ru/algo/ternary_search
    2. https://neerc.ifmo.ru/wiki/index.php?title=Поиск_с_помощью_золотого_сечения
    3. покоординатный спуск: http://www.machinelearning.ru/wiki/index.php?title=Метод_покоординатного_спуска
    4. градиентный спуск: http://www.machinelearning.ru/wiki/index.php?title=Метод_градиентного_спуска
    5. Самарский, Гулин "Численные методы", глава 5 http://samarskii.ru/books/book1989.pdf
14. Стриминговые алгоритмы:
    1. записки https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf
    2. материалы к http://people.cs.georgetown.edu/jthaler/COSC548.html
    3. материалы к https://people.cs.umass.edu/~mcgregor/courses/CS711S12/index.html
15. Задача линейного программирования, симплекс-метод, двойственность:
    1. Кормен, гл. 29, стр. 883
    2. трюк с булевыми функциями http://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html

FAQ

Q: А когда будет FAQ?

A: Уже готово, см. вики-страницу курса

Q: А зачем нужен FAQ?

A: Мы тоже не очень понимаем

Преподаватели и ассистенты

Преподаватель	Подгруппа	Присутственные часы	Контакты
Преподаватели
Глеб Евстропов	191-1
Станислав Артюхин	191-2
Григорий Резников	193-1
Иван Смирнов	193-2
Святослав Фельдшеров	195-1
Никита Сендерович	195-2
Ассистенты
Филипп Грибов		вторник, 4 пара (13:30 - 15:10)	@grphil
Иван Сафонов		понедельник, 2 пара (10:30 - 11:50)	@isaf27
Максим Деб Натх		среда, 5.5 пара (15:40 - 17:00)	@debnatkh
Александр Курилкин		среда, (18:00 - ?)	@wrg0ababd
Никита Морозов		пятница, 5 пара (15:10 - 16:30)	@madn_boi