Реферат: Нормальные Алгоритмы Маркова Построение алгоритмов из алгоритмов

В 1956 году отечественным математиком А.А. Марковым было предложено новое уточнение понятия алгоритма, которое позднее было названо его именем.

В этом уточнении выделенные нами 7 параметров были определены следующим образом:

Совокупность исходных данных - слова в алфавите S;

Совокупность возможных результатов - слова в алфавите W;

Совокупность возможных промежуточных результатов - слова в алфавите

Р=SWV, где V - алфавит служебных вспомогательных символов.

Действия:

Действия имеют вид либо a®g, либо aag, где a, gÎP^* , где

P* - множество слов над алфавитом Р, и называется правилом подстановки. Смысл этого правила состоит в том, что обрабатываемое слово w просматривается слева направо и ищется вхождение в него слова a.

Определение.3.1. Слово a называется вхождением в слово w, если существуют такие слова b и n над тем же алфавитом, что и a и w, для которых верно: w=ban.

Если вхождение a в w найдено, то слово a заменяется на слово g.

Все правила постановки упорядочиваются. Сначала ищется вхождение для первого правила подстановки. Если оно найдено, то происходит подстановка и преобразуемое слово опять просматривается слева направо в поисках вхождения. Если вхождение для первого правила не найдено, то ищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотр правил начинается с первого, а слово просматривается сначала и слева направо.

Вся совокупность правил подстановки называется схемой алгоритма.

Правило начала - просмотр правил всегда начинается с первого.

Правило окончания - выполнение алгоритма заканчивается, если:

было применено правило подстановки вида aag,

не применимо ни одно правило подстановки из схемы алгоритма.

7. Правило размещения результата - слово, полученное после окончания выполнения алгоритма.

Рассмотрим пример 1 из лекции 2:

построить алгоритм для вычисления

U(n)=n+1;

S={0,1,2,3,4,5,6,7,8,9}; S=W; V={*,+}.

Cхема этого НАМ показана на рисунке 3.1.

	Перегоняем служебный символ * в конец слова n, чтобы отметить последнюю цифру младших разрядов. Увеличиваем на единицу, начиная с цифр младших разрядов.
	Вводим служебный символ * в слово, чтобы им отметить последнюю цифру в слове.

Рис.3.1. Схема НАМ для вычисления U₁ (n)=n+1

Нетрудно сообразить, что сложность этого алгоритма, выраженная в количестве выполненных правил подстановки, будет равна:

(k+1)+(l+1),

--> ЧИТАТЬ ПОЛНОСТЬЮ <--