Версия 00:04, 5 июня 2018

Лекции

1. 2 апреля. Графы: определения и приложения. Представление графов: матрица смежности и списки смежности. Поиск в глубину (рекурсивная формулировка). Сложность поиска в глубину. Применение поиска в глубину: поиск компонент связности в неориентированном графе, топологическая сортировка. Поиск в ширину. Сложность поиска в ширину. Поиск кратчайших путей.
2. 5 апреля. Компоненты связности в неориентированных и ориентированных графах. Алгоритм поиска компонент сильной связности. Вычисление выполняющего набора для 2-КНФ на основе поиска компонент сильной связности.
3. 9 апреля. Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры: формулировка, условия применимости, доказательство корректности, оценка сложности. Формулировка алгоритма Беллмана – Форда для графов без циклов с отрицательным весом.
4. 12 апреля. Алгоритмы Беллмана – Форда и Флойда – Уоршелла как алгоритмы динамического программирования.
5. 16 апреля. Динамическое программирование: наибольшая общая подпоследовательность, разбиение абзаца на строки, задача о рюкзаке.
6. 19 апреля. Жадные алгоритмы: выбор максимального подмножества непересекающихся отрезков; составление плана работ с заданными продолжительностями и повременными штрафами за невыполнение, минимизирующего общий штраф; код Хаффмана.
7. 23 апреля. Матроиды: графовый матроид, матроид для последовательности задач. Жадный алгоритм на взвешенном матроиде: поиск минимального остовного дерева, составление расписания задач с минимальным штрафом.
8. 26 апреля. Минимальные остовные деревья. Алгоритмы Прима, Крускала, Борувки.
9. 30 апреля. Лекции не будет.
10. 10 мая. Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков).
11. 14 мая. Письменная контрольная работа по апрельским темам. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная проходит в ауд. 317 (группы 172, 174, 175) и ауд. 622 (группы 176, 177 и 178).
12. 17 мая. Самоорганизующиеся списки: метод потенциалов для анализа онлайн-алгоритмов. Кучи Фибоначчи.
13. 21 мая. Система непересекающихся множеств.
14. 24 мая. Минимальный разрез, алгоритмы Каргера и Каргера – Штайна.
15. 28 мая. Максимальный поток, алгоритм Форда – Фалкерсона.
16. 31 мая. Лекции не будет.
17. 4 июня. Детерминированные и недетерминированные конечные автоматы, их эквивалентность. Регулярные языки. Регулярные операции. Замкнутость регулярных языков относительно регулярных операций.

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

Задачи из апрельских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 мая со штрафом 50%. Задачи из майских домашних заданий можно сдавать после указанного ниже срока, но до конца 9 июня со штрафом 50%.

1. Контест 7940 — до 8.04.2018 (22:00)
   
2. Контест 7993 — до 15.04.2018 (23:59)
   
3. Контест 8053 — до 22.04.2018 (23:59)
   
4. Контест 8116 — до 30.04.2018 (9:00)
   
5. Контест 8224 — до 23.05.2018 (9:00)
   
6. Контест 8256 — до 30.05.2018 (9:00)
   
7. Контест 8329 — до 9.06.2018 (9:00)
   

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

Оценки

Критерии оценок

Даты показа работ:

Задачи I варианта

1. 24 мая, 11:50 - 12:30, ауд. 308
2. 23 и 30 мая, 11:30 – 12:00, ауд. 311
3. 31 мая 9.00 - 11.30, ауд. 605

Задачи II варианта

2. 29 мая, 11:50 – 12:20, ауд. 313
3. 31 мая, 9:00 – 11:50, ауд. 420
4. 25 мая, 9:50 – 10:30, ауд. 432
5. 6 июня, 9:30 – 12:00, ауд. 412