Новосибирский государственный университет
ММФ 
Кафедра теоретической кибернетики

Thin_Red_and_BlueA205.gif (1558 bytes)

 А. В. Кононов

Приближенные алгоритмы

Курс лекций (слайды)

НГУ, МехМат
Магистратура 1 год
 

Лекция 1. Введение AppRusLect1.ppt
Лекция 2. Комбинаторные алгоритмы. Задача о покрытии AppRusLect2.ppt
Лекция 3.
Комбинаторные алгоритмы. Задачи с метрикой
AppRusLect3.ppt
Лекция 4. Комбинаторные алгоритмы. Параметрическое сокращение AppRusLect4.ppt
Лекция 5. Комбинаторные алгоритмы. Локальный поиск AppRusLect5.ppt
Лекция 6. Приближенные схемы. Задача теории расписаний AppRusLect6.ppt
Лекция 7. Приближенные схемы. Задачи упаковки AppRusLect7.ppt
Лекция 8. Приближенные схемы. Цеховая задача с нефиксированными маршрутами AppRusLect8.ppt
Лекция 9. Линейное программирование. Задача теории расписаний AppRusLect9.ppt
Лекция 10.

Линейное программирование. Задача о покрытии

 
AppRusLect10.pptx
Лекция 11.

Линейное программирование. Процедура отделимости.

 
AppRusLect11.pptx
     
  Контрольная работа 1 Kont1.pdf
  Контрольная работа 2.1 Kont2.1.pdf
  Контрольная работа 2.2 Kont2.2.pdf
  Вопросы к экзамену Ekzamen2.pdf
  Устные вопросы перед экзаменом Ustnye_voprosu.pdf
     

 

Учебное пособие:  А.В. Кононов, П.А. Кононова. Приближенные алгоритмы для NP-трудных задач
Учебно-методическое пособие. Новосиб. гос. ун-т. – Новосибирск : РИЦ НГУ, 2014. – 117 с.

 

Литература

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)

3V. 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)

6. D.Hochbaum (Ed.) Approximation Algorithms for NP-hard problems. PWS Publishing Company, 1997.

 


Лектор: к.ф.-м.н., доцент Кононов Александр Вениаминович
e-mail:  alvenko@math.nsc.ru  

Редакция 21.04.2016