1631124435-59a81a8a1084f5170bbbb6e23ee88408 (848542)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

1.1. Алгоритмы и оценки их качества. Трудоемкость, память, точность. Примерыполиноминальных и экспоненциальных алгоритмов.Алг. A наз. полиномиальным, если его трудоемкость () = ( ), где d – целоеположительное число. Алг., трудоемкость которого не ограничена полиномом от длинывхода, наз.

экспоненциальным.Трудоемкость алгоритма A называется функция () = sup{ (): () = }, где ()∊количество элементарных операций выполняемых алгоритмом А при решениииндивидуальной задачи X ∊P.ПРИМЕР: Пусть n – входная длина.Алг. A1 решает задачу P с трудоемкостью O(n5). Алг. A2 имеет трудоемкость O(2n) решениязадачи P.

ЭВМ - 1 млн. опер./сек. Тогда при n = 60 алг. A1 будет работать около 13 минут, а алг.A2 – более 300 столетий!Предположим, что A2 строит решение задачи размерности D на вышеупомянутом компьютереза 1 час. Если взять компьютер, выполняющий в 1000 раз больше операций в секунду, торазмерность задачи, которая решается алг. A2 на таком компьютере в течение 1 часа, будетвсего D + 9.97. Пол. алг. – эффективные! Эксп.

– не эффективны!1.2. Можно ли в сетевой модели сначала найти поздние времена наступления событий, а затемранние? Ответ обосновать.Нет. Для нахождения позднего времени наступление событий в алгоритме Форда необходимоналичия раннего времени наступления последнего события.1.3. Для каких задач псевдополиномиальный алгоритм становится полиномиальным?Привести примеры.При ограничении числовых параметров сверху некоторой наперед заданной константойпсевдополиномиальный алгоритм становится полиномиальным.

Задача, для которойсуществует такой алгоритм, называется псевдополиномиально разрешимой. Пример – задача оранце2.1. Потоки в сетях. Разрезы. Теорема Форда-Фалкерсона (с доказательством)Сеть - связный ориентированный граф G = (V, A) без петель и мультидуг, с 1 источником sV и1 стоком tV. (Запретим одновременное  дуг (i, j) и (j, i)).  дуге графа (i, j)  A, приписанапропускная способность bij ≥ 0, целое число, которое задает max доп. величину потока по дуге.Потоком из источника s в сток t (или s−t потоком) в сети G назовем множествонеотрицательных чисел xij, (i, j) ∈ A, для которых выполнены условия сохранения потокаРазрезы. Назовем s−t разрез минимальным, если он имеет наименьшую пропускнуюспособность среди всех s−t разрезов. Справедлива следующая теорема.Теорема (Форда−Фалкерсона).

В любой сети величина максимального s−t потока равнапропускной способности минимального s−t разреза.Доказательство. Рассмотрим доп. поток {xij}. Если v = проп. спос. некоторого разреза, тотеорема доказана. В прот. сл. величину потока можно  по приводимому ниже правилу до техпор, пока v не станет = проп. спос. нек. разреза.Имея поток {xij}, находим подмн. в.

Х по след. правилам:0. Поместим источник s в мн. X.1. Если i  X и xij < bij (дуга (i, j) не насыщена), то в. j  X.2. Если i  X и xji > 0 ( > 0 поток по (j, i)), то в. j  X.Пусть 1 = min(bi,i+1 – xi,i+1) по всем прямым дугам (i, i+1) пути,2 = minxi+1,i по всем обратным дугам (i+1, i), = min{1, 2} > 0.Проп. спос.

