КОНТРОЛЬ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ

На контроль самостоятельной работы студентов отводится 4 часа для решения задач по теме «Теория игр».

ПРИМЕРНЫЕ ЗАДАНИЯ ДЛЯ КОНТРОЛЬНЫХ РАБОТ

Контрольная работа №1

1. Найти кратчайшие пути от вершины S до всех остальных вершин.

2. Построить максимальный поток и указать минимальный разрез в сети.

3. Построить поток мощности m минимальной стоимости с помощью алгоритма Клейна. Доказать, что стоимость минимальна.

4. Докажите, что положительный поток положительной мощности можно разложить в сумму элементарных положительных потоков вдоль контуров и вдоль путей, идущих от источника к стоку(считая, что в сети один источник и один сток)

Контрольная работа №2

Контрольная работа №3

ВОПРОСЫ К ЭКЗАМЕНУ

1. Графы. Маршруты, цепи, циклы, связные компоненты.

2. Три леммы о неориентированных графах.

3. Эйлеровы графы. Теорема Эйлера.

4. Алгоритм построения эйлерова цикла.

5. Деревья и их свойства.

6. Остовные деревья. Алгоритм Прима и его обоснование.

7. Алгоритм Краскала и его обоснование.

8. Ориентированные графы, маршруты, цепи, пути, циклы, контуры.

9. Алгоритм Дийкстры и его обоснование.

10. Алгоритм Флойда и его обоснование.

11. Нахождение контуров отрицательной длины.

12. Сети, потоки, разрезы. Леммы о дивергении и мощности потока.

13. Элементарные потоки. Разложение циркуляции на элементарные потоки.

14. Разложение потока на элементарные потоки.

15. Допустимые потоки. Лемма о мощности допустимого потока.

16. Увеличивающие цепи и теорема Форда–Фалкерсона.

17. Алгоритм Форда–Фалкерсона.

18. Потоки минимальной стоимости. Действия над потоками в исходной сети и в графе модифицированных стоимостей.

19. Критерий оптимальности допустимого потока.

20. Алгоритм Басакера–Гоуэна и его обоснование.

21. Алгоритм Клейна.

22. Метод ветвей и границ.

23. Задача коммивояжера. Алгоритм Литтла.

24. Сетевое планирование. Работы, события, алгоритм построения сетевой модели, ранжирование событий.

25. Минимальный и максимальный сроки наступления событий, их свойства. Критический путь. Свободный и полный резерв времени.

26. Игры (бескоалиционные, матричные, биматричные).

27. Доминирующие и недоминируемые стратегии. Их существование.

28. Осторожные стратегии и их существование. Гарантированный выигрыш.

29. Оптимальные по Парето исходы, их существование.

30. Несущественные игры, их свойства.

31. Игра двух лиц с нулевой суммой. Нижняя и верхняя цена игры. Связь цены игры с несущественностью.

32. Цена игры и седловые точки. Свойства седловых точек.

33. Теорема фон Нойманна.

34. Правила принятия решений и равновесия. Теоремы о неподвижной точке.

35. Канонические правила принятия решений. Равновесия по Нэшу и теорема Нэша.

36. Смешанные расширения конечных игр. Равновесия в них.

37. Смешанные расширения бесконечных игр.

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

ОСНОВНАЯ ЛИТЕРАТУРА

1. Бахтин В.И., Коваленок А.П., Лебедев А.В., Лысенко Ю.В. Исследование операций. – Минск, БГУ, 2003.

2. Майника Э. Алгоритмы оптимизации на сетях и графах. 1977.

3. Басакер P., Саати Т. Конечные графы и сети. 1974.

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА

1. Ху Т. Целочисленное программирование и потоки в сетях. 1974.

2. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. 1966.

3. Харари Ф. Теория графов. 1973.

4. Оре О. Теория графов. 1980.

5. Мулен P. Теория игр и экономические приложения. 1979.

6. Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. 1970.

7. Льюс Р.Д., Райфа X. Игры и решения. 1961.

8. Оуэн Г. Теория игр. 1971.

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

Поиск по сайту: