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