Полная версия

Главная arrow Логистика arrow Методы управления инвестициями в логистических системах

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ДЕТЕРМИНИРОВАННЫЕ И НЕДЕТЕРМИНИРОВАННЫЕ МАШИНЫ ТЬЮРИНГА И СЛОЖНОСТЬ ВЫЧИСЛЕНИЯ

Детерминированная машина Тьюринга и класс Р

Для того чтобы формализовать понятие «алгоритм», необходимо зафиксировать определенную модель процесса вычисления. Далее такой моделью будет служить детерминированная одноленточная машина Тьюринга (сокращенно ДМТ), которая схематически изображена на рис. 9.2.

Машина Тьюринга состоит из управляющего устройства с конечным числом состояний, читающей (пишущей) головки, которая может считывать и записывать символы, и неограниченной в обе стороны ленты, разделенной на бесконечное число одинаковых ячеек, занумерованных числами:..., —3, —2, —1,0, 1, 2, 3,...

Схема модели ДМТ

Рис. 9.2. Схема модели ДМТ

Программа для ДМТ, или ДМТ-программа, определена следующими компонентами:

  • 1) конечное множество Г символов, которые записываются на ленте, подмножество Z с: Г входных символов и выделенный пустой символ b с= Г Z;
  • 2) конечное множество состояний Q, в котором выделены начальное состояние #0 и два заключительных состояния:

3) функция перехода 5:

Работа программы определяется следующим образом. Входом для детерминированной программы является слово X е Z*. Слово записывается налейте в ячейках с номерами 1, 2,..., |Х|, по одному символу в ячейке. Остальные ячейки в начальный момент времени содержат пустой символ b и называются пустыми. Программа начинает работу, находясь в состоянии qQ. При этом читающая (пишущая) головка находится над ячейкой с номером 1.

Далее процесс вычислений осуществляется последовательно, шаг за шагом. Если текущее состояние q есть q или qN, результатом будет «да» при q — qy и «нет» при q = qN. В противном случае текущее состояние принадлежит множеству Q {qy, qN}, при этом головка читает на ленте некий символ S е Г. Далее определяется значение 5(<7, S). Предположим, что 5(q, S) = (q', S', А), где А задает смещение читающей головки. В этом случае головка стирает символ S, пишет на его месте S' и сдвигается на одну ячейку влево, если А = -1, или на одну ячейку вправо, если А = +1. Одновременно управляющее устройство переходит из состояния q в q'. На этом заканчивается один шаг процесса вычисления, и программа готова к выполнению следующего шага.

Пример простой ДМТ-программы представлен на рис. 9.3.

Функция перехода 5 определена таблицей, где величина, записанная в Г-строке и S-столбце, есть значение 5(q, S). Рисунок 9.4 иллюстрирует вычисление по программе М при входе X = 10100, здесь указаны состояние, положение головки и содержание пустых ячеек ленты до и после каждого шага.

Пример ДМТ-программы М = (Q, Г, 8)

Рис. 9.3. Пример ДМТ-программы М = (Q, Г, 8)

Заметим, что вычисление после восьми шагов оканчивается в состоянии q , поэтому на входе 10100 ответом будет «да».

В общем случае будем говорить, что программа М, имеющая входной алфавит Z, принимает X е Z* в том и только в том случае, когда, будучи примененной ко входу X, она останавливается в состоянии q .

Вычисление по программе М при входе 10100

Рис. 9.4. Вычисление по программе М при входе 10100

Язык LM, распознаваемый программой М, задается следующим образом:

Нетрудно видеть, что программа, представленная на рис. 9.3, распознает язык { X е {0, 1}}.

Отметим, что при таком определении распознавания языка не требуется, чтобы программа М останавливалась при всех входах из Z*, она обязана останавливаться лишь при входах LM.

Если X е Z* LM, то работа программы М на X может либо заканчиваться в состоянии qN, либо бесконечно продолжаться без остановки. Однако ДМТ-программа, соответствующая нашему пониманию алгоритма, должна останавливаться на всех словах входного алгоритма. В этом смысле программа на рис. 9.3 является алгоритмической, так как, начиная работать на любом слове из символов 0,1, она будет останавливаться.

Соответствие между «распознаванием» языков и «решением» задач распознавания определяется следующим образом. Будем говорить, что ДМТ-программа М решает задачу распознавания II при кодировании е, если М останавливается на всех словах, составленных из букв входного алфавита LM = L(II, е). Программа на рис. 9.3 иллюстрирует это соответствие.

Рассмотрим задачу распознавания «Делимость на четыре».

Условие. Дано положительное число N.

Вопрос. Существует ли положительное число т, такое, что N — 4т?

При стандартном кодировании целое число N представляется словом из 0, 1, т.е. двоичной записью этого числа. Так как положительное целое число делится на четыре тогда и только тогда, когда последние две цифры двоичной записи этого числа являются нулями, то программа, изображенная на рис. 9.4, «решает» при нашем стандартном кодировании задачу «Делимость на четыре».

Заметим, что ДМТ-программой можно пользоваться и для вычисления функций. Предположим, что программа М, имеющая входной алфавит Z и ленточный алфавит Г, останавливается на любом входе из Z*. Тогда М вычисляет функцию fM: Z* —» Г*, которая для каждого X е Z* определяется следующим образом. Если программа М, начиная работать при входе X, останавливается, то в качестве fM(X) берется слово, составленное из символов, записанных после остановки машины в ячейке с номерами 1, 2, 3,..., включая последнюю пустую ячейку.

Программа М, представленная на рис. 9.4, вычисляет функцию fM: {0, 1}* —»{0, 1, Ь}*, которая отображает каждое слово X е {0, 1}* в слово fM, получаемое из X удалением двух крайних справа символов (если |Х| < 2, то М выдаст в качестве fM пустое слово).

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

Определим понятие «временная сложность». Время, требуемое ДМТ-программой М для вычисления при входе X, есть число шагов, выполняемых до момента остановки. Если программа М останавливается на всех входах X е Z*, то временную сложность Тм: Z+ Z+ можно определить так:

Детерминированная программа М называется полиномиальной ДМТ-программой, если существует такой полином Р, что Тм (п) < Р(п) для всех п е Z+.

Далее определим формально первый важный класс языков — класс Р:

Будем говорить, что задача распознавания II принадлежит классу Р при кодировании е, если L(II, е) е Р, т.е. существует полиномиальная ДМТ-программа, которая «решает» задачу при кодировании е. Далее, не упоминая конкретные схемы кодирования, будем просто говорить, что задача распознавания II принадлежит классу Р.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>