А. В. Кононов
Дискретные
экстремальные задачи
Курс лекций (слайды)
НГУ, МехМат
Годовой спецкурс для студентов 4-6 курсов
| Лекция 1. |
Введение |
lec1.ppt |
| Лекция
2. |
Графы |
lec2.ppt |
| Лекция 3. |
Алгоритмы сканирования и обхода
|
lec3.ppt |
| Лекция 4. |
Остовные деревья |
lec4.ppt |
| Лекция 5. |
Кратчайшие пути |
lec5.ppt |
| Лекция 6. |
Потоки в сетях |
lec6.ppt |
| Лекция 7. |
Потоковые алгоритмы |
lec7.ppt |
| Лекция 8. |
Паросочетания в
двудольных графах |
lec8.ppt |
| Лекция 9. |
Фактор-критические
графы |
lec9.ppt |
| Лекция 10. |
M-чередующиеся декомпозиции |
lec10.ppt |
| Лекция 11. |
Алгоритм Эдмондса |
lec11.ppt |
| Лекция 12. |
Матроиды |
lec12.ppt |
| Лекция 13. |
NP-полнота.
Машина Тьюринга
|
lec13.ppt |
| Лекция 14. |
Теорема Кука |
lec14.ppt |
| Лекция 15. |
Основные
NP-полные
задачи
|
lec15.ppt |
| Лекция 16. |
Комбинаторные алгоритмы |
lec16.ppt |
| Лекция 16
(альтернативная). |
Приближенные алгоритмы.
Задача о
покрытии множествами. Алгоритмы на
основе ЛП |
AppRus16New2015.pptx |
| Лекция 17. |
Комбинаторные алгоритмы.
Задачи
с метрикой
|
lec17.ppt |
| Лекция 17
(альтернативная). |
Приближенные алгоритмы.
Задача о покрытии
множествами. Жадная стратегия
|
AppRus17New2015.pptx |
| Лекция 18. |
Комбинаторные алгоритмы.
Задача о
k-центрах
|
lec18.ppt |
| Лекция 19. |
Линейное программирование.
Задача теории расписаний
|
lec19.ppt |
| Лекция 20. |
Линейное программирование.
Задача о покрытии
|
lec20.ppt |
| Лекция 21. |
Приближенные схемы |
lec21.ppt |
| Лекция 22. |
Асимптотическая приближенная
схема |
lec22.ppt |
Литература
1. М.
Гэри, Д. Джонсон. Вычислительные
машины и труднорешаемые задачи. М.: Мир,
1982. с. 154–191. (djvu-file
10 Mb)
2. B. Korte, J.
Vygen. Combimatorial Optimization. Theory and Algorithms.
Berlin:
Springer-Verlag, 2002. (pdf-file
22 Mb)
3.
V.
Vazirani, Approximation Algorithms, Berlin: Springer-Verlag, 2001. (pdf-file
14 Mb)
4. Х.
Пападимитриу, К. Стайглиц.
Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
(djvu-file
4,5 Mb)
5.
P.
Schuurman, G. Woeginger.
Approximation
Schemes – A Tutorial, chapter of the book “Lecture on Scheduling” (pdf-file
0,5 Mb)
Лектор: к.ф.-м.н., доцент
Кононов
Александр Вениаминович
e-mail:
alvenko@math.nsc.ru
Редакция
17.04.2015
