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



         

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


Чтобы получить реалистичные и стабильные рассмотрения сложности, рассмотрим Т-машину с k лентами. Для каждой из k лент имеется своя головка чтения/записи. Конфигурация состоит из внутреннего состояния Т-машины и для каждой из ее лент из слова слева от головки, знака под ней и слова справа от головки. На каждом шаге вычислений - в зависимости от внутреннего состояния и знаков под каждой из головок - определенные знаки заносятся в ячейки под головками, определенные головки сдвигаются влево или вправо, а также меняется внутреннее состояние. Рассмотрим Т-машину М с k лентами (каждая из них бесконечна в обе стороны), одна из которых содержит входное слово. Для каждого входного слова w длины n машина делает, если она завершает свою работу, b(w) шагов вычислений. Число b(w) тем самым обозначает длину соответствующей последовательности шагов вычислений. Если для функции Т: N®N для всех слов w длины n = /w/ справедливо b(w) Î Т(n), то машина М называется Т(п)-ограниченной по времени Т- машиной.

Это означает, что вычисление для входа w (а в недетерминированном случае - существует ветвь вычислений, которая) требует самое большее T(/w/) шагов вычислений.

Многоленточные Т-машины в смысле вычислимости не мощнее одноленточных машин, однако, они дают более реалистичные оценки затрат времени. Если, например, одноленточная машина должна сравнить два слова, записанные на ее ленте, то во время работы головка постоянно должна смещаться туда и сюда от одного слова к другому и тем самым возникает нереалистичная мера сложности.

Если задача Р может быть решена на Т-машине и эта машина является Т(n)-ограниченной по времени, то задача Р также называется Т(n)-ограниченной по времени. Обратим внимание: по этому определению сложность тесно связана с представлением входа/выхода. Мы понимаем затраты времени Т-машины как функцию, которая растет с ростом длины входного слова. Тем самым различные представления (например, для чисел представление в виде штрихов или двоичное представление) приводят к различным высказываниям о сложности.


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