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

Thin_Red_and_BlueA205.gif (1558 bytes)

 А. В. Кононов

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

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

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

Лекция 1. Введение AppRusLect01-2018.pdf
Лекция 2. Комбинаторные алгоритмы. Задача о покрытии AppRusLect02-2018.pdf
Лекция 3.
Комбинаторные алгоритмы. Задачи с метрикой
AppRusLect03-2018.pdf
Лекция 4. Комбинаторные алгоритмы. Параметрическое сокращение AppRusLect04-2018.pdf
Лекция 5. Комбинаторные алгоритмы. Локальный поиск AppRusLect05-2018.pdf
Лекция 6. Приближенные схемы. Задача теории расписаний AppRusLect06-2018.pdf
Лекция 7. Приближенные схемы. Задачи упаковки AppRusLect07-2018.pdf
Лекция 8. Приближенные схемы. Цеховая задача с нефиксированными маршрутами AppRusLect08-2018.pdf
Лекция 9. Линейное программирование. Задача теории расписаний AppRusLect09-2018.pdf
Лекция 10.

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

 
AppRusLect10-2018.pdf
Лекция 11.

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

 
AppRusLect11-2018.pdf
     
  Контрольная работа 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  

Редакция 08.05.2018