ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6588
Скачиваний: 50
51
Последовательность слов
Р, P
1
, Р
2
, ..., М
называется дедуктивной цепочкой, ведущей от
слова
Р к
слову
М,
если каждое из двух рядом стоящих слов этой цепочки - смежное.
Слова
Р
и
М
называют эквивалентными, если существует цепочка от
Р
к
М
и обратно.
Пример
Алфавит
Подстановки
{
а, b, с, d, е
}
ас - сa,
abac - abace
ad - da;
eca - ae
bc - cb;
eda - be
bd - db;
edb - be
Слова
abcde
и
acbde
- смежные (подстановка
bc
-
cb
). Слова
abcde
-
cadbe
эквивалентны.
Может быть рассмотрен специальный вид ассоциативного исчисления, в котором подста-
новки являются ориентированными: N → М (стрелка означает, что подстановку разрешается про-
изводить лишь слева направо). Для каждого ассоциативного исчисления существует задача: для
любых двух слов определить, являются ли они эквивалентными или нет.
Любой процесс вывода формул, математические выкладки и преобразования также являют-
ся дедуктивными цепочками в некотором ассоциативном исчислении. Построение ассоциативных
исчислений является универсальным методом детерминированной переработки информации и по-
зволяет формализовать понятие алгоритма.
Введем понятие алгоритма на основе ассоциативного исчисления: алгоритмом в алфавите А
называется понятное точное предписание, определяющее процесс над словами из А и допускаю-
щее любое слово в качестве исходного. Алгоритм в алфавите А задается в виде системы допусти-
мых подстановок, дополненной точным предписанием о том, в каком порядке нужно применять
допустимые подстановки и когда наступает остановка.
Пример
Алфавит:
Система подстановок
В:
А = {
а, b, с
}
cb - cc
сса - аb
ab – bса
Предписание о применении подстановок: в произвольном слове
Р
надо сделать возможные
подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь получен-
ным словом.
Так, применяя систему подстановок
В
из рассмотренного примера к словам
babaac
и
bсaсаbс
получаем:
babaac
→
bbcaaac
→ остановка
bcacabc → bcacbcac
→
bcacccac
→
bсасаbс
→ бесконечные процесс (остановки нет), так
как мы получили исходное слово.
Предложенный А.А.Марковым способ уточнения понятия алгоритма основан на понятии
нормального алгоритма, который определяется следующим образом. Пусть задан алфавит
А
и сис-
тема подстановок
В.
Для произвольного слова
Р
подстановки из
В
подбираются в том же порядке,
в каком они следуют в
В.
.Если подходящей подстановки нет, то процесс останавливается. В про-
тивном случае берется первая из подходящих подстановок и производится замена ее правой ча-
стью первого вхождения ее левой части в
Р.
Затем все действия повторяются для получившегося
слова
P
1
.
Если применяется последняя подстановка из системы
В,
процесс останавливается.
Такой набор предписаний вместе с алфавитом
А
и набором подстановок
В
определяют нор-
мальный алгоритм. Процесс останавливается только в двух случаях: 1) когда подходящая подста-
новка не найдена; 2) когда применена последняя подстановка из их набора. Различные нормаль-
ные алгоритмы отличаются друг от друга алфавитами и системами подстановок.
Приведем пример нормального алгоритма, описывающего сложение -натуральных чисел
(представленных наборами единиц).
Пример
52
Алфавит:
Система подстановок В:
А = (+, 1)
1 + → + 1
+ 1 → 1
1 → 1
Слово Р: 11+11+111
Последовательная переработка слова
Р
с помощью нормального алгоритма Маркова прохо-
дит через следующие этапы:
Р = 11 + 11 + 111
Р
5
= + 1 + 111111
Р
1
= 1 + 111 + 111
Р
6
= ++ 1111111
Р
2
= + 1111 + 111
Р
7
= + 1111111
Р
3
= + 111 + 1111
Р
8
= 1111111
Р
4
= + 11 + 11111
Р
9
= 1111111
Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания
любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормали-
зации: для любого алгоритма в произвольном конечном алфавите
А
можно построить эквивалент-
ный ему нормальный алгоритм над алфавитом
А,
Разъясним последнее утверждение. В некоторых случаях не удается построить нормальный
алгоритм, эквивалентный данному в алфавите
А,
если использовать в подстановках алгоритма
только буквы этого алфавита. Однако, можно построить требуемый нормальный алгоритм, произ-
водя расширение алфавита
А
(добавляя к нему некоторое число новых букв). В этом случае гово-
рят, что построенный алгоритм является алгоритмом над алфавитом
А,
хотя он будет применяться
лишь к словам в исходном алфавите
A
.
Если алгоритм
N
задан в некотором расширении алфавита
А,
то говорят, что
N
есть нор-
мальный алгоритм над алфавитом
А.
Условимся называть тот или иной алгоритм нормализуемым, если можно построить экви-
валентный ему нормальный алгоритм, и ненормализуемым в противном случае. Принцип норма-
лизации теперь может быть высказан в видоизмененной форме: все алгоритмы нормализуемы.
| Данный принцип не может быть строго доказан, поскольку понятие произвольного алго-
ритма не является строго определенным и основывается на том, что все Известные в настоящее
время алгоритмы являются нормализуемыми, а способы ромпозиции алгоритмов, позволяющие
строить новые алгоритмы из уже известных, не выводят за пределы класса нормализуемых алго-
ритмов. Ниже перечислены способы композиции нормальных алгоритмов.
I.
Суперпозиция алгоритмов.
При суперпозиции двух алгоритмов
А
и
В
выходное слово
первого алгоритма рассматривается как входное слово второго алгоритма
В.
Результат суперпози-
ции
С
может быть представлен в виде
С(р)
=
В(А(р)),
II.
Объединение алгоритмов.
Объединением алгоритмов
А
и
В
в одном и том же алфавите
называется алгоритм С в том же алфавите, преобразующий любое слово
р,
содержащееся в пере-
сечении областей определения алгоритмов
А
и
В,
в записанные рядом слова
А(р)
и
В(р).
III.
Разветвление алгоритмов.
Разветвление алгоритмов представляет собой композицию
D
трех алгоритмов
А, В
и
С,
причем область определения алгоритма
D
является пересечением об-
ластей определения всех трех алгоритмов
А, В
и С, а для любого слова
р
из этого пересечения
D(p)
=
А(р),
если
С(р)
=
е, D(p)
=
B(p),
если
С(р) = е,
где
е -
пустая строка.
IV.
Итерация алгоритмов.
Итерация (повторение) представляет собой такую композицию
С двух алгоритмов
А
и
В,
что для любого входного слова
р
соответствующее слово
С(р)
получает-
ся в результате последовательного многократного применения алгоритма
А
до тех пор, пока не
получится слово, преобразуемое алгоритмом
В.
Нормальные алгоритмы Маркова являются не только средством теоретических построений,
но и основой специализированного языка программирования, применяемого как язык символьных
преобразований при разработке систем искусственного интеллекта. Это один из немногих языков,
разработанных в России и получивших известность во всем мире.
Существует строгое доказательство того, что по возможностям преобразования нормаль-
ные алгоритмы Маркова эквивалентны машинам Тьюринга.
53
7.5. РЕКУРСИВНЫЕ ФУНКЦИИ
Еще одним подходом к проблеме формализации понятия алгоритма являются, так называе-
мые, рекурсивные функции. Исторически этот подход возник первым, поэтому в математических
исследованиях, посвященных алгоритмам, он имеет наибольшее распространение.
Рекурсией называется способ задания функции, при котором значение функции при опре-
деленном значении аргументов выражается через уже заданные значения функции при других
значениях аргументов. Применение рекурсивных функций в теории алгоритмов основано на идее
нумерации слов в произвольном алфавите последовательными натуральными числами. Таким об-
разом любой алгоритм можно свести к вычислению значений некоторой целочисленной функции
при целочисленных значениях аргументов.
Введем несколько основных понятий. Пусть
X, Y -
два множества. Частичной функцией
(или отображением) из
Х
в
Y
будем называть пару
<D(f), f>
, состоящую из подмножества
D(f)
X
(называемого областью определения
f)
и отображения
f
:
D(f)
Y.
Если
D(f)
пусто, то
f
нигде не
определена. Будем считать, что существует единственная нигде не определенная частичная функ-
ция.
Через
N
будем обозначать множество натуральных чисел. Через
(N)
n
(при
п
1) будем обо-
значать
n
-кратное декартово произведение
N
на себя, т.е. множество упорядоченных
n
-ок (
х
1
...,
x
n
),
х
i
N.
Основным объектом дальнейших построений будут частичные функции из
(N)
m
в
(N)
n
для различных
т
и
п.
Частичная функция
f
из
(N)
m
в
(N)
n
называется вычислимой, если можно указать такой ал-
горитм («программу»), который для входного набора
х
(N)
m
дает на выходе
f(x),
если
х
D(f)
и
нуль, если
х
D(f).
В этом определении неформальное понятие алгоритма (программы) оказыва-
ется связанным (отождествленным) с понятием вычислимости функции. Вместо алгоритмов далее
будут изучаться свойства вычислимых функций. Вместо вычислимых функций оказывается необ-
ходимым использовать более широкий класс функций (и более слабое определение) - полувычис-
лимые функции. Частичная функция из
(N)"
в
(N)"
полувычислима, если можно указать такой ал-
горитм (программу), который для входного набора
х
с
(N)"
дает на выходе
х
е
D(f),
или алгоритм
работает неопределенно долго, если
х
е
D(f).
Очевидно, что вычислимые функции полувычисли-
мы, а всюду определенные полувычислимые функции вычислимы.
Частичная функция
f
называется невычислимой, если она не является ни вычислимой, ни
полувычислимой.
Из вновь введенных понятий основным является полувычислимость, так как вычислимость
сводится к нему. Существуют как невычислимые функции, так и функции, являющиеся полувы-
числимыми, но не вычислимые. Пример такой функции:
Можно показать, что существует такой многочлен с целыми коэффициентами
P(t, x
1
,...,x
n
),
что
g(t) -
невычислима. Однако, легко видеть, что
g(t) -
полувычислима.
Фундаментальным открытием теории вычислимости явился, так называемый, тезис Черча,
который в слабейшей форме имеет следующий вид: можно явно указать а) семейство простейших
полувычислимых функций; б) семейство элементарных операций, которые позволяют строить по
одним полувычислимым функциям другие полувычислимые функции с тем свойством, что любая
полувычислимая функция получается за конечное число шагов, каждый из которых состоит в
применении одной из элементарных операций к ранее построенным или к простейшим функциям.
Простейшие функции:
suc:
N
N;
suc
(x)
=
x
+1 - определение следующего за
х
числа;
l
(n)
:
(N)
n
N; l
(n)
(x
1
,..., х
n
)
= 1,
п
0 - определение «размерности» области определения
функции;
рr
n
i
: (N)
n
N; pr
n
i
(x
1
,..., х
n
)
=
х
i
, х
1 - «проекция» области определения на одну из пере-
менных.
54
Элементарные операции над частичными функциями:
а)
композиция
(или подстановка) ставит в соответствие паре функций
f
из
(N)
m
в
(N)
n
и
g
из
(N)
n
в
(N)
p
функцию
h = g
o
f
из
(N)
m
в
(N)
p
,
которая определяется как
б) соединение
ставит в соответствие частичным функциям
f
i
из
(N)
ni
, i =
1, ...,
k
функцию (
f
i,
...,
f
k
)
из
(N)
m
в
(N)
n1
х... х
(N)
nk
,
которая определяется как
в)
рекурсия
ставит в соответствие паре функций
f
из
(N)
n
в
N
и
g
из
(N)
n+2
в
N
функцию
h
из
(N)
n+2
в N,
которая определяется рекурсией по последнему аргументу
h(x
1
,
... ,
х
n
, 1) =
f
(
x
1
,
... ,x
п
)
(начальное условие),
h (x
1
,... ,х
n
, k+1) = g(x
1
,... ,x
n
, k, h(x
1
,... ,х
n
, k))
при
k
1 (рекурсивный шаг).
Область определения
D(h)
описывается также рекурсивно:
г)
операция т,
которая ставит в соответствие частичной функции
f
из
(N)
n+1
в
N
частичную
функцию
h
из
(N)
n
в
N,
которая определяется как
Операция
т
позволяет вводить в вычисления перебор объектов для отыскания нужного в
бесконечном семействе.
Теперь, когда введены простейшие функции и элементарные операции, можно дать сле-
дующие основные определения:
а) последовательность частичных функций
f
i, . . .
,f
N
называют частично рекурсивным (со-
ответственно примитивно рекурсивным) описанием функции
f
N
= f
, если
f
i - одна из простейших
функций;
f
i
для всех
i
2 либо является простейшей функцией, либо получается применением од-
ной из элементарных операций к некоторым из функций
f
i,...,
f
i-1
(соответственно одной из элемен-
тарных операций, кроме
т);
б) функция
f
называется частично рекурсивной (соответственно примитивно рекурсивной),
если она допускает частично рекурсивное (соответственно примитивно рекурсивное) описание.
Теперь можно привести тезис Черча в обычной форме:
а) функция
f
полувычислима, если и только если она частично рекурсивна;
б) функция
f
вычислима, если и только если рекурсивны
f
и характеристическая функция
X
D(f)
.
Характеристическая функция подмножества
Х
в
Y(X
Y)
есть такая функция, что
55
Тезис Черча может использоваться как определение алгоритмической неразрешимости.
Пусть имеется счетная последовательность «задач»
P
1
,
P
2
, ...,
которые имеют ответ «да»
или «нет». Такая последовательность носит название «массовой проблемы». Свяжем с ней функ-
цию
f
из
N
в
N:
Массовая проблема
Р
называется алгоритмически разрешимой, если функции
f
и
X
D(f)
час-
тично рекурсивны. В противном случае
Р
называется алгоритмически неразрешимой.
Контрольные вопросы и задания
1. Для чего необходимо формализовать понятие алгоритма?
2. Что означает фраза: «Машины Поста и Тьюринга являются абстрактными машинами»?
3. Для чего предназначены машины Поста и Тьюринга?
4. Как «устроена» машина Поста?
5. Перечислите и запишите команды машины Поста.
6. С помощью бумаги, карандаша и стиральной резинки «исполните» вместо машины Поста
программы сложения чисел из текста.
7. Составьте (и проверьте) программу для машины Поста, создающую на ленте копию за-
данной последовательности меток справа от нее.
8. Пользуясь предыдущей программой, составьте программу умножения чисел для машины
Поста.
9. Как «устроена» машина Тьюринга?
10. Каков принцип исполнения программы машиной Тьюринга?
11. Сравните машины Поста и Тьюринга. Укажите различия.
12. Выполните вместо машины Тьюринга примеры программ из текста.
13. Каким образом могут быть обобщена машина Тьюринга?
14. Что такое ассоциативное исчисление?
15. Постройте дедуктивную цепочку от слова «мука» к слову «торт», заменяя каждый раз
по одной букве так, чтобы каждый раз получалось слово.
16. Дайте определение нормального алгоритма Маркова.
17. В чем состоит принцип нормализации алгоритмов?
18. Охарактеризуйте способы композиции нормальных алгоритмов.
19. Как алгоритм может быть связан с рекурсивной функцией?
20. Дайте определения частичной, полувычислимой и вычислимой функции.
21. В чем состоит тезис Черча в слабейшей и в обычной формах?
22. Перечислите простейшие функции.
23. Перечислите элементарные операции.
24. Чем отличается рекурсивная функция от примитивно-рекурсивной?
25. Дайте определение частично-рекурсивной функции.
26. Что называется массовой проблемой? Что означает алгоритмическая разрешимость мас-
совой проблемы?
§ 8. ПРИНЦИПЫ РАЗРАБОТКИ АЛГОРИТМОВ
И ПРОГРАММ ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ
8.1. ОПЕРАЦИОНАЛЬНЫЙ ПОДХОД
В настоящее время создание алгоритмов - написание программ для электронных вычисли-
тельных машин - стало видом человеческой деятельности. Важнейший конструктивный компо-
нент программирования, не зависящий от особенностей синтаксиса языков программирования и
специфики функционирования конкретных вычислительных машин, - разработка алгоритма.
Подходы к созданию алгоритмов и требования к ним существенно изменялись в ходе эво-