Главная
страница 1
скачать файл
Теория игр и исследование операций

Кафедра ИО.
ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ ПО КУРСУ ТЕОРИЯ ИГР И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
9-й семестр, 5-й курс, 3-й поток
лектор доцент Фуругян М.Г.


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

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

  3. Для функции K(x,y) = 1 - (x - y)2, определенной на множествах X = Y = [0, 1], вычислить .

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

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

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

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

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

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

  10. Необходимые условия для седловой точки у функции K(x, y), определенной на множествах ai ? xi ? bi, i = 1, ..., n, cj ? yj ? dj, j = 1, ..., m.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  37. С помощью алгоритма Форда-Фалкерсона найти максимальный поток из 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 соответственно.

  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. Задача о потоке минимальной стоимости в сети. Алгоритм дефекта.

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

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

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

  43. Путем сведения задачи построения допустимого расписания к задаче о максимальном потоке в сети построить допустимое расписание (с прерываниями) выполнения трех заданий на двух одинаковых процессорах. Директивные интервалы и длительности заданий следующие: [b1, f1] = [0, 6], [b2, f2] = [0, 3], [b3, f3] = [1, 6], t1 = 5, t2 = 3, t3 = 4.

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

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

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

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

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

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

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

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

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

  53. Путем сведения к одной из семи основных NP-полных задач доказать NP-полноту задачи ? Наибольший общий подграф. Заданы два графа G1 = (V1, E1), G2 = (V2, E2) и число K. Существуют ли такие подмножества E'1 I E1 и E'2 I E2, что | E'1| = | E'2| ? K, а подграфы G'1=(V1, E'1) и G'2 = (V2, E'2) изоморфны?? .

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

  55. Путем сведения к одной из семи основных NP-полных задач доказать NP-полноту задачи ? Минимум суммы квадратов. Заданы конечное множество N, размер si для каждого i I N и числа K и J. Могут ли элементы из N быть разбиты на K непересекающихся множеств N1, ..., NK, таких, что ? .

  56. Путем сведения к одной из семи основных NP-полных задач доказатьNP-полноту задачи ? Минимизация веса невыполненных заданий. Заданы конечное множество N заданий, число K, а также для каждого задания i I N длительность ti, вес wi и директивный срок fi. Существует ли однопроцессорное расписание (без прерываний) r для заданий из N, такое, что , где ri - момент начала выполнения задания i I N??.

  57. Путем сведения к одной из семи основных NP-полных задач доказать NP-полноту задачи ? Многопроцессорное расписание с учетом затрат на прерывания. Заданы конечное множество N заданий, число одинаковых процессоров m, а также для каждого задания i I N длительность ti и директивный интервал [bi, fi]. Существует ли m-процессорное допустимое расписание (прерывания допускаются) при условии, что каждое прерывание и переключение с одного процессора на другой требует дополнительно t > 0 единиц процессорного времени?? .

  58. Путем сведения к одной из семи основных NP-полных задач доказать NP-полноту задачи ? Упаковка в контейнеры. Заданы конечное множество N предметов, размер si каждого предмета i I N, вместимость B контейнера и число K. Существует ли такое разбиение множества N на непересекающиеся подмножества N1, ..., NK, что для всех j=1, ..., K?? .

  59. Путем сведения к одной из семи основных NP-полных задач доказать NP-полноту задачи ? Интеграл от произведения косинусов. Задана последовательность целых чисел a1, a2, ..., an. Верно ли, что ?? .

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

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

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

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

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

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

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

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

  68. Сводимость по Тьюрингу. NP-трудные задачи.

  69. Доказать, что задача ? К-е по порядку множество? является NP-трудной.

  70. Доказать, что оптимизационные варианты семи основных NP-полных задач являются NP-эквивалентными.

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

  72. Приближенный алгоритм решения задачи ? упаковка в контейнеры? с оценкой RA <2.

  73. Доказать, что если P ? NP, то не существует полиномиального приближенного алгоритма решения задачи о рюкзаке с оценкой ? A(I) - OPT(I)? ? K.

  74. Доказать, что если P ? NP, то не существует полиномиального приближенного алгоритма решения задачи о максимальном независимом множестве с оценкой ? A(I) - OPT(I)? ? K.

  75. Приближенный алгоритм решения задачи коммивояжера с оценкой RA < 1.5.

  76. Приближенный алгоритм решения задачи ? многопроцессорное расписание без прерываний? с оценкой RA <2.

  77. Метод ? ветвей и границ? для решения задачи ? многопроцессорное расписание без прерываний (случай различных процессоров)? .

  78. Метод ? ветвей и границ? для решения задачи распределения нескладируемых ресурсов на сети.

  79. Метод ? ветвей и границ? для решения задачи коммивояжера.

  80. Метод ? ветвей и границ? для решения задачи ? самый длинный путь? .

  81. Приближенный алгоритм решения задачи о рюкзаке с временной сложностью O(n4/e ).

  82. Сети Петри. Построение конечного дерева достижимости.

  83. Матричная форма представления сетей Петри. Решение задачи о достижимости маркировки.

  84. Моделирование вычислительных систем с помощью сетей Петри.

  85. Представление конечных автоматов и графов вычислений сетями Петри.

  86. Вероятностный метод построения детерминированного алгоритма приближенного решения задачи целочисленного линейного программирования.

  87. Лемма Шварца. Рандомизированный алгоритм решения задачи об идентичности полиномов и задачи о паросочетаниях.
скачать файл



Смотрите также:
Программа-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика»
39.47kb.
Теория игр и исследование операций
68.64kb.
Рабочая программа дисциплины исследование операций
182.55kb.
Журналы Российской академии наук
48.74kb.
Теория игр для экономистов. Вводный курс Печерский С. Л., Беляева А. А
782.88kb.
1. Основы теории управления Основные понятия теории управления: цели и принципы управления, динамические системы
104.09kb.
Что изучает и когда возникла теория вероятностей. Понятие случайного эксперимента. Пространство элементарных исходов. Типы и примеры. Элементы комбинаторики. Понятие события
184.62kb.
Учебно-методический комплекс по дисциплине теория игр (наименование дисциплины) для направления(ий)
231.18kb.
"Решение оптимизационных задач линейного программирования"
336.89kb.
Исследование операций руководитель проф. В. Р. Фазылов
10.79kb.
Олимпийские хроники. Встреча Олимпийской сборной России. Гала-концерт закрытия игр XXII зимние игры в Сочи-2014 подошли к концу
112.79kb.
Курсовой проект по дисциплине «Теория механизмов и машин» «Проектирование и исследование механизмов подачи заготовок»
332.36kb.