1631124435-59a81a8a1084f5170bbbb6e23ee88408 (848542), страница 2
Текст из файла (страница 2)
Другими словами, если существует оптимальнаястратегия p (q) такая, что p_i > 0 (q_i > 0), то чистая стратегия i (j) является активной дляпервого (второго) игрока.Теорема (Об активных стратегиях). Если один игрок придерживается оптимальнойстратегии, то его соперник достигает цены игры ν, применяя любую свою смешаннуюстратегию, в которой используются только активные стратегии.7.2.
Привести примеры NP-полных задачКласс NP-полных проблем (обозначим его NPC) – это подмножество задач PNP, обладающихсвойством, что любая задача из класса NP полиномиально сводится к P.Примеры: определение наличия в графе гамильтонова цикла, задача о коммивояжёре.7.3. Является ли NP-трудной задача нахождения пути минимальной длины между парой вершинв произвольном взвешенном графе с положительными весами ребер?Нет, т.к.
для решения этой задачи существует алгоритм Дейкстры с квадратичнойтрудоемкостью.8.1. Метод ветвей и границ для задачи коммивояжера. Способы построения нижних границ8.2. Можно ли в сетевой модели сначала найти поздние времена наступления событий, а затемранние? Ответ обосноватьНет. Для нахождения позднего времени наступление событий в алгоритме Форда необходимоналичия раннего времени наступления последнего события.8.3. Является ли NP-трудной в сильном смысле булева задача о ранце?Нет. Она может быть решена псевдополиномиальным алгоритмом, следовательно, не являетсяNP-полной в СС, а значит не является NP-трудной в СС.9.1. Применение теории NP- полноты для анализа задач.Полиномиальные задачи есть смысл решать, а если она неполиномиальная, то нечего мучитьсяи искать полиномиальные алгоритмы9.2.
Теорема об активных стратегиях (с доказательством).Чистая стратегия i является активной, если она используется в некоторой оптимальнойстратегии с положительной вероятностью. Другими словами, если существует оптимальнаястратегия p (q) такая, что > 0 ( > 0), то чистая стратегия i (j) является активной дляпервого (второго) игрока.Т.(Об активных стратегиях). Если один игрок придерживается оптимальной стратегии, тоего соперник достигает цены игры ν, применяя любую свою смешанную стратегию, вкоторой используются только активные стратегии.Док-во. Пусть первый игрок использует оптимальную стратегию p*, а второй − смешаннуюстратегию q, в которой q j > 0, j ∈ J′, где J′ − подмножество активных стратегий второгоигрока. Необходимо показать, что цена игры ν = E(p*, q).9.3.
Является ли NP-трудной (в сильном смысле) задача Гамильтонов цикл?Да.10.1. Задачи с числовыми параметрами. Сильная NP-полнота и псевдополиномиальныеалгоритмыЗадачи с числовыми параметрами – задача коммивояжера.Зам. Если задача П NP-полна в сильном смысле, то она не может быть решенапсевдоплиномиальным алгоритмом (Если P не равно NP)10.2. Является ли NP-трудной (в сильном смысле) задача коммивояжера?10.3. Два игрока бросают по 1 кости каждый. Первый игрок выигрывает выпавшую сумму, еслиэта сумма четная и проигрывает эту сумму, в противном случае. Существует ли решение вчистых стратегиях?Составим платежную матрицу12345612-34-56-72-34-56-7834-56-78-94-56-78-91056-78-910-116-78-910-1112где i-ая строка – число, которое выпало у первого игрока, j-ый столбец – число, которое выпалоу второго игрока.
Т.к. в матрице нет седловой точки, то по теореме о необходимом идостаточном условии равенства верхней и нижней цен игры не существует решения игры вчистых стратегиях.11.1. Теорема о (не)существовании приближенного полиномиального алгоритма для задачи оранце с гарантированной оценкой абсолютной погрешности (с доказательством).Если P ≠ NP, то не существует полиномиального алгоритма A для решения булевой задачи оранце (ЗР):∑=1 → max ; ∑=1 ≤ с целочисленными неотрицательными∊параметрами ck и ak, кот.
строит решение любой инд. задачи IЗР с ограниченной const абс.погрешностью: |A(I) – OPT(I)| Q = const(*).11.2. Существует ли псевдополиномиальный алгоритм решения задачи о ранце?Да. Также схема динамического программирования реализует псевдополиномиальныйалгоритм для целочисленной задачи о ранце с трудоемкостью O(nA).11.3. Два игрока бросают по 1 кости каждый.
Выигрыш 1 игрока равен разнице между числом,выпавшим на его кости, и числом, выпавшим на кости соперника. Имеет ли игра решение вчистых стратегиях?Составим платежную матрицу12345610123452-1012343-2-101234-3-2-10125-4-3-2-1016-5-4-3-2-10где i-ая строка – число, которое выпало у первого игрока, j-ый столбец – число, которое выпалоу второго игрока. Т.к.
в матрице есть седловая точка – элемент (6,6), то по теореме онеобходимом и достаточном условии равенства верхней и нижней цен игры существуетрешения игры в чистых стратегиях12.1. Теорема о минимальном разрезе и максимальном потоке (с доказательством).12.2. Пусть задачи P, Qможно сказать о P?NP, Q полиномиально разрешима, и P полиномиально сводится к Q.
Что(P полиномиально разрешима)12.3. Можно ли решить линейную задачу о ранце за полиномиальное время, если веса всехпредметов одинаковы?Да13.1. Теорема о (не)существовании приближенного полиномиального алгоритма для задачикоммивояжера с гарантированной оценкой относительной погрешности.Если P ≠ NP, то не существует полиномиального алгоритма A решения задачи КМ сотносительной погрешностью ограниченной константой.13.2.
Задачи распознавания свойств и их связь с экстремальными задачами.Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых являетсяответ «Да» или «Нет».Для экстремальной задачи на минимум задача распознавания свойств - это задача: есть ли х:F(x)≤B, где B константа, а для задачи на максимум наоборот.13.3. Почтовый голубь может выбрать три высоты полета.
За ним охотятся кошка, хулиган срогаткой и коршун. На первой высоте кошка поймает голубя с вероятностью 0.4, хулиганпопадет с вероятностью 0.3 и коршун поймает с вероятностью 0.1. На второй высотесоответствующие вероятности: 0.1, 0.4 и 0.5. И на третьей высоте – 0, 0.2 и 0.8. Существует лирешение игры в чистых стратегиях?Составим платежную матрицу0,40,100,30,40,20,10,50,8где i-ая строка – высота, которую выбрал голубь, j-ый столбец – вероятность окончить своебренное существование по вине, соответственно, беспощадной кошки, безжалостногохулигана, или бездушного, но голодного коршуна.
Т.к. в матрице нет седловой точки, то потеореме о необходимом и достаточном условии равенства верхней и нижней цен игры несуществует решения игры в чистых стратегиях.14.1. Лемма о сводимости NP- полных проблем (с доказательством).14.2. Как осуществить правильное упорядочивание дуг в сетевой модели, имея правильнуюнумерацию вершин?14.3. Почтовый голубь может выбрать три высоты полета. За ним охотятся кошка, хулиган срогаткой и коршун. На первой высоте кошка поймает голубя с вероятностью 0.4, хулиганпопадет с вероятностью 0.3 и коршун поймает с вероятностью 0.1. На второй высотесоответствующие вероятности: 0.1, 0.4 и 0.5. И на третьей высоте – 0, 0.2 и 0.8.
Существует лирешение игры в чистых стратегиях?Составим платежную матрицу0,40,100,30,40,20,10,50,8где i-ая строка – высота, которую выбрал голубь, j-ый столбец – вероятность окончить своебренное существование по вине, соответственно, беспощадной кошки, безжалостногохулигана, или бездушного, но голодного коршуна. Т.к. в матрице нет седловой точки, то потеореме о необходимом и достаточном условии равенства верхней и нижней цен игры несуществует решения игры в чистых стратегиях.15.1. Сетевые модели планирования и управления.
Сети «работы-дуги», «работы-вершины».Упрощение сети путем склейки вершин. Необходимое и достаточное условие эквивалентности сетейдо и после склейки.Сетевая модель (сетевой график) – это представление списка работ проекта в виде взвешенной сети,которое позволяет адекватно отразить связи между работами проекта.Используются два типа сетевых моделей, которые условно можно назвать: 1) «работы-вершины»; 2)«работы-дуги».«Работы-вершины»: вершина – образ работы; дуги служат для пред. отношения предшествованияработ. Для построения: ∀ работе проекта → вершина, имеющая вес = длительности; дуга (i, j) ∃, еслиработа i непосредственно предшествует работе j.В моделях «работы-дуги»: работы – дуги; направление дуги отображает част. порядок на мн.
работ.Вершины соответствуют событиям – моменты завершения одних работ и возможность началавыполнения других. Для построения: ∀ работе → дуга, имеющая вес = длительности. Из конечнойвер. дуги p проводится дуга в начальную вер. дуги q, если работа p непосредственно предшествуетработе q.
Дуга, которая не имеет прообраза в мн. работ и введена для задания отношенияпредшествования, называется фиктивной. Не фиктивные дуги называются фактическими.2 сети с одинаковым мн. фактических дуг наз. эквивалентными, если они представляют одно и то жеотношение предшествования фактических дуг.̅ – мн. фактических дуг сети, − подмножество фактических дуг ∊ μ(1, i), −подмножество фактических дуг ∊ μ(i, n).Рассмотрим пару вершин i и k:(1) не ∃ инцидентной им обеим фактической дуги.̅ : i(p)=i(q), k(p)=i, k(q)=k; или k(p)=k(q), i(p)=I, i(q)=k.(2) не ∃ дуг p, q∊ Результатом склейки вер. i и k в сети S, удовлетворяющих свойствам (1) и (2), является сеть S’, в кот.вер.
k удалена, а все дуги, кот. были ей инцидентные в S, в S’ инцидентны вер. i. Если в S окажетсянесколько параллельных фиктивных дуг, то все они, кроме одной, удаляются.Теорема. Пусть вершины i и k удовлетворяют условиям (1) и (2). Сеть S’, полученная из S врезультате склеивания вершин i, k и исключения k, эквивалентна S ⇔ = или = .15.2. НЕТ!!!! Пусть задачи P, Q NP, Q NPC, и P полиномиально сводится к Q.
Что можносказать о P?15.3. Почтовый голубь может выбрать три высоты полета. За ним охотятся кошка, хулиган с рогаткойи коршун. На первой высоте кошка поймает голубя с вероятностью 0.4, хулиган попадет свероятностью 0.3 и коршун поймает с вероятностью 0.1. На второй высоте соответствующиевероятности: 0.1, 0.4 и 0.5. И на третьей высоте – 0, 0.2 и 0.8. Существует ли решение игры в чистыхстратегиях?Составим платежную матрицу0,40,30,10,10,40,500,20,8где i-ая строка – высота, которую выбрал голубь, j-ый столбец – вероятность окончить свое бренноесуществование по вине, соответственно, беспощадной кошки, безжалостного хулигана, илибездушного, но голодного коршуна. Т.к. в матрице нет седловой точки, то по теореме о необходимоми достаточном условии равенства верхней и нижней цен игры не существует решения игры в чистыхстратегиях.16.1. Ранг события в сетевой модели. Алгоритм Форда и доказательство его корректности. Вычислениеранних и поздних времен наступления событий.Определение.
Ранг события (вершины) i, равен максимальному количеству дуг в пути из входа 1 ввершину i.Для нахождения рангов событий используется следующий алгоритм Форда.Шаг 0. Для всех вершин v = 1, …, n полагаем = 0. Пусть в результате s − 1 шагов найдены величины .Шаг s. Просматриваем последовательно работы-дуги j = 1, …, m и пересчитываем величины () =max{() , () + 1}.Если на каком-то шаге s ни одна из величин , v = 1, …, n, не изменилась, то они являются рангамисобытий, и алгоритм останавливается. Иначе, полагаем s = s + 1 и повторяем шаг s.Теорема.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
