Учебная работа. Курсовая работа: Труднорешаемые задачи Последовательный анализ вариантов

Учебная работа. Курсовая работа: Труднорешаемые задачи Последовательный анализ вариантов

Курсовая работа

по дисциплине «Методы с оценками»

На тему «Труднорешаемые задачки. Поочередный анализ вариантов»

Содержание

Введение

1. задачки, NP-трудные в сильном смысле

1.1. Сервис требований без задержек

2.метод

2.1 Поочередный анализ вариантов

3. Псевдополиномиальное сведение задач и NP-трудные в сильном смысле задачки
4.Внедрение NP-трудных задач

Заключение

Библиографический перечень

Введение

Большая часть задач, увлекательных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) методы решения. Другими словами время работы метода на входе длины n составляет не наиболее O(nk) для некой константы k (не зависящей от длины входа). Очевидно, не любая задачка имеет метод решения, удовлетворяющий этому свойству. Некие задачки совершенно не могут быть решены никаким методом. Традиционный пример таковой задачки — «неувязка остановки» (узнать останавливается ли данная программка на данном входе). Не считая того, бывают задачки, для которых существует решающий их метод, но хоть какой таковой метод работает «длительно» — время его работы не есть O(nk) ни для какого фиксированного числа k.

Если мы желаем провести пусть грубую, но формальную границу меж «практическими» методами и методами, представляющими только теоретический Энтузиазм, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы разглядим, руководствуясь [1], класс задач, именуемых NP-полными. Для этих задач не найдены полиномиальные методы, но и не подтверждено, что таковых алгоритмов не существует. исследование NP-полных задач соединено с так именуемым вопросцем «P = NP». Этот вопросец был поставлен в 1971 году и является на данный момент одной из более сложных заморочек теории вычислений.

Для чего программеру знать о NP-полных задачках? Если для некой задачки удается обосновать ее NP-полноту, есть основания считать ее фактически неразрешимой. В этом случае лучше издержать время на построение приближенного метода, чем продолжать находить резвый метод, решающий ее буквально.

1. задачки, NP-трудные в сильном смысле

Приводятся примеры доказательств NP-трудности в сильном смысле ряда задач теории расписаний. техника подтверждения результатов такового рода почти во всем припоминает приемы которые использовались при установлении NP трудности (в обыкновенном смысле) экстремальных задач теории расписаний. Для подтверждения NP-трудности в сильном смысле тон либо другой экстремальной задачки будем обосновывать №» трудность в сильном смысле соответственной задачки определения. Для этого довольно показать, что к ней сводится некая популярная NP –полная в сильном смысле задачка. В качестве таковой задачки в данном параграфе выбрана задачка о
которая заключается в последующем. Имеется огромное количество любому элементу которого поставлено в соответствие натуральное число (вес) е,, при этом

Существует ли такое разбиение мужества .V0
на трехэлементные подмножества



…..
такие, что для всех ;

Отметим, что условие является значимым. Оно значит, что сумма весов всех 4 (и наиболее) частей будет больше, чем Е. а всех 2-ух частей — меньше, чем
Подчеркнем также то, что задачка о разбиении — исторически 1-ая задачка, для которой установлена W-полнота в сильном смысле.

Чтоб обеспечить псевдополиномиальное сведение задачки с 3-раэбнении к некой задачке определения, нужно конвертировать входную информацию задачки о 3-разбиении во входную информацию некой ее персональной задачки определения. Число выполняемых при всем этом действий обязано полиномиально зависеть от длины входа задачки о 3 разбиении, представленного в унарной системе счисления, иными словами, от величины время от времени удается установить обыденную полиномиальную сводимость. В этом случае число действий но преобразованию входной инфы полиномиально зависит от либо даже от n0
. Построенная в итоге преобразования входа задачки о З разбиении –персональная задачка определения обязана иметь ответ и тогда лишь тогда, когда таковой же ответ имеет задачка о 3 разбиений.

