Теория алгоритмов

Задачи, не попадающие ни" в класс Р, ни в класс Е

К этому классу относятся следующие задачи:

-Решение систем уравнений с целыми переменными

-Определение цикла, проходящего через все вершины некоторого графа (цикл Гамильтона)

-Существование среди заданных подмножеств некоторого избранного семейства, покрывающего данное множество.

-Составление расписаний (и соответственно раскрасок), учитывающих определенные условия (и соответственно бинарные отношения)

-Существование множества значений логических переменных, которые позволяют сделать значение произвольного заданного логического выражения ИСТИННЫМ.

-Оптимизация пути коммивояжера через сеть городов.

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

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

-Оптимальная загрузка емкости (рюкзак, поезд, корабль, самолет) при наименьшей стоимости.

-Диагностика (болезни, поломки, дефекты печатных схем).

Этот список можно продолжить. Проблема состоит в следующем: можем ли мы надеяться, что какие-либо из этих задач попадут в класс «Р»? К сожалению, в настоящее время ни для одной из этих задач не найдено полиномиального алгоритма. Более того, для всех перечисленных задач была доказана взаимная эквивалентность, т. е. если все-таки удастся представить для одной из этих задач хороший (т. е. полиномиальный) алгоритм, то все они автоматически будут решены.

Наиболее удобный класс «Р» -множество полиномиальных задач уже обсуждался выше где мы отметили, что этих задач слишком мало: формальные задачи, которые люди сегодня умеют решать хорошо (т. е. алгоритмически и полиномиально)‚ образуют весьма небольшое семейство. Все остальные задачи являются трудными и по определению относятся к области искусственного интеллекта. Наконец, отметим, что, даже если для сформулированной на обычном языке задачи полиномиальный алгоритм существует, необходимость узнать это, сформулировать и смоделировать условия задачи так, чтобы ее можно было обработать хорошим алгоритмом, опять приводит к неполиномиальной сложности.

 Класс NР: недетерминированные полиномиальные задачи

Когда для решения задачи мы не располагаем ни явной формулой, ни рекурсивным выражением приемлемой сложности, нам остается два последних способа: построение действенного алгоритма подсчета или метод перебора. Если мы говорим, что сложность задачи полиноминальна‚ это означает, что в любом случае, не прибегая к перебору, мы достигнем решения за полиномиальное число шагов. Абстрактной моделью такого полиномиального алгоритма является черный ящик, умеющий выполнять только заданное множество элементарных операций: +, -, , ИЛИ, И, ЧИТАТЬ, ПИСАТЬ, ЕСЛИ... ТО..., ПОВТОРЯТЬ. В заданный момент этот автомат находится в строго определенном состоянии; за один шаг он совершает единственное действие, обусловленное этим состоянием. Затем он переходит в следующее состояние, и все начинается сначала. Такой автомат называется так- же детерминированной машиной Тьюринга (ДМТ). Механизм перебора, т. е. продвижения на ощупь, совершая предварительные попытки (а в некоторых задачах без этого обойтись нельзя), можно смоделировать с помощью другой, тоже весьма абстрактной, машины Тьюринга, называемой недетерминированной (НДМТ). Помимо обычного набора инструкций в такой машине существует специальная инструкция “ВЫБОР [Е]", которая создает столько копий текущего состояния, сколько существует элементов во множестве Е. По соглашению машина останавливается в тот момент, когда одна из возникших ее копий достигает инструкции КОНЕЦ. Задача относится к у классу, недетерминированных полиномиальных задач если существует алгоритм, позволяющий выдвинуть гипотезу о возможном решении, а затем проверить правильность этой гипотезы с помощью полиномиальных затрат времени. Идея такого подхода состоит в том, что если бы можно было воспользоваться сколь угодно большим количеством процессоров, чтобы проверить одновременно все гипотезы, или оказаться крайне удачливым и всегда с первого раза находить правильную гипотезу, то NP-трудные задачи стали бы Р-трудными задачами. Одним из самых важных нерешенных вопросов в компьютерных науках является то, будет ли класс NP эквивалентным классу Р, если нельзя воспользоваться бесконечным количеством процессоров или способностью находить правильную гипотезу с первого раза. Большинство специалистов в области компьютерных наук согласны с тем, что РФЫР, иными словами, что задачи NP являются изначально трудными и для них не существует алгоритмов с полиномиальными затратами времени. Но это утверждение так и не было доказано. 
Ученые, пытающиеся найти ответ на вопрос о том, эквивалентны ли классы Р и NP, выделили подкласс класса NP, называемый NP-полными задачами. В этой формулировке слово "полный" означает "являющийся наиболее ярким представителем" и поэтому указывает на самые трудные задачи из класса NP. Было доказано, что либо все NP-полные задачи принадлежат к классу Р, либо ни одна из них к нему не относится. Таким образом, данный класс представляет определенный теоретический интерес, но он важен также с точки зрения практики, поскольку известно, что многие серьезные задачи являются NP-полными. В качестве примера можно указать задачу установления выполнимости: если дано высказывание пропозициональной логики, то есть ли такой вариант присваивания истинностных значений пропозициональным символам в высказывании, при котором оно становится истинным? Если не произойдет чудо и не совпадут друг с другом классы Р и NP, то нельзя будет найти алгоритм, который позволяет решить все задачи установления выполнимости за полиномиальное время. Но исследователей в области искусственного интеллекта в большей степени интересует то, существуют ли алгоритмы, действующие достаточно эффективно при решении типичных задач, выбранных с помощью заранее заданного распределения

 

 

 

 

 

 

 