bij  целые числа.Начнем с целочисленного потока (например, 0).   целое > 0Можно увеличить на  потоки по всем прямым дугам пути и уменьшить на  потоки по всемобратным дугам пути. величина st потока увеличится на , и новые значения дуговых потоков останутсядопустимыми.Используя новый поток, можно построить новое мн. Х. Если t попадет в Х, то можно сноваувеличить поток и т. д.Т.к. проп. спос. min разреза ограничена, и на каж. шаге величина потока   на 1, то послеконечного числа шагов получим ситуацию I и  max поток.2.2 Класс NP. Пример задачи распознавания свойств, которая не принадлежит NP.Класс NP - класс задач распознавания свойств, у которого проверка ответа «да» для заданногорешения осуществляется за полиномиальное время.Примеры: определение наличия в графе гамильтонова цикла, задача о коммивояжёре.2.3. Какие алгоритмы называются полиномиальными, а какие экспоненциальными? Привестипримеры таких алгоритмов.Алгор.

полиномиальный, если его трудоемкость () = ( ), где d – целое положительноечисло. Пример: алгоритм Дейкстры поиска кратчайшего пути в графе с неотрициательнымивесами ребер. Его трудоемкость квадратична.Алгор. экспоненциальный, если его трудоемкость не ограничена полиномом от длины входа.Пример: алгоритм перебора всех двоичных слов длины n, он имеет трудоемкость 2n.ПРИМЕР: Пусть n – входная длина.Алг. A1 решает задачу P с трудоемкостью O(n5).

Алг. A2 имеет трудоемкость O(2n) решениязадачи P. ЭВМ - 1 млн. опер./сек. Тогда при n = 60 алг. A1 будет работать около 13 минут, а алг.A2 – более 300 столетий! Предположим, что A2 строит решение задачи размерности D навышеупомянутом компьютере за 1 час. Если взять компьютер, выполняющий в 1000 разбольше операций в секунду, то размерность задачи, которая решается алг. A2 на такомкомпьютере в течение 1 часа, будет всего D + 9.97. Пол. алг. – эффективные! Эксп. – неэффективны!3.1 Теорема об активных стратегиях (без доказательства). Игра 2х2Чистая стратегия i является активной, если она используется в некоторой оптимальнойстратегии с положительной вероятностью. Другими словами, если существует оптимальнаястратегия p (q) такая, что p_i > 0 (q_i > 0), то чистая стратегия i (j) является активной дляпервого (второго) игрока.Теорема (Об активных стратегиях). Если один игрок придерживается оптимальнойстратегии, то его соперник достигает цены игры ν, применяя любую свою смешаннуюстратегию, в которой используются только активные стратегии.3.2.

Пусть задачи P, Q  NP, P полиномиально разрешима и полиномиально сводится к Q. Чтоможно сказать о Q?Что Q полиномиально решается.3.3. Какие задачи NP-полны в сильном смысле? Привести примеры таких задач.Задачу P ∈ NP называют NP-полной в сильном смысле, если для ее решения не существуетпсевдополиномиального алгоритма. К NP-полным в сильном смысле проблемам относятся всеNP-полные задачи без числовых параметром (например, задача ГЦ), а также некоторые хорошоизвестные задачи с числовыми параметрами (например, задача КМ).

Примеры NP-полныхзадач. Задача коммивояжёра, задача гамильтонова цикла, проблема раскраски графа,кратчайшее решение «пятнашек» размера nxn.4.1. Решение матричной игры в смешанных стратегиях. Теорема Фон-Неймана (с док-вом)Смешанная стратегия – это вероятностное распределение на множестве чистых стратегий.Смешанные стратегии игроков определяются векторами:4.2. Пусть задачи P, Q  NP, P  NPC и полиномиально сводится к Q. Что можно сказать о Q?Это значит, если вы умеете решать P за полиномиальное время, то умеете решать Q заполиномиальное время.

(что Q∈NPC)4.3. Является ли полиномиальным алгоритм Форда-Фалкерсона для нахождения максимальногопотока в сети?Нет, в случае целочисленных пропускных способностей дуг количество итераций поискаувеличивающих путей ограничено величиной потока. Поэтому трудоемкость алгоритмаФорда−Фалкерсона зависит от v и, следовательно, является псевдополиномиальной.5.1. Полиномиальная сводимость. Лемма о сводимости (с доказательством)Пусть задачи P и Q принадлежат классу NP.

