Алгоритмы и анализ сложности (стр. 6 )

Фактически, это формальное определение алгоритма, из которого следует:

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

- сравнения и преобразования одного алгоритма в другой – это формальные операции над МТ.

Существуют и другие универсальные алгоритмические схемы, для к-рых была показана их эквивалентность МТ:

- рекурсивные функции,

- нормальные алгоритмы Маркова,

- операторные схемы Янова,

- любой алгоритмич. язык без количественных ограничений.

В самом общем понимании МТ должна распознавать цепочки некоторого языка и давать ответ «да», если цепочка принадлежит языку. В противном случае вообще-то не обязательно дается ответ «нет» - алгоритм может и циклить на неправильной цепочке.

Алгоритм, к-рый не может гарантированно распознать любую цепочку за конечное время, называется частичным (ЧА).

ЧА не может полноценно решить задачу, поэтому он не представляет практической ценности.

Класс задач является алгоритмически неразрешимым, если для их решения не существует конечного алгоритма.

Иногда конечный алгоритм существует для частных случаев задач, к-рые в общем случае явл-ся алг. неразрешимыми.

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

Примеры алгоритмически неразрешимых задач

1. Распознавание цепочек языка класса 0 (без ограничений).

2. Любой алгоритм можно рассматривать как его описание – цепочку символов или бит. Если алгоритм читает свое описание и закончит работу, сообщив «да», то называется самоприменимым. АН проблема – создание общего алгоритма, проверяющего любой алгоритм на самоприменимость.

3. Проблема остановки МТ: МТ читает свое описание и вход – необходимо установить, закончит она работу или нет.

4. Создание общего алгоритма, проверяющего любой алгоритм на конечность.

Докажем от противного: пусть такой конечный алгоритм существует и для любого проверяемого алг-ма сообщает «да», если конечный, или «нет», если – частичный алгоритм.

Перейдем к другому конечному алгоритму :

сообщает «да», если проверяемый алгоритм является частичным или несамоприменимым.

Применим алгоритм к самому себе:

– противоречие для не существует  не может существовать.

Если известно, что задача имеет конечный алгоритм, то возникает вопрос о его эффективности.

Рассмотрим 2 мн-ва алгоритмов с трудоемкостями и . Для них характерно:

1. можно найти такое , что при экспоненциальная сложность будет выше.

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

3. При увеличении длины входа в раз трудоемкость полиномального алгоритма увеличивается в раз, и он остается полиномиальным. Сложность экспоненциального алгоритма увеличится в раз – множитель зависит от длины входа.

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

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

Далее для полиномов произвольной степени будем использовать сокращенное обозначение .

-полные и -трудные задачи

Мы познакомились со многими алгоритмами, к-рые вычисляются на обычном компьютере за время .

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

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

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

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

Аналогично можно определить классы и . Очевидно, что ; позднее докажем, что .

Полиномиальная сводимость задач

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

(Пример – линейное и квадратное уравнения).

В классе существует мн-во задач, к к-рым может быть сведена любая задача из (в т. ч. они сами друг к другу). Эти задачи называются полными (), и они играют особую роль в классе :

1. полные – это наиболее сложные задачи из .