Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Сложение чисел линейно (длине входного слова), ленточно-ограниченно
Примем следующее упрощающее предположение: для функции ленточной сложности S(n) всегда имеет место
(n)?log(n),где log(n)={[log2(n)]+1 при n?1
{ 1 при n=0
Это говорит о том, что будут рассматриваться такие машины, которые необходимостью используют память для упаковки входного слова на рабочей ленте.
В вопросах о сложности, конечно, особенно интересуют достаточно точные оценки, но их получение весьма затруднительно, поэтому на практике приходится довольствоваться лишь верхними границами затрат (времени или памяти). При этом исследуется сложность в пределе, при увеличении размера задачи (т. е. длины входного слова) – так называемая асимптотическая сложность.
Мы говорим, что функция g, характеризующая сложность задачи, имеет порядок роста O(f(n)), если справедливо высказывание
$ с, d Î N/{0}, nо Î N: " n Î N, n ³ no: d * f(n) £ g(n) £ с * f(n).
Тогда функция g с точностью до постоянного множителя имеет асимптотически тот же рост, что и функция f. В частности, говорят о логарифмически-, линейно-, квадратично-, полиномиально- и экспоненциально-, ограниченном росте g, если функция g асимптотически растет соответствующим образом.
Определенные задачи хотя теоретически и являются вычислимыми, но имеют такую сложность, что практически они не могут быть вычислены.
В связи с вычислимостью нас, прежде всего, интересовали детерминированные Т-машины. Для вопросов сложности имеют значение и недетерминированные Т-машины, поскольку они характеризуют определенные классы сложностей. Для этого необходимо определить, что значит, для недетерминированной Т-машины принимать (допускать) слово, Т-машина принимает слово, если она приходит в заключительное состояние по некоторому пути вычисления.
Концепцию временной и ленточной ограниченности можно обобщить и на недетерминированные Т-машины. Так, недетерминированная Т-машина называется недетерминированной Т неограниченной по времени, если эта оценка имеет место для каждого слова w при его недетерминированной обработке (т. е. для каждого слова w, Ц = n, существует допускающая его ветвь вычисления, по времени не превосходящего Т(n)). Аналогично определяется и недетерминированная S(n) ленточная ограниченность.
