Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

10.2. Последовательная композиция. Часто встречается ситуация, когда два алгоритма — в частности, две тыоринговы программы SI, 23, — приходится сочетать следу­ ющим образом. Предписывается исходя из начальных дан­ ных, т. е. из слова Р, сначала применить алгоритм 21, а за­ тем к его результату, т. е. к слову ЩР), применить алго­ ритм 23 и, следовательно, получить слово 33(^1 (Р)). Это предписание составляет новый алгоритм — последователь­ ную композицию алгоритмов "21, 23, обозначаемую 3}. Естественно спросить, можно ли (а если да, то как) постро­ ить функциональную схему для последовательной компо­ зиции, коль скоро мы располагаем функциональными схе­ мами "21, 25. Утвердительный ответ содержится в следующей почти очевидной теореме.

Т е о р е м а (о программировании последовательной композиции). Каковы бы ни были тыорйнговы программы "21 и 23, может быть эффективно построена тыорингова про­

Программирующий алгоритм, который строит (эффек­ тивно) программу е, заключается в следующем. Предва­ рительно препарированные программы *2l, 93 объединяются в одну программу, а в подпрограмме «а всюду заменяется символ «!» символом начального состояния программы 93

не в заключительном состоянии «!», а в начальном состоя­ нии гх подпрограммы 93. Благодаря этому далее продол-

91

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

дартное изображение слов, лишь бы гарантировалась со­ гласованность перехода от 31 к ЙЗ. В качестве примера по­ строим функциональную схему алгоритма, перерабатываю­ щего пару чисел а, Ь, заданных соответствующими наборами палочек в их общий наибольший делитель, записанный в десятичной системе счисления. Поскольку этот алгоритм является последовательной композицией двух ранее рас­ смотренных алгоритмов (в п. 9.5 и 9.2), его функциональная схема (рис. 25, б) может быть получена из схем рис. 14 и 18, так, как этого требует описанный программирующий алго­ ритм. Состояния схемы рис. 18 здесь переименованы в р,.,

ръ р 2 . Хотя схемы рис. 14 и 18 не были составлены нами

применительно к стандартному изображению начальных и результирующих слов, тем не менее построенная схема рис. 25, б годится, ибо схема рис. 14 заканчивает работу на крайнем правом символе слова, а схема рис. 18 начинает там же работу (т. е. обеспечена согласованность перехода от первой программы ко второй).

92

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

10.3. Параллельная композиция алгоритмов 21, 23 заклю-. чается по существу в совместном рассмотрении их работы применительно к соответствующим исходным данным; пусть это будут слова Р и Н, соответственно. Более точно эту разновидность сочетания алгоритмов можно описать сле­ дующим образом. Допустим, что || — некоторый символ, не встречающийся в алфавитах, посредством которых изо­ бражаются исходные данные и результаты алгоритмов $1, 23; тогда слова Р \\ Н и ЩР) || ЩН) могут применяться как изображения пар исходных слов и пар результирующих

писание и составляет новый алгоритм — параллельную ком­

увеличит на единицу десятичное число 389, приведет сло­ жение слагаемых 6 + 4 и выдаст результат:

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

93