Математический аппарат инженера

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

Элементарность шагов алгоритма. Предписание о получении последующей совокупности величин из предшествующей должно быть простым и локальным. Это означает, что соответствующая операция должна быть элементарной для исполнителя алгоритма (человека ли машины). Например, встречающиеся в алгоритме Евклида операции сравнения, вычитания и перестановки чисел можно было бы расчленить на более простые операции, если бы они не считались достаточно стандартными и привычными. В то же время сам алгоритм Евклида может фигурировать в качестве элементарной операции более сложного алгоритма.

5. Ассоциативное исчисление. Дальнейшее обобщение понятия алгоритма связано с ассоциативным исчислением, которое строится на множестве всех слов в данном алфавите.

Напомним, что алфавит представляет собой любую конечную систему различных символов, называемых буквами. Любая конечная последовательность n букв некоторого алфавита является словом длины n в этом алфавите. Например, в алфавите из трех букв {a, b, c} словами будут последовательности b, ac, bac, abba, cbcccacabca и т.д. Пустое слово, не содержащее ни одной буквы, обычно обозначается через ∧. если слово L является частью слова M, то говорят о вхождении слова L в слово M. Например, в слове abcbcbab имеются два вхождения слова bcb и одно вхождение слова ba.

В качестве операций ассоциативного исчисления определяется система допустимых подстановок, с помощью которых одни слова преобразуются в другие. Подстановка вида L-M, где L и M — слова в том же алфавите, означает замену вхождения левой части правой, равно как и замену правой части левой. Иначе говоря, если в некотором слове R имеется одно или несколько вхождений слова L, то каждое из этих вхождений может заменяться словом M, и наоборот, если имеется вхождение слова М, то его можно заменить словом L. Например, подстановка ab-bcb применима четырьмя способами к слову abcbcbab. Замена каждого из двух вхождений bcb даст слова aabcbab и abcabab, а замена каждого из двух вхождений ab дает слова bcbcbcbsb, abcbcbbcb. В то же время к слову bacb эта подстановка не применима. Подстановка вида Р-∧ означает, что из преобразуемого слова выбрасывается вхождение слова Р,

- 624 -

а также что между двумя какими-либо буквами преобразуемого слова или впереди него, или за ним вставляется слово Р.

Итак, ассоциативное исчисление — это множество всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Очевидно, чтобы задать ассоциативное исчисление, достаточно определить алфавит и систему допустимых подстановок (например, алфавит {a, b, c, d, e} и система подстановок ac-ca, ad-da, bc-cb, bd-db, abac-abacc, eca-ae, edb-be).

6. Эквивалентность слов. Два слова называются эквивалентными, если одно из них можно получить из другого последовательным применением допустимых подстановок. Так, в приведенном выше (5) исчислении эквивалентными являются, например, слова abcde cadedb, что видно из следующих последовательных преобразований: abc

de, acbde, cabde, cadbe, cadedb. Последовательность слов R₁

, R₂, ..., R_n, когда каждое следующее слово является результатом однократного применения допустимой подстановки к предыдущему слову, образует дедуктивную цепочку, причем соседние слова в этой цепочке называют смежными. Очевидно, любые два слова в дедуктивной цепочке являются эквивалентными.

Эквивалентность слов L и M обозначается L ~ M и обладает всеми свойствами отношения эквивалентности (рефлексивность, симметричность и транзитивность). Если L ~ M, то при наличии в каком-либо слове R вхождения L в результате подстановки L-M получается слово, эквивалентное R. Например, воспользовавшись эквивалентностью abcde~cadbe, из слова bbabcdec получаем эквивалентное ему слово bbcadbec.