Устные вопросы до экзамена
4 курс,
ММФ НГУ, зимняя сессия
1.
Приближенные алгоритмы с
гарантированной относительной точностью. Модифицированный жадный
алгоритм для задачи о рюкзаке и алгоритм с точностью ¾.
2.
Аппроксимационные схемы, полиномиальные и полностью полиномиальные схемы
для задачи о рюкзаке.
3.
Задача упаковки в контейнеры. Алгоритмы
NF,
FF,
BF,
FFD,
отрицательный результат об аппроксимируемости.
4.
Нижние оценки
Martello
и Toth.
5.
Метод генерации столбцов
для задачи упаковки в контейнеры.
6.
Задача календарного планирования. Критические работы, пути и критическое
время проекта.
7.
Задачи календарного планирования с ограниченными ресурсами.
8.
Алгоритм Гимади для задачи со складируемыми ресурсами.
9.
Задача коммивояжера. Теорема о погрешности приближенных полиномиальных
алгоритмов и алгоритмов локального спуска.
10. Задача
коммивояжера с неравенством треугольника. Алгоритм с гарантированной
оценкой точности 2.
11. Нижние
оценки в задаче коммивояжера
12. Алгоритм
Лаулера для задачи 1|
prec|
fmax
13. Алгоритм
решения задачи
P
| pmtn
|Cmax
14. Алгоритм
решения задачи
P
| pmtn,
ri
|Lmax
15. Алгоритм
решения задачи
F2
|| Cmax
16. Задачи
о покрытии, алгоритм Чватала
17. Задача
размещения в условиях конкуренциии «безнадежный» пример.
18. Матричные
игры. Определение седловой точки.
19. Теорема
Фон-Неймана.
20. Бескоалиционные
игры, равновесие по Нэшу.
21. Многокритериальная
оптимизация. Эффективные решения по Парето и Джеоффриону. Метод уступок.
Список
вопросов в pdf