Вывод

Рассмотрев данную тему можно сделать следующие выводы:

Понятие «алгоритм» одно из самых весомых и распространенных понятий, как в бытовом понимании этого слова, так и в научном, непосредственно связанным с математикой, информатикой и кибернетикой. Но необходимо четко отделять для себя понятие «Алгоритма» интересующего нас, от бытового понятия. В бытовом понимании может быть использовано данное определение: «Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения результата» Но для нас необходимо некоторое уточнение понятия. Поговорим о различии между математикой и информатикой: в информатике недостаточно высказать утверждение о существовании некоторого объекта в теории и даже недостаточно найти конструктивное доказательство этого факта, т. е. алгоритм. Мы должны учитывать противоречия пространства и времени, навязываемые нам миром, в котором мы живем: необходимо, чтобы решение можно было вычислить, используя объем памяти и время, приемлемые для человека или машины. То есть определение алгоритма принимает для нас конкретный характер: «Алгоритм - это точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным данным результата». Каждый алгоритм обязан соответствовать определенным  требованиям, которые в свою очередь, и определяют его.

-Алгоритм должен иметь входы и выходы, т.е. он применяется к исходным данным и выдает результаты.

- Данные алгоритма (входные, выходные и промежуточные), для своего размещения требуют памяти

- Алгоритм состоит из отдельных элементарных шагов, или действий, причем множество различных шагов, из которых составлен алгоритм, конечно.

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

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

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

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

Выделяют три класса сложности задач:

Класс _Р : Полиномиальные алгоритмы - задача называется “хорошей”, или принадлежащей классу Р, для которой существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных) К данному классу задач относятся самые элементарные задачи - деление‚ извлечение квадратного корня, решение уравнений второй степени.

Класс Е: Экспоненциальные алгоритмы - по природе экспоненциальной считается задача, сложность которой не менее порядка f^n (где f - константа или полином от n), например, в случае, когда число ожидаемых ответов уже само по себе экспоненциально. К этому классу относятся задачи, в которых требуется построить все подмножества некоторого множества, все клики (т. е. полные подграфы) некоторого графа или же все поддеревья некоторого графа

Класс NР: недетерминированные полиномиальные задачи – Называют задачи решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за время, не превосходящее полинома от размера данных) проверить на машине Тьюринга. Задача относится к этому классу, если существует алгоритм, позволяющий выдвинуть гипотезу о возможном решении, а затем проверить правильность этой гипотезы с помощью полиномиальных затрат времени. Идея такого подхода состоит в том, что если бы можно было воспользоваться сколь угодно большим количеством процессоров, чтобы проверить одновременно все гипотезы, или оказаться крайне удачливым и всегда с первого раза находить правильную гипотезу, то NP-трудные задачи стали бы Р - трудными задачами.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

1)Кузнецов О.П., Адельсон  – Вельский Г.М. «Дискретная математика  для инженера. 2 изд. М., Энергоатомиздат, 1988г.

2)Лорьер Ж.Л. « Системы искусственного интеллекта» М., Мир, 1992г.

3)Математический и энциклопедический  словарь. М. Сов. Энциклопедия, 1988г.