Если по любой индивидуальной задаче X ∈ P можнопостроить за полиномиальное число операций некоторую индивидуальную задачу Y ∈ Q и пооптимальному решению задачи Y полиномиально строится оптимальное решение задачи X, тоговорят, что задача P полиномиально сводится к задаче Q.Лемма (О сводимости) Пусть задачи P,Q ∈ NP. Тогда справедливы следующие утверждения:1) если Q ∈ P и задача P полиномиально сводится к задаче Q, то P ∈ P;2) если P ∈ NPC и задача P полиномиально сводится к задаче Q, то Q ∈ NPC.

Доказательство. 1)очевидно из определения.Докажем 2). Возьмем произвольную задачу R ∈ NP. Так как P ∈ NPC, то R полиномиальносводится к P. Однако P полиномиально сводится к Q и, следовательно, R полиномиальносводится к Q. Так как это имеет место для любой задачи R ∈ NP, значит, Q ∈ NPC5.2. Можно ли с помощью алгоритма Дийкстра найти кратчайший путь между парой вершинграфа, ребра которого имеют отрицательные длины? Ответ обосновать.Нет, можно привести очень простой пример: граф состоит из четырех вершин:1->2 вес 15, 2->3 вес 10, 2->4 вес -10, 1->3 вес 10, 3->4 вес 15.

Алгоритм Дейкстры укажет, чтодо вершины 4 кратчайшим является путь, проходящий через ребро, соединяющее вершины 1 и4. На самом деле путь, проходящий через вершины 1, 2 и 4, в два раза короче.5.3. Можно ли склеить пару вершин сетевой модели, между которыми нет фиктивной дуги, иполучить эквивалентную сеть?Нельзя, т.к. это можно сделать тогда и только тогда, когда множество фактических дуг,принадлежащих путям из вершины i в сток совпадает с аналогичным множеством длявершины k, или множество фактических дуг, принадлежащих путям из источника в вершину iсовпадает с аналогичным множеством для вершина k.(по теореме 4.1 в лекциях).

Но этоневозможно, если между вершинами i и k нет фиктивной дуги.6.1. Теорема Кука для задачи ВЫПОЛНИМОСТЬ (без док-ва). Схема доказательствапринадлежности задачи классу NP-полных проблем на основе леммы о полиномиальнойсводимости.Т. Кука. Задача ВЫПОЛНИМОСТИ является NP-полной. Для доказательства принадлежностизадачи P ∈ NP классу NPC достаточно найти некоторую NP-полную задачу Q и полиномиальносвести ее к задаче P.6.2. Можно ли найти самый длинный простой путь между парой вершин произвольноговзвешенного графа с помощью алгоритма Форда?Нет, т.к. если в графе есть цикл положительного веса, то алгоритм никогда не остановится иможет сделать путь между вершинами сколь угодно длинным.6.3. Два игрока «выбрасывают» произвольное количество пальцев одной руки.

Первый игроквыигрывает +1, если сумма пальцев четная и проигрывает -1, в противном случае. Существуетли решение игры в чистых стратегиях?Составим платежную матрицу, где i-ая строка – число пальцев, которое выкинул первый игрок,j-ый столбец – число пальцев, которое выкинул второй игрок. Т.к. в матрице нет седловойточки, то по теореме о необходимом и достаточном условии равенства верхней и нижней ценигры не существует решения игры в чистых стратегиях.1234511-11-112-11-11-131-11-114-11-11-151-11-117.1. Теорема об активных стратегиях (без доказательства). Схема решения игры 2хn.Чистая стратегия i является активной, если она используется в некоторой оптимальнойстратегии с положительной вероятностью.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов вопросов/заданий