Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Временная сложность - часть 2


Из соображений эффективности естественно для чисел выбрать их двоичное представление.

В задачах анализа формальных языков  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 говорит о том, что мы будем рассматривать только такие машины, вторые всегда просматривают все входное слово до того, как они останавливаются.




Содержание  Назад  Вперед