Реферат: Разрешимость и сложность в теории алгоритмов

Разрешимость и сложность в теории алгоритмов.

Универсальная машина

Проблема самоприменимости в ТА.

Сложность алгоритма.


13.1.Универсальная машина.

Композиция алгоритмов

А0 В

С = В(А(х)), х – исходные данные

2) Ветвление

А,В,С,D

Если результат применения А(х) =<пустое слово>, то D(x) – B(x)

Если нет, то С(х)

Итерация

Повторение алгоритма


Универсальная машина = U

Исходные данные, запись программы

(Р) – запись программы

Х – исходные данные(на ленте)

(Р) * Х

U((P)*X) = P(X)


Гёделевская нумерация алгоритмов(М)




У1 1 → У1/ 1R

A = {1,λ}

У1 λ → Уk / 1E Y = { У1, Уk }

T = {L, R, E}


21 31 51 71 112 131 172 192 231 293




1 команда 2 команда


^ Многоленточная машина Тьюринга.





1 выходное – нельзя читать или корректировать.


головка неподвижная, ленты двигаются в разных направлениях


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


^ 13.2.Проблема самоприменимости в ТА.

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


Самоприменима («С»), т.е. применима к своей собственной записи.

Обозначается: Р((Р))


Р : 0 => 1; 1 => 0




B: 1) ? {, 2}

HLT


B – применима только к пустому слову, т.е. несамоприменима («Н»).

Проблема самоприменимости: отыскание такого алгоритма, который бы для любой программы определял её самоприменимость.




«Н» S((P))=<пустое слово>

«С» S((P))=< пустое слово >





«Н» R((P))=< пустое слово >

«C» R((P))= не определен


R = B0S


Применима ли R к своей собственной записи?


«Н» R((R))=< пустое слово > «С»

«С» R((R))= не определен «Н»

не определен

исходная посылка неверна

Нет машины, которая определяла бы проблему самоприменимости.


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

Не существует алгоритма применимости, но несуществование общего алгоритма не говорит о не существовании частного решения.

Кроме понятий разрешимости и неразрешимости, вводится понятие сложность алгоритма.

^ 13.3.Сложность алгоритма.


Временная (число шагов)

Пространственная (объём памяти)


Стоимость (эффективность)

Эффективность → бесконечность

Отношение:

Стоимость → 0

Сложность овеществляет стоимость во времени и пространстве.


O(n) – сложность порядка n, n – параметр исходных данных.


O(n2) – сложность порядка n2


Сложность бывает минимальной, средней и максимальной.

Сложностью задачи называется сложность наилучшего алгоритма.


Основные классы сложности.

Полиномиальная сложность.

P(n) – полином от n/

O(P(n)) – класс n

Полиномиальные задачи

n не входит в степень

O(x2) – класс Е – экспоненциальный


Недетерминированный алгоритм – варианты выбираются случайным образом.

Полиномиальная оценка

NP – алгоритмы

NP – полные задачи

Нет гарантированных оценок временной сложности.

Борьба с перебором.

Эвристические подходы


Алгоритмы NP класса: существует ничтожно малая вероятность эффективного решения задачи.