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

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

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

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

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

1. В начале входное слово алгоритма объявляется текущим.

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

3. Если в списке не нашлось ни одной подстановки, применимой к текущему слову, алгоритм завершает работу.

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

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

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

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

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

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

1) A+B → +
1) B+A → +
2) + → @, где @ — пустое слово.

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