Алгорифмы Маркова

На введении в специальность нам в ограниченном объёме преподают элементы теории алгоритмов, в частности, алгорифмы Маркова.

Алгорифмы Маркова (алгорифм - марковский вариант написания) - одна из алгоритмических моделей, применяемых для формализации понятия алгоритма. В алгоритмических моделях (машине Тьюринга, нормальных алгоритмах Маркова, частично рекурсивных функциях, МПД) принимается за основу некоторый принцип конструирования алгоритма из некоторых элементарных составляющих сущностей и принципов.

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

Последовательный список подстановок индуцирует некоторый алгоритм преобразования входного слова алгоритма:

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

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

Такая алгоритмическая модель полностью совместима с машиной Тьюринга и частично рекурсивными функциями.

Рассмотрим некоторые примеры алгоритмов Маркова.

Сложение двух целых чисел

Входной алфавит (список букв, из которых может состоять входное слово): <A, B, +>. Запись AAA..A обозначает положительное целое число, равное 1*(количество A в записи), запись BBB..B - соответственно отрицательное число.

В таком случае алгоритм будет состоять из трёх подстановок:

1) A+B -> +
2) B+A -> +
3) + -> @, где @ - пустое слово.

Например, при применении данного алгоритма к слову AA+BBB (что символизирует 2+(-3)=2-3) произойдёт последовательность таких замен: AA+BBB -> A+BB -> +B -> @B, что равно B (пустое слово - обозначение void; т.е любое слово начинается/заканчивается/содержит где угодно пустое слово), что символизирует -1.

Отметим, что это алгоритм годится и для входных слов вида AA+BBB+AAAA+A.., т.е. тех, где более одного знака сложения.

Для натуральных чисел (которые задаются словами вида “AAAAA..A”) алгоритм сложения будет состоять из одной-единственной подстановки:

1) + -> @

Умножение двух натуральных чисел

Входной алфавит для алгоритма: <1, '*'> - символ для записи натуральных чисел и знак умножения. На входе подаётся слово вида 11*1111, на выходе должно получиться слово вида 11111111 (2*4=8) В этом варианте алгоритма умножения я использовал два дополнительных символа в рабочем алфавите.

Что есть умножение? В нашем случае нужно каждой единице в части слева от знака * сопоставить число справа. Поскольку одно число справа уже есть, нам нужно скопировать эту правую часть n-1 раз, гд n - количество единиц в левой части.

В основе алгоритма лежит следующая конструкция-копир:

1) _1->1_Z
2) Z1->1Z

Её функция - “копирование” входного слова определённого формата: из _111 при помощи этого алгоритма мы получим 111_ZZZ, вот протокол работы (в квадратных скобках указан номер подстановки, применённой на данном шаге):

1: [1] 1_Z11
2: [2] 1_1Z1
3: [1] 11_ZZ1
4: [2] 11_Z1Z
5: [2] 11_1ZZ
6: [1] 111_ZZZ

Остаётся только использовать эту простейшую пару подстановок для умножения чисел. Итак, алгоритм нахождения произведения двух чисел:

1) 1*->x
2) _1->1_Z
3) Z1->1Z
4) 1x->x_
5) x->
6) _->
7) Z->1

Первая подстановка срезает одну единицу с левой части. Количество срезаемых единиц ограничивается при помощи использования рабочего знака умножения - x - вместо знака во входном слове - *. Вторая и третья подстановки - выполнение начатого копирования правой части. Четвёртая подстановка отнимает единицу от левой части, инициируя процесс копирования правой части в одном экземпляре. Подстановки с пятой по седьмую предназначены для приведение слова из рабочего в нормальный выходной формат.

Протокол работы алгоритма умножения для входного слова 111*111 (3*3):

01: [1] 11x111
02: [4] 1x_111
03: [2] 1x1_Z11
04: [3] 1x1_1Z1
05: [2] 1x11_ZZ1
06: [3] 1x11_Z1Z
07: [3] 1x11_1ZZ
08: [2] 1x111_ZZZ
09: [4] x_111_ZZZ
10: [2] x1_Z11_ZZZ
11: [3] x1_1Z1_ZZZ
12: [2] x11_ZZ1_ZZZ
13: [3] x11_Z1Z_ZZZ
14: [3] x11_1ZZ_ZZZ
15: [2] x111_ZZZ_ZZZ
16: [5] 111_ZZZ_ZZZ
17: [6] 111ZZZ_ZZZ
18: [6] 111ZZZZZZ
19: [7] 1111ZZZZZ
20: [7] 11111ZZZZ
21: [7] 111111ZZZ
22: [7] 1111111ZZ
23: [7] 11111111Z
24: [7] 111111111