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