Новосибирский государственный университет
ММФ  Кафедра теоретической кибернетики
 Thin_Red_and_BlueA205.gif (1558 bytes)

 А. В. Кононов

Приближенные алгоритмы
 Курс лекций (слайды)

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


     

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

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

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

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

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

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)

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

 

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

Редакция 31.05.2022