Текущая версия на 12:45, 18 июня 2019

Лектор: С.А. Объедков

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

Лекции

понедельник 10:30 – 11:50, ауд. 622

среда 15:10 – 16:30, ауд. 622

1. 29 октября. Задача сортировки. Сортировка вставками: анализ корректности с использованием инварианта цикла и времени работы. Асимптотические обозначения. Циклическая сортировка.
2. 31 октября. Стратегия "Разделяй и властвуй". Сортировка слиянием. Доказательство корректности рекурсивных алгоритмов по индукции. Оценка времени работы рекурсивных алгоритмов при помощи рекуррентных соотношений: дерево рекурсии, итерационный метод, основная теорема.
3. 7 ноября. Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска k-ой порядковой статистики.
4. 12 ноября. Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка.
5. 14 ноября. Рандомизированные алгоритмы. Лас-Вегас и Монте-Карло. Краткое введение в теорию вероятностей: вероятностные пространства, события, случайные переменные, математическое ожидание и его линейность, геометрические случайные переменные. Алгоритмы Bogosort и Quicksort.
6. 19 ноября. Таблицы с прямой адресацией. Хеш-таблицы. Хеш-функции. Универсальные семейства хеш-функций. Открытая адресация.
7. 21 ноября. Двоичные деревья поиска. Семейства сбалансированных деревьев. Красно-черные деревья.
8. 26 ноября. Вставка элемента в красно-черное дерево. Ориентированные и неориентированные графы. Представление графов в памяти компьютера: матрицы смежности и списки смежности. Поиск в ширину и в глубину.
9. 28 ноября. Вычисление расстояний при помощи обхода в ширину. Вычисление компонент связности в неориентированном графе и компонент сильной связности в ориентированном графе. Топологическая сортировка.
10. 3 декабря Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры.
11. 5 декабря Динамическое программирование: алгоритмы Беллмана – Форда и Флойда – Уоршелла.
12. 10 декабря. Контрольная работа по материалам осенних лекций (29 октября – 28 ноября). В частности, в контрольной работе могут быть даны задачи на рекуррентные соотношения, хеш-таблицы, рандомизированные алгоритмы, а также задачи, похожие на задачи для подготовки. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная состоится 10 декабря в 10:30 – 11:50 в ауд. 402 (группы 182 и 184) и в ауд. 622 (группы 185, 186, 187, 188 и 189). Те, кто пропустил контрольную работу по уважительной причине, смогут ее написать 17 декабря в 16:40-18:00 в ауд. 622.
13. 12 декабря. Динамическое программирование: задача о рюкзаке, независимое множество максимального веса в дереве.
14. 17 декабря. Жадные алгоритмы, способы доказательства их корректности. Минимальные основные деревья. Алгоритм Прима.

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

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

1. Простые сортировки, бинарный поиск — с 29 октября по 4 ноября (со штрафом 50% — с 5 по 11 ноября).
2. Рекурсия, сортировка слиянием — с 5 по 13 ноября (со штрафом 50% — с 14 по 18 ноября).
3. Задачи на асимптотику и рекуррентные соотношения — с 7 по 20 ноября. UPDATE: Задание в пункте 4 несколько упрощено.
4. Сортировка подсчетом, поразрядная и др. — с 12 по 18 ноября (со штрафом 50% — с 19 по 25 ноября).
5. Быстрая сортировка, порядковые статистики, хеши — с 19 по 25 ноября (со штрафом 50% — с 26 ноября по 2 декабря).
6. Бинарные деревья поиска — с 26 ноября по 2 декабря (со штрафом 50% — с 3 по 9 декабря).
7. Задачи на сортировку, хеш-функции, структуры данных — с 27 ноября по 9 декабря. Для получения зачета по задачам из листка нужно решить их все письменно и защитить устно. UPDATE: Исправлена опечатка в задаче 2.
8. Обход в глубину и ширину — с 3 по 10 декабря (со штрафом 50% — с 11 по 16 декабря).
9. Алгоритм Дейкстры — с 10 по 17 декабря.
10. Задачи на динамическое программирование — с 11 по 18 декабря. Для получения зачета по задачам из листка нужно решить обе задачи письменно и защитить устно.

Экзамен

Экзамен состоится 19 декабря в 15:10 – 18:00. На экзамене нужно будет решить несколько задач в системе Яндекс.Контест. Желательно прийти со своим ноутбуком. Если у вас нет такой возможности, отметьтесь, пожалуйста, здесь.

Те, кто собирается писать экзамен на своем ноутбуке, приходят в ауд. 317 (группы 182, 184, 185, 186) и в ауд. 205 (группы 187, 188, 189). Те, кому нужны компьютеры, приходят в ауд. 311.

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

Лекции

понедельник, четверг 15:10 – 16:30, ауд. 622

