В теории алгоритмов аналогично машинам Тьюринга доказана возможность построения различных композиций нормальных алгоритмов: суперпозиции, ветвления, цикла. Это позволяет получать все новые и новые нормальные алгоритмы.
Алгоритм называется нормализуемым, если можно построить эквивалентный ему нормальный алгоритм, и ненормализуемым в противном случае.
На данный момент неизвестно ни одного ненормализуемого алгоритма.
Таким образом, нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации (тезис Маркова): для любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм над алфавитом А. Другими словами, всякий алгоритм нормализуем.
Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих разработанных в России языков, получивших известность во всем мире.
Задание
1) Составить программу, имитирующую исполнение нормального алгоритма.
Внешний алфавит, программа решения конкретной задачи и входной текст считываются из файла input.txt
Пример файла input.txt для решения задачи о нахождении целой части и остатка от деления на 3 числа, записанного в унарной системе счисления:
/
/////
*///>/*
*!*
>*
Замечание: завершающую команду будем обозначать !
Не завершающую >
Алгоритм решения задачи:
Program Alg_Markova;
Uses Crt;
Type Command=Record {команда }
oldstr : String; {искомый фрагмент }
step : Boolean; {вид команды }
Newstr : String; {строка подстановки}
End;
Arr_Com=Array[1..100] Of Command; {массив команд}
Var a : Arr_Com;
alf : Set Of Char; {входной алфавит }
inp_str : String; {входная строка }
Count : Integer; {количество команд в алгоритме}
F : Boolean; {признак корректности ввода }
Procedure Init_Alf;
Var i : Integer;
s : String;
Begin
ReadLn(s);
{< формирование alf – множества символов строки s (входного алфавита) >}
End;
Procedure Init_A;
Var i : Integer;
alg : String;
Begin
{ < Повторять (пока не конец файла): > }
{ < считывание строки команд алгоритма > }
{ < определение i – номера команды > }
{ < формирование искомой подстроки (a[i].oldstr) i-ой команды > }
{ < формирование вида команды (a[i].step) > }
{ < формирование строки подстановки команды (a[i].newstr) > }
Count:=i; {запомнить количество команд в алгоритме}
End;
Procedure Init_str;
Var i : Integer;
Begin
{ < считывание из файла входной строки inp_str > }
{ < проверка корректности ввода: }
{ если ввод корректен, то f=true, иначе f=false > }
End;
Procedure Init;
Begin
Assign(input,’input.txt’);
Reset(input);
Init_alf; {процедура формирования alf – множества символов строки alfav}
Init_str; {процедура ввода из файла входной строки и проверка корректности ввода}
Init_A; {формирование массива команд алгоритма}
{a[i] – i-ая команда алгоритма, состоящая из трех полей:}
{oldstr – преобразуемая подстрока }
{step – вид команды: false – завершающая команда, true – в прот.случае} {newstr – подстрока подстановки}
Close(input);
End;
Procedure Solve;
{процедура работы со строкой (inp_str) сформированного алгоритма Маркова (А)}
Var k, p : Integer;
c : Char;
Begin
k:=1; { Настройка на первую формулу}
While k<=Count Do {Пока не все формулы проверены.}
Begin
If a[k].oldstr=» Then p:=1 Else p:=Pos(a[k].oldstr,inp_str); {Если левая часть формулы пустой текст, то вставка правой части с первой позиции, иначе определение позиции первого вхождения фрагмента в текст}
If p<>0 Then {Если формула выполнима}
Begin {Замена первого вхождения в тексте – выполнение подстановки}
Delete(inp_str,p,Length(a[k].oldstr));
If a[k].newstr<>» Then Insert(a[k].newstr,inp_str,p);
If Not (a[k].step) Then k:=Count Else k:=0;
End;
Inc(k)
End
End;
Begin
ClrScr;
Init;
WriteLn(‘Входная строка: ‘,inp_str);
If f Then Begin Solve; WriteLn(‘Результат: ‘,inp_str); End
Else WriteLn(‘Ввод не корректен’)
End.
2) Составить нормальные алгоритмы для решения следующих задач:
– упорядочивание (в порядке возрастания) букв в слове в алфавите A={a, b, c, d, e};
– удвоение каждого вхождения гласных букв в слове в алфавите A={a, b, c, d, e};
– увеличение числа в два раза в системе счисления с основанием p;
– уменьшение числа в два раза в системе счисления с основанием p;
– уменьшение числа на единицу в системе счисления с основанием p;
– нахождение остатка от деления числа на три в десятичной системе счисления.
3) Выполнить трассировку алгоритма. Каков результат работы нормального алгоритма для входного слова ‘aababc’ в алфавите {a, b, c}? Определить область применимости данного алгоритма.
1. *a #
2. *b #
3. *c #
4. #a a#
5. #b b# 6. #c c#
7. a# !
8. b# !
9. c# !
10. *
Loading ...