Нормаль алгоритмдер

Нормаль алгоримтдерде қарапайым оператор ретінде алмастыру операторы (подстановка), ал қарапайым танып-білгіш ретінде кіріс танып-білгіші қолданылады.

Кіріс танып-білгіші р1 сөзінің қандай да бір q сөзінің құрамына енетіндігі-енбейтіндігі шартын тексереді.

Алмастыру операторы q сөзінің сол жағынан бастап, р1сөзін р2 сөзімен алмастырады, яғни р1→р2. Мысалы, abcabca сөзіне қолданылған bc→cb алмастыруы 2 қадамнан кейін acbacba сөзін береді:

abcabca→acbabca→acbacba.

Алгоритмнің орындалуы барысында алынатын р1,р2,…, рn сөздер тізбегі р1 сөзінен рn сөзіне жеткізетін дедуктивтік тізбекделінеді. Кіріс танып-білгіші мен алмастыру операторлары арқылы граф түрінде берілген алгоритмдер жалпыланған нормаль алгоритмдер деп аталады. Мұнда əрбір алмастыру операторына сəйкес танып-білгіштен шығатын бір ғана доға сəйкестендіріледі.

ba→ab, bc→ba, bb→aс алмастырулары арқылы берілген жалпыланған нормаль алгоритмді қарастырайық(2-сурет). Бастапқы сөз bcbaab түрінде берілсін. Нəтижеде baaaac сөзі алынады:

bcbaab→bcabab→bcaabb→baaabb→baaaac.

Граф-схемалары келесі шарттарды қанағат-тандыратын жалпы нормаль алгоритмдер нормаль алгоритмдер делінеді:

1. Танып-білгішке сəйкестендірілген барлық тораптар нөмірлері бойынша 1 мен n арасында реттелінеді.

2. Алмастыру операторына сай тораптан шығатын доғалар алғашқы танып-білгішке қатысты торапта немесе шығыс торабында түйіседі. Алғашқы жағдайда алмастыру қарапайым алмастыру деп, екінші жағдайда нəтижелік алмастыру деп аталады.

3. Кіріс торабы доға арқылы бірінші танып- білгішке жалғастырылады.

 

2-сурет

Жалпы, нормаль алгоритмдерде қарапайым алмастырулар р1→р2 түрінде, ал нəтижелі калмастырулар р1→.р2 түрінде таңбаланады. Ешқандай алмастыруды сөзге қолдану мүмкін болмағанда немесе қандай да бір нəтижелік алмастыру орындалған жағдайда алмастыруларды орындау тоқтатылады.

Алфавиті А={+,1} жəне алмастыру жүйесі ‘1+1’→’11’, ‘1’→.’1’ болатын А.А.Марков нормаль алгоритмі жұмысын қарастырайық. Бастапқы сөз ‘11+11+1’ түрінде берілсін. Алгоритмнің орындалу нəтижесі:

‘11+11+1’→’1111+1’→’11111’.

Алгоритм бірліктерді топтастырады.

Нормализация принципі. Қандай да біршекті А алфавиті арқылы құрылған кез-келген алгоритмге осы алфавит бойынша эквивалентті нормаль алгоритм құруға болады.

Көптеген жағдайда Аалфавиті бойынша құрылған алгоритмге эквивалентті алгоритм құру мүмкін болмайды. Бірақ А алфавитіне жаңа əріптер қосып, кеңейте отырып, қажетті нормаль алгоритм тұрғызуға болады (3-сурет). Егер де N алгоритмі А алфавитінің кеңейтілуі арқылы құрылса, онда N алгоритмі А алфавитке қатысты нормаль алгоритм делінеді.А алфавитіне қатысты F(p) бір орынды бөлікше сөздік функция нормаль есептелінетін делінеді, егер де А алфавитіндегі əрбір р сөзі үшін F(p)=N(p) орындалатындай N нормаль алгоритмі табылса.

3-сурет

Нормаль алгоритм графы

Мысал. {0,1} алфавитінде F(p)=pa формуласы мен берілген сөздік функцияны қарастырайық. {0,1,2} кеңейтілген алфавитінде 20→02, 21→12, 2→.а, Λ→2 схемалы N нормаль алгоритмі берілсін (мұндағы, Λ- бос орын). {0,1} алфавитінің қандай да бір 0110=p сөзін алайық. Бірінші қадам нəтижесі бойынша - 20110. Əрбір келесі қадамда 2 символы бір орынға жылжытылады. Бесінші қадамнан кейін 01102 сөзі алынады, яғни 0110 а=ра. Дербес жағдайда Λ→.Λ схемалы алгоритм F(p)=p функциясын, ал Λ→Λ схемалы алгоритм еш жерде анықталмаған функция мəнін есептейді. Нормализация принципі математикалық тұрғыдан дəлелденбейді.

3. Нормаль алгоритмдердің композициясы.

Берілген алгоритмнен жаңа алгоритм құру процесі композиция делінеді.

1) Алгоритмнің суперпозициясы. А мен В алгоритмдерінің суперпозициясында А алгоритмінің шығыс сөзі В алгоритмінің кіріс сөзі ретінде қарастырылады. Нəтижені C(p)=B(A(p)) арқылы өрнектеуге болады. Суперпозиция кез-келген саны шекті алгоритмдер үшін орындалады.

