Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.
Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.
В 1956 году отечественным математиком А.А. Марковым было
предложено новое уточнение понятия алгоритма, которое позднее было названо его
именем.
В этом уточнении
выделенные нами 7 параметров были определены следующим образом:
Совокупность исходных данных - слова в алфавите S;
Совокупность возможных результатов - слова в алфавите W;
Совокупность возможных промежуточных результатов - слова в
алфавите
Р=S
WV, где V - алфавит служебных вспомогательных символов.
Действия:
Действия имеют вид либо a®g, либо a a g, где a, g ÎP*, где
P* - множество слов над алфавитом Р,
и называется правилом подстановки. Смысл этого правила состоит в том, что
обрабатываемое слово w
просматривается слева направо и ищется вхождение в него слова a.
Определение.3.1. Слово a называется
вхождением в слово w, если
существуют такие слова b и n над тем же алфавитом, что и a и w, для которых верно: w=ban.
Если вхождение a в w найдено, то слово a заменяется
на слово g.
Все правила постановки упорядочиваются. Сначала ищется вхождение
для первого правила подстановки. Если оно найдено, то происходит подстановка и
преобразуемое слово опять просматривается слева направо в поисках вхождения.
Если вхождение для первого правила не найдено, то ищется вхождение для второго
правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотр правил
начинается с первого, а слово просматривается сначала и слева направо.
Вся совокупность правил подстановки называется схемой алгоритма.
Правило начала - просмотр правил всегда начинается с первого.
Правило окончания - выполнение алгоритма заканчивается, если:
было применено правило подстановки вида a a g,
не применимо ни одно правило подстановки из схемы алгоритма.
7. Правило размещения результата - слово, полученное после
окончания выполнения алгоритма.
Рассмотрим пример 1 из
лекции 2:
построить алгоритм для вычисления
U(n)=n+1;
S={0,1,2,3,4,5,6,7,8,9}; S=W;
V={*,+}.
Cхема этого НАМ показана на рисунке 3.1.
