.Вопрос 35

Нормальные алгоритмы А. А. Маркова. Графическое представление, принцип нормализации, пример.

Алгоритмическая система основана на соответствии между словами в абстрактном алфавите и включает в себя объекты двоякой природы:

1. Элементарные операторы – это достаточно просто задаваемые алфавитные операторы с помощью последовательного выполнения, которых реализуются любые алгоритмы в рассматриваемой алгоритмической системе.

2. Элементарные распознаватели служат для распознавания тех или иных свойств переработки инф. , и для изменения в зависимости от рез-тов распознавания последоват. , в которой будут выполняться элементарные операторы.

В нормальных алгоритмах Маркова используется единственный оператор – подстановки. Обычно отображают в виде граф-схемы в которой имеются 2 особых узла : вход, выход. Из каждого узла сопоставл. распознавателя выходит = 2 дуги, и с каждого узла сопоставления подстановки = 1 дуга. Кол-во входящих дуг может быть различно. Входное слово поступает на вход. Далее двигаются по стрелкам. Снова попадая в узел распознавателя, проверяет на наличие условия. Если условия выполняются далее двигаются по стрелкам к узле ЭО, в противном случае к след.распознавателю.

Если входное слово проходя через узлы схемы через конечное число шагов попадает на выход , то алгоритм применим к этому слову. А если слово двигается по схеме бесконечно долго, не попадая на выход, то говорят что алгоритм не применим к этому слову.

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

Нормальные алгоритмы должны удовлетворять след.условию:

1. Все узлы соответств. распознавателя должны быть упорядочены с помощью их номерации от 1 до n.

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

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

В качестве пустого символа пишут –e или ƛ. Внутри слова пустой символ не пишется.

Принцип нормализации.

Принцип нормализации любого алгоритма (конструктивно-заданного алфавитного отображения), в произвольном конечном алфавите А можно построить эквивал. ему алгоритм над алгоритмом А.

Принцип нормализации математически доказать не возможно , поскольку здесь используется не строгое матем. использование алгоритма. Справедливость этого принципа позволяет выполнять операции композиции нормальных алгоритмов. В результате такой операции будет получен нормальный алгоритм, который не выходит за пределы класса нормальных алгоритмов.

Пример:

Вопрос 36

композиция нормальных алгоритмов Маркова: суперпозиция, объединение, разветвление и повторение (итерация).

1. При суперпозиии 2-х алгоритмов A и B выходное слово 1-го алгоритма рассматривается как 2-е слово входного алгоритма .

2. Объединение алгоритмов А и В в одном и том же алгоритме называется алгоритм С в том же алфавите преобразует любое входное слово содержащееся в пересечении образовав.определ. А и В в записанные рядом слова А(р) В(р) В(р) А(р).

3. Разветвление алгоритма представляет собой композицию 3-х алгоритмов А, В, С результат D имеет область совпадения с пересечением. Область определения всех 3 алгоритмов A,B, C и для любого входного слова p

4. Повторение или итерация представляют собой композицию 2-х алгоритмов А и В.

Входное слово получается в результате последовательного многократного применения алгоритма А до тех пор пока не будет получено слово переработанное алгоритмом В, в некоторой фиксированной аналогии цикла с постусловием.