quest (811104)
Текст из файла
5
ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ
ПО КУРСУ ²ТЕОРИЯ ИГР И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ²
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 £ 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) + xy2, определенная на множествах X=Y=[0, 1], имеет седловую точку.
11. Необходимые условия для седловой точки у функции K(x, y), определенной на множествах ai £ xi £ bi, i = 1, ..., n, cj £ yj £ dj, j = 1, ..., m.
12. Найти седловую точку функции K(x, y) = 8(4xy2 -2x2 -y), определенной на множествах X = Y = [0, 1].
13. Смешанные стратегии в матричных антагонистических играх.
Существование седловой точки в смешанных стратегиях.
14. Свойства оптимальных смешанных стратегий в матричных
антагонистических играх.
15. Доминирование строк и столбцов в матричных антагонистических играх.
16. Решение матричных антагонистических игр 2 ´ m и n ´ 2.
17. Найти решение в смешанных стратегиях в антагонистической игре с платежной матрицей
.
18. Найти решение в смешанных стратегиях в антагонистической игре с платежной матрицей
.
19. Найти решение в смешанных стратегиях в антагонистической игре с платежной матрицей
.
20. Найти решение в смешанных стратегиях в антагонистической игре с платежной матрицей
.
21. Найти решение в смешанных стратегиях в антагонистической игре с платежной матрицей
.
22. Итеративный метод Брауна решения матричных антагонистических игр.
23. Вычисление простых решений матричных антагонистических игр. Вполне смешанные игры.
24. Необходимые и достаточные условия для крайних оптимальных
смешанных стратегий в матричной антагонистической игре.
25. Найти все крайние оптимальные смешанные стратегии в антагонистической игре с платежной матрицей 
.
26. Доказать, что множества оптимальных смешанных стратегий игроков в матричной антагонистической игре являются выпуклыми многогранниками.
27. Связь между существованием решения задачи линейного программирования в стандартной форме и седловой точкой функции Лагранжа.
28. Сведение решения конечной антагонистической игры к задаче линейного программирования.
29. Оптимальные смешанные стратегии в бесконечных антагонистических играх. Существование седловой точки в смешанных стратегиях в играх с непрерывной платежной функцией.
30. Бескоалиционные игры. Необходимые и достаточные условия для ситуации равновесия.
31. Принцип уравнивания Ю.Б. Гермейера в задачах распределения ресурсов.
32. Модель Гросса ²Оборона - нападение².
33. Найти 
, где Wi > 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)}. Параметры дуг (Lij, Uij, cij) следующие: (0,2,2), (0,4,5), (0,1,1), (0,4,3), 0,1,1), (1,2,6), (3,3,0).
43. Построение допустимого расписания с прерываниями для многопроцессорной системы при заданных длительностях работ и директивных интервалах.
44. Путем сведения задачи построения допустимого расписания к задаче о максимальном потоке в сети построить допустимое расписание (с прерываниями) выполнения трех заданий на двух одинаковых процессорах. Директивные интервалы и длительности заданий следующие:
[b1, f1] = [0, 6], [b2, f2] = [0, 3], [b3, f3] = [1, 6], t1 = 5, t2 = 3, t3 = 4.
45. Алгоритм Коффмана построения допустимого расписания с прерываниями для однопроцессорной системы при заданных длительностях работ и директивных интервалах.
46. Теорема Кука.
47. Семь основных NP-полных задач. Доказательство NP-полноты задачи ²3-выполнимость².
48. Доказательство NP-полноты задачи ²вершинное покрытие².
49. Доказательство NP-полноты задачи ²клика².
50. Доказать NP-полноту задачи ²расписание для мультипроцессорной системы без прерываний² [Задано конечное множество заданий N и для каждого i Î N длительность ti, и общий директивный срок T. Существует ли m-процессорное расписание без прерываний, при котором все задания завершатся не позднее срока T ?] путем сведения к ней одной из семи основных NP-полных задач.
51. Доказать NP-полноту задачи ²упорядочение внутри интервалов² [Задано конечное множество заданий N и для каждого i Î N длительность ti и директивный интервал (bi,fi]. Существует ли однопроцессорное расписание без прерываний, такое, что каждое задание полностью выполняется в своем директивном интервале?] путем сведения к ней одной из семи основных NP-полных задач.
52. Доказать NP-полноту задачи ²упорядочение с минимальным запаздыванием² [Задано конечное множество заданий N, для каждого i Î N длительность ti =1 и директивный интервал (0, fi], граф частичного порядка G=(N,A) и число K. Существует ли однопроцессорное расписание без прерываний, при котором число заданий, не выполненных к своему директивному сроку, не превосходит K ?] путем сведения к ней одной из семи основных NP-полных задач.
53. Доказать NP-полноту задачи ²Самый длинный путь² [Заданы граф G = (V, E) и число K £ |V|. Имеется ли в G простой путь (т.е. путь, не проходящий дважды ни через одну вершину), состоящий не менее чем из K ребер?] путем сведения к ней одной из семи основных NP-полных задач.
54. Доказать NP-полноту задачи ²Упаковка множеств² [Заданы семейство C конечных множеств и число K, K £ |C|. Верно ли, что в C имеется K непересекающихся множеств?²] путем сведения к ней одной из семи основных NP-полных задач.
55. Доказать NP-полноту задачи ²Наибольший общий подграф² [Заданы два графа G1=(V1, E1), G2 = (V2, E2) и число K. Существуют ли такие подмножества E'1 Í E1 и E'2 Í E2, что |E'1| = |E'2| ³ K, а подграфы G'1=(V1, E'1) и G'2 = (V2, E'2) изоморфны?] путем сведения к ней одной из семи основных NP-полных задач.
56. Доказать NP-полноту задачи ²Доминирующее множество² [Заданы граф G = (V, E) и число K, K £ |V|. Существует ли такое подмножество V'Í V, что |V'| £ K и каждая вершина v ÎV\ V' соединена ребром по крайней мере с одной вершиной из V'?] путем сведения к ней одной из семи основных NP-полных задач.
57. Доказать NP-полноту задачи ²Минимум суммы квадратов² [Заданы конечное множество N, размер si для каждого i Î N и числа K и J. Могут ли элементы из N быть разбиты на K непересекающихся множеств N1, ..., NK, таких, что 
] путем сведения к ней одной из семи основных NP-полных задач.
58. ДоказатьNP-полноту задачи ²Минимизация веса невыполненных заданий² [Заданы конечное множество N заданий, число K, а также для каждого задания i Î N длительность ti, вес wi и директивный срок fi. Существует ли однопроцессорное расписание (без прерываний) r для заданий из N, такое, что 
, где ri - момент начала выполнения задания i Î N?] путем сведения к ней одной из семи основных NP-полных задач.
59. Доказать NP-полноту задачи ²Упаковка в контейнеры² [Заданы конечное множество N предметов, размер si каждого предмета i Î N, вместимость B контейнера и число K. Существует ли такое разбиение множества N на непересекающиеся подмножества N1, ..., NK, что 
для всех j=1, ..., K?] путем сведения к ней одной из семи основных NP-полных задач.
60. Доказать NP-полноту задачи ²Интеграл от произведения косинусов² [Задана последовательность целых чисел a1, a2, ..., an. Верно ли, что
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
