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

Вводятся понятия задач с полиномиальной потребной памятью, с NP- потребной памятью и т.д. Имеет место следующая теорема: Теорема 7.2. Для ленточной (ёмкостной) характеристики сложности вы­ числения функции/имеет место оценка Sf(x) < Х+1+ t/x) где t/x) -временная сложность вычисления/fe). Доказательство. В начальный момент на ленте машины Тьюринга записа­ но число X (в унарной системе), следовательно, занято х+1 клеток ленты. На каждом такте (шаге) активной становится не более одной новой клетки, поэто­ му получим указанную оценку для Sf(x). Эта теорема показывает, что если известна временная сложность, то можно оценить сверху ленточную сложность. Интересно, что нет пределов сложности вычислений. Можно доказать, что какую бы сложную задачу ни взять, то суш,ествует еш,ё более сложная задача. § 8. Проблемы анализа сложности алгоритма Применение ЭВМ послужило стимулом развитию теории алгоритмов и изучению алгоритмических моделей, к изучению алгоритмов с целью их срав­ нения по рабочим характеристикам (числу действий, расходу памяти), а также их оптимизации. Возникло важное направление в теории алгоритмов - слож­ ность алгоритмов и вычислений. Начала складываться так называемая метриче­ ская теория алгоритмов, основным содержанием которой является классифика­ ция задач по классам сложности. Сами алгоритмы стали объектом точного ис­ следования, как и те объекты, для работы с которыми они предназначены. В этой области естественно выделяются задачи получения верхних и нижних оценок сложности алгоритмов, и оказалось, что методы решения этих задач со­ вершенно различны. Для получения верхних оценок достаточно интуитивного понятия алгоритма. Для этого строится неформальный алгоритм решения кон­ кретной задачи и затем он формализуется для реализации на подходящей алго­ ритмической модели. Если показывается, что сложность (время или память) вычисления для этого алгоритма не превосходит значения подходящей функ­ ции при всех значениях аргумента, то эта функция объявляется верхней оцен­ кой сложности решения рассматриваемой задачи. В области получения верхних оценок получено много ярких результатов для конкретных задач. Среди них разработаны быстрые алгоритмы умножения целых чисел, многочленов, мат­ риц, решения линейных систем уравнений, которые требуют значительно меньше ресурсов, чем традиционные алгоритмы. 232