Алгоритмы на графах и динамическое программирование 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