REKURSIOON - Recursion Otsene ja kaudne rekursioon ehk iseenesessepöördumine Otsene: Kaudne: ->>PROCEDURE P(...); PROCEDURE P(...);FORWARD; 2 . ... -- P(...); -->PROCEDURE Q(...); 1 ... ... END; -- P(...); Q ... 2 ...
Variant R-26 Rekursioon Koostada algoritm ja sellele vastav programm (C- või Java-keeles), mille abil: 1. klaviatuurilt sisestatakse reaalarvulised X (X<1) ja (0<<1); 2. rekursiivse funktsiooni abil moodustatakse reaalarvuline massiiv A elementidega A0 = 1, A1 = X2/2!, A2 = X4/4!, . . . kuni massiivi A elementide arv L kas vastab tingimusele AL AL 1 või (kui see tingimus ei ole rahuldatud) L = 15; 3. faili F väljastatakse massiivi A elementide arv L ning elemendid
kasutada ka väljundparameetrite realiseerimiseks. 5. rekursiivne funktsioon Rekursiivne funktsioon on ennastkopeeriv funktsioon. Funktsiooni nimetatakse rekursiivseks, kui selles kasutatakse ühe (või ka mitme) sammuna sama funktsiooni ennast, et lahendada funktsioonile antud probleemi kergem variant. Rekursiivse funktsiooni puhul on alati defineeritud baasjuhtum, mille korral rekursiooni edasikaevumine lihtsama variandi poole peatub. Kui baasjuhtumit ei defineerita, siis on rekursioon lõputu ja 99% juhtudest toob kaasa programmi kokkujooksmise.
1. Sissejuhatus: 1.1. Mis on loogiline programmeerimine? l Programmeerimise paradigma l loogiline (LP) l funktsionaalne (FP) l jt Fookus: MIDA ARVUTADA l LP ja FP on deklaratiivsed programmeerimisstiilid; l LP põhineb loogika printsiipidel ja kasutab automaattõestamise protseduure (resolutsioon, unifitseerimine); l LP keel on Prolog, kuid LP ≠ Prolog; 1.1. Mis on loogiline programmeerimine? (2) l LP sobib tehisintellekti rakenduste programmeerimiseks: l loomuliku keele analüüs ( DCG grammatikareeglid) l ekspertsüsteemid (otsingu- ja järeldusreeglid) l kujundituvastus (tuvastusreeglid) l kitsendustega planeerimine (logistika, marsruudi otsimine) l rekursiivsete funktsioonide püsipunkti arvutus l jne l LP ei sobi: l Kiired numbrilised arvutused (n. maatriksarvutused, võrrandid) l OOP (kuigi on toetatud mõnes prologis) l kasu...
Ainus efekt, mis funktsiooni rakendamine argumentidele annab, on resultaadi leidmine. Kombineeritud funktsionaalsed keeled – MI, Lisp, Scheme – kombineerivad puhaste funktsionaalsete keelte mehhanisme imperatiivsete mehhanismidega. Rekursiooni äratundmine – funktsioon kutsub iseennast välja. On defineeritav iseenda kaudu (ei anna mingit infot). Rekursiooni baasjuht - rekursiooni enam välja ei kutsuta (tingimus, millal rekursioon lõpeb) Rekursiivne juht - rekursioon kutsutakse välja, iga välja kutse on lihtsam (kas asi läheb lihtsamaks, ise vaja välja mõelda) Rekursiooni ekvivalentsus tsükliga - kõike mida saab progeda while ja for tsükli abil, saab progeda rekursiooniga ja vastupidi lambda-arvutus - Lambda-arvutuse keel on Alonzo Churchi poolt 1930. aastatel leiutatud lihtne ja universaalne meetod funktsioonide kirjapanekuks. Churchi tees: mida
Iga registermasina programm on realiseeritav Turingi masinal: Esitame registermasina kõigi nullist erinevate registrite sisu Turingi masina lindil Turingi masin ja registermasin on arvutatavuse mõttes ekvivalentsed. Church-Turingi tees: iga efektiivselt arvutatav funktsioon on realiseeritav Turingi masinal 24. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. Arvtatavuseks piisab kolmest operaatorist: · superpositsioon (f.-nide järjest rakendamine) · rekursioon (f.-ni rakendamine iseenda sees omaenese eelmistele väärtustele) · minimeerimine arvutamine teatud tingimuse täitumiseni Superpositsioon: n-kohaline f.-n f on saadud m kohalisest f.-nist g ja n kohalistest f.-nidest hi (i = 1,..,m) superpositsioonioperaatori rakendamisel, kui f = Sm+1(g;h1,..,hm) = g(h1,..,hm) Rekursioon: n+1-kohaline f-n f on saadud n-kohalisest f.-nist g ning n+2-kohalisest f.-nist h
Eelda me et f(x1)= f(x2), s iis 3*x1-5= 3*x2-5, mill es t järeldub, et x1= x2. S eega f on inj ektiivne. Ees poolnäit as ime, et s ee funkts ioon on s ürj ektiivne, kokku s aame bij ektiivs us e. Ü l: N äidata, et funkts ioon f:R-> R f(x)= x*x ei ole bij ektiivne. Ü l2: Leida ees pooltoodud funkts ioonile f(x)= 3x-5 pöördfunkts ioon S t. f -1( y ) = x . S elleks tähis tame es ialgs es s eos es f(x)= y j a lahenda me s elle x s uhtes ..................................... 8. Rekursioon R ekurentne relats ioon järj es tus ele a1 , a2 ,..., an on s elline, mis defineerib liikme an eel mis t e liik met e a1 , a2 ,..., an-1 kaudu. V ale mit mis liiget an eelnevatega s eob nimeta taks e genereeri mis e reegliks (generating rule) Teatud liik me tele( es imes t ele tavalis e lt) väärtus te omis tamis t nime tat aks e inits ialis e erimis eks (algväärtus ta mi s eks ). N 1: F ibonacci j ärj es tus 1,1,2,3,5,.... A lgväärtus ta me 2 es imes t liiget a0 = a1 =1
Eelda me et f(x1)= f(x2), s iis 3*x1-5= 3*x2-5, mill es t järeldub, et x1= x2. S eega f on inj ektiivne. Ees poolnäit as ime, et s ee funkts ioon on s ürj ektiivne, kokku s aame bij ektiivs us e. Ü l: N äidata, et funkts ioon f:R-> R f(x)= x*x ei ole bij ektiivne. Ü l2: Leida ees pooltoodud funkts ioonile f(x)= 3x-5 pöördfunkts ioon S t. f -1( y ) = x . S elleks tähis tame es ialgs es s eos es f(x)= y j a lahenda me s elle x s uhtes ..................................... 8. Rekursioon R ekurentne relats ioon järj es tus ele a1 , a2 ,..., an on s elline, mis defineerib liikme an eel mis t e liik met e a1 , a2 ,..., an-1 kaudu. V ale mit mis liiget an eelnevatega s eob nimeta taks e genereeri mis e reegliks (generating rule) Teatud liik me tele( es imes t ele tavalis e lt) väärtus te omis tamis t nime tat aks e inits ialis e erimis eks (algväärtus ta mi s eks ). N 1: F ibonacci j ärj es tus 1,1,2,3,5,.... A lgväärtus ta me 2 es imes t liiget a0 = a1 =1
Konvergentsiteooria = lähenemisteooria): keelkonnad on tekkinud eri keelte lähenemise teel, ilma et oleks kunagi ühist eellast olnud. Divergentsiteooria- keeled on tekkinud millestki lahknemisel, nt keelepuu SAE (Standard Average European-) hierarhia keeletüpoloogias-tänapäeva keeletüpoloogias väga päevakorraline teema. Nt ühildumishierarhia. semantiline kaart -iseloomulik tänapäeva tüpoloogiale, koondab grammatilisi sarnasusi. Rekursiivsus - keelevõime kitsas tähenduses ehk rekursioon: keel on lõplik hulk vahendeid, millest saab luua lõputu hulga lauseid, alati saab midagi lisada. Transformatsioonireeglid- tuumlause esituse või transformatsioonide kaudu saadakse muid lauseid. - Siirdetransformatsioon . Rektor laulis jõulupeol. Jõulupeol rektor laulis - Asendustranformatsioon Ta laulis jõulupeol. Ta laulis seal. Rektor laulis seal. - Lisamistransformatsioon Miks rektor laulis? Rektor ei laulnud.