На введении в специальность нам в ограниченном объёме преподают элементы теории алгоритмов, в частности, алгорифмы Маркова.
Алгорифмы Маркова (алгорифм - марковский вариант написания) - одна из алгоритмических моделей, применяемых для формализации понятия алгоритма. В алгоритмических моделях (машине Тьюринга, нормальных алгоритмах Маркова, частично рекурсивных функциях, МПД) принимается за основу некоторый принцип конструирования алгоритма из некоторых элементарных составляющих сущностей и принципов.
В нормальных алгоритмах Маркова такой сущностью является подстановка,
задающая правило преобразования слова, состоящего из букв заданного
конечного алфавита. Подстановки устроены следующим образом: 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