1.1 Сервис требований без задержек

Установим NP трудность
сильном смысле В данной задачке условие значит что требование I не обслуживается устройством LПри таковой интерпретации нулевых длительностей наилучшее расписание без задержек необязательно принадлежит классу перестановленных расписаний .

Иными — словами, задачки
и в этом случае не эквивалентны. Напомним, что задачки и эквивалентны, если все или посреди f.t
имеются равные нулю и запись
значит, что продолжительность. Справедлива

Аксиома 1.1.
задачка является NPтрудной в сильном смысле, если условие
значит, что требование
устройством
не обслуживается.

подтверждение.
Сформулируем подобающую задачку определения: найти, существует ли расписание s
°,
при котором для данного числа у. Покажем, что к данной задачке сводится задачка о 3-разбиении. Для преобразования входной инфы задачки о 3-раэбиении во входную информацию персональной задачки определения нужно значения
и у
выразить через

Положим
и разобьем огромное количество
на две группы: и-требования, обозначаемые Uij
и v-требовання, обозначаемые

Положим , и зададим / . Покажем, что в построенной задачке расписание S
°
, при котором существует и тогда лишь тогда, когда имеет решение задачка о 3-разбиеиии. имеет решение задачка о 3 разбиений.

1.
Пусть задачка о 3-разбиении имеет решение и отысканные трехэлементные подмножества частей огромного количества N
0
. Через
обозначим произвольную перестановку u-требований с номерами из огромного количества . Устройство 1 работает без простоев во временном интервале ], а устройство 2 — в интервале [0; у]. При всем этом устройство 1 в интервале обслуживает требование . Устройство 2 в интервале обслуживает требование v
0

, а в любом из интервалов
последовательность требований Требование обслуживается устройством 2 в интервале

2. Пусть существует расписание s
°
. Потому что и устройство 2 работает в интервале [0; у] без простоев.

Рис.(1.1)

Устройство 1 завершает сервис всех требований не ранее момента времени
С учетом того, что задержки запрещены, крайним требованием, которое обслуживает устройство 2, будет некое v-требование, а устройство 1 должен работать без простоев в интервале . Так как требования , не различаются друг от друга по длительностям обслуживания, не нарушая общности можно считать, что они обслуживаются устройством I в порядке возрастания их номеров. Отсюда сходу следует, что требования, обслуживаются при расписании s
°
так же, как и при расписании, представленном на рис. 1.1. Требование vc
обслуживается устройством 2 в интервале , потому что это единственный незанятый подинтервал длины 2Е интервала Требования
должны обслуживаться устройством 2 в интервалах . Обозначая через огромное количество номеров и-требований, обслуживаемых устройством 2 в интервале , получаем решение задачка о 3-разбиении. Тем за
действий задачка о 3-раз-биении сведена к задачке о существовании расписания



Аксиома подтверждена.

Аксиома 2
. задачка является NP-трудной в сильном смысле.

Аксиома 3.
задачка является NP-трудной в сильном смысле.

Подтверждение.
Сформулируем подобающую задачку определения. В обслуживающую систему, состоящую из 2-ух устройств А и В, в момент времени

поступает отчасти упорядоченное огромное количество требований

N
{1,2…., л}.
. Любая компонента связности графа редукции дела -, данного на

является цепью. Продолжительность выполнения каждой операции равна единице. Требуется найти, существует ли расписание S
°
, при котором для данного значения у
.

Построим псевдополнномиальное сведение задачки о 3-разбиении к сформулированной задачке определения.

Положим: , где

На огромном количестве N заладим отношение -, считай /

и тогда лишь тогда, когда

Разумеется, любая компонента связности графа редукции этого дела представляет собой цепь.

Пусть процесс обслуживания всякого требования
состоит в выполнении единственной операции. Для требований из огромного количества N
1

положим
1

= (В) при . Для всякого
, положим

