Алгоритмы на графах и динамическое программирование 2026
Команда курса
Лектор: Троян-Головян Владислав
Семинарист: Аксёненко Денис
Ассистенты:
Андреев Ярослав Андреевич Прохорчук Екатерина Александровна
Программа курса
Форма контроля: Дифференцированный зачет и экзамен
| № недели | Лекция / семинар |
|---|---|
| 1 | Основные идеи, базовые задачи: НОП, НВП, Банкомат |
| 2 | Динамическое программирование 2: матричное ДП, алгоритм Хиршберга, задача о рюкзаке, ДП по цифрам |
| 3 | ДП по битмаскам, гамильтоновы пути, клики; ДП по профилю, скошенному профилю |
| 4 | Convex Hull Trick |
| 5 | Графы 1: способы хранения, DFS, BFS, цвета вершин |
| 6 | Графы 2: DFS и времена входа и выхода, топологическая сортировка, поиск КСС, 2-SAT, мосты и точки сочленения |
| 7 | Остовные деревья, СНМ, алгоритм Крускала, алгоритм Прима, матроиды |
| 8 | Алгоритм Борувки, LCA: поиск при помощи двух указателей, бинарных подъёмов, сведение LCA к RMQ. Алгоритм Фарака–Колтона и Бендера. Сведение RMQ к LCA |
| 9 | Кратчайшие пути 1: алгоритм Дейкстры, алгоритм A*, алгоритм Форда–Беллмана, алгоритм Флойда–Уоршелла |
| 10 | Кратчайшие пути 2: алгоритм Джонсона, улучшения алгоритма Дейкстры, двунаправленный A*, алгоритм IDA* |
| 11 | Паросочетания: алгоритм Куна, теорема Бержа, теорема Кёнига. Построение минимального вершинного покрытия |
| 12 | Потоки 1: основные понятия, теорема о максимальном потоке и минимальном разрезе, метод Форда–Фалкерсона, алгоритм Эдмондса–Карпа. Поиск максимального паросочетания при помощи поиска потока |
| 13 | Алгоритмы Диница и Хопкрофта–Карпа |
| 14 | Min-cost flow. Задача о назначениях |
Коммуникация
Ссылка на чат курса в мессенджере (ближе к старту семестра)
Прогресс студентов
Ссылка на таблицу студентов с оценками (ближе к старту семестра)
Система оценивания
В течение семестра проводится 6 контестов, в каждом из которых одна задача выполняется с последующим код-ревью.
Критерии оценивания и формы контроля успеваемости
По задачам на ревью опрелеляется верхняя граница оценки(далее X):
Если пройдено
Для порога уд. 4 нужно пройти(получить approve) 3,
Для порога хор. 7, нужно пройти 4,
Для порога отл. 8-9, нужно пройти 5
Для порога отл. 10, нужно пройти 6.
Контрольные работы
В течение семестра проводится 2 контрольные работы. За каждую контрольную можно получить от 0 до 10 баллов.
Блокирующее условие на неуд: сумма оценок по двум контрольным должна быть хотя бы 6б.
Итоговая оценка рассчитывается на основе трёх составляющих:
- A - контесты(от 1 до 10, выставляется по порогам)
- B - AVG контрольные(от 1 до 10)
- C - оценка от семинариста(от -1 до +1)
Далее вычисляется Y=0.5*A+0.5*B+C
И выставляется Min(X,Y)
Пороги для оценки A:
>= 50%: уд3,
>= 55%: уд4,
>= 65%: хор 5,
>= 70%: хор 6,
>= 75%: хор 7,
>= 85%: отл 8,
>= 90%: отл 9,
>= 95%: отл 10,
Иначе: неуд 1