18.Алгоритмическая, информационная и инфологическая сложность.

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

Понятие алгоритмической сложности введено советским математиком А.Н.Колмогоровым. Под алгоритмической сложностью он понимал минимально необходимый размер программы для данного алгоритма.

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

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 и характер этого роста следует считать лавинообразным.

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

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

ОПРЕДЕЛЕНИЕ. Класс задач распознавания типа ДА-НЕТ с хорошим алгоритмом проверки решения называется классом NP (nondeterministic polynomial).

Почему здесь фигурирует слова nondeterministic polynomial (недетерминированный полиномиальный). Речь идет о том, что все такие задачи можно решить за полиномиальное время на н е д е т е р м и н и р о в а н н о й машине Тьюринга. В самом деле, рассмотрим нашу задачу об угадывании слова. Пусть в общем случае слово состоит из N>2 букв. Тогда имеется N правил для выбора позиции для первой буквы, N правил для выбора позиции второй буквы, N правил для выбора позиции третьей буквы и т.д., всего N² правил. Однако имеется одно единственное вычисление, использующее ровно N правил, дающее правильный ответ. Это, разумеется, полиномиальное по сложности вычисление.

Итак, класс NP нами определен. В этом классе есть хорошие и плохие задачи. Подкласс хроших задач в NP называется классом P (polynomial). Подкласс плохих - вссе остальные. Гипотеза мирового значения, которая все еще не доказана, записывается как P=NP