Для требования из огромного количества — линейно –упорядоченное и число его частей равно , то при любом расписаний с общим временем обслуживания требований, равным у, требования огромного количества N3
n
+1
должны обслуживаться безпрерывно одно за остальным начиная с момента времени
= 0. На рис. 2 представлен фрагмент расписания обслуживания требований огромного количества при котором общее время обслуживания требований равно у. Это расписание является повторяющимся с периодом

Рис(1.2)

Таковым образом, сервис требований огромного количества при любом расписании с общим временем обслуживания требований, равным у, быть может осуществлено лишь в тех единичных интервалах, которые определяются последовательностью

Покажем, что расписание

0


можно выстроить и тогда лишь тогда, когда имеет решение задачка о 3-раэбиении. Пусть существует разбиение огромного количества № на n0
трехэлементных подмножеств таковых, что при j=1,0. Тогда, обслуживая огромное количество требований
интервале , в согласовании с отношением получаем расписание с общим временем обслуживания требований, равным у
.

Пусть существует расписание S
°
, при котором .Потому что суммарная продолжительность обслуживания всех требований устройством
(устройством
равна у
, то при расписании S
как устройство
так и устройство
в интервале [0; у] не простаивает. По условию сервис всякого требования для которого

Беря во внимание, что в построенном при подтверждении аксиомы 3 примере процесс обслуживания всякого требования состоит из единственной операции, можно прийти к выводу о том, что и задачка является NP-трудной в сильном смысле.

2. метод

Шаг 1.
Выстроить бесконтурный граф в итоге выполнения последующего шага не наиболее чем q — 1 раз. Сначало положить

Пусть опосля выполнения шагов получен смешанный граф , у которого l
вершин отмечено и существует неотмеченная верхушка i,
в которую не входит ни одна дуга, исходящая из неотмеченной верхушки. (Если таковой верхушки нет, то в графе (Q,U) содержится контур. Конец.)

Шаг 1 + 1.
Отметить верхушку i
и в случае, если в графе G(1)
есть ребра, инцидентные данной верхушке, то поменять их исходящими из нее дугами. Приобретенный в итоге граф обозначить G(J+1)
= (Q,
U
(

l

+1),

V(

l

+1)

).
Если V(
l
+1)
= , то бесконтурный граф построен: . В неприятном случае выполнить этот шаг, заменив l на l + 1.

Шаг 2
. В согласовании с методом 3.1 выстроить которое допустимо относительно нацеленного графа и смешанного графа G. Конец.

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

Разумеется, трудозатратность
метода не превосходит и, как следует, общая трудозатратность построения активного расписания, допустимого относительно смешанного графа G, не превосходит

Если для всякого графа G(1)
в методе разглядывать все вероятные варианты выбора верхушки i, то получим все огромное количество P(G) = {G1
G2
, …, G} бесконтурных графов, порождаемых смешанным графом G. Как следует, все огромное количество допустимых относительно G активных расписаний можно выстроить за простых действий.

Пример 1.
В критериях примера 3.1 (см. рис. 1) воспользуемся методом 2 для построения допустимого относительно С = (Q, V, V) расписания.

На шаге 1 метода строим бесконтурный направленный граф из огромного количества P{G). Положим G0
= G и выберем на шаг 1 верхушку 1, в которую не входит ни одна дуга. Отметим верхушку 1 и заменим дугами инцидентные ей ребра. Получим смешанный граф

На шаге 2 подобные преобразования проделаем для верхушки 3, на шаге 3 — для верхушки 4, на шаге 4 — для верхушки 2, на шаге 5 — для верхушки 9. Приобретенный в итоге граф представлен на рис1 в виде сетевого графика.

Рис (2.1)

На шаге 2 воспользуемся методом 1 для построения активного расписания, допустимого относительно нацеленного графа . Поначалу сформируем списки потомков и списки предшественников каждой верхушки , потом распределим верхушки графа по рангам в конце концов, по формуле 1 вычислим значения для всех вершин поочередно в порядке неубывания рангов вершин. Приобретенные значения указаны около соответственных вершин сетевого графика.

2.1 Поочередный анализ вариантов

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

Если на любом шаге метода 2 разглядывать все вероятные варианты выбора верхушки

, в которую не входит ни одна исходящая из: неотмеченной верхушки дуги, то можно получить все огромное количество P(G={G1
,G2
….G} бесконтурных графов порождаемых графом G = (Q, U, V). Задачку можно решить в итоге построения активных расписаний, допустимых относительно графов
и выбора посреди их расписания S* минимизирующего







Трудозатратность полного перебора всех активных расписаний задачки может бытьограничена величиной при условии, что для вычисления функции F(s) требуется не наиболее простых действий.

К огорчению, мощность огромного количества







вырастает в обшей случае экспоненциально с ростом характеристик задачки n и М. К примеру, для задачки
равно n!. Граф
при всем этом является полным не нацеленным:
и q
=
n
.
Рост значений |v| и
показан в табл. 1

Таблица 1.

Сокращение числа перебираемых расписании можно обеспечить способом поочередного анализа вариантов. Для организации целенаправленного перебора графов огромного количества P(G)будем употреблять функцию поочередного разбиения огромного количества



на подмножества.

При всем этом подмножество



поначалу разбивается
подмножества P(G1
), P(G2
)…… P(Gk
)
где Gk



h- графы, получаемые из в итоге подмены 1-го либо нескольких ребер V дугами. Потом одно из множеств P(Gk
)
к примеру P(Gl
)
в свою очередь разбивается на подмножества P(Gh
+1
)
P(Gh
+2
)
…, P(Gh
+
p
)
итоге получаем разбиение начального огромного количества

Этот процесс комфортно представлять „возрастающим» выходящим деревом где Zm

— огромное количество его верхушка.

Огромное количество всех конечных вершин дерева (Zm, Wm) будем обозначать через Zm. При выполнении условия а) получаем четкое для хоть какого графа . При выполнении условия в) существует граф таковой, что . Как следует, при поиске рационального расписания граф G1
можно исключить из рассмотрения, если условие б) либо в) производится.

