Новосибирский государственный университет
Кафедра дискретного анализа и исследования операций

Thin_Red_and_BlueA205.gif (1558 bytes)

Ю.А. Кочетов

Теория принятия решений
Устные вопросы перед экзаменом

НГУ, Факультет информационных технологий
3 курс летняя сессия 2012 год
             

 

 

            

                      

                    

1. Метод динамического программирования на примере распределительной задачи.

2. Алгоритмы для задачи о рюкзаке с гарантированной точностью 0.5 и 0.75.

3. Аппроксимационные схемы. Полиномиальные и полностью полиномиальные аппроксимационные схемы.

4. Задача упаковки в контейнеры, отрицательный результат об аппроксимируемости.

5. Нижние оценки Martello и Toth.

6. Метод генерации столбцов для задачи упаковки в контейнеры.

7. Задача календарного планирования. Критические работы, пути и критическое время проекта.

8. Постановка задачи календарного планирования с ограниченными ресурсами.

9. Задача коммивояжера. Теорема о погрешности приближенных полиномиальных алгоритмов и алгоритмов локального спуска.

10. Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2. 

11. Нижние оценки в задаче коммивояжера: примитивная оценка, оценка линейного программирования, оценка задачи о назначениях и минимальные 1-деревья.

12. Алгоритм решения задачи о назначениях.

13. Метод ветвей и границ для задачи коммивояжера.

14. Классификация задач теории расписаний. Примеры.

15. Алгоритм Лаулера для задачи  1| prec| fmax

16. Алгоритм решения задачи  P | pmtn |Cmax

17. Алгоритм решения задачи  F2 || Cmax

18. Задачи о покрытии, алгоритм Хватала, оценка его погрешности и экстремальный пример.

19. Задачи размещения в условиях конкуренции, их связь с принятием решений голосованием, «безнадежный» пример.

20. Матричные игры. Определение седловой точки.  Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема Фон-Неймана. Дилемма заключенных.

 

Устные вопр. до экзам.ТПР_2012_.pdf

 

Лектор: д.ф.-м.н., профессор Кочетов Юрий Андреевич
e-mail:  jkochet@math.nsc.ru  

Редакция 22.05.2012