Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Временная сложность
Чтобы получить реалистичные и стабильные рассмотрения сложности, рассмотрим Т-машину с k лентами. Для каждой из k лент имеется своя головка чтения/записи. Конфигурация состоит из внутреннего состояния Т-машины и для каждой из ее лент из слова слева от головки, знака под ней и слова справа от головки. На каждом шаге вычислений - в зависимости от внутреннего состояния и знаков под каждой из головок - определенные знаки заносятся в ячейки под головками, определенные головки сдвигаются влево или вправо, а также меняется внутреннее состояние. Рассмотрим Т-машину М с k лентами (каждая из них бесконечна в обе стороны), одна из которых содержит входное слово. Для каждого входного слова w длины n машина делает, если она завершает свою работу, b(w) шагов вычислений. Число b(w) тем самым обозначает длину соответствующей последовательности шагов вычислений. Если для функции Т: N®N для всех слов w длины n = /w/ справедливо b(w) Î Т(n), то машина М называется Т(п)-ограниченной по времени Т- машиной.
Это означает, что вычисление для входа w (а в недетерминированном случае - существует ветвь вычислений, которая) требует самое большее T(/w/) шагов вычислений.
Многоленточные Т-машины в смысле вычислимости не мощнее одноленточных машин, однако, они дают более реалистичные оценки затрат времени. Если, например, одноленточная машина должна сравнить два слова, записанные на ее ленте, то во время работы головка постоянно должна смещаться туда и сюда от одного слова к другому и тем самым возникает нереалистичная мера сложности.
Если задача Р может быть решена на Т-машине и эта машина является Т(n)-ограниченной по времени, то задача Р также называется Т(n)-ограниченной по времени. Обратим внимание: по этому определению сложность тесно связана с представлением входа/выхода. Мы понимаем затраты времени Т-машины как функцию, которая растет с ростом длины входного слова. Тем самым различные представления (например, для чисел представление в виде штрихов или двоичное представление) приводят к различным высказываниям о сложности.
Из соображений эффективности естественно для чисел выбрать их двоичное представление.
В задачах анализа формальных языков L Í V* будем считать, что при представлении слова (последовательности букв входного алфавита) каждая буква хранится в одной ячейке ленты. Для языка L Í V* определим: L имеет сложность Т(п), если задача принятия (допустимости) слова из L имеет сложность Т(п), где n есть длина входного слова.
Пример (сложность языков).
(1) Язык L == {а^ с b^ : Ù Î N}
имеет (n+1)-ограниченную сложность, поскольку существует Т-машина ТМ, которая любое слово w из L с /W/ == n принимает за n + 1 шаг. ТМ хранит принимаемое слово на первой из своих лент, и головка в начале работы указывает на первый (самый левый) знак. Как только под головкой оказывается знак а, машина записывает его на вторую ленту и на обеих лентах сдвигает головки вправо. Появление знака с под головкой первой ленты влечет за собой сдвиг головки по первой ленте вправо, а по второй - влево. Далее эти сдвиги повторяются, пока на первой ленте прочитывается знак b, а на второй - знак а. Если события «на первой ленте не прочитывается знак b» и «на второй ленте не прочитывается знак а» происходят одновременно, то слово принимается.
(2) Сложение двух чисел а, b > 1 (в двоичном представлении) в предположении, что а и Ь заданы на входной ленте с соответствующим разделительным знаком, требует
[ log2(b+a)]+ l+2*([log2(b)]+1)+2
Запись [log2(b)] для вещественного числа г обозначает наименьшее целое число n, такое, что r < n) шагов вычислений, если мы предположим, что к началу работы головка стоит на позиции единиц числа b. Действительно, сначала нужно [log2(b)]+l шагов для копирования числа b на вторую ленту; затем мы проходим шаг за шагом по числам и производим поразрядные сложения, обеспечивая переносы через состояния. Таким образом, временная сложность операции сложения линейна относительно длин складываемых чисел в их двоичном представлении.
Часто принимается следующее упрощающее предположение: для функций временной сложности всегда имеет место Т(n) ³ n+1.
Этo говорит о том, что мы будем рассматривать только такие машины, вторые всегда просматривают все входное слово до того, как они останавливаются.
