Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Нормальні алгоритми Маркова.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
КН-214
Частина тексту файла (без зображень, графіків і формул):
МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
Кафедра САПР
ЗВІТ
до лабораторної роботи № 9
на тему:
Нормальні алгоритми Маркова
Виконав:
Гр. КН-214
Перевірив:
Денисюк П. Ю.
Львiв 2007
Мета: Ознайомитись з алгоритмічною системою Маркова, навчитись зображати алгоритм Маркова у вигляді граф-схеми.
Алгоритмічна система Маркова заснована на відповідності між слова ми в абстрактному алфавіті і містить у собі об'єкти подвійної природи: элемен тарні оператори й елементарні розпізнавачі. Елементарні оператори- опера то ри алфавіту, послідовне виконання яких реалізує будь-які алгоритми в аналізо ва ній алгоритмічній системі. Елементарні розпізнавачі виконують розпізна вання присутності тих або інших властивостей інформації, що переробляється алго ритмом, а також для зміни (у залежності від результатів розпізнавання) по слідовності виконання елементарних операторів. Для визначення множини еле ментарних операторів і порядка їх виконан ня у конкретному алгоритмі зручно користуватися особливими орієнтованими графами, які називають граф-схема ми алгоритмів.
Граф-схема ал го ритму (її загальний вигляд наведено на мал. 1) являє со бою скінчену множину вузлів, з’єднаних між собою відповідно наступним правилам:
( вузол «вхід» не має вхідних дуг (це позначається як Р+(х) = 0), але має одну вихідну дугу (Р-(х) = 1);
( кожному вузлові, окрім «входу» і «виходу», зіставляєть ся елементар ний оператор або розпізнавач;
( у загальному випадку кількість дуг, що входять у вузол граф-схеми, мо же бути до вільною;
в окремому випадку (див. мал. 3):
- у кожний вузол, якому зіставлено елементарний розпізнавач, вхо дить по дві дуги (Р+(х) = 2) і з кожного такого вузла виходить по дві дуги (Р-(х) = 2);
- у кожний вузол, якому зіставлено елементарний оператор, в хо дить по одній дузі (Р+(х) = 1) і з кожного такого вузла виходить по одній дузі (Р-(х) = 1);
( вузол «вихід» має одну вхідну дугу (Р+(х) = 1) і не має вихідних дуг (Р-(х) = 0);
Мал. 3
Алгоритм, визначений граф-схемою, працює таким чином. Вхідне слово надходить на вхід і рухається по напрямкам, зазначеним стрілками. При влу чен ні слова в розпізнавальний вузол здійснюється перевірка умови, зіставленої вуз лові. При виконанні умови слово спрямовується в операторний вузол, при неви ко нанні, - у наступний розпізнавач. Якщо вхідне слово р, яке подано на вхід граф-схе ми, проходить через її вузли, перетворюється і кінець-кінцем потрапляє через скінчену кількість кроків на вихід, то враховується, що алгоритм можна за стосовувати до слова р (тобто слово р входить в область визначення цього ал горитму). Результатом впливу на слово р буде те слово, що потрапляє до виходу граф-схеми. Якщо ж після подачі слова р на вхід граф-схеми перетворення і пря мування слова вздовжо граф-схеми продовжується нескінчено довго, не при водячи на вихід, то враховується, що алгоритм не можна застосовувати до слова р (тобто слово р не входить в область визначення алгоритму).
У нормальних ал горитмах в якості элементарного розпізнавача викорис то вується розпіз на вач входження, а в якості элементарного оператора - опера тор підста новки. Розпізнавач входження перевіряє умову «слово р входить у якості підслова у деяке надане слово q ?». Оператор підстановки заміняє пер ше зліва входження слова рi у слово q на деяке надане слово р2. Оператор під становки за звичай задається у вигляді: рi( р2. Наприклад, для слова abcabca застосування підстановки bc(cb через два кроки:
( abcabca ( acbabca
( abcacba ( acbacba
призводить до слова acbacba. Послідовність слів p1, p2, ..., pn, одержуваних у процесі реалізації алгоритму, називається дедуктивним ланцюжком.
Алгоритм, що задається граф-схемою, яку складено виключно з розпізна вачів входження слів і операторів підстановки, називають узагальненим норма ль ним алгоритмом. При цьому передбачається, що до кожного оператора під ста новки веде лише одна дуга, що виходить із відповідного розпізнавача (Р+(х) = 1).
Нормальним алгоритмом називають такий узагальнений нормальний ал горитм, граф-схема якого задовольняє наступним вимогам:
( всі вузли, що відповідають розпізнавачам, упорядковано за їхньою ну мерацією від 1 до n.
( вихідні дуги вузлів, що відповідають операторам підстановки, під’єд нуються або до вузла, відповідного першому розпізнавачу, або до вихідного вуз ла. У першому випадку підстановка називається звичайною, у другому - заключ ною.
( вхідний вузол під’єднується дугою до першого розпізнавача.
Нормальні алгоритми прийнято задавати упорядкованою множиною під становок всіх операторів алгоритму (тобто схемою алгоритму). При цьому зви чайні підстановки записуються у вигляді рi(р2, а заключні підстановки - у виг ляді рi (· р2 (з точкою після стрілки). Процес виконання підстановок завершу ється лише тоді, коли жодна з підстановок не застосовна до отриманого слова або коли виконано заключну підстановку.
Розгляньмо, наприклад, роботу нормального алгоритма Маркова, який задано алфавітом A = {+, 1} і системою підстановок: 1+1(11 та 1(· 1 (граф-схему алгоритму наведено на мал. 4).
Нехай на вході задано рядок 11+11+1. Тоді наведеним алгоритмом його буде перетворено на рядок 11+11+1(1111+1(11111(11111. Таким чином, алгоритм реалізує додавання одиниць.
Наявність у нормальних алгоритмах підстановок двох видів: звичайної і заключної є необхідною умовою універсальності нормальних алгоритмів, яка формулюється як принцип нормалізації: «Для абиякого алгоритму у довільному скінченому алфавіті А можна побудувати эквівалентний йому нормальний ал го ритм над алфавітом А».
На основі відомих нормальних алгоритмів можуть бути побудовані нові алгоритми шляхом застосування різноманітних засобів композиції алгоритмів:
( суперпозиції алгоритмів А і В, коли вихідне слово алгоритму А роз гля дається як вхідне слово алгоритму В;
( об’єднання алгоритмів А і В в алгоритм С, що перетворює абияке сло во р, що міститься на перетинанні областей визначення алгоритмів А і В, в розта шовані поряд слова A(p) i B(p).
Мал . 4
Наприклад, якщо задано: X = {a, b}, A = {ab ( ba}, B = {ba ( ab} і слово аbа із області перетинання, то: A(aba) = baa, B(aba) = aab, C(aba) = baaaab;
( розгалуження алгоритмів, тобто композиції D алгоритмів A, B і C, об ласть визначення якої співпадає з перетинанням областей визначення алго рит мів A, B і C, а для абиякого слова р з цього перетинання:
D(p) = A(p), якщо C(p) = e,
D(p) = B(p),
C(p) ( e
, де е - порожній рядок.
Наприклад, якщо задано: A = {ab(ba}, B = {ba(ab}, C = {ab(a, ba( e} в алфавіті X = {a, b}, то дії алгоритму D можна уявити як:
A(aba) = baa A(bab) = bba
B(aba) = aab B(bab) = abb
C(aba) = aa C(bab) = e
D(aba) = aab D(bab) = bba
( повторення (ітерація) являє собою комозицію С двох алгоритмів А і В. Для будь-яко го вхідного слова р відповідне йому вихідне слово С(р) утворю ється у резу льтаті послідовного багатократного застосування алгоритму А до тих пір, поки не утвориться слово, що переробляється алгоритмом В в деяке фік соване слово.
Наприклад, якщо задано: X = {a, b}, A = {ab(ba}, B = {bbbaa(ab}, тоді C(ababb) = ab, оскільки: babb(baabb(babab(bbabb(bbaba(bbbaa(ab.
Важливе значення має можливість побудови складового універсального алгоритму, що може виконувати будь-які нормальні алгоритми; на його основі може бути побудовано універсальний комп’ютер.
Завдання: Задана стрічка символів, використовуючи алгоритм Маркова перетворити її з допомогою операції додавання. Намалювати граф-схему використаного алгоритму.
Текст програми
program markov;
Uses crt;
var st:string[70];
st5,st4,st2,st6,st3,st1:string[70];
i:integer;
begin
Clrscr;
writeln ('Zadana stri4ka: wadwtodere');
st:='wadwtodere';
writeln;
writeln('Operacii peretvorenia:');
writeln;
writeln('ad->d');
writeln('ere->aa');
writeln('o->w');
writeln;
st1:='ad';
st2:='ere';
st3:='d';
st4:='aa';
st5:='o';
st6:='w';
for i:=1 to length(st) do
if (copy (st,i,length(st1))=st1) then
begin
delete(st,i,length(st1));
insert(st3,st,i);
end;
for i:=1 to length(st) do
if (copy (st,i,length(st2))=st2) then
begin
delete(st,i,length(st2));
insert(st4,st,i);
end;
for i:=1 to length(st) do
if (copy (st,i,length(st1))=st5) then
begin
delete(st,i,length(st1));
insert(st6,st,i);
end;
writeln('-----------------Peretvorena stri4ka-----------------');
writeln;
writeln(st);
readln;
end.
Результати:
Задана стрічка -> zadltherefo
Операції:
ad->d
ere->aa
o->w
Перетворена стрічка -> zdlthaafw
Висновок: У даній лабораторній роботі я ознайомився з алгоритмічною системою Маркова, зобразив роботу системи на прикладі програми , а також у вигляді граф- схеми.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора