(no subject)

Sep 13, 2009 17:45

Пользуясь случаем, хочу сделать объявление про спецкурс, который собираюсь читать в наступившем семестре. На раз этот планируется годовой курс про теорию потоков. Рассказывать предполагается с нуля, так что никаких предварительных знаний не потребуется.

Занятия будут проходить на 5-й паре по пятницам начиная с 18 сентября, ауд. 1327.
Приходите :)



  1. Потоки, разрезы и остаточные сети
  2. Декомпозиции потоков
  3. Теорема Форда--Фалкерсона о максимальном потоке и минимальном разрезе
  4. Целочисленные максимальные потоки
  5. Теоремы Менгера
  6. Жадный алгоритм нахождения максимального потока
  7. Паросочетания и вершинные покрытия в двудольных графах
  8. Теоремы Кёнига--Эгервари и Холла
  9. Алгоритм Куна
  10. Алгоритм Эдмондса--Карпа
  11. Блокирующие потоки и их свойства
  12. Алгоритм Диница
  13. Алгоритм Малхотры--Кумара--Махешвари построения блокирующего потока
  14. Алгоритм Карзанова построения блокирующего потока
  15. Оценки Карзанова на число фаз алгоритма Диница, алгоритм Хопкрофта--Карпа
  16. Предпотоки и их свойства
  17. Функция высоты, операции подъема и проталкивания
  18. Операция разгрузки, стратегии разгрузки предпотока
  19. Оценка Черияна--Махешвари
  20. Двухфазные алгоритмы проталкивания предпотока
  21. Эвристики зазора и глобальной переоценки
  22. Динамические деревья Слитора--Таржана
  23. Алгоритм проталкивания предпотока Гольдберга--Таржана
  24. Параметрические потоки в сетях специального вида
  25. Алгоритм нахождения максимальной точки излома
  26. Задача о подграфе максимальной плотности
  27. Алгоритм Галло--Григориадиса--Таржана нахождения полного множества точек излома
  28. Минимальные разрезы в ненаправленных графах, алгоритмы Каргера--Стайна и Стёра--Вагнера
  29. Потоки в ненаправленных графах, деревья Гомори--Ху
  30. Минимальные нечетные разрезы
Previous post Next post
Up