ПЗ-03 Нормальные алгоритмы Маркова
1 Цель занятия изучить методику разработки и трассировки работы нормальных алгоритмов Маркова (НАМ).
2 Краткие методические указания. Любое преобразование информации можно свести к преобразованию слов некоторого алфавита. Например 
=1.4142…, 
=1.7120 описание преобразования обозначения величины корня из двух и трех в их значения в виде чисел. Однако такое перечисление значений не обладает свойством массовости. А калькулятор, из которого взяты эти значения, выполняет алгоритм, который этим свойством обладает. На этом занятии мы изучим методику описания и трассировки алгоритмов предложенных советским ученым Марковым. На сайте https://cmcmsu.no-ip.info/1course/alg.schema.nam.htm# дано краткое описание методики описания алгоритмов Маркова и размещен эмулятор, который выполняет эти алгоритмы.
Рассмотрим пример построения и трассировки работы НАМ. Рассматриваются слова в алфавите А={0,1}. Требуется описать НАМ, который заменит в слове из алфавита А все 0 на 1 и 1 на 0.
Нормальный алгоритм может быть таким:
0→1
1→0
Однако этот алгоритм не результативен. Он завершается только для пустого слова, так как в нем нет символов. Для любого другого слова из алфавита А алгоритм будет бесконечно заменять значение первого символа. Для получения результативного алгоритма введем в алфавит дополнительный символ, например *. Этот символ (маркер), будет обозначать позицию обрабатываемого символа и позволит завершить выполнение за конечное число шагов.
Алгоритм может быть таким:
1 *0→1* Обработка очередного символа 0 и сдвиг маркера к следующему символу;
2 *1→0* Обработка очередного символа 1 и сдвиг маркера к следующему символу;
|
|
3 *a Заключительная формула преобразования и стирание маркера;
4 →* Установка маркера перед первым символом слова.
Этот НАМ состоит из четырех формул подстановки. Первые две формулы заменяют значение символа и продвигают символ * - маркер позиции. Третья формула является заключительной. Она выполняется, если маркер достиг конца слова. В трассе мы будем записывать шаги выполнения алгоритма. Вначале будем записывать состояние слова с подчеркиванием обнаруженного фрагмента для замены, затем номер формулы подстановки в круглых скобках, затем вид формулы подстановки и результат подстановки. Знак → означает обычную подстановку, а знак a - заключительную.
Трасса работы алгоритма для слова 1001 будет следующей
1001 (4) → *1001 Ставим дополнительный символ перед словом
*1 001 (2)→ 0*001 Заменяем первую 1 на 0 и продвигаем *
0 *0 01 (1)→ 01*01 Заменяем 0 на 1 и продвигаем *
01 *0 1 (1)→ 011*1 Заменяем 0 на 1 и продвигаем *
011*1 (2)→ 0110* Заменяем 1 на 0 и продвигаем *
0110 * ( 3)a 0110 Стираем * и завершаем
В рабочее поле эмулятора не следует записывать номера правил.
Если рассматривать входное слово как двоичный вектор, то этот алгоритм выполняет инверсию двоичного вектора.
Рассмотрим решение некоторых задач из [1].
1 Замена bb на ddd и стирание с в словах алфавита А={abcd}.
c->
bb=>ddd
1 Стираем в слове все с
2 заменяем первую пару bb на ddd.
Для слова abcdbbbcd получим трассу выполнения.
аb c dbbbcd (1)→abdbbbcd исключили первую букву с
abdbbb c d (1)→abdbbbd исключили вторую букву с
abd bb bd (2)→abddddbd заменили bb на ddd
Завершили так как ни одно из правил не применяется.
|
|
После применения алгоритма к слову abcdbbbcd получим Результат: abddddbd
bbcddabbcd - Результат: dddddadddd
cbbbbdcbba - Результат: dddddddddda
Размещаем в слове сначала буквы а, а затем b.
ba->ab
ab ba bbaaabb (1)→ababbbaaabb
a ba bbbaaabb (1)→aabbbbaaabb
aabbb ba aabb (1)→ aabbbabaabb
aabb ba baabb (1)→ aabbabbaabb
aab ba bbaabb (1)→ aababbbaabb
aababbbaabb (1)→ aaabbbbaabb
aaabbb ba abb (1)→ aaabbbababb
aaabb ba babb (1)→ aaabbabbabb
aaab ba bbabb (1)→ aaababbbabb
aaa ba bbbabb (1)→ aaaabbbbabb
aaaabbb ba bb (1)→ aaaabbbabbb
aaaabb ba bbb (1)→ aaaabbabbbb
aaaab ba bbbb (1)→ aaaababbbbb
aaaa ba bbbbb (1)→ aaaaabbbbbb
Алгоритм завершен так как нет подстановок.
3 стираем первый символ в слове алфавита A={a,b}
*a=>
*b=>
* =>
->*
(4) Устанавливаем символ * перед словом.
(1,2) Удаляем первый символ и завершаем.
(3) Завершение для пустого слова.
baab (4)→ *baab
*b aab (2)→ aab
4 Записать символ а в конец слова алфавита А={a,b}.
*a->a*
*b->b*
*=>a
->*
(4) устанавливаем маркер * перед словом.
(1,2) Сдвигаем маркер к концу слова.
(3) Завершаем с вставкой символа а вместо маркера в конце слова.
Нормальный алгоритм Маркова целесообразно разрабатывать поэтапно. Вначале описать процесс подготовки к решению основной задачи, затем последовательно описывать остальные процессы. Рассмотрим процесс описания алгоритма перевода унарного числа в позиционное двоичное число.
Перевод унарного числа в двоичную систему счисления.
1-й шаг(H1). Маркер = вправо.
1) =| --> |= Двигаем маркер = вправо
2) = -->. = Завершаем, если он справа
3) ^ --> = Устанавливаем маркер = в начале слова.
Применяя алгоритм к слову
Получим Результат: ||=.
Й шаг(Н2). Маркер влево.
Деление на 2 будем делать двигая маркер вправо на две единицы. Но маркер = уже использовался. Поэтому вместо завершающего правила 2) = -->. = выполняем правило установки нового маркера * в правиле 4. Добавляем правило 2 сдвига маркера * влево и завершаем в правиле 3 при достижении маркером * начала слова.
|
|
Новый алгоритм H2 получаем как композицию алгоритма H2 и H1. Для этого вместо подчеркнутого заключительного правила в алгоритме Н1 записываем правила алгоритма Н2. Алгоритм Н2 работает со словом Р=, которое получено после работы алгоритма Н1 со словом Р Н2=Н2(Н1(Р)).
1) =| --> |= Двигаем маркер = вправо H1
2) |* --> *| Двигаем маркер * влево H2
3 ) * -->. * Завершаем, если маркер * слева. H2
4) = --> *= Установка нового маркера * справа H2
5) ^ --> = Устанавливаем маркер = в начале слова. H1
Применяя алгоритм к слову
Получим Результат: *||=