Нормальные алгоритмы Маркова

Советский ученый А.А.Марков избрал другой путь для уточнения понятия алгоритма. Он разработал строгую теорию класса алгоритмов, которые назвал нормальными алгоритмами (алгорифмами).

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

Рассмотрим два алфавита: А=(1,2,3,4) и В=(1,2,3,4,5,6). Поскольку каждая буква алфавита А является буквой алфавита В, то алфавит В будем называть расширением алфавита А.

Используя символы алфавита, можно образовывать произвольные последовательности слов. Например, пусть задан алфавит букв русского языка, на основе которого получено слово алгоритм. Из этого слова можно вырезать части слова, например ал, гори, ритм и т.д. Такие слова будем называть вхождениями в это слово.

Слова будем обозначать заглавными латинскими буквами, а признак соответствия будем отражать символом равенства. Например, R=алгоритм, D=гори, при этом D является вхождением в R. Возможны случаи многократных вхождений каких-либо слов в другие слова, например, слово а входит в слово задача три раза, поэтому будем различать так называемое первое вхождение. Отметим, что пустое слово может входить в непустые слова несколько раз (перед первой буквой, между соседними буквами и после последней буквы).

Введем операцию марковской подстановки, задаваемой с помощью пары слов (P, Q) и заключающейся в следующем: если задано исходное слово R, то в нем находим первое вхождение слова P и заменяем это вхождение словом Q, не заменяя остальных частей слова. Полученное таким образом слово является результатом марковской подстановки к слову R. Если вхождений слова P в слове R нет, то считается, что марковская подстановка (P, Q) не применима к слову R.

Возможны варианты использования в записи марковской подстановки пустого слова, например, запись (,H) означает замену первого вхождения пустого слова на слово H; (G,) – замену первого вхождения слова G на пустое слово; (,) – замену первого вхождения пустого слова на пустое слово.

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

Введем еще два обозначения:

P→Q – соответствует обычной подстановке (P,Q);

PÞQ – соответствует конечной подстановке (P,Q).

Рассмотрим единое правило применения марковской подстановки для всех нормальных алгоритмов. Обозначим: A – исходное слово; B – слово, полученное в результате применения марковской подстановки; N – номер подстановки. В качестве начального слова берется слово A, и к нему применяют по порядку каждую подстановку из схемы подстановки. Если подстановка возможна, то ее осуществляют и начинают подстановки сначала. Если процесс обрывается (нет ни одной допустимой подстановки) на слове B или приходит в конечную подстановку, то данный нормальный алгоритм преобразовал A в B.

Пример: задан алфавит букв русского языка. Множество подстановок представим в следующем виде:

1. я®П

2. з®о

3. ы®с

4. кÞт

5. м®ф

6. …

Применим нормальный алгоритм с приведенными подстановками для исходного слова язык. Первая подстановка применима, и слово язык превращается в результате ее использования в слово Пзык. Поскольку это не конечная подстановка, то слово Пзык становится исходным, и к нему снова надо применить первую постановку. Но она не применима, поэтому переходим ко второй подстановке, в результате применения которой получаем слово Поык, которое и становится исходным. Далее получаем слово Поск. Последней выполняется подстановка кÞт, и процесс завершается, поскольку эта подстановка является конечной (подстановки 5, 6 и т.д. не рассматриваются). В результате мы получили слово Пост.

В несколько усложненном виде вы использовали нормальные алгоритмы Маркова во время детской игры (составление метаграмм) суть которой заключается в том, что, используя подстановки вида а®б, …, а®я, …, я®а, …, я®ю необходимо из одного слова получить заданное другое, причем промежуточные слова должны принадлежать словарю русского языка: миг-маг-май-чай-час; душа-суша-сушь-суть-сеть-сень-сено-село-тело.

Нормальные алгоритмы разработаны с целью формализации понятия алгоритма, имеют очень частный характер и описаны с полной математической строгостью и точностью.

Существует гипотеза, известная под названием принципа нормализации: «Любому алгоритму, использующему в качестве исходных и результирующих данных некоторые слова из одного алфавита А, соответствует эквивалентный ему нормальный алгоритм над алфавитом А».