2) Х алфавитіндегі А,В алгоритмдерінің бірігуі деп сол алфавитке қатысты С алфавитін айтады. Мұнда А жəне В алгоритмдерінің анықталу облыстарының қиылысуындағы кез-келген р сөзі A(p) жəне B(p) қатар орналасқан сөздеріне түрлендіріледі. Ал басқа сөздер үшін бұл алгоритм анықталмаған.

Мысалы, X={a,b} алфавиті, A={ab→ba}, B={ba→ab} алгоритмдері жəне олардың анықталу облыстарының қиылысуында жатқан аba сөзі берілсін.

Нəтиже A(aba)=baa, B(aba)=aab, C(aba)=baaaab түрінде алынады.

3) Алгоритмнің тармақталуы А,В жəне С алгоритмдерінің композициясын құрайды. Композиция нəтижесі D болсын. D алгоритмінің анықталу облысы А,В жəне С үш алгоритмінің анықталу облыстарымен 4 беттеседі.Осы қиылысуда жатқан кез келген р сөзі үшін егер де C(p)=e болса, онда D(p)=A(p) жəне D(p)=B(p) орындалады. Мұндағы е– бос жол.

4) Итерация амалы А, В алгоритмдерінің композициясы арқылы өрнектеледі. Композиция нəтижесі С алгоритмі арқылы беріледі. Қандай да бір р кіріс сөзінен C(p) шығыс сөзі А алгоритмін бірнеше рет тізбектей қолдану арқылы В алгоритмінен алынады.

Мысалы, X={a,b} алфавиті, A={ab→ba}, B={bbbaa→ab} алгоритмдері берілсін. Демек, C(ababb)=ab нəтижесі келесі түрде алынады:

ababb→baabb→babab→bbaab→bbaba→bbbaa→ab.

1-4 композицияларды нормаль алгоритмдерге қолдануда нормаль алгоритмдер алынады. Кез-келген алгоритмнің жұмысын орындайтын универсал алгоритм құру есебінің маңызы зор.

Алгорифмдердің композициясы. Марков алгоритмдердің таралуы және бірігуі. Басқарушы алгоритм. Марковтың тармақталатын алгоритмі. Есептелінетін функциялар. Егер өзіне эквивалент қалыпты алгоритм құруға болатын болса, онда қандай да бір алгоритмді қалыптандырылымды, ал кері жағдайда бейқалыптандырылымды деп атауға келісейік. Қалыптандыру принципін енді басқаша айтуға болады: қандай алгоритм болмасын қалыптандырымды. Бұл негізді қатаң дәлелдеу мүмкін емес, себебі кез келген алгоритм ұғымы қатаң анықталмаған және қазіргі кезде белгілі алгоритмдердің бәрі де қалыптандырылымды, ал енді белгілі алгоритмдерден жаңа алгоритмдер құруға мүмкіндік беретін алгоритмдер композициясының тәсілдері оларды қалыптындырылатын алгоритмдер тобы шеңберінен шығармайтындығына негізделген. Төменде қалыпты алгоритмдерді композициялау тәсілдері келтірілген.

І Алгоритмдер суперпозициясы. А мен В екі алгоритмді суперпозициялау барысында бірінші алгоритмнің шығыс сөзі екінші В алгоритмінің кіріс сөзі ретінде қарастырылады, суперпозиция нәтижесі С мына түрде беріледі:

С(р)=В(А(р))

ІІ Алгоритмдерді біріктіру. А мен В алгоритмдерінің бір әріппеде біріктірілуі деп, А мен В алгоритмдерінің анықталу облыстарының қиылысын қамтитын кез келген р сөзін қатар жазылған А(р)және В(р) сөздеріне түрлендіретін сол әріппедегі С алгоритмін айтамыз.

ІІІ Алгоритмдердің тармақталуы. Алгоритмдердің тармақталуы үш А,В және С алгоритмдерінің композициясын білдіреді; сонымен бірге D алгоритмінің анықталу облысы үш бірдей А,В,С алгоритмдерінің анықталу облыстарының қиылысы болып табылады, ал осы қиылыстағы кез келген р сөзі үшін D(р)=А(р), егер С(р)=е; D(р)=В(р), егер С(р)=е, мұндағы е- бос жол.

ІV Алгоритмдер итерациясы. Итерация (қайталану) дегеніміз, кез келген р кіріс сөзі үшін сәйкес С(р) сөзі В алгоритмі түрлендіретін сөз пайда болғанға дейін біртіндеп А алгоритмін бірнеше рет қолдану нәтижесінде алынатын А мен В екі алгоритмінің С композициясы. Марковтың қалыпты алгоритмдері теориялық құрастыру құралы ғана емес, ол жасанды интеллект жүйесін жасау барысындағы таңбадық түрлендірулер тілі ретінде қолданылатын арнайы программалау тілінің негізі де. Түрлендіру мүмкіндігіне қарай Марковтың қалыпты алгоритмі Тьюринг машиналаларына пара-пар екендігінің қатаң дәлелденбеген.