Практикум павлодар 2014 удк
Марковтың нормальды алгоритмдері
жүктеу/скачать 1,42 Mb.
|
| 4.4 Марковтың нормальды алгоритмдері
Алгоритм ұғымын тұрпаттандыру үшін Россия математигі А.А. Марков ассоциативтік қисапты пайдалануды ұсынды. Ассоциативтік қисаптың кейбір ұғымдарын қарастырайық. Әріппе (әртүрлі таңбалардың ақырлы жиынтығы) бар болсын. Оны құраушы таңбаларды әріптер деп атаймыз. Әріппе әріптерінің кез келген ақырлы тізбегі (олардың сызықты қатары) осы әріппедегі сөз деп аталады. Әлдебір А әріппесіндегі N және M екі сөзін қарастырайық. Егер N M-нің бөлігі болса, онда M-ге енеді дейді. Әлдебір әріппеде алмастырулардың ақырлы жүйесі берілсін: N-M, S-Т, ..., мұндағы N, M, S, T,... – осы әріппедегі сөздер. Кез келген N-M алмастыруын әлдебір К сөзіне былай қолдануға болады: егер К-да N-сөзінің бір немесе бірнеше кірістері болса, онда олардың кез келгенін М-мен алмастыруға болады және керісінше, егер М-нің кірісі бар болса, онда оны N-мен алмастыруға болады. Р1 және Р2 сөздері әлдебір ассоциативтік қисапта сыбайлас аталады, егер олардың біреуі екіншісінен мүмкін алмастыруды бір ғана қолданғанда түрлендірілетін болса. Р, Р1, Р2,..., М cөздерінің тізбегі Р сөзінен М сөзіне әкелетін дедуктивті тізбек аталады, егер осы тізбектің қатар тұрған екі сөзінің әрқайсысы сыбайлас болса. Егер Р-дан М-ге тізбек және кері тізбек бар болса, онда Р және М сөздері эквивалентті аталады. Мысал: Әріппе Алмастырулар {а,в,с,d,e} ac-ca; abac-abace аd-da; eca-ae bc-cb; eda-be
39
өңдеудің әмбебап әдісі болып табылады және алгоритм ұғымын тұрпаттандыруға мүмкіндік береді. Ассоциативтік қисап негізінде алгоритм ұғымын енгізейік: А әріппесінде Алгоритм деп, А-дағы сөздерге үрдіс анықтайтын және бастапқы сөз ретінде кез келген сөзді мақұлдайтын түсінікті дәл ұйғарым. А әріппесінде алгоритм мақұл алмастыруларды қай тәртіппен қолдануға болатындығы және қашан тоқтайтындығы туралы дәл ұйғарыммен толықтырылған мақұл алмастырулар жүйесі түрінде беріледі. Мысал: Әріппе В алмастырулар жүйесі А={a,b,c} cb-cc cca-ab
Алмастыруларды қолдану туралы ұйғарым: кез келген Р сөзінде алмастырулардың сол жағын оң жағына ауыстырып, мүмкін алмастырулар жасау керек; жаңа алынған сөзбен үрдісті қайталау керек. Осылай, қарастырылған мысалдағы алмастырулар жүйесін ваваас және всасавс сөздеріне қолданып, мынаны аламыз:
bcacabc bcacbcac bcacccac bcacabc ақырсыз үрдіс (тоқтау жоқ), осымен біз бастапқы сөзді алдық. А.А.Марков ұсынған алгоритм ұғымын анықтау тәсілі мына төмендегідей анықталатын қалыпты алгоритм ұғымына негізделген. әріппесі және В алмастырулар жүйесі берілсін. Кез келген Р сөзі үшін В-дағы алмастырулар сол В-дағы өз ретімен алынады. Егер келісті алмастыру табылмаса, үрдіс тоқтатылады. Керісінше жағдайда келісімді алмастырулардың біріншісі алынып, оның Р-дағы солжақ бөлігінің бірінші кірісі оның оңжақ бөлігімен ауыстырылады. Сонаң соң барлық әрекет жаңадан алынған Р1 үшін қайталанады. Егер В жүйесінің соңғы алмастыруы қолданылатын болса, үрдіс тоқтатылады. Мұндай ұйғарымдар жиыны А әріппесімен және В алмастырулар жиынымен қалыпты алгоритмді анықтайды. Үрдіс екі жағдайда ғана тоқтайды: тиімді алмастыру табылмаған жағдайда; 2) олардың жиынындағы соңғы алмастыру пайдалынылған жағдайда. Әртүрлі қалыпты алгоритмдер бір-бірінен әріппелері және алмастырулар жүйесі арқылы ерекшеленеді. Натурал сандарды (бірлер жиынымен берілген) қосуды сипаттайтын қалыпты алгоритмге мысал келтірейік.
Мысал: Әріппе
Алмастырулар жүйесі 11 1 1 1 1
P сөзі: 11+11=111
40
сөзін Марковтың қалыпты алгоритмі арқылы біртіндеп қайта өңдеу мына кезеңдер арқылы өтеді: Р=11+11+111P5=+1+111111 P1=1+11+111Р6=++1111111
Марковтың қалыпты алгоритмін кез келген алгоритм берілуінің әмбебап түрі ретінде қарастыруға болады. Қалыпты алгоритмдер әмбебаптығы қалыптастыру принципі арқылы жарияланады: кез келген ақырлы А әріппесінде кез келген алгоритм үшін оған пара-пар А әріппесі бойынша қалыпты алгоритм құруға болады. Соңғы тұжырымды түсіндірейік. Кейбір жағдайларда алмастыруларында тек А әріппесінің әріптерін пайдаланатын болсақ, А әріппесінде берілген алгоритмге эквивалент қалыпты алгоритм құрылмайды. Дегенмен А әріппесін кеңейту арқылы (оған жаңа әріптерді қосу арқылы) қажетті, қалыпты алгоритм құруға болады. Бұл жағдайда, бастапқы А әріппесіндегі сөздерге ғана қолданы-латын болса да құрылған алгоритмді А әріппесі бойынша алгоритм дейді. Егер N алгоритмі А әріппесінің кейбір кеңейімінде берілген болса, онда N А әріппесі бойынша қалыпты алгоритм дейді. жүктеу/скачать 1,42 Mb. Достарыңызбен бөлісу:
|