Нормальные алгорифмы Маркова (НАМ).

Они были предложены в качестве формального подхода к понятию алгоритма выдающимся русским математиком А.А.Марковым в 1950-х годах.

Рассматривается некоторый алфавит A и слова в этом алфавите.

Конкатенацией двух слов Q и R назовем слово QR, то есть в конкатенации сначала идут последовательно все символы слова Q, а затем все символы слова R. (Не зная слов Q и R, мы воспринимаем слово QR как единое целое).

Любую подпоследовательность идущих друг за другом символов слова назовем подсловом.

Слово, не имеющее букв, называется пустым словом и обозначается через L.

Слова, состоящие из одинаковых последовательностей символов, считаются эквивалентными. Заметим, что слова PQ, LPQ, PLQ, PQL эквивалентны в рамках формализма НАМ.

НАМ состоит из последовательности шагов работы. При определении шагов работы НАМ используются понятия преобразования, обычного и завершающего.

Обычным преобразованием слова P назовем переход от слова P к слову S. Завершающее преобразование состоит из обычного преобразования и команды остановки, которая обозначается точкой – (·). То есть после выполнения конечного преобразования работа заканчивается.

Преобразование p_i обозначается или в виде P_i®S_i (обычное), или в виде P_i®·S_i (завершающее).

Формально НАМ - это четверка {A,B,D, P}, где A - входной алфавит,B - надалфавит А, D - пустое слово, P - конечный упорядоченный набор преобразований P={p₁,…,p_n}. В каждом таком преобразовании присутствуют слова над алфавитом A (в алфавите B). Входное и выходное слова - это слова в алфавите A.

Если для слова P не существует ни одного преобразования такого, что P_i является его подсловом, то эту ситуацию обозначим следующим образом: PÜ. Если в результате применения НАМ к слову P образовалось слово R, то обозначим это через PÞR.

НАМ преобразует входное слово P в выходное Q. Работа НАМ осуществляется шаг за шагом. На первом шаге в качестве входного слова используется слово P. На каждом следующем шаге в качестве входного слова используется результат предыдущего шага. На каждом шаге во входном слове поочередно для i=1,…,n ищутся крайние левые подслова, эквивалентные P_i. Если такое подслово найдено, то выполняется преобразование p_i. Если это преобразование завершающее, то работа НАМ заканчивается. В противном случае переход к следующему шагу. И так для всех i=1,…,n. Если ни для какого из этих i упомянутое выше подслово не найдено, то работа НАМ заканчивается.

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

Входной алфавит - это алфавит, в котором написано входное слово. Составление НАМ - это нахождение B и P={p₁,…,p_n}. Предполагается, что пустое слово не входит ни в один из рабочих алфавитов НАМ.

Перейдем теперь к рассмотрению конкретных примеров. Договоримся о некоторых обозначениях. Целые числа задаются в алфавите {1, *}. Целое число n кодируется последовательностью из n+1 единицы. Несколько аргументов функции разделяются символом *. Например, при вычислении значения функции F(x,y,z) от трех переменных x=2, y=5, z=1 входное слово НАМ имеет вид 111*111111*11.

Для сокращения записи схемы алгоритма буквами h, x, z будем обозначать любые буквы входного алфавита A, а буквами a, b, g обозначаются конкретные буквы, не входящие в A. Например, имеем алфавит из 10 букв, а в схеме алгоритма идут подряд 10 преобразований стирания каждой одной буквы, которые могут выполняться в произвольном порядке. Все эти преобразования можно обозначать как h®D.

Дата добавления: 2015-07-11