VOPR02 (811102)
Текст из файла
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. Доминирование строк и столбцов в матричных антагонистических играх.
17. Решение матричных антагонистических игр 2 ´ m и n ´ 2.
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-полноту задачи ²расписание для мультипроцессорной системы без прерываний² путем сведения к ней одной из семи основных 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-полноту задачи ²Наибольший общий подграф [Заданы два графа 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-полных задач.
55. Доказать NP-полноту задачи ²Доминирующее множество [Заданы граф G = (V, E) и число K, K £ |V|. Существует ли такое подмножество V'Í V, что |V'| £ K и каждая вершина v ÎV\ V' соединена ребром по крайней мере с одной вершиной из V'?²] путем сведения к ней одной из семи основных NP-полных задач.
56. Доказать NP-полноту задачи ²Минимум суммы квадратов [Заданы конечное множество N, размер si для каждого i Î N и числа K и J. Могут ли элементы из N быть разбиты на K непересекающихся множеств N1, ..., NK, таких, что 
²] путем сведения к ней одной из семи основных NP-полных задач.
57. ДоказатьNP-полноту задачи ²Минимизация веса невыполненных заданий [Заданы конечное множество N заданий, число K, а также для каждого задания i Î N длительность ti, вес wi и директивный срок fi. Существует ли однопроцессорное расписание (без прерываний) r для заданий из N, такое, что 
, где ri - момент начала выполнения задания i Î N?²] путем сведения к ней одной из семи основных NP-полных задач.
58. Доказать NP-полноту задачи ²Многопроцессорное расписание с учетом затрат на прерывания [Заданы конечное множество N заданий, число одинаковых процессоров m, а также для каждого задания i Î N длительность ti и директивный интервал [bi, fi]. Существует ли m-процессорное допустимое расписание (прерывания допускаются) при условии, что каждое прерывание и переключение с одного процессора на другой требует дополнительно t > 0 единиц процессорного времени?²] путем сведения к ней одной из семи основных NP-полных задач.
59. Доказать NP-полноту задачи ²Упаковка в контейнеры [Заданы конечное множество N предметов, размер si каждого предмета i Î N, вместимость B контейнера и число K. Существует ли такое разбиение множества N на непересекающиеся подмножества N1, ..., NK, что 
для всех j=1, ..., K?²] путем сведения к ней одной из семи основных NP-полных задач.
60. Доказать NP-полноту задачи ²Интеграл от произведения косинусов [Задана последовательность целых чисел a1, a2, ..., an. Верно ли, что
?²] путем сведения к ней одной из семи основных NP-полных задач.
61. Задачи с числовыми параметрами. Псевдополиномиальный алгоритм решения задачи о разбиении.
62. Псевдополиномиальный алгоритм решения задачи о рюкзаке.
63. Псевдополиномиальный алгоритм решения задачи ²расписание для многопроцессорной системы без прерываний с фиксированным числом процессоров².
64. Псевдополиномиальный алгоритм решения задачи ²упаковка в контейнеры² с фиксированным числом контейнеров.
65. NP-полнота в сильном смысле. Псевдополиномиальная сводимость. Методы доказательства сильной NP-полноты.
66. Доказать, что задача ²упорядочение внутри интервалов² является NP- полной в сильном смысле.
67. Доказать, что задача ²многопроцессорное расписание без прерываний² является NP- полной в сильном смысле.
68. Доказать, что задача коммивояжера является NP- полной в сильном смысле.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как 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}
