Специальная математика. Соловьев А.Е. - 67 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

Бросается в глаза быстрый рост сложности вычислений в последней строке.
Действительно, с точки зрения теории сложности вычислений, между последним и двумя
первыми типами задач пропасть. Первые две задачи относятся к классу задач с
полиномиальной сложностью. А последняя – к задачам с экспоненциальной сложностью.
Такие задачи называются трудноразрешимыми. Класс этих задач формируется эмпирически
и носит название класса NP - полных задач.
Есть какая-то аналогия между проблемами алгоритмической разрешимости и
трудноразрешимости. Как из-за невозможности определить понятие алгоритма проблема
алгоритмической разрешимости сводится к возможности построения конкретизации, так и
трудноразрешимость устанавливается сведением исследуемой задачи к одной из
«эталонных» NP - полных задач.
6.4. Машины Тьюринга
Известны случаи построения школьниками железных машин Тьюринга с колесами.
Но машина Тьюринга – это все-таки прежде всего метод математического моделирования.
Машина Тьюринга включает:
1. Потенциально бесконечную (вправо) ленту, разделенную на ячейки.
2. Считывающе-записывающую головку с устройством управления (УУ).
3. Алфавит внутренних состояний {q
0,
q
1
...q
n
}.
4. Входной-выходной алфавит.
Определяется начальная конфигурация. Головка смотрит на какую-то ячейку и устройство
управления находится в начальном состоянии q
1
.
Устройство управления на основании считанного из ячейки символа и внутреннего
состояния пишет в ячейку символ (возможно, тот же самый), совершает действие D и
переходит в новое внутреннее состояние (возможно прежнее). Это и есть команда Машины
Тьюринга, которую можно записать так:
a
i
q
i
a
j
D
j
q
j
.
D
= {Л, П, С}
- множество действий.
Л – влево, П – вправо, С - стоять.
Совокупность команд составляет программу машины Тьюринга, которая обычно
оформляется в виде таблицы.
Машина заканчивает работу, когда переходит в состояние q
0.
- пустой символ.
Пример: Построим машину Т, которая в сплошной последовательности 1 стирает первую и
две последние. ( - пустой символ).
q
1
q
2
q
3
q
4
1
Пq
2
1Пq
2
Лq
4
Сq
0
-
Лq
3
- -
6.5. Нормальные алгорифмы Маркова
Автор - А.А. Марков, отдавал предпочтение транскрипции алгорифм. Нормальные
алгорифмы Маркова представляются нормальной схемой подстановок, которая состоит из
— 67 —
УУ
Бросается в глаза быстрый рост сложности вычислений в последней строке.
Действительно, с точки зрения теории сложности вычислений, между последним и двумя
первыми типами задач пропасть. Первые две задачи относятся к классу задач с
полиномиальной сложностью. А последняя – к задачам с экспоненциальной сложностью.
Такие задачи называются трудноразрешимыми. Класс этих задач формируется эмпирически
и носит название класса NP - полных задач.
Есть какая-то аналогия между проблемами алгоритмической разрешимости и
трудноразрешимости. Как из-за невозможности определить понятие алгоритма проблема
алгоритмической разрешимости сводится к возможности построения конкретизации, так и
трудноразрешимость устанавливается сведением исследуемой задачи к одной из
«эталонных» NP - полных задач.

                               6.4. Машины Тьюринга

Известны случаи построения школьниками железных машин Тьюринга с колесами.
Но машина Тьюринга – это все-таки прежде всего метод математического моделирования.
Машина Тьюринга включает:
1. Потенциально бесконечную (вправо) ленту, разделенную на ячейки.
2. Считывающе-записывающую головку с устройством управления (УУ).
3. Алфавит внутренних состояний {q0, q1...qn}.
4. Входной-выходной алфавит.



           УУ
Определяется начальная конфигурация. Головка смотрит на какую-то ячейку и устройство
управления находится в начальном состоянии q1.
Устройство управления на основании считанного из ячейки символа и внутреннего
состояния пишет в ячейку символ (возможно, тот же самый), совершает действие D и
переходит в новое внутреннее состояние (возможно прежнее). Это и есть команда Машины
Тьюринга, которую можно записать так:
aiqi  ajDjqj.
D = {Л, П, С} - множество действий.
     Л – влево, П – вправо, С - стоять.
Совокупность команд составляет программу машины Тьюринга, которая обычно
оформляется в виде таблицы.
Машина заканчивает работу, когда переходит в состояние q0.
      - пустой символ.

Пример: Построим машину Т, которая в сплошной последовательности 1 стирает первую и
две последние. ( - пустой символ).

        q1       q2      q3     q4
  1    Пq2     1Пq2    Лq4   Сq0
       -       Лq3     -      -

                       6.5. Нормальные алгорифмы Маркова

Автор - А.А. Марков, отдавал предпочтение транскрипции алгорифм. Нормальные
алгорифмы Маркова представляются нормальной схемой подстановок, которая состоит из

                                      — 67 —

Страницы