Алгоритмы и структуры данных на ПМИ 2017/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 июня. Детерминированные и недетерминированные конечные автоматы, их эквивалентность. Регулярные языки. Регулярные операции. Замкнутость регулярных языков относительно регулярных операций.
18. 7 июня. Регулярные выражения. Эквивалентность регулярных выражений и конечных автоматов. Минимизация конечного автомата. Нерегулярные языки. Формулировка и применение леммы о накачке.
19. 11 июня. Доказательство леммы о накачке. Нерегулярный язык, удовлетворяющий условиям леммы о накачке. Теорема Майхилла — Нероуда.
20. 14 июня. Разбор экзаменационных задач прошлого года.

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

Задачи из апрельских домашних заданий можно сдавать после указанного ниже срока, но до конца 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 — до 12.06.2018 (23:59)
   

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

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

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

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

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

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

1. 8 июня, 9:50 - 11:20, ауд. 420
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

Экзамен

Экзамен пройдет 26 июня в 10:30 – 13:30 в ауд. 317 (группы 172, 174, 175) и ауд. 509 (группы 176, 177 и 178). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается.

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

Оценки

Накопленная оценка = 0,4 * контрольная работа + 0,6 * домашние задания
Итоговая оценка = 0,4 * экзамен + 0,6 * накопленная оценка

Для тех, кто пропустил контрольную работу по уважительной причине:

Накопленная оценка = домашние задания
Итоговая оценка = 0,64 * экзамен + 0,36 * накопленная оценка

Текущие оценки