3. Псевдополиномиальное сведение задач и
NP
-трудные в сильном смысле задачки

вместе с разделением задач на NP-трудные и полиномиально разрешимые, NP-трудные задачки, в свою очередь, разделяются на NP-трудные в сильном смысле задачки и задачки, имеющие псевдополиномиальные методы решения.

Метод решения задачки Π именуется
если его временная сложность не превосходит некого полинома от 2-ух переменных



и


для хоть какого примера
задачки Π. Соответственная задачка именуется

Несложно увидеть, что хоть какой
Не считая того, ни одна из NP-трудных задач, не имеющая числовых характеристик, не может иметь псевдополиномиального метода решения, если

В неприятном случае таковая задачка имела бы полиномиальный метод решения, так как для хоть какого ее примера. Аналогично, если для задачки Π существует таковой полином, что для хоть какого
то Π
удучи NP-трудной, не быть может псевдополиномиально разрешимой.

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

Пусть пары функций




и




сопоставлены задачкам Π и Π’ соответственно.

молвят, что задачка определения Π
к задачке определения Π’
если существует словарная функция Φ
переводящая задачку Π в задачку Π’ и удовлетворяющая последующим условиям:

(а) для хоть какого примера
соотношение
производится и тогда лишь тогда, когда производится

(б) временная сложность вычисления функции Φ не превосходит некого полинома
от 2-ух переменных



и
п

(в) есть такие полиномы
iи

что для хоть какого

задачка определения Π именуется

если существует NP-трудная задачка определения Π
которая псевдополиномиально сводится к Π и для хоть какого

Так как неважно какая задачка псевдополиномиально сводится к для себя,


(1.3),