1. 1 апреля. Приоритетные очереди и их применение в алгоритмах Дейкстры и Прима. Реализация приоритетной очереди при помощи двоичной кучи.
2. 4 апреля. Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков).
3. 8 апреля. Биномиальные кучи.
4. 11 апреля. Кучи Фибоначчи.
5. 16 апреля. Алгоритм Крускала и система непересекающихся множеств.
6. 18 апреля. Наименьшее значение в подмассиве: простые алгоритмы (линейный поиск, предподсчет всех возможных ответов), разбиение на блоки, разреженные таблицы, комбинирование структур данных для вычисления наименьших значений внутри блоков и наименьшего значения в массиве минимумов в блоках.
7. 22 апреля. Декартово дерево и его построение по массиву за линейное время. Структура Фишера – Хойна.
8. 25 апреля. Поиск подстроки в строке. Алгоритм Ахо – Корасик.
9. 29 апреля. Суффиксное дерево, его использование для поиска подстрок, самой длинной повторяющейся подстроки, самой длинной общей подстроки для двух строк. Суффиксный массив, его использование для поиска подстрок. Вспомогательная структура для поиска максимального общего префикса, ее использование при вычислении самого длинного палиндрома в строке.
10. 13 мая. Контрольная работа по материалам апрельских лекций. В частности, в контрольной работе могут быть даны задачи на двоичную, биномиальную и фибоначчиеву кучи и их применение, амортизационный анализ, структуры данных, поддерживающие вычисление наименьшего значения в подмассиве, и подобные им, автомат Ахо – Корасик и использование суффиксного дерева и суффиксного массива. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная состоится 13 мая в 15:10 – 16:30 в ауд. 509 (группы 182, 184 и 185) и в ауд. 622 (группы 186, 187, 188 и 189).
11. 16 мая. Жадные алгоритмы: выбор непересекающихся интервалов, коды Хаффмана.
12. 20 мая. Задачи, для которых не известны полиномиальные алгоритмы. Задача о коммивояжере: полный перебор за O(n!) и алгоритм с временем работы O(2ⁿn²). Задача о вершинном покрытии: 2-приближенный алгоритм. Задача о рюкзаке: приближенная схема полностью полиномиального времени.
13. 23 мая. Минимальный разрез. Алгоритмы Каргера и Каргера – Штайна.
14. 27 мая. Максимальный поток. Алгоритм Форда – Фалкерсона. Алгоритм Эдмондса-Карпа (без доказательства оценки сложности).
15. 30 мая. Совершенное паросочетание в двудольном графе. Циркуляция. Оценка сложности алгоритма Эдмондса-Карпа.
16. 3 июня. Детерминированные конечные автоматы. Минимизация конечного автомата. Регулярные операции.
17. 6 июня. Недетерминированные конечные автоматы. Эквивалентность детерминированных и недетерминированных автоматов. Замкнутость регулярных языков относительно регулярных операций. Регулярные выражения.
18. 10 июня. Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки.
19. 13 июня. Разбор примерных экзаменационных задач.

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

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

1. Двоичная куча и ее применение — с 8 по 14 апреля (со штрафом 50% — с 15 по 21 апреля). Требуется реализовать и использовать двоичную кучу при решении хотя бы двух задач.
2. Домашнее задание состоит из четырех задач контеста и шести задач, которые нужно решить письменно. Срок выполнения — 30 апреля для контеста и 2 мая для письменных задач.
3. Контест и теоретические задачи — с 3 по 21 мая.
4. Контест — c 26 мая по 2 июня. Решение каждой задачи необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности, которые нужно прислать в файле в формате PDF по электронной почте преподавателю и учебному ассистенту своей группы.
5. Контест — c 6 по 12 июня.

Контрольная работа

Те, кто пропустил контрольную работу 13 мая по уважительной причине, смогут написать ее 13 июня в 18:10 – 19:30 в ауд. 306. Для этого нужно записаться здесь.

Если вы хотели бы аннулировать свой балл за контрольную работу 13 мая и переписать ее 13 июня, запишитесь, пожалуйста, здесь до 13:30 13 июня. Если желающих окажется не очень много, такая возможность может быть предоставлена.

Экзамен

Экзамен пройдет 18 июня в 10:30 – 13:30 в ауд. 509 (группы 182, 184 и 185) и в ауд. 622 (группы 186, 187, 188 и 189). С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. На экзамене возможны задачи по следующим темам:

• Кратчайшие пути
• Разделяй и властвуй
• Динамическое программирование
• Жадные алгоритмы
• Приближенные алгоритмы
• Минимальный разрез и максимальный поток
• Структуры данных
• Конечные автоматы, регулярные выражения, нерегулярные языки

Показ работ — 20 июня в 10:30 – 11:50 в ауд. 205.

Литература

Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МЦНМО, 2014.

Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.

Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.

Студенческие конспекты: 2015 г., 2016 г., 2017 г.

Оценки

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

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

Текущая оценка: контрольная работа — 40%, домашние задания — 60%.

Промежуточная оценка: экзамен — 40%, текущая оценка — 60%.

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

Накопленная оценка: контрольная работа — 50%, домашние задания — 50%.

Итог

Завершающая накопленная оценка: среднее промежуточной оценки за второй модуль и накопленной оценки за четвертый модуль.

Итоговая оценка: экзамен — 25%, завершающая накопленная оценка — 75%.