АЛГОРИФМЫ МАРКОВА

Задача 1.

Напишите программу, позволяющую автоматически реализовать нормальный алгоритм Маркова, обрабатывающий входное слово с помощью системы подстановок. Например, дано слово из алфавита {a,b,c,d}, следует расположить буквы в алфавитном порядке.

Нормальная система подстановок осуществляется так: сначала выполняется первая подстановка (x[1] заменяется на y[1]), слово переписывается. Затем - снова первая подстановка; если невозможно - вторая; если вторая не проходит, то третья. Слово переписывается. Снова первая подстановка, если невозможно - вторая; если невозможно - третья. Слово переписывается. Система подстановок, позволяющая расположить буквы в алфавитном порядка, представлена ниже:

slovo:='dabadbcadcbd';
------------
x[1]:='ba';  y[1]:='ab';
x[2]:='ca';  y[2]:='ac';
x[3]:='da';  y[3]:='ad';
x[4]:='cb';  y[4]:='bc';
x[5]:='db';  y[5]:='bd';
x[6]:='dc';  y[6]:='cd';

Для автоматического выполнения нормальногой алгоритм Маркова используется программа ПР-1. Результат работы программы - на рис. 1.


1 daabdbcadcbd | подстановка 1
2 daabdbacdcbd | подстановка 2
3 daabdabcdcbd | подстановка 1
4 adabdabcdcbd | подстановка 3
5 aadbdabcdcbd | подстановка 3
6 aadbadbcdcbd | подстановка 3
7 aadabdbcdcbd | подстановка 1
8 aaadbdbcdcbd | подстановка 3
9 aaadbdbcdbcd | подстановка 4
10 aaabddbcdbcd | подстановка 5
11 aaabdbdcdbcd | подстановка 5
12 aaabbddcdbcd | подстановка 5
13 aaabbddcbdcd | подстановка 5
14 aaabbddbcdcd | подстановка 4
15 aaabbdbdcdcd | подстановка 5
16 aaabbbddcdcd | подстановка 5
17 aaabbbdcddcd | подстановка 6
18 aaabbbcdddcd | подстановка 6
19 aaabbbcddcdd | подстановка 6
20 aaabbbcdcddd | подстановка 6
21 aaabbbccdddd | подстановка 6

Рис. 1. Перестановка букв по алфавиту

Задача 2.

Дана последовательность скобок. С помощью нормальной системы подстановок Маркова определите правильность скобочной структуры.

Чтобы реализовать нормальную систему подстановок Маркова, в программу ПР-1 следует вставить код:

slovo:='()()(())(()())(())';
--------------
x[1]:='**';   y[1]:='*';
x[2]:='()*';  y[2]:='*';
x[3]:='*()';  y[3]:='*';
x[4]:='(*)';  y[4]:='*';
x[5]:='()';  y[5]:='*';

Результат исполнения программы представлен на рис. 2.


1 *()(())(()())(()) | подстановка 5
2 *(())(()())(()) | подстановка 3
3 *(*)(()())(()) | подстановка 5
4 **(()())(()) | подстановка 4
5 *(()())(()) | подстановка 1
6 *(*())(()) | подстановка 5
7 *(*)(()) | подстановка 3
8 **(()) | подстановка 4
9 *(()) | подстановка 1
10 *(*) | подстановка 5
11 ** | подстановка 4
12 * | подстановка 1

Рис. 2. Определение правильности скобочной структуры.

Задача 3.

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

Чтобы решить эту задачу, в программу ПР-1 следует вставить код:

slovo:='10011';
----------
x[1]:='|0'; y[1]:='0||';
x[2]:='1';  y[2]:='0|';
x[3]:='0|';  y[3]:='|';

Результат решения задачи -- на рис. 3.


