Город: Санкт-Петербург Казань Язык: Русский English

Избранные главы теории потоков
Санкт-Петербург / весна 2017, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Теория потоков, без сомнения, представляет собой один из наиболее хорошо изученных разделов комбинаторной оптимизации, имеющий разнообразные приложения, как теоретические, так и практические.

Курс начнется с краткого введения в предмет, в котором мы разберем базовые алгоритмы для задачи о максимальном потоке, а затем быстро перейдем к более современным темам: проталкиванию предпотока и параметрическим потоковым задачам. В заключительной части курса коснемся обобщений понятия потока: изучим простейшие виды мультипотоковых задач, а также поговорим о потоках в кососиметрических и двунаправленных графах.

От слушателей предполагается знакомство с базовыми понятиями алгоритмической теории графов.

Предполагаемые темы, которые будут затронуты на занятиях:

  1. Задача о максимальном потоке и простейшие способы ее решения: алгоритмы Форда-Фалксерсона, Эдмондса-Карпа и Диница

  2. Оценки Карзанова для количества фаз алгоритма Диница

  3. Масштабирование пропускных способностей

  4. Проталкивание предпотока: общая схема, разгрузка вершин

  5. Стратегии разгрузки предпотока

  6. Быстрая декомпозиция мультитерминальных потоков

  7. Двухфазные алгоритмы проталкивания предпотока

  8. Эвристики, ускоряющие работу алгоритмов проталкивания предпотока

  9. Параметрический максимальный поток

  10. Задача о подграфе максимальной плотности

  11. Динамические деревья в задачах о максимальном потоке

  12. Алгоритм Гольдберга-Рао

  13. Свободные мультипотоки: теорема Ловаса-Черкасского, алгоритм Ибараки-Карзанова-Нагамочи

  14. Бипотоки и биразрезы в неориентированных графах: теорема Ротшильда-Винстона, алгоритм Ху

  15. Потоки в кососимметрических и двунаправленых графах, приложения к недвудольным паросочетаниям

Дата и время Название Место Материалы
13 мая
17:20–18:50
Лекция 1, лекция ПОМИ РАН видео
13 мая
19:10–20:40
Лекция 2, лекция ПОМИ РАН видео
14 мая
11:15–12:45
Лекция 3, лекция ПОМИ РАН видео
14 мая
13:00–14:30
Лекция 4, лекция ПОМИ РАН видео
14 мая
15:30–17:00
Лекция 5, лекция ПОМИ РАН видео
20 мая
17:20–18:50
Лекция 6, лекция ПОМИ РАН видео
20 мая
19:10–20:40
Лекция 7, лекция ПОМИ РАН видео
21 мая
11:15–12:45
Лекция 8, лекция ПОМИ РАН видео
21 мая
13:00–14:30
Лекция 9, лекция ПОМИ РАН видео
21 мая
15:30–17:00
Лекция 10, лекция ПОМИ РАН видео