Не считая того, неважно какая NP-трудная в сильном смысле задачка является NP-трудной, и ни одна из NP-трудных в сильном смысле задач не может иметь псевдополиномиального метода решения, если

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

задачка определения Π именуется

если Π и Π является NP-трудной в сильном смысле.

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

Ниже приведены формулировки NP-трудных задач, которые в предстоящем употребляются при подтверждении NP-трудности задач рационального планирования.

Разбиение:

Заданы целые положительные числа




г

и
такие,

Требуется найти, существует ли огромное количество такое что

4. Внедрение NP-трудных задач

В истинное время огромное распространение получили криптосистемы с открытыми ключами, соответствующим свойством которых будет то, что познание метода не даёт доп преимуществ при взломе, в отличие от симметричных систем, которые просто взламываются, если знать, по какому базисному правилу они работают. Обычным и самым пользующимся популярностью на данный момент примером системы с открытым ключом является RSA (метод был размещен в 1977 Ривестом, Шамиром, Эдлманом в MIT). Эта система ординарна в использовании, и, что наиболее принципиально, сложна во взломе. Но до сего времени остаётся открытым вопросец – относится ли задачка факторизации, на которой базируется метод RSA, к классу полиномиально разрешимых P либо же к классу NP-трудных задач. задачка Р versus NP отчасти должна собственной значимостью пользующейся фуррором теории завершенности NP и отчасти теории криптографии. метод удовлетворимости, будучи поистине действенным методом по отношению к задачке завершенности NP, с одной стороны, мог бы вызвать к жизни целый ряд нужных алгоритмов для решения почти всех практических вычислительных задач в индустрии, но, с иной стороны, таковой метод разрушил бы сохранность денежных и других сделок, обширно использующих веб. Не сегодня-завтра может оказаться, что задачка факторизации не является NP-трудной и наиболее того, может найтись полиномиальный метод её решения. В этом случае пригодятся совсем остальные способы криптографии. В данной работе я покажу некие криптографические способы, основанные на трудности обширно известной NP-трудной задачки, задачки о ранце(Knapsack problem)

Заключение

Итак, какой практический смысл имеет исследование теории трудности и систематизация задач исходя из убеждений NP-полноты? Ответ предельно ясен — часто еще разумнее и эффективнее отыскать подтверждение того, что рассматриваемая задачка принадлежит к классу NP-полных, и в соответствие с сиим заняться поиском довольно четких приближенных алгоритмов, нежели безрезультативно растрачивать время на отыскание полиномиальных алгоритмов ее решения. ясно, что конкретно NP-полные задачки играют тут центральную роль — дело в том, что полиномиальное время является, хоть и первым, но довольно неплохим приближением понятия «практической разрешимости задачки».

Но существует много остальных увлекательных книжек по данной теме, заслуживающих пристального внимания со стороны читателя. Посреди их хотелось бы выделить, где можно отыскать огромное обилие NP-полных задач из самых разных областей. Читателям, желающим подробнее ознакомиться с теорией трудности, на мой взор, будет увлекателен подробный курс лекций, глубоко освещающий данную тему

Библиографический перечень

1. Гэри М., Джонсон Д. «Вычислительные машинки и труднорешаемые задачки» М.: мир 1982-466 стр.

2. Иванова А.П. «Введение в прикладное программирование. Модели и вычислительные методы» М.: Физматлит 2002 г.

3. Перепелица В.А. «Асимптотически подход и решение неких экстремальных задач на графах. Трудности кибернетики » М.: Наука, 1973 г.

4. А.В. Яковлев, А.А. Безбогов, В.В. Родин, В.Н.Шамкин, КРИПТОГРАФИЧЕСКАЯЗАЩИТА инфы

5. Еремеев А.В., Романова А.А., Сервах В.В., Чаухан С.С. Приближенное решение одной задачки управления поставками // Дискретн. анализ и исслед. операций. Серия 2. 2006. Т. 13, № 1. С. 27–39.

]]>