VOPR02 (Билеты)

5

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

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

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

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

1. Доказать, что .

2. Доказать, что если функция K(x,y) непрерывна на X´Y (X, Y - компакты), то функция непрерывна на X.

3. Для функции K(x,y) = 1 - (x - y)², определенной на множествах

X = Y = [0, 1], вычислить .

4. Найти чистые оптимальные гарантирующие стратегии первого и второго игроков в игре с платежной функцией K(x, y) = (x - y)² - 0.5x², -1 £ x £ 1, -1 £ y £ 1.

5. Выписать платежную функцию для антагонистической игры типа ²бесшумная дуэль² и найти чистые оптимальные гарантирующие стратегии игроков для случая, когда функции меткости p(x) = x, q(y) = y, 0 £ x £ 1, 0 £ y £ 1.

6. Выписать платежную функцию для антагонистической игры типа ²шумная дуэль² и найти чистые оптимальные гарантирующие стратегии игроков для случая, когда функции меткости p(x) = x, q(y) = y, 0£ x £ 1, 0 £ y £ 1.

7. Выписать платежную функцию для антагонистической ²игры с задержкой² и найти смешанные оптимальные гарантирующие стратегии игроков.

8. Понятие седловой точки. Необходимые и достаточные условия существования седловой точки в чистых стратегиях в антагонистической игре.

9. Теорема Фон Неймана о существовании седловой точки у вогнуто-выпуклых функций.

10. Доказать, что функция K(x, y) = yln(x+2) + xy², определенная на множествах X = Y = [0, 1], имеет седловую точку.

11. Необходимые условия для седловой точки у функции K(x, y), определенной на множествах a_i £ x_i £ b_i, i = 1, ..., n, c_j £ y_j £ d_j, j = 1, ..., m.

12. Найти седловую точку функции K(x, y) = 8(4xy² -2x² -y), определенной на множествах X = Y = [0, 1].

13. Сведение задачи поиска максимина к задаче максимизации.

14. Смешанные стратегии в матричных антагонистических играх.

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

15. Свойства оптимальных смешанных стратегий в матричных

антагонистических играх.

16. Доминирование строк и столбцов в матричных антагонистических играх.

17. Решение матричных антагонистических игр 2 ´ m и n ´ 2.

18. Найти решение в смешанных стратегиях антагонистической игры с платежной матрицей

.

19. Найти решение в смешанных стратегиях антагонистической игры с платежной матрицей

.

20. Найти решение в смешанных стратегиях антагонистической игры с платежной матрицей

.

21. Найти решение в смешанных стратегиях антагонистической игры с платежной матрицей

.

22. Итеративный метод Брауна решения матричных антагонистических игр.

23. Вычисление простых решений матричных антагонистических игр. Вполне смешанные игры.

24. Необходимые и достаточные условия для крайних оптимальных

смешанных стратегий в матричной антагонистической игре.

25. Найти все крайние оптимальные смешанные стратегии в антагонистической игре с платежной матрицей .

26. Доказать, что множества оптимальных смешанных стратегий игроков в матричной антагонистической игре являются выпуклыми многогранниками.

27. Связь между существованием решения задачи линейного программирования в стандартной форме и седловой точкой функции Лагранжа.

28. Сведение решения конечной антагонистической игры к задаче линейного программирования.

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

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

31. Принцип уравнивания Ю.Б. Гермейера в задачах распределения ресурсов.

32. Модель Гросса ²Оборона - нападение².

33. Найти , где W_i > 0 (i = 1, ..., n).

34. Потоки в сетях. Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.

35. Привести пример, когда алгоритм Форда-Фалкерсона не находит максимального потока.

36. Теорема о максимальном потоке и минимальном разрезе в сетях.

37. Алгоритм Карзанова нахождения максимального потока в сети.

38. С помощью алгоритма Форда-Фалкерсона найти максимальный поток из s в t в сети с дугами (s, 1), (s, 2), (s, 3), (1,2), (1, t), (2, 3), (2, t), (3, t), пропускные способности которых равны 2, 3, 1, 4, 3, 1, 2, 2 соответственно.

39. С помощью алгоритма Карзанова найти максимальный поток из s в t в сети с дугами (s, 1), (s, 2), (s, 3), (1,2), (1, t), (2, 3), (2, t), (3, t), пропускные способности которых равны 2, 3, 1, 4, 3, 1, 2, 2 соответственно.

40. Задача о потоке минимальной стоимости в сети. Алгоритм дефекта.

41. Сведение к задаче о потоке минимальной стоимости в сети транспортной задачи, задачи о назначениях, задачи о максимальном потоке, задач о кратчайшем и самом длинном путях, задачи составления графика выполнения заданий с жесткими директивными интервалами, задачи о паросочетаниях.

42. С помощью алгоритма дефекта найти поток минимальной стоимости в сети G=(V, A), V = {1, 2, 3, 4}, A = {(1,2), (1,3), (2,3), (2,4), (3,2), (3,4), (4,1)}. Параметры дуг (L_ij, U_ij, c_ij) следующие: (0,2,2), (0,4,5), (0,1,1), (0,4,3), 0,1,1), (1,2,6), (3,3,0).

43. Построение допустимого расписания с прерываниями для многопроцессорной системы при заданных длительностях работ и директивных интервалах.

