Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

Записать алгоритм сложения двух чисел с указанием против каждой команды соответствующих конфигураций, заданных на лен­ те в виде:

где 0 — пустой символ, a q^ — заключительное состояние. Программа задана в виде:

42

Записать алгоритм сложения чисел, заданных на ленте в виде

Машина начинает просмотр с самой левой единицы, находясь в со­ стоянии <7о.

Результат суммирования должен быть представлен в виде

1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1

3. Машина Тьюринга задана следующей таблицей:

Процесс сложения-состоит в следующем: левое число т прибав­ ляется к первому числу п, потом т прибавляется к полученной сум­ ме п + т и т. д.

Просмотр ленты начинается с самой левой единицы. Машина находится в состоянии qo.

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

мирования выполнялся столько раз, сколько единиц во множителе, после чего следует останов машины.

43

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

V<?3

Результат умножения должен быть представлен в виде:

V

Записать алгоритм с указанием для каждой команды соответст­ вующей конфигурации. .

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

8.Составить таблицу соответствия для машины Тьюринга, вы­ полняющей алгоритм деления, записать алгоритм с соответствую­ щими конфигурациями.

9.Пользуясь понятием машины Поста, записать алгоритмы:

Яе

Останов

Записать алгоритм счетчика единиц с указанием соответствую­ щих конфигураций. •.

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

44

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

1.4. Нормальные алгоритмы А. А. Маркова

Как мы уже условились, всякий общий способ задания алгорит­ мов называется алгоритмической системой. Алгоритмическая систе­ ма, основанная на соответствии между словами в абстрактном ал­

фавитные операторы, с помощью последовательного выполнения ко­ торых реализуются любые алгоритмы в рассматриваемой алгорит­ мической системе.

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

Для указания набора элементарных операторов и порядка их

зываемых узлами граф-схемы. Каждому узлу, кроме особых узлов, называемых входом и выходом, сопоставляется какой-либо элемен­ тарный оператор или распознаватель. Из каждого узла, которому сопоставлен оператор, а также из входного узла исходит точно по одной дуге. Из каждого узла, которому сопоставлен распознава­ тель, исходит точно по две дуги. Из выходного узла не исходит ни одной дуги. Число дуг, входящих в узел граф-схемы, может быть любьш.

Рассмотрим на примере общий вид такой граф-схемы (стр. 46).

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

Алгоритм, определенный граф-схемой, работает следующим об­ разом. Входное слово поступает на вход и двигается по направле­ ниям, указанным стрелками. При попадании^слова в распознава-

45

тельный узел осуществляется проверка условия, сопоставленного этому узлу. При выполнении условия слово направляется в опера­ торный узел, при невыполнении — к следующему распознавателю (иногда эти стрелки соответственно обозначают знаками « + » и «—»).

Если входное слово р , поданное на вход граф-схемы, проходя через узлы схемы и преобразуясь, попадает через конечное число шагов на выход^ то считается, что алгоритм применим к слову р (слово р входит в область определения этого алгоритма). Резуль­ татом воздействия на слово р будет то слово, которое оказывается на выходе схемы. Если после подачи слова р на вход графа его преобразование и движение по граф-схеме продолжается бесконеч­ но долго, не приводя на выход, считается, что алгоритм не приме­ ним к слову р , т. е. слово р не входит в область определения алго-

ЭР,

ЭР,

ЭР,

ритма. В нормальных алгоритмах в качестве элементарного опера­ тора используется оператор подстановки, а в качестве элементарно­ го распознавателя — распознаватель вхождения.

Распознаватель вхождения проверяет условие — имеет ли место вхождение рассматриваемого слова pi в качестве подслова некото­

реализации алгоритма, называется дедуктивной цепочкой, ведущей от слова pi к слову р п .

46