Новосибирский государственный университет
Кафедра дискретного анализа и исследования операций
Thin_Red_and_BlueA205.gif (1558 bytes)

  Устные вопросы "до билета" на экзамене

Теория принятия решений

3 курс  ФИТ   НГУ Летняя сессия,  2010 г.  
                 
      

Вопросы к экзамену

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

 

Вопросы к экзамену

Вернуться к лекциям


Редакция 18.05.2010