Білім беру бағдарламасы білім алушыларына арналған. Лекциялар жинағы «Техника және ақпараттандыру»
жүктеу/скачать 316.11 Kb.
|
- Бұл бет үшін навигация:
- Ұсынылған әдебиеттер
- ЛЕКЦИЯ № 5 5. Тақырыбы : Прологта бағдарламаның орындалуын басқару. ЛЕКЦИЯ ЖОСПАРЫ
- ЛЕКЦИЯ МАЗМҰНЫ
| Бақылау сұрақтары:
1. Рекурсия тсінігіне анықтама бер 2. Транзитивті үзіліс деген не? 3. Рекурсия базисі деген не 4. Рекурия мақсатын қалай анықтаймыз 5. Рекурсия мен итерация айырмашылығы 6. Артқы рекурсияға анықтама беріп, мысал келтіріңдер 7. Рекурсиядағы аргументтер. 8. Қима алу дегеніміз не? Ұсынылған әдебиеттер 1. Рассел, С Жасанды интеллект. 1-том. Жаңашыл әдіс-Логика. А,2013-540 (ҚР БЖҒМ «Оқулық» орталығы бекіткен). 2. Абдрахманова, Г., Визуалды бағдарламалау технологиясы [Мәтін]: Оқу құралы / Г. Абдрахманова -Шымкент, 2019. ЛЕКЦИЯ № 5 5. Тақырыбы: Прологта бағдарламаның орындалуын басқару. ЛЕКЦИЯ ЖОСПАРЫ Тереңдікте іздестіру əдісі. Сəтсіздіктен кейінгі шегіну. Кесу жəне шегіну. Қолданушымен анықталатын іздестіру əдісі. ЛЕКЦИЯ МАЗМҰНЫ Бұл дəріс Прологта бағдарламалау кезіндегі бағдарламаны басқаруды ұйымдастыру əдістерін таныстырады. Əрине, айқын немесе айқын емес түрдегі ұйымдастыру əдістерінің қандай да бір бөлігін біз алдағы дəрістерде қарастырғанбыз. Мұнда бұл уақытқа дейін айқын емес түрде қолданғандар тұжырымдалады. Бұл əдістер қандай кезде қолданылатынын, олар қалай жұмыс істейтінін жəне оларды қалай қолдану керектігін қарастырамыз. Сонымен қатар, бұл уақытқа дейін қарастырмаған кейбір жаңа əдістерді талдаймыз. Бэктрекингті (немесе шегіну, немесе __________кейін оралумен іздестіру, немесе тереңдікте іздестіру механизмі) тағы бір рет талқылаудан бастайық. Шегіну туралы алдағы дəрістерде атап өткенбіз. Бұл механизмнің мəні мынада: бағдарламаның бірнеше нұсқаларды таңдап алынуы жерінен келесі рет осы позицияға оралу үшін Пролог кейін оралу нүктесін арнайы стекте сақтайды. Кейін оралу нүктесі шегіну кезіндегі процедураны қайта бастағанда керекті ақпаратқа ие. Мүмкін болатын нұсқалардың біреуін таңдалады, бұдан кейін бағдарламаның орындалуы жалғаса береді. Альтернативасы бар бағдарламаның барлық нүктелерінде көрсеткіштер стекке енгізіледі. Егер нəтижесінде таңдалған нұсқа сəттілікке əкелмейтін болса, онда бағдарламаның стекте бар альтернативті нұсқалардың біреуі таңдалған соңғы нүктеге шегіну орындалады. Нұсқаның тағы біреуі таңдалады, бағдарлама өзінің жұмысын жалғастырады. Нүктедегі барлық нұсқалар қолданылып болса, онда сəтсіз аяқталу тіркеледі жəне мұндай бар болатын болса алдағы оралу нүктесіне өту орындалады. Шегіну кезіндегі осы нүктеден кейін белгіленген барлық байланысқан айнымалылар тағы да босайды. Бэктрекинг мəнін түсіндіру кезінде лабиринтте жол іздеу мысалын жиі келтіреді. Лабиринттен жол табудың мүмкін əдістерінің бірі - тұйыққа тірелгенше дейін əр жол торабынан бір жаққа бұрыла беру керек. Тұйыққа тірелген соң ең жақын жол торабына дейін кері қайту керек. Оның үстінде басқа бағыт таңдау керек. Бұдан кейін барлық жол торабтарынан ең басында таңдалған бағыт бойынша бұрылыстарды таңдау қажет. Бұл алгоритмді лабириттен шыққанша жалғастыра береміз. Мысал. Шегіну механизімінің жұмысын туыстық қарым-қатынасты сипаттайтын сəл модификацияланған бағдарлама негізінде қарастырайық. Домендерді жəне предикаттарды сипаттау бөлімін өзгеріссіз қалдырайық, ал біздің мақсатымызға сай болу үшін сөйлемдер бөлімінде факттар ретін өзгертейік. Келесі бағдарламаға ие боламыз: DOMAINS /* домендерді сипаттау бөлімі*/ s=string /* мəліметтің жолдық типі үшін синонимді енгіземіз */ PREDICATES /* предикаттарды сипаттау бөлімі */ mother(s,s) /* мама предикаты жолдық итптің екі аргументтіне ие болады */ grandmother(s,s) /* əже предикатына да орыны бар */ CLAUSES /* сөйлемдерді сипаттау бөлімі */ mother("Даша","Маша"). /* «Даша» и «Маша» мама қарым-қатынасымен байланысқан */ mother("Наташа",”Даша"). /*«Наташа» «Даша»-ның мамасы*/ mother("Наташа",”Глаша"). /* «Наташа» жəне «Глаша» мама қарым-қатынасымен байланысқан */ mother("Даша",”Саша"). /* «Даша» «Саша»-ның мамасы */ grandmother(X,Y):– /* X Y-тің əжесі,егер */mother(X,Z), /* X Z-тің мамасы, ал */mother(Z,Y). /* Z Y-тің мамасы */ деген Z табылса, бағдарламаны іске қосудан кейінгі сыртқы мақсат ретінде барлық əжелер мен немерелердің атын сұрайық (grandmother(B,V)). Пролог- жүйесінің біздің сұрағымызға жауап іздеу кезіндегі жұмыстың үрдісін бақылау үшін бағдарламаның басында trace компиляторына дерективаны жазу арқылы трассировканы жалғауға болады. Редакциялау терезесінде курсор бұл қадамда орындалатын мақсатастыны (подцель) көрсетеді. Трссировка терезесінде қосымша ақпарат көрсетіледі. Ескертейік, мақсатастынан мақсатастына өту F10 функционалдық батырмасы арқылы орындалады. grandmother(B,V) мақсаты орындалу үшін екі mother(B,Z) жəне mother(Z,V) мақсатасты қанағаттандырылуы керек. Бірінші мақсатасты «мама болу» қарым-қатынасын сипаттайын бірінші сөйлеммен унифицияланады. Бұл кезде В айнымалысы «Даша», ал Z айнымалысы «Маша» атымен нақтыланады. Бұл кезде трассировка терезесінде RETURN сөзінен кейін шығатын ағымдағы мақсатастының есептелу нəтижесі (mother("Даша",”Маша")) мақсатастының альтернативті шешімі барын көсететін (*) жұлдызшамен қосақталып жүреді. Келесі рет оралу мүмкіндігі үшін Пролог қайта оралу нүктелер стекіне сол жерге сілтеушіні енгізеді. Одан кейін mother(Z,V) екінші мақсатастын қанағаттандыруға əрекет жасалады, жəне де Z айнымалысы «Маша» атымен белгіленген. Бұл мақсатастыны mother предикатына қатысы бар бір фактпен унифициялау сəтсіздікке ұшырайды. Бұл біздің білім базасында Машаның балалары туралы ақпарат болмағандықтан болып отыр. Сəтсіздік туралы трассировка терезесіндегі FAIL сөзі айтып отыр. Кейін қайту нүктелер стекінде сақталған орынға дейін шегінеді. Бұл кезде шегіну кезіне белгіленген B жəне Z айнымалылары қайтып бос болады. Екінші альтернатива таңдалады. Бұл кезде В айнымалысы «Наташа» атына тең болады, ал Z айнымалысы «Даша» мəніне ие болады. Трассировка терезесіндегі бұл нүктені бірінші өтуі кезіндегідей жұлдызша біздің мақсатастыны қанағаттандыратын барлық альтернативалардың таусылмағанын көрсетеді. Екінші мақсатастына mother(Z,V) (Z = "Даша" болған кезде) шешім табу əрекеті жасалып жатыр. Мother предикатын іске асыратын процедурадағы бірінші сөйлем ағымдағы мақсатастымен унифицияланады, V айнымалысы «Маша» мəніне ие болады. Трассировка терезесіндегі кезекті жұлдызша осы жерге қайтып келу үшін осы орынға сілтегіш қайта оралу нүкте стекіне орналастырылғандығын көрсетеді жəне ағымдағы мақсатастыны сəттілікке əкелетін V айнымалысына басқа да мəндер берілуі мүмкін. Біздің сұрағымызға жауапты мына айнымалылар келесі мəндерге ие болған кезде B=Наташа, V=Маша ала аламыз. Бұл жауап диалог терезесінде көрсетіледі, бұдан кейін қайта оралу стекіне жазылған соңғы жерге шегіну іске асырылады. Бұл кезде «Маша» атымен белгіленген V айнымалысы босатылады. mother(Даша,V) мақсатасты mother предикатын анықтайтын процедураның соңғы сойлемнің басымен унифицияланады. V айнымалысы «Саша» атымен белгіленеді. Диалогтық терезеде біз қойған сыртқы мақсат түріндегі сұраққа: B=Наташа, V=Саша екінші мүмкін жауабы шығарылады. mother(Даша,V) мақсатастына арналған альтернативті шешім басқа жоқ. Сəйкесінше, трассировка терезесінде жұлдызша болмайды, ал қайта оралу нүкте стекінде grandmother қатынасын анықтайтын екінші мақсатастының ережелері үшін жаңа мəндерді таңдау мақсатында қайта оралуға болатын жерге сілтеуші жоқ. Бірақ қайта оралу нүктелер стекінде «быть бабушкой» қатынасын анықтайтын ереже денесінде бағдарламаның бірінші мақсатастына айнымалыларды мəндендірушілер орналасқан бағдарламаның бөліміне сілтеуші қалады. Пролог-жүйе жолшыбай айнымалыларды босата отырып шегінеді. Бірінші мақсатасты үшінші факт mother("Наташа",”Глаша")-мен сəйкестендіріледі. Трассировка терезесінде ағымдағы mother(B,Z) мақсатасты үшін арналған нұсқалар ішінен əлі барлығы қолданылмағандығын көрсететін бізге таныс жұлдызша таңбасын көреміз. mother("Глаша",V) мақсатастын білімдер базасындағы бар фактпен сəйкестендіруге тізбекті сынақтан өткізулер жасалады. Бірақ та Глашаның балалары туралы ақпараттар біздің бағдарламада жоқ болғандықтан бұл сынақтан өткізулер сəтсіздікпен аяқталады. Трассировка терезесінде бұл сəтсіздік туралы хабарлайтын FAIL сөзі шығады. Бағдарламаны соңғы рет орындау үрдісі бірінші мақсатасты үшін шешім табатын жерге шегінеді. Мақсатасты процедурадағы мамаларға қатысты білімдерді сипаттайтыни соңғы ұсыныспен унифицирияланады. В айнымалысы "Даша" атымен, ал Z айнымалысы-"Cаша" атымен нақтыланады. Бірінші мақсатастыны сəйкестендіру үшін басқа нұсқалар қалмайды. Қайта оралу нүкте стекі бос. Трассировка терезесінде қайтып келуге болатын альтернативті шешімдер туралы хабарлайтын индикаттар жоқ. Пролог-жүйесі екінші мақсатастыны mother("Саша",V) бірденемен сəйкестіргісі келеді, бірақ оны ол іске асыра алмайды. Факттың бірде біреуі бірінші аргумент кейпінде "Саша" атына ие емес. Даша үшін немерелерді табудағы кезектң сəтсіздік. Бағдарлама аяқталады. Диалогтық терезеде жұмыс барысында табылған екі шешім: B=Наташа, V=Маша B= Наташа, V=Саша 2 Solutions Енді програмисте шегінуді басқарудың қандай мүмкіндіктері барын көрейік. Қосымша шешімдер алуға мүмкіндік беретін жəне сəтсіздіктен кейінгі шегіну əдісі деп аталатын тереңдікте іздестіру механизмнің модификациясын қарастырайық. Бұл əдіс бір ғана емес осы жағдайда барлық мүмкін жауаптар алу үшін қолданылады. Мысалы, егер сұрақ ішкі мақсат болып табылса, онда Турбо Пролог бірінші сəтті мақсатты есептеуден кейін іздестіруді аяқтайды. Бұл кезде тек бірінші шешім ғана анықталады. Мысал. Алдағы мысалда қойған сұрақты қояйық, бірақ сыптқы мақсат ретінде емес ішкі мақсаттың сипаттама бөлімінде көрсетейік: GOAL grandmother(B,V) Егер бұл бағдарламаны іске қосатын болсақ, ол өзінің жұмысын диалог терезесінде ештенені шығармай аяқтайды. Себебі, бағдарламада ішкі мақсат болатын болса, Турбо Пролог диалогтық терезеде айнымалылардың мəнін көрсетпейді, ал __________сыртқы мақсатты іске асырған кезде Турбо Пролог трезеге сұрақта бар барлық айнымалыларды шығарады. Бұл сыртқы мен ішкі мақсаттың ең бірінші маңызды айырмашылығы. Бірақ та іште құрастырылға write предикаттын қолданып, мақсатасты ретінде B жəне V айнымалыларды қоса отырып ішкі мақсаттың есептеу нəтижесіндегі шешімін экранға шығаруды біз өзіміз ұйымдастыруымызға болады. Ішкі мақсатты сипаттау бөлімі, мысалы, мынадай болуы мүмкін: GOAL grandmother(B,V),write("Имя бабушки — ",B), write(", имя внучки — ",V),nl Бұл кезде біз экранда əже мен немеренің атын көреміз, бірақ диалог терезесінде екі шешім емес тек бір ғана шешім шығады: Əженің аты — Наташа, енмеренің аты — Маша. Бағдарламада ішкі мақсат болатын болса, Турбо Пролог сыртқы мақсат жағдайында сияқты барлық мүмкін айнымалыларды мəндендіруді емес, тек мүмкін болатын біреуін ғана табады. Бұл сыртқы мен ішкі мақсаттардың екінші ерекшелігі. Егер бізге барлық шешімдер керек болатын болса, оныəдейі ұйымдастыру керек, мысалы, сəтсіздіктен кейінгі шегіну əдісі арқылы. Жаңа предикаттарды кейінге қалдыру сатысында сыртқы мақсаттар қолданылады. Егер бізге өңдеу ортасынан тыс іске қосыла алатын бағдарлама керек болатын болса, онда оның ішінде міндетті түрде ішкі мақсат болуы керек. Сəтсіздіктен кейінгі шегіну əдісінде негізінде əрдайым алдындағы лекцияда айтылған жалған предикат fail қолданылады. Бірақ та, бұл предикаттың орнына қандай да бір біле тұра жалған айтылуды қолданылуға болады. Мысалы, 1=2 немесе осы сияқты. Егер біздің ішкі мақсатымызға fail предикатын қосатын болсақ, онда диалог терезесінде сыртқы мақсатты қолдана отырып осы сұрақты қойғанда көре алатын екі шешімді алатын боламыз: Əженің аты — Наташа, немеренің аты — Маша Əженің аты — Наташа, немеренің аты — Саша. Мысал. Енді write стандартты предикаты арқылы барлық қыздардың аттарын экранға шығаратын предикат жазайық. show_names:– mother(_,Name), /* Name айнымалысы қыз атымен */ write(" ", Name), nl, /* айнымалының мəнін шығарады Name на экран */ fail. /* қайта оралу нүктелер стекінде сақталған орынға шегінуді */ Осы предикатты, оның сипаттамасын PREDICATES бөліміне қосуды ұмытпай, мамалар мен əжелер туралы біздің бағдаламаға жазайық. Ішкі мақсат ретінде "Имена дочек:" хабарламасын шығаруды көрсетейік (write предикаты арқылы), nl стандартты предикат арқылы курсорды келесі жолға ауыстырайық. Үшінші мақсатасты ретінде барлық қыздардың атын шығаратын show_names предикатын жазып алайық. GOAL write("Имена дочек:"),nl, show_names. Бұл бағдарлама қалай жұмыс істейді? Ең алдымен "Имена дочек:" жол шығарылады, содан соң келесі жолға өтеміз. Бұдан кейін show_names мақсатасты орындалады. Осы мақсатастыны есептеу кезінде унификация механизмі mother предикатын сипаттайтын процедураның бірінші сөйлемінде екінші аргумент кейпінде көрсетілген айнымалыны қыздың атымен белгілейді. Name айнымалысы "Маша" мəніне ие болады. Сонымен қатар қайта оралу стекінде mother(_,Name) мақсатастының басқа шешімдерін алу үшін шегінуге болатын жерге сілтеуші барын көрсететін жұлдызшаны трассировка терезесінде көруге болады. Write предикаты арқылы "Маша" аты экранға шығарылады. Осыдан кейін fail предикаты ережені сəтсіз аяқтауды шақырады, содан соң стекке ең соңғы енгізілген нүктесіне шегіну іске асырылады. Бұл үрдіс mother(_,Name) мақсатастыға қол жеткізудің барлық əдістері біткенше дейін жалғаса береді. Диалог терезесінде барлық қыздардың аттар тізімі біздің бағдарламада көрсетілген ретпен шығарылады: Имена дочек: Маша Даша Глаша Саша Мысал. Біздің предикатты барлық қыздардың аттарын емес, тек бір ғана маманың қыздарының аттарын шығаратындай қылып өзгертейік. Бұл үшін предикатқа маманың аты кейпіндегі аргументті қосу керек. Сонымен қатар бірінші мақсатастында жасырын айнымалыны біршама жай айнымалымен ауыстыру керек жəне оны содан соң предикаттың аргумент кейпінде көрсетілген маманың атымен салыстыру керек. show_names2(Mother):– mother(M,Name), /* Name айнымалысын маманың қызының атымен белгілейді Mother */ M=Mother, /* M жəне Mother */ мамалардың аттарының сəйкестігін тексереді write(" ", Name), nl, /* Name айнымалысының мəнін экранға шығарады */ fail. /* қайта оралу нүктелер стекінде сақталған жерге шегінуді шақырады */ Бастапқы екі мақсатастының орнына mother(M,Name), M=Mother альтернативтік нұсқаны жазуға болады: mother(Mother,Name). Оның нəтижесі содай, бірақ есептеу үрдісі ерекшелеу болады. Модифицияланған предикат арқылы Дашаның қыздарының аттарын шығарайық. Бұл үшін ішкі мақсатты мынадай қылып өзгертеміз: GOAL write("Имена дочек Даши:"),nl, show_names2("Даша"). Барлық қыздардың аттарын шығаратын предикаттан осы предикаттың жұмыс істеу ерекшелігі келесіде. М айнымалысы кезекті маманың атымен белгіленгеннен кейін оның мəнінің "Даша" атымен сəйкестігін тексереді. Сəйкес болған кезде Дашаның қызының аты шығады да, шегіну орындалады. Ал егер аты "Даша" атынан өзгеше болатын болса, шегіну дəл сол мезетте орындалады. Бұл жағдайда бағдарламаны орындау қыздың атын экранға шығаруға дейін жете алмайды. fail предикаты M=Mother мақсатасты өзінен өзі сəтсіз болғандықтан керек емес болып қалады. Əйтсе де, fail стандартты предикаттың ереженің соңғы мақсатасты түрінде болуы M=Mother мақсатасты сəтті болған жағдайда шегінуді шақыру үшін керек. Бұл бағдарламаның жұмысы аяқталған кезде диалогтық терезеде нəтижені көруге болады: Имена дочек Даши: Маша Саша Енді кесу мен шегіну əдістерін қарастырайық. Бұл əдістін негізінде fail предикаттарының комбинациясын (сəтсіздікті имитациялау жəне шегінуді əдейі ұйымдастыру үшін) жəне қандай да бір шарттың орындалуы кезінде бұл процесті аяқтауға мүмкіндік беретін ｫ!ｻ (кесу немесе cut) қолдану жатыр. Кесу туралы біз үшінші дəрісте сөз қылғанбыз. Бұл əдісті мысалға негізделіп қарастырайық. жүктеу/скачать 316.11 Kb. Достарыңызбен бөлісу:
|