1 0|0011 | подстановка 2
2 00||011 | подстановка 1
3 00|0||11 | подстановка 1
4 000||||11 | подстановка 1
5 000||||0|1 | подстановка 2
6 000|||0|||1 | подстановка 1
7 000||0|||||1 | подстановка 1
8 000|0|||||||1 | подстановка 1
9 0000|||||||||1 | подстановка 1
10 0000|||||||||0| | подстановка 2
11 0000||||||||0||| | подстановка 1
12 0000|||||||0||||| | подстановка 1
13 0000||||||0||||||| | подстановка 1
14 0000|||||0||||||||| | подстановка 1
15 0000||||0||||||||||| | подстановка 1
16 0000|||0||||||||||||| | подстановка 1
17 0000||0||||||||||||||| | подстановка 1
18 0000|0||||||||||||||||| | подстановка 1
19 00000||||||||||||||||||| | подстановка 1
20 0000||||||||||||||||||| | подстановка 3
21 000||||||||||||||||||| | подстановка 3
22 00||||||||||||||||||| | подстановка 3
23 0||||||||||||||||||| | подстановка 3
24 ||||||||||||||||||| | подстановка 3

Рис. 3. Перевод числа из двоичной системы в унарную

Задача 4.

Напишите программу, автоматически реализующую нормальный алгоритм Маркова, складывающий два числа.

В программу ПР-1 следует вставить код:

slovo:='8eight+5five';
-------------
x[1]:='1one'; y[1]:='|';
x[2]:='2two'; y[2]:='||';
x[3]:='3three'; y[3]:='|||';
x[4]:='4four'; y[4]:='||||';
x[5]:='5five'; y[5]:='|||||';
x[6]:='6six'; y[6]:='||||||';
x[7]:='7seven'; y[7]:='|||||||';
x[8]:='8eight'; y[8]:='||||||||';
x[9]:='9nine'; y[9]:='|||||||||';
x[10]:='|+|'; y[10]:='||';
x[11]:='||||||||||'; y[11]:='10';
x[12]:='0|||||||||'; y[12]:='9';
x[13]:='0||||||||'; y[13]:='8';
x[14]:='0|||||||'; y[14]:='7';
x[15]:='0||||||'; y[15]:='6';
x[16]:='0|||||'; y[16]:='5';
x[17]:='0||||'; y[17]:='4';
x[18]:='0|||'; y[18]:='3';
x[19]:='0||'; y[19]:='2';
x[20]:='0|'; y[20]:='1';
x[21]:='|||||||||'; y[21]:='9';
x[22]:='||||||||'; y[22]:='8';
x[23]:='|||||||'; y[23]:='7';
x[24]:='||||||'; y[24]:='6';
x[25]:='|||||'; y[25]:='5';
x[26]:='||||'; y[26]:='4';
x[27]:='|||'; y[27]:='3';
x[28]:='||'; y[28]:='2';
x[29]:='|'; y[29]:='1';

Результат решения задачи - на рис. 4.


slovo:='8eight+5five';
----------------
1 8eight+||||| | подстановка 5
2 ||||||||+||||| | подстановка 8
3 ||||||||||||| | подстановка 10
4 10||| | подстановка 11
5 13 | подстановка 18

Рис. 4. Сложение двух чисел

Задача 5.

Напишите программу, автоматически реализующий нормальный алгоритм Маркова, умножающий два числа.

В программу ПР-1 следует вставить код:

slovo:='1111*111';
----------
x[1]:='*11'; y[1]:='A*1';
x[2]:='*1'; y[2]:='A';
x[3]:='1A'; y[3]:='A1B';
x[4]:='BA'; y[4]:='AB';
x[5]:='B1'; y[5]:='1B';
x[6]:='A1'; y[6]:='A';
x[7]:='AB'; y[7]:='B';
x[8]:='B'; y[8]:='1';

Результат работы программы - на рис. 5. Другой пример решения задачи:

