Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Метод ветвей и границ успешно решает задачу о рюкзаке, хотя этот алго­ ритм имеет экспоненциальную временную сложность. Примеров экспоненциальных алгоритмов, успешно используемых на прак­ тике, мало. Более того, даже для полиномиальных алгоритмов представляют практический интерес алгоритмы, сложность которых имеет порядок или . Ясно, что алгоритмы со сложностью порядка вряд ли будут практически используемы. Интересно, что экспоненциальный алгоритм может оказаться при малом размере задачи более быстрым, чем полиномиальный, однако с ростом размера задачи полиномиальный становится более быстрым. Экспоненциальная сложность задачи имеет следуюш,ие аспекты: -для отыскания решения требуется экспоненциальное время; -искомое решение может быть настолько велико, что не может быть пред­ ставлено выражением, длина которого была бы ограничена полиномом от дли­ ны входа. Вторая ситуация возникает, например, если в задаче коммивояжера требу­ ется найти все маршруты длины, не превосходяш,ей заданной величины L. Мо­ жет оказаться, что имеется экспоненциальное число маршрутов длины, не пре- восходяш,ей L. § 7. Ёмкостная (ленточная) сложность алгоритма Ёмкостная, или ленточная, сложность алгоритма характеризует необходи­ мую для вычисления память для хранения исходных данных, промежуточных результатов и окончательного результата. При применении машины Тьюринга как модели вычислений, ёмкостная сложность оценивается длиной части ленты, используемой для записи исходных данных и вычислений. Пусть машина Тьюринга вычисляет значение функции/ Активной зоной ленты (машины Тьюринга) в данный момент времени t на­ зывается связанная часть ленты, содержаш,ая обозреваемую ячейку и все ячей­ ки, в которых имеются символы из внешнего алфавита машины. Активной зо­ ной при работе машины Тьюринга на числе п называется объединение всех ак­ тивных зон за время вычисления. Определим S/x) как длину активной зоны при работе машины Т на числе х, если f(x) определено. В противном случае значение Sj(x) будем считать неопре­ делённым. Функцию Sj(x) назовём ленточной сложностью. Отметим, что в настояш,ее время уделяется суш,ественно больше внимания временным характеристикам и значительно меньше ёмкостным, хотя эта харак­ теристика тоже суш,ественна при использовании ЭВМ с ограниченной памятью. 231