prog (Билеты)

2

ПРОГРАММА ПО КУРСУ

²ТЕОРИЯ ИГР И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ²

9-й семестр, 5-й курс, 3-й поток

лектор доцент Фуругян М.Г.

1. Антагонистические игры. Верхнее и нижнее значения игры. Седловая точка. Смешанные стратегии. Необходимые и достаточные условия существования седловой точки. Теорема Фон Неймана о существовании седловой точки у вогнуто-выпуклых функций на компактах.

Смешанные стратегии в конечных антагонистических играх. Существование седловой точки в смешанных стратегиях в конечной игре. Свойства оптимальных смешанных стратегий в конечной игре. Доминирование строк и столбцов в матричной игре. Простое решение конечной игры. Крайние оптимальные смешанные стратегии. Теорема о крайних стратегиях. Игры 2´m и n´2. Связь теории игр с линейным программированием. Функция Лагранжа и ее свойства. Сведение антагонистической игры к задаче линейного программирования. Итеративный метод Брауна решения матричных игр.

Смешанные стратегии в бесконечных антагонистических играх. Аппроксимация непрерывных игр конечными. Существование седловой точки в смешанных стратегиях в играх с непрервыной платежной функцией.

Бескоалиционные игры. Ситуация равновесия по Нэшу. Необходимые и достаточные условия для ситуации равновесия.

Принцип уравнивания Ю.Б. Гермейера. Модель Гросса ²Нападение - оборона².

2. Потоки в сетях. Задача о максимальном потоке и ее решение (алгоритмы Форда-Фалкерсона и Карзанова). Теорема о максимальном потоке и минимальном разрезе.

Решение задачи составления допустимого расписания с прерываниями для многопроцессорной системы при заданных директивных интервалах. Алгоритм упаковки для задачи с одинаковыми директивными интервалами. Алгоритм Э.Г. Коффмана для однопроцессорной системы. Алгоритм коррекции директивных интервалов в случае задания графа частичного порядка.

3. Задача о потоке минимальной стоимости и ее приложения (транспортная задача, задача о назначениях, задача о максимальном потоке, задачи о кратчайшем и самом длинном путях, составление графика выполнения работ при жестких директивных интервалах, задача о паросочетаниях). Алгоритм дефекта.

4. Сети Петри. Матричная форма представления. Построение конечного дерева достижимости. Моделирование вычислительных систем. Представление конечных автоматов и графов вычислений сетями Петри.

5. Дополнительные вопросы теории сложности. Семь основных NP-полных задач (выполнимость, 3-выполнимость, трехмерное сочетание, вершинное покрытие, разбиение, гамильтонов цикл, клика). Теорема Кука. Методы доказательства NP-полноты (3-выполнимость, вершинное покрытие, независимое множество, клика, множество представителей, изоморфизм подграфу, остовное дерево ограниченной степени, рюкзак, самый длинный путь, упаковка множеств, наибольший общий подграф, минимум суммы квадратов, минимизация веса невыполненных заданий, упаковка в контейнеры, интеграл от произведения косинусов, доминирующее множество, расписание для многопроцессорной системы, упорядочение работ внутри интервалов, упорядочение с минимальным запаздыванием).

Псевдополиномиальные алгоритмы решения задач: разбиение, рюкзак, расписание для многопроцессорной системы (число процессоров фиксировано), упаковка в контейнеры (число контейнеров фиксировано). Псевдополиномиальная сводимость. Сильная NP-полнота задач упорядочение работ внутри интервалов, многопроцессорное расписание без прерываний, коммивояжер, упаковка в контейнеры.

NP-трудные задачи: K-е по порядку множество. NP-эквивалентные задачи (оптимизационные варианты семи основных NP-полных задач, оптимизационная задача коммивояжера).

6. Методы решения NP-трудных задач. Метод ветвей и границ решения задач: самый длинный путь, коммивояжер, оптимальное расписание в системе с несколькими различными процессорами, распределение возобновляемых ресурсов.

Приближенные алгоритмы решения NP-трудных задач: упаковка в контейнеры, рюкзак, коммивояжер, расписание для многопроцессорной системы, вершинное покрытие; оценки их погрешности. Применение теории NP-полноты к отысканию приближенных решений.

Рандомизированные алгоритмы. Лемма Шварца. (Задача проверки идентичности полиномов. Задача о паросочетаниях).

ЛИТЕРАТУРА

1. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

2. Гермейер Ю.Б. Игры с непротивоположными интересами.

3. Давыдов Э.Г. Исследование операций. М.: Высшая школа, 1990.

4. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.: Высш. Шк., 1998.

5. Морозов В.В. Основы теории игр. М.: МГУ, 2002.

6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

7. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984.

8. Теория расписаний и вычислительные машины/ Под ред. Коффмана Э.Г. М.: Наука, 1984.

9. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

10. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.

11. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.

12. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.

13. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ.

М.: МЦНМО, 2001.

14. WWW.ECCC.UNI-TRIER.DE/ECCC.