Білім беру бағдарламасы білім алушыларына арналған. Лекциялар жинағы «Техника және ақпараттандыру»
жүктеу/скачать 316.11 Kb.
|
- Бұл бет үшін навигация:
- ЛЕКЦИЯ МАЗМҰНЫ
| ЛЕКЦИЯ № 4
4. Тақырыбы: Рекурсия ЛЕКЦИЯ МАЗМҰНЫ 1. Рекурсия. 2. Рекурсияның артышылықтары мен кемшіліктері. 3. Артқы рекурсия. 4.Рекурсия негізінде цикл құрастыру. 5. Факториалдарды есептеу. ЛЕКЦИЯ МАЗМҰНЫ Негізгі тəсілі қайталанатын əрекеттерді циклмен бейнелейтін, дəстүрлі программалау тілдерінен айырмашылығы, Пролог бұл үшін қайтып іздеу процедурасын(шегіну) жəне рекурсияны пайдаланады. Шегіну (откат) программаға бағытталған бір сұрақпен көп шешім алуға болады, ал рекурсия предикатты анықтау процесінде оның өзін қолданады. Рекурсияны қарастырғанда барон Мюнхгаузенмен болған оқиға мысал ретінде беріледі.Шегіну туралы 6 шы дəрісте айтылады, ал бұнда рекурсия туралы айтылады. Рекурсия тек қана Прологта емес тағы да жай императив программалау тілінде де кездеседі. Прологқа басқа тілдерге қарағанда рекурсия негізгі программалау əдісі болып табылады. Пролог рекурсивтік мəліметтер құрылымын анықтауға көмектеседі. Осылармен жұмысқа арнап бірнеше лекция арналады. Прологты оқуды классикалық мысалдан бастайық. Мысалға білім қорында, “ата-ана” болу қатынасымен байланысқан адамдар туралы кейбір факттер бар делік. Ата-ана предикатының екі аргументі бар. Бірінші аргумент ретінде ата-ана есімі ал екінші аргумент - бала аты. Aта-ана предикатын қолдана отырып алғы буын қатынасын құрастыралық. Бір адам алғы буын болу үшін,ол оның ата-анасы болу керек не басқа буынның ата- анасы болу керек. Бұл есеп жазайық: алғы буын (алғы буын, артқы буын) ата-ана (алғы буын, артқы буын) /*алғы буын болып ата-ана табылады*/ алғы буын (алғы буын, артқы буын) ата-ана (алғы буын, адам) алғы буын( адам, артқы буын) /*алғы буын болып алғы буын ата-анасы болып табылады*/ Алғы буын қатынасы ата-ана қатынасының транзитивті үзілісі болып, ата-ана қатынасы мен транзитивтілік қасиетін қосатын ең аз қатынастар. Қатынас транзитивті деп аталады, егер (А,В) жəне (В,С) қатынастары болса, онда (А,С) да осы қатынаста болады. Бірінші сөлемде жазылғандай, кез-келген ата-ана алғы буын болып табылады. Екінші сөйлем транзитивтілік береді. Рекурсияға ұқсас математикалық индукция аналогиясымен, кез-келген рекурсия өзіне базис жəне қадамды қосу керек. Рекурсия базисі – бұл, кей бастапқы ситуация не аяқталу моменті ситуациясын анықтайтын сөйлем. Заң бойынша, жауап рекурсиясыз шығатын жай əрекет жазатын сөйлем шығады. Жоғарыдағы мысалда,алғы буын предикатын сипаттайтын, келтірілгендей, рекурсия базисі бірінші талап болып, ол бойынша адамның жақын буындары ретінде оның ата-анасы алынады. Бұл сөйлем көбіне шарт ұсынады, оның нəтижесінде не рекурсиядан, не кесу орындалатынын білдіреді. Рекурсия қадамы – бұл талап, денесіндегі мақсат түрінде белгілі предикат шақыру жатыр. Айналшықтап қалудан алшақ болу үшін, анықталатын предикат талап басындағылардан болмауы керек. Əрбір қадамда параметр өзгергенде, не рекурсия базисі не рекурсиядан шығу шарты іске қосылуы керек, талап орналасқан. Рекурсия қадамын іске асыратын талап жалпы түрі: [<Міндет>] [<Рекурсиядан шығу шарты>] [<Мақсат>] [<Анықталатцын предикат аты>] [<Мақсат>] Кейбір жағдайда рекурсия базисін реализациялайтын сөйлем жəне рекурсия қадамын сипаттайтын сөйлем бірнеше болуы мүмкін. Талап бойынша бұл күрделі жағдайларда болады, мысалы, рекурсия қадамыреализация процесінің орындалуы бір шарттың орындалу не орындалмауына байланысты. Осындай есептер келесі, мəліметтердің рекурсивті құрылымын сөз еткенде,лекцияларда өтеміз. Ал бұл лекцияда жай рекурсиялармен, бір базисі жəне бір қадамнан тұратын, танысамыз. Мысал: Натуралдық сан бойынша оның факториалын есептейтін предикат шығарайық. Бұл есепті көптеген программалау тілдерінде шешуге, жəне рекурсивті математикалық сипаттамаға ие: 1!=1/*бір факториалы бірге тең*/ N!=(N-1)*N/*бір сан факториалын есептеу үшін осыдан бірге кем сан факториалын есептеп бастапқы санға көбейтеміз*/ Эквивалентті математикалық анықтамалы предикатты,предикат реализациясын жазып көрелік: Fact(1,1)/* бір факториалы бірге тең*/ Fact(N,F):-\ N1=N-1, Fact(N1,F),/* F1 бастапқы саннан бірге кем санның факториалы тең*/ /*бастапқы сан факториалы тең болады F1 сол санға туындысы*/ Өкінішке орай, жоғарыдағы предикатымен есептеу кезінде, туындылы __________натурал санның факториалын есептеу жағдайында стектер толып кетеді. Бұлай болу себебін қарастырайық. Қарастырсақ, мысалға, егер үштің факториалын табатын болсақ, не болады. Осы сұрақты келесідей түрде жазуға болады: Fact(3,F). Пролог – жүйе бірінші сөйлем басындағы (Fact(3,F)) мақсатты унифицирлеуге талпынады. Бұл келмейді, өйткені үш бірге тең емес. Екінші сөйлем (Fact(N,F)) басында мақсат унификациялағанда, N айнымалысы үш санымен анықталады, ал Х айнымалысы F айнымалысымен байланысады. Осыдан кейін, дененің солдан оңға қарай орналасқан талаптарын, мақсатты орындау талпынысы болады. Бірінші N1 айнымалысы, N айнымалысынан, бірге кем сан мəнін қабылдап, екі мəніне тең болады. Келесі (Fact(N1,F1)) мақсат іске қосылуы, N1 айнымалысының мəнімен, екіге тең, факториал есептейтін, рекурсивті предикатты шақыруға əкеледі. Бірінші аргумент үшке тең болғандай, бірінші сөйлемнің басындағы унификацияда жүрмейді. Екінші талап басымен қойғанда, жақсы жүреді. Əрі қарай, бəрі N айнымалысы сияқты, үшке тең болды. N1 айнымалысының жаңа мəні, бірі кем екіге, яғни бірге тең. Пролог қайтадан (Fact(N1,F1)) мақсатын есептеуге тырысады. Бұл жерде (Fact(1,F1)) мақсатымен бірінші сөйлемнің басын салыстыру жүріп, онда F1 айнымалысы бір санымен анықталады. Пролог – жүйе əйтеуір екінші талаптың екінші мақсатын есептейді, енді ол (F=F1*N) үшінші мақсатын есептеуге кіріседі. N айнымалысы екіге тең, F1 айнымалысы бірге, екі мен бір туындысы екіге тең, сондықтан F айнымалысы екімен анықталады. Рекурсияның кері жүрісі басталады. Екінің факториялы есептеліп болғаннан кейін, Пролог жүйе үштің факториалын есептеуге дайын. Бұл үшін екінің факториалын үшке көбейту керек. F айнымалысы 6 санымен анықталады. Біз үштің факториалы туралы шешім алдық. Бірақтан есептеу бұл жерден бітпейді. Пролог жүйе Fact(1,F1) мақсаты бірінші сөйлем басымен де жəне (fact(N,F)) талабының басымен салыстыруға келмейтінін анықтайды. N айнымалысы бірмен анықталады, ал F1 айнымалысы F айнымалысымен байланысады. Осыдан кейін, N1 айнымалысы бірге кем сан мəнін, N айнымалысының мəніне қарағанда, яғни нольге тең. Пролог-жүйе fact(0,F1) мақсатын есептеуге тырысады. (fact(1,1)) бірінші сөйлемінің басын осы мақсатпен салыстыруға болмайды, өйткені ноль бірге тең емес. Бірақта екінші сөйлем басындағы (fact(N,F)) мақсатыжақсы унифицирленеді. N айнымалысы минус бірге тең болады. Осыдан кейін fact(-1,F1).... сосын fact(-2,F1), fact(-3,F1), fact(-4,F1), fact(-5,F1)... . мақсатын есептеу талпыныс жасайды. Бұл процесс жедел жадыдағы стекке бөлінген бөлігі біткенше жүреді. Осыдан кейін программа тоқтап, стек толған жайлы мəлімет шығады. Бұл қалай болды? Біз нені дұрыс істемедік? Мұның мəнісі бастапқы факториал анықталғанда, ол тек натурал сандардың оңдарымен ғана жұмыс істемейді. Ал бізде есеп теріс сандарды есептеуге шығып, ал ол формула бойынша қарастырылмаған. Қалай қатені жөндеуге болады? Бізде жөндеудің екі варианты қарастырылған. Талаптар қолданылатын сандардың бірден үлкендігін тексеруге болады. Бір үшін, бірдің факториалы бір екендігі, факт болып қалмақ. Бұл вариант былай бейнеленеді: fact(1,1). /* бірдің факториалы бірге тең */ fact(N,F):- N>1, /* санның бірден үлкендігін қарастырамыз */ N1=N-1, fact(N1,F1), /* F1 бастапқы саннан бірге кем сан факториалына тең */ F=F1*N. /* бастапқы сан факториалы тең болады F1 дің сол санға туындысы */ Бұл жағдайда fact(-1,F1) мақсатының қайталама келісуі жүрсе де, N айнымалысы бірмен анықталса да, F айнымалысы F1 айнымалысымен байланысса да, (N>1) талабының бірінші мақсаты жалған болады. Осында прцесс үзіледі. Теріс сандардың факториалын есептеуге тырысқанмен, процедура бізге қолайлы күйде жұмыс атқарады. Проблема шешудің екінші варианты – бірінші сөйлемге кесу (отсечение) процедурасын қосу. Еске сала кетсек, кесуді шақырсақ, ол процедураның сөйлемдерінен төмен жатқандар қарастырылмайды. Соған байланысты, кей мақсаттар бірінші сөйлем басымен келісілген болса, кесу іске қосылады да, екінші сөйлем басы мақсатты унификациялауға тырыспайды. Бұл жағдайда процедура келесідей болады: fact(1,1):-!. /* рекурсияны тоқтату шарты */ fact(N,F):- N1=N-1, fact(N1,F1), /* F1 бастапқы саннан бірге кем сан факториалына тең */ F=F1*N. /* бастапқы сан факториалы тең болады F1 дің сол санға туындысы */ Əрине бір жағынан рекурсия əдісі итерация əдісінен,императивті программалау тілдерінде көп қолданылатын, жақсы.рекурсивтік алгоритмдер иьтерациялықтарға қарағанда əлде қайда жеңіл. Кейбір алгоритмдерді рекурсивті түрде жазу өте ыңғайлы. Бірақ рекурсияның үлкен кемшідігі бар, ол жалпы айтқанда, жұмыс үшін стектегі орын жетіспейді. əрбір предикаттың рекурсивті шақырылуында арнаулы стектік фреймдерде керекті уақытаралық айнымалылар сақталынады. MS DOS операциялық жүйесіндегі стектердің максималды көлемі 64 Мб қана. Бұл тек 3 не 4 мың стектік фреймдерді ғана сыйдыруға болады. Өте үлкен мəліметтер стекке сыймауы мүмкін. Рекурсияның тағы бір түрі императивті программалау тіліндегі итерациялар сияқты жедел жадыда аз орын алады. Бұны артқы не оң ренкурсия деп атайды. Анықталған предикатты рекурсувті шақыру кезінде ол рекурсивті талаптың денесіндегі соңғы мақсаты болуы керек жəне рекурсивті шақыру моментінде қайта оралу нүктелері болмауы тиіс. Бұл дегеніміз анықталатын предикаттың рекурсивті шақыруынан сол жағында жатқан мақсаттардың тексерілмеген варианттары алмауы керек жəне працедурада рекурсивті талаптан төмен жатқан сөйлем болмауы тиіс. Осы біздің курсымызда қарастырылатын Турбо Пролог артқы рекурсияны танып, онымен байланысты қосымша шығындарды жояды.. Бұл процес артқы рекурсияның оптимизациясы не соңғы шақыру оптимизациясы деп аталады. Мысал. Артқұы рекурсияны пайдалана отырып факториалды есептеп көрейік. Бізге қосымша екі параметр, уақыт аралық шешімдерді сақтау үшін, керек. Үшінші параметр факториал есептелініп жатқан натурал сандар сақтау үшін, төртінші параметр – үшінші параметрдегі санның факториалы сақталынады. Факториалды есептеуді бастау факториал есептелінетін парметр санына тең кезде басталады. Үшінші жəне төртінші аргумент бірге тең. Екінші аргументке рекурсивті есептеулер аяқталысымен бірінші параметрдегі сан факториалы орналасады. Əр бір қадамда үшінші аргументтерді бірге көбейтіп отырамыз, ал екінші аргументті үшінші аргументтің жаңа мəнімен көбейтеміз. Рекурсияны үшінші аргумент бірінші аргументке тең болғанда тоқтатамыз, бұл кезде төртінші аргументте ізделінді факториал, екінші аргументке жауап ретінде орналастыруға болатын, жиналады. fact2(N,F,N,F):-!. /* рекурсияны үшінші аргумент бірінші аргументке тең болғанда тоқтатамыз*/ fact2(N,F,N1,F1):- N2=N1+1, /* N2 - N1-ден кекейінгі натурал сан */ F2=F1*N2, /* F2 - N2 факториалы */ fact2(N,F,N2,F2). /*жаңа N2 натурал санымен жəне оған сəйкес F2 факториалының рекурсивті шақыру / Рекурсияны тоқтату үшін, рекурсия базисінде кесуді қолданамыз немесе екінші сөйлемнің басына N1 мен N қоссақ. Егер бізге төрт аргументті предикат ыңғайсыз болса, онда біз қосымша екі аргументті предикат, ол бастапқы предикатты жүргізеді, енгізуге болады: factM(N,F):- fact2(N,F,1,1). /*берілген бастапқы мəндері бар предикатты шақырамыз */ Мысал. Өткен лекцияда біз императивті бұтақтану аналогын кесу қолданып шешкенбіз. Қазір рекурсия мен кесу қолдана отырып циклды жүзеге асырамыз. Ол цикл былай болуы мүмкін while <шарт> do P. Бұл «орын бар болғанша <шарт> орындау Р» мəтіндік сипаттамаға ие. Прологта осындай құрылымды келесідей етуге болады: w:- <Шарт>,p,w. w:-!. Бірақта модификациаланған процедура дəл осылай жұмыс істемейді. Егерде адамдар атын, біреуі алғы буын болып табылатын, аргумент ретінде көрсетіп, алғы буын2 предикатын шақырсақ, онда ол бірінші адамның екінші адамға алғы буын болады. Ал қалған əрекеттерде барлығы ойдағыдай болмайды. Бастапқы алғы буын предикаты сияқты келесі предикатта жауап шығарғаннан кейін, ол осында айналшықтап қалып, сосын стек толғаны туралы мəлімет шығарады. Оригиналды алғы буын предикатымен бұлай болмайды, өйткені бірінші міндеттің екінші талабында ата-ана міндетін шақыру тұрады. Осы міндеттің орындалу нəтижесінде Адам айнымалысы басқа бір адамның атын мəн ретінде алады. Сондықтан алғы буын екінші міндетін шақыру уақытында Адам айнымалысы байланысты болады. Ал предикаттың жаңа версиясында екінші талап алғы буын2 міндетін шақырудан бастайды, ал Адам айнымалысы онда бос. Процедураның бірінші сөйлемі арқылы бос айнымалылардың түсінудің барлық альтернативалары біткеннен кейін, міндет екінші сөйлемнің басымен унифицирленеді. Бос Адам айнымалысы Алғы буын айнымалысымен байланысып, мақсатты Артқы буын айнымалысы талап басы Артқы буын айнымалысымен. Талаптың бірінші мақсатын орындау қайталауында бəрі қайталанады. Стектердегі бос орын қалмайынша бұл процесс жүре береді. Талаптың денесі ізделінді предикаттың рекурсивті шақыруынан басталса,онда бұл рекурсияның түрін солжақтық рекурсия деп аталады. Солжақтық рекурсиямен əрдайым қиындықтар туады. Сондықтан солжақтық рекурсияны қолданудан барынша алшақ болып, барынша оңжақтық рекурсияны не артқы рекурсияны қолданған жөн. Өзіндік жұмыстар 1. бүтін санның теріс дəрежесін есептейтін, предикат шығарыңыз. 2. N натурал санын 1-ден N-ге дейінгі суммасы есептеу предикатын шығарыңыз. 3. N натурал санымен N-ге дейінгі тақ сандар суммасын есептейтін предикат шығарыңыз. 4. екі натурал санды да бөлетін ең үлкен санды есептейтін предикат шығару. 5. екі натурал санды да бөлетін ең кіші санды есептейтін предикат шығару 6. ( repeat <оператор> until <шарт> сияқты) шартты циклды рекурсия мен қиып алуды отсечение қолдану арқылы есептеу. 7. (for i:=1 to N do <оператор> типті) счетчикті циклды рекурсия мен қиып алуды отсечение қолдану арқылы есептеу. 8. (for i:=1 downto N do <оператор> типті) счетчикті циклды рекурсия мен қиып алуды қима қолдану арқылы есептеу. жүктеу/скачать 316.11 Kb. Достарыңызбен бөлісу:
|