slovo:='1111*111';
-----------
x[1]:='1*'; y[1]:='X';
x[2]:='_1'; y[2]:='1_Z';
x[3]:='Z1'; y[3]:='1Z';
x[4]:='1X'; y[4]:='X_';
x[5]:='X'; y[5]:='';
x[6]:='_'; y[6]:='';
x[7]:='Z'; y[7]:='1';


slovo:='1111*111';
-------------
1 1111A*11 | подстановка 1
2 1111AA*1 | подстановка 1
3 1111AAA | подстановка 2
4 111A1BAA | подстановка 3
5 11A1B1BAA | подстановка 3
6 1A1B1B1BAA | подстановка 3
7 A1B1B1B1BAA | подстановка 3
8 A1B1B1B1ABA | подстановка 4
9 A1B1B1BA1BBA | подстановка 3
10 A1B1B1AB1BBA | подстановка 4
11 A1B1BA1BB1BBA | подстановка 3
12 A1B1AB1BB1BBA | подстановка 4
13 A1BA1BB1BB1BBA | подстановка 3
14 A1AB1BB1BB1BBA | подстановка 4
15 AA1BB1BB1BB1BBA | подстановка 3
16 AA1BB1BB1BB1BAB | подстановка 4
17 AA1BB1BB1BB1ABB | подстановка 4
18 AA1BB1BB1BBA1BBB | подстановка 3
...............................
56 1111BBBBBBBB | подстановка 8
57 11111BBBBBBB | подстановка 8
58 111111BBBBBB | подстановка 8
59 1111111BBBBB | подстановка 8
60 11111111BBBB | подстановка 8
61 111111111BBB | подстановка 8
62 1111111111BB | подстановка 8
63 11111111111B | подстановка 8
64 111111111111 | подстановка 8

Рис. 5. Умножение целых чисел

Задача 6.

Имеется число в четверичной системе счисления. Предложите систему нормальных подстановок, которая переводит это число в двоичную систему счисления. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*3021032';
------------
x[1]:='*0';  y[1]:='00*';
x[2]:='*1';  y[2]:='01*';
x[3]:='*2';  y[3]:='10*';
x[4]:='*3';  y[4]:='11*';
x[5]:='*';   y[5]:=' ';

Задача 7.

Дано двоичное число. Предложите систему нормальных подстановок, которая инвертирует все 0 и 1. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*011010101';
-----------
x[1]:='*0';  y[1]:='1*';
x[2]:='*1';  y[2]:='0*';
x[3]:='*';   y[3]:=' ';

Задача 8.

Дано число в унарной системе счисления от 1 до 15. Предложите систему нормальных подстановок, которая представляет его как сумму степеней числа 2. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='|||||||||||||_';
-------------
x[1]:='||||||||';   y[1]:='8+';
x[2]:='||||';       y[2]:='4+';
x[3]:='||';         y[3]:='2+';
x[4]:='|';          y[4]:='1+';
x[5]:='+_';         y[5]:=' ';

Задача 9.

Имеется слово 'BAB_BA_AA_BABB_ABA'. Создайте нормальный алгоритм Маркова, который символы 'A' переносит влево, символы 'B' - вправо, а пробелы оставляет посередине. Промоделируйте на компьютере. (Ответ: 1) 'BA' => 'AB'; 2) 'B_' => '_B'; 3) '_A' => 'A_').

Задача 10.

Имеется слово 'abcbacbdacdb'. Создайте нормальный алгоритм Маркова, который кодирует это слово. Промоделируйте на компьютере. (Ответ: 1) 'a' => '00-'; 2) 'b' => '01-'; 3) 'c' => '10-'; 4) 'd' => '11-'; 5) 'e' => '111-').

Тексты программ находятся в zip-архиве, файл gl-15.pas.


ВВЕРХ

Майер, Р. В. Задачи, алгоритмы, программы / Р. В. Майер [Электронный ресурс]. - Глазов: ГГПИ, 2012 // Web-site http://maier-rv.glazov.net .