Алгоритмы и анализ сложности (стр. 5 )

Общий вид правила: ,

где и - порядковые номера символов в алфавите ( также входит в алфавит).

Правила вида определяют ячейку останова и финальное состояние (их м\б несколько). Если МТ приходит в такое состояние, то считается, что МТ распознала входную строку и завершает работу (говорит «да»).

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

В общем случае возможно и зацикливание (МТ не достигает финального состояния и не приходит в тупик).

Если для любой пары существует не более 1 правила перехода, то МТ является детерминированной (ДМТ).

В противном случае МТ недетерминированная (НМТ). Она работает так же, как недетерминированный алгоритм: создает собственные копии для параллельной и независимой обработки всех возможных правил перехода для пары .

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

Для НМТ эти значения – максимальные по всем экземплярам.

Пример простейшей МТ – увеличение целого числа на 1.

Иногда выгодно использовать лент (вход, выход, промежуточные результаты).

Для -МТ предполагается, что на каждом шаге возможны чтение, запись и сдвиг на 1 ячейку на каждой ленте по правилам вида:

, .

В -НМТ для одной пары в правых частях правил может существовать множество троек (но не всевозможные сочетания элементов).

                                                                       алфавит

для -МТ равна максимальному по всем лентам числу занятых ячеек.

Смоделируем -МТ на -МТ (перенесем информацию с лент на одну и смоделируем все правила переходов -МТ):

Емкостная сложность: .

Вместо одного шага на -МТ для поиска и изменения нужно пройти всю ленту вправо и влево

трудоемкость .

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

Моделирование МТ на РАМ

В силу того, что РАМ имеет более развитую систему команд, любую команду МТ можно смоделировать конечным числом команд РАМ. Содержимое любой ячейки ленты можно сохранить в одном регистре РАМ, следовательно:

,  .

Моделирование РАМ на МТ

Для РАМ можно использовать только логарифмический весовой критерий (для числа нужно ячеек на ленте МТ и столько же операций при чтении\записи). В этом случае на обработку произвольного числа тратится операций – как на РАМ, так и на МТ.

Каждой команде РАМ будет соответствовать некоторое множество состояний МТ.

Для представления РАМ используем 5 лент МТ:

1. Номера исп-мых в данный момент р-ров РАМ и их значения.

2. Содержимое сумматора.

3. Рабочая.

4. Вход РАМ.

5. Выход РАМ.

Примеры выполнения операций add *20 и store 10.

На каждую команду РАМ (кроме mult и div) требуется раз просмотреть ленту 1.

Пусть РАМ использует регистров, к-рые содержат значения, не превышающие .

Тогда при логарифмическом весовом критерии трудоемкость .

В МТ длина 1-й ленты (емкостная сложность МТ) составляет

.

Трудоемкость , если не используются операции mult и div.

В общем случае , т. е. при лог. весовом критерии РАМ и МТ полиномиально связаны.

В последующих доказательствах свойств алгоритмов мы будем использовать различные алгоритмические схемы (НМТ на нижнем уровне и РАМ как приближение к реальному языку программирования).

Мы показали, что РАМ и НМТ полиномиально связаны, поэтому далее безразлично, по какой схеме будет получен результат: НМТ, РАМ или язык высокого уровня.

Теория алгоритмов

При формализации объектов мы сделали вывод, что все алгоритмы занимаются преобразованием строк – распознаванием входных и формированием выходных.

Разным входам соответствуют разные входные строки – алгоритм их распознает (допустимый вход) или нет (недопустимый вход) и заканчивается (с формированием выходной строки и сообщением «да» или «нет») или циклит.

Множество допускаемых строк образует язык вывод:

каждый алгоритм распознает строки некоторого языка.

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

Например, по МТ и можно построить:

1. Выполнить , затем выполнить .

2. Выполнить и, если получено «да», то выполнить .

3. Выполнять и , пока не сообщит «нет».

Простота схемы МТ позволяет строить такие композиции на формальном уровне – объединяя алфавиты и множества состояний.

В результате был сделан вывод об универсальности данной алгоритмической схемы и выдвинут тезис Черча-Тьюринга:

всякий алгоритм м\б реализован соответствующей МТ.