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

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

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

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

  1. Идея динамического программирования.

  2. Полиномиальные алгоритмы с гарантированной точностью.

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

  4. Задача упаковки в контейнеры. Нижние оценки целевой функции.

  5. On-line алгоритмы, примеры таких алгоритмов для задачи упаковки в контейнеры.

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

  7. Идея алгоритм имитации отжига.

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

  9. Постановки задач календарного планирования с ограниченными ресурсами. Три типа ресурсов. Т-поздние расписания. Алгоритм Гимади.

  10. Две постановки задач календарного планирования с переменными длительностями работ.

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

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

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

  14. Идея метода ветвей и границ.

  15. Классификация задач теории расписаний: задачи  1| prec | fmax ,    1| prec, pmtn, ri| fmax

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

  17. Идея генетических алгоритмов

  18. Постановки задач размещения производства, квадратичной задачи о назначениях, задачи размещения производства с предпочтениями клиентов.

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

  20. Матричные игры. Определение седловой точки. Чистые и смешанные стратегии.

  21. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема Фон-Неймана.

 

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


Редакция 30.05.2007