Кафедра дискретного анализа и исследования операций
Новосибирский
государственный университет
Кафедра
дискретного анализа и исследования
операций
Устные
вопросы "до билета" на экзамене
Теория
принятия решений
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