19. Понятие вычислительной сложности. Примеры ее определения

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

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

4, 8, 10, 3, 6,9,5,12.

Здесь всего 8 чисел. Один из возможных алгоритмов решения этой задачи состоит в следующем. Сначала найдем наименьшее число и поставим его на первое место. Затем найдем из оставшихся чисел следующее наименьшее число и поставим его на второе место и т.д.

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

(N-1) + (N-2) + (N-3) + (N-4) + …. +1 = N*N- (1+2+3+…+N-1)=N*N-N*(N-1)/2=

=N*(N-1)/2.

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

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

Рассмотрим следующий пример. Дано слово

НОИКДПОНОК

Буквы в слове переставлены. Нужно определить, какое же слово здесь написано. Пусть наш алгоритм п е р е б и р а е т рутинным способом все возможные варианты и отыскивает полученное слово в словаре русского языка. Из математики известно, что число всех переборов из N элементов составляет N*(N-1)*(N-2)*…*2*1= N! (читается N факториал). В среднем придется сделать половину всех переборов, т.е. 0.58N! Это число для нашего слова все равно очень велико (между прочим, написано - подоконник) и составляет 1714400. Из математики опять-таки известно, что N! растет быстрее любого полинома от N и характер этого роста следует считать лавинообразным.

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

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

20.Детерминированная и недетерминированная машина Тьюринга

Важным понятием в теории распознавания языков является понятие недетерминированной машины Тьюринга.

Вспомним, как мы определяли правила машины Тьюринга. Для этого мы вводили таблицу вида (например)

	0	1	
Q0	ULQ0	0LQ0	UUQ1

В этой таблице определены три правила (по количеству ячеек). Внутри ячейки размещается операционная часть правила. Строка и столбец, определяющие ячейку, содержат условную часть правила. Условная часть просто сообщает, в какой ситуации следует применить правило. Например, условная часть (Q₀,0) соответствующая первой строке и первому столбцу говорит: ”Если машина находится в состоянии Q₀ и читает символ 0, то следует выполнить действие ULQ₀”.

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

Для иллюстрации сказанного рассмотрим следующий пример:

	0	1	
Q0	LQ0 LQ1	LQ1	QНЕТ
Q1	QДА	LQ0	QНЕТ

Рассмотрим входное слово 000. Теперь уже машина может сразу же выполнить правило

LQ₁. После этого на втором такте может завершить работу в состоянии ДА. Кроме того, можно убедиться, что машина принимает все слова, заканчивающиеся на 10, которой может предшествовать группа из подряд идущих нулей.

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

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