Версия 00:22, 21 мая 2020

Лекторы: Г.А. Погудин (2-ой модуль) С.А. Объедков (4-ый модуль)

Второй модуль

Лекции

Вторник 10:30 – 11:50, ауд. R404

Четверг 15:10 – 16:30, ауд. R404

1. 29 октября. Понятие сложности алгоритма, О-большое и о-малое, анализ простейших алгоритмов.Jupyter, Слайды

2. 31 октября. Про О-большие и пределы. Примеры: скользящее среднее, два указателя (merge). In-place алгоритмы: отражение и циклический сдвиг. Jupyter, Jupyter PDF, Слайды

3. 5 ноября. Стэк, очередь, дэк. Про реализации на списках и массивах. Jupyter, Jupyter PDF, Slides. Дополнительное чтение: Стэки и очереди

4. 7 ноября. Рекурсия: быстрое возведение в степень, перечисление подмножеств. Jupyter, Jupyter PDF, Slides. Дополнительное чтение: Раздел 1.10 про быстрое возведение в степень

5. 12 ноября. Рекурсия: перечисление перестановок и подмножеств, subset sum как пример простейшего branch&bound. Jupyter html Jupyter

6. 14 ноября. Динамическое программирование: введение и text justification. Slides Jupyter Jupyter html. Дополнительное чтение: TJ, TJ (как за n log n)

7. 19 ноября. Динамическое программирование: наибольшая общая подпоследовательность, top-down vs bottom-up. Jupyter Jupyter html. Дополнительное чтение: видеолекция про LCS

8. 21 ноября. Контрольная работа. Задачи

9. 26 ноября. Динамическое программирование: задача о рюкзаке, приближенный алгоритм. Jupyter, Jupyter html. Чтение: как делать рюкзак динамикой (bottom-up), видео про то же, но top-down, полиномальная аппроксимация (очень рекомендую)

10. 28 ноября. Поиск и сортировка: бинарный поиск, сортировка вставкой, сортировка слиянием. Jupyter (до лекции)

11. 3 декабря. Сортировка: сложность слияния, нижняя оценка на comparison-based sorting, qsort без анализа сложности. Jupyter Jupyter html

12. 5 декабря. Графы, поиск в глубину, проверка ацикличности. Jupyter Jupyter html Почитать: часть 1 часть 2

13. 10 декабря. Поиск в глубину (продолжение), поиск в ширину. Jupyter Jupyter html

14. 12 декабря. Алгоритмы поиска кратчайших путей: Floyd-Warshall & Bellman-Ford. Jupyter Jupyter html

15. 16 декабря. Внимание: лекция будет именно 16 декабря, в понедельник в 16:40-18:00 в ауд. R401. Разделяй и властвую: умножение многочленов и быстрое преобразование Фурье Jupyter (до лекции)

16. 19 декабря. Повторение перед экзаменом, разбор нескольких задач Jupyter (до лекции)

Пробный экзамен

Домашние задания

1. Домашнее задание 1. Дедлайн - 8 ноября.
2. Домашнее задание 2 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и C. Дедлайн - 15 ноября.
3. Домашнее задание 3. Дедлайн - 22 ноября.
4. Домашнее задание 4 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и B. Дедлайн - 29 ноября. Дедлайн со штрафом 50% - 6 декабря.
5. Домашнее задание 5 (контест). Дедлайн - 8 декабря. Дедлайн со штрафом 50% - 13 декабря.
6. Домашнее задание 6 (контест). Дедлайн - 15 декабря. Дедлайн со штрафом 50% - 20 декабря.
7. Домашнее задание 7 (контест). Дедлайн - 22 декабря.

Семинары

1. Неделя 1
2. Неделя 2
3. Неделя 3
4. Неделя 4
5. Неделя 5
6. Неделя 6
7. Неделя 7
8. Неделя 8

Четвертый модуль

Лекции

Понедельник 9:00 – 10:20

Четверг 15:10 – 16:30

1. 6 апреля. Структуры данных. Амортизационный анализ. Слайды
2. 9 апреля. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Слайды
3. 13 апреля. Методы задания хеш-функций. Универсальное хеширование. Слайды
4. 16 апреля. Двоичные деревья поиска. Слайды
5. 20 апреля. Краcно-черные деревья. Слайды. Заметки: 1, 2, 3, 4
6. 23 апреля. Жадные алгоритмы. Слайды. Иллюстрация к последнему доказательству.
7. 27 апреля. Алгоритм Дейкстры. Слайды.
8. 30 апреля. Двоичная куча. Слайды.
9. 7 мая. Биномиальная куча. Слайды.
10. 14 мая. Контрольная работа (контест) по темам 1 – 6. Оценка: одна решенная задача — 3 балла, две — 7 баллов, три — 10 баллов. Пробный вариант.
11. 18 мая. Минимальные остовные деревья. Слайды.

Домашние задания

1. Домашнее задание 1. Дедлайн — 16 апреля.
2. Домашнее задание 2 (контест). Дедлайн — 26 апреля, 18:05. Штрафы, которые назначаются в системе за количество попыток, не учитываются при выставлении оценки. Дедлайн со штрафом 50% — 2 мая. Внутренние тесты для первых двух задач.
3. Домашнее задание 3. Дедлайн — 3 мая, 18:00. Дедлайн со штрафом 50% — 10 мая.
4. Домашнее задание 4 (контест). Дедлайн — 14 мая. Для алгоритмов в задачах задач B и C нужно дополнительно доказать корректность и оценить сложность (и прислать доказательства преподавателю своей группы).
5. Домашнее задание 5 (контест). Дедлайн — 21 мая.
6. Домашнее задание 6 (контест). Дедлайн — 28 мая. Дедлайн со штрафом 50% — 2 июня.

Семинары

1. Неделя 1
2. Неделя 2
3. Неделя 3
4. Неделя 4
5. Неделя 5
6. Неделя 6

Ближайшая консультация

16 мая 12:10 – 13:30

Учебные ассистенты

• 192-2 Шамиль Аюпов
• 194-1 Першина Анна
• 194-2 Константин Матвеев
• 196-1 Денис Семенов
• 196-2 Георгий Новиков
• 197-1 Шамиль Аюпов
• 197-2 Георгий Новиков
• 198-1 Денис Семенов
• 198-2 Арсений Болотин
• 199-1 Константин Матвеев
• 199-2 Першина Анна
• 1910-1 Арсений Болотин
• 1910-2 Даниил Мячин
• 1911-1 Байков Ильнур
• 1911-2 Байков Ильнур
• 1912-1 Даниил Мячин

Литература

Наш курс не следует какому-то конкретному учебнику. Мы бы рекомендовали для дополнительного чтения следующие книги:

1. Dasgupta S., Papadimitriou K., Vazirani U. Algorithms english, russian (недавно издана МЦНМО, можно купить бумажную)
2. Erickson J. Algorithms
3. Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.
4. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.

Экзамен

Экзамен пройдет в устном формате и будет включать в себя темы всего курса (второй и четвертый модули).

Оценки

Итоговая оценка рассчитывается следующим образом:

• Оценка за второй модуль — 33%
• Домашние задания в четвертом модуле — 20%
• Контрольная работа в четвертом модуле — 7%
• Работа на семинарах в четвертом модуле — 7%
• Экзамен — 33%

Таблицы с оценками