44. Путем сведения задачи построения допустимого расписания к задаче о максимальном потоке в сети построить допустимое расписание (с прерываниями) выполнения трех заданий на двух одинаковых процессорах. Директивные интервалы и длительности заданий следующие:

[b₁, f₁] = [0, 6], [b₂, f₂] = [0, 3], [b₃, f₃] = [1, 6], t₁ = 5, t₂ = 3, t₃ = 4.

45. Алгоритм Коффмана построения допустимого расписания с прерываниями для однопроцессорной системы при заданных длительностях работ и директивных интервалах.

46. Теорема Кука.

47. Семь основных NP-полных задач. Доказательство NP-полноты задачи ²3-выполнимость².

48. Доказательство NP-полноты задач ²вершинное покрытие² и ²клика².

49. Доказать NP-полноту задачи ²расписание для мультипроцессорной системы без прерываний² путем сведения к ней одной из семи основных NP-полных задач.

50. Доказать NP-полноту задачи ²упорядочение внутри интервалов² путем сведения к ней одной из семи основных NP-полных задач.

51. Доказать NP-полноту задачи ²упорядочение с минимальным запаздыванием² путем сведения к ней одной из семи основных NP-полных задач.

52. Доказать NP-полноту задачи ²Самый длинный путь [Заданы граф G = (V, E) и число K £ |V|. Имеется ли в G простой путь (т.е. путь, не проходящий дважды ни через одну вершину), состоящий не менее чем из K ребер?²] путем сведения к ней одной из семи основных NP-полных задач.

53. Доказать NP-полноту задачи ²Упаковка множеств [Заданы семейство C конечных множеств и число K, K £ |C|. Верно ли, что в C имеется K непересекающихся множеств?²] путем сведения к ней одной из семи основных NP-полных задач.

54. Доказать NP-полноту задачи ²Наибольший общий подграф [Заданы два графа G₁ = (V₁, E₁), G₂ = (V₂, E₂) и число K. Существуют ли такие подмножества E'₁ Í E₁ и E'₂ Í E₂, что |E'₁| = |E'₂| ³ K, а подграфы G'₁=(V₁, E'₁) и G'₂ = (V₂, E'₂) изоморфны?²] путем сведения к ней одной из семи основных NP-полных задач.

55. Доказать NP-полноту задачи ²Доминирующее множество [Заданы граф G = (V, E) и число K, K £ |V|. Существует ли такое подмножество V'Í V, что |V'| £ K и каждая вершина v ÎV\ V' соединена ребром по крайней мере с одной вершиной из V'?²] путем сведения к ней одной из семи основных NP-полных задач.

56. Доказать NP-полноту задачи ²Минимум суммы квадратов [Заданы конечное множество N, размер s_i для каждого i Î N и числа K и J. Могут ли элементы из N быть разбиты на K непересекающихся множеств N₁, ..., N_K, таких, что ²] путем сведения к ней одной из семи основных NP-полных задач.

57. ДоказатьNP-полноту задачи ²Минимизация веса невыполненных заданий [Заданы конечное множество N заданий, число K, а также для каждого задания i Î N длительность t_i, вес w_i и директивный срок f_i. Существует ли однопроцессорное расписание (без прерываний) r для заданий из N, такое, что , где r_i - момент начала выполнения задания i Î N?²] путем сведения к ней одной из семи основных NP-полных задач.

58. Доказать NP-полноту задачи ²Многопроцессорное расписание с учетом затрат на прерывания [Заданы конечное множество N заданий, число одинаковых процессоров m, а также для каждого задания i Î N длительность t_i и директивный интервал [b_i, f_i]. Существует ли m-процессорное допустимое расписание (прерывания допускаются) при условии, что каждое прерывание и переключение с одного процессора на другой требует дополнительно t > 0 единиц процессорного времени?²] путем сведения к ней одной из семи основных NP-полных задач.

59. Доказать NP-полноту задачи ²Упаковка в контейнеры [Заданы конечное множество N предметов, размер s_i каждого предмета i Î N, вместимость B контейнера и число K. Существует ли такое разбиение множества N на непересекающиеся подмножества N₁, ..., N_K, что для всех j=1, ..., K?²] путем сведения к ней одной из семи основных NP-полных задач.

60. Доказать NP-полноту задачи ²Интеграл от произведения косинусов [Задана последовательность целых чисел a₁, a₂, ..., a_n. Верно ли, что

?²] путем сведения к ней одной из семи основных NP-полных задач.

61. Задачи с числовыми параметрами. Псевдополиномиальный алгоритм решения задачи о разбиении.

62. Псевдополиномиальный алгоритм решения задачи о рюкзаке.

63. Псевдополиномиальный алгоритм решения задачи ²расписание для многопроцессорной системы без прерываний с фиксированным числом процессоров².

64. Псевдополиномиальный алгоритм решения задачи ²упаковка в контейнеры² с фиксированным числом контейнеров.

65. NP-полнота в сильном смысле. Псевдополиномиальная сводимость. Методы доказательства сильной NP-полноты.

66. Доказать, что задача ²упорядочение внутри интервалов² является NP- полной в сильном смысле.

67. Доказать, что задача ²многопроцессорное расписание без прерываний² является NP- полной в сильном смысле.

68. Доказать, что задача коммивояжера является NP- полной в сильном смысле.