Математическая логика и теория алгоритмов

Глава?. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С помощью АЛГОРИТМОВ § 1. Понятие о сложности вычислений В главе 6 рассматривались проблемы принципиальной возмож­ ности вычислений и были исследованы различные подходы к понятию вычислимости. При этом не обращалось внимание на ресурсы време­ ни и памяти. Однако существуют задачи, которые теоретически раз­ решимы, но при практической реализации требуют столь больших вычислений, что их решение практически неосуществимо. Следова­ тельно, принципиальная алгоритмическая разрешимость еще не озна­ чает практическую реализуемость. Рассмотрим некоторые характери­ стики вычислений. Считаем, что при вычислении используем алгоритм. Различают сложность описания алгоритма и исходных данных, и сложность применения алгоритма к исходным данным. Сложностьописанияалгоритма зависит от выбора того или иного способа задания алгоритма. Если такой способ выбран (машина Тьюринга, нормальный алгоритм или рекурсивное задание и т.д.), то сложность алгоритма может быть введена как длина записи алгоритма или как длина встречающихся специальных выражений и т.д. Напри­ мер, для машины Тьюринга ее сложность может быть введена как число букв внешнего и внутреннего алфавитов. Введем следующее определение. Говорят, что неотрицательная функция g { n ) есть 0(/{п)), если существует такая постоянная с, что g { n ) < c f { n ) для всех, кроме конечного (возможно пустого) множества значений п, ?ге{0,1, 2, 3,...}. В этом случае записываем; g { n ) = Q i f i r i ) ) , П6