12.Машина Тьюринга. Тезис Чёрча.

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 годудля формализации понятия алгоритма.

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

Те́зис Чёрча — Тью́ринга — фундаментальное эвристическое утверждение, существенное для многих областей науки, в том числе, для математической логики, теории доказательств, информатики, кибернетики, дающее интуитивное понятие о вычислимости. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

В терминах теории рекурсии, это утверждение формулируется как совпадение классов вычислимых и частично рекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча.

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

Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает эквивалентность между строго формализованным понятием частично вычислимой функции и неформальным понятием вычислимости.

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

• физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;

• Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

13.Оценка сложности алгоритмов. Классы p и np.

Основные определения:

Сложность алгоритма - Кол-во операций зав. от входных данных.

Аргумент ф-ии - размер входных данных.

Результат - кол-во элементарных операций.

Оценка сложности:  функция характеризующая рост сложности с размером входных данных.

f(n)=O(g(n))

сущ-т C : f(n) <= C*g(n), для люб. n>N

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

 

Класс P

Если сложность O(полином) - полиномиальная сложность (принадлежит классу P).

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

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

 

NP класс - выше чем полиномиальная.

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

Класс NP включает в себя класс P.

 

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

 

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

Задача A полиномиально сводится к алгоритму B если для зад A сущ-т полиномиальный алгоритм эл. операцию в котором можно заменить на алгоритм В.

Оценка сложности

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

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

Тогда алгоритм называется полиномиальным, если fA(n) растет не быстрее чем полином от n.

Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)].

Сложность можно характеризовать числом операций N и общим объемом информации P, то есть общим количеством слов, используемых при выполнении алгоритма. Тогда, время его выполнения на конкретной ЭВМ связано с числом операций, а объем информации связан с объемом памяти, необходимой машине для реализации соответствующей программы. Следовательно, время реализации алгоритма есть функция T=f(N). При таком подходе значение T и P называют соответственно вычислительной емкостной сложностью алгоритма.

 

Анализ трудоёмкости алгоритмов

Цель - нах-е опт-ого алг-ма для решения данной зад. Критерий оптимальности - трудоемкость алгоритма. Функцией трудоемкости называется отношение, связывающие входные данные алгоритма с количеством элементарных операций.

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

 

Асимптотический анализ алгоритмов

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

 

Задача распознавания – для индивидуальной задачи и заданной константы L найти ответ на вопрос существует ли решение стоимость которого не больше (не меньше) заданной границы L.

 

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

 

Задача распознавания: для даной формулы определить может ли она быть истинной для какого-либо набора переменных.

Удостоверение: может служить набор значений истинности.

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

Дополнение задачи коммивояжера: определить что в данном графе нет обходов меньше L. Эта задача не относиться к классу NP, т.е. перебрать все существующие обходы и доказать, что они меньше L, нельзя за полиномиальное время.

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

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

Теорема Кука: задача о выполнимости является NP полной.

Еще ряд задач из NP(Клика и ЗК) являются NP- полными, для доказательства этого рассматриваемую задачу преобразуют в задачу ВЫПОЛНИМОСТЬ или какую-нибудь другую задачу, NP-полнота которой уже доказана.