..,xn ∈ N korral kehtib seos f (x1,...,xn) = a) y, mis on vähim selline element, et g(x1,...,xn,y) = 0 ja iga z < y korral g(x ,...,xn,z) on määratud ja pole 0; b) pole määratud, vastasel juhul. Ehk y on esimene element, mille puhul g(x1,...,xn,y) = 0. Funktsiooni f esitatakse sel juhil operaatortermi abil selliselt: f = μy [g]. DEF: Osaliselt rekursiivsed funktsioonid on konstrueeritavad elementaarfunktsioonidest superpositsiooni-, rekursiooni- ja minimeerimisoperaatori abil. DEF: Kõikjal määratud rekursiivseid funktsioone nimetatakse täisrekursiivseteks funktsioonideks. 20 Cantori funktsioonid. Arvutatava funktsiooni ühekohalised esindajad. Cantori funktsioon (kahekohaline) seab igale naturaalarvude paarile vastavusse tema koodi: c(x,y) = 0,5(x +y)(x+y+1)+x. Leiduvad ka pöördfunktsioonid koodile vastava naturaalarvu leidmiseks. l(c(x, y)) = x; r(c(x, y)) = y c3(x,y,z) = c(x,c(y,z)) cm(x1,x2,...,xm) = c(x1,cm−1(x2,..
Hulk A on rekursiivselt loenduv, kui A või leidub totaalne arvutataf funktsioon f , nii et A range f . Kas antud hulkade omadused on rekursiivselt invariantsed: 1. Sisaldab vähemalt 3 elementi Olgu f bijektiine ja rekursiivne, kui A sisaldab vähemalt 3 elementi, siis f (A) samuti tänu bijektiivsusele 2. On tühi samuti tänu bijektiivsusele 3. On lõputu 2 Margus Martsepp, Rekursiooni- ja keerukusteooria harjutus 3.nb samuti tänu bijektiivsusele 4. On rekursiivselt loenduv (RL) A on rekursiivselt loendub hulk, ta on kas tühi (siis 3.) või leidub totaalne funktsioon f , nii et A range f . Olgu g suvaline bijektiivne rekursiivne funtsioon B g(a), B range (g f ), kus g f on totaalne arvutatav funktsioon ja annab täpselt B ele- menti. x f (x) annab A elementi, g on totaalne. g saab sisendiks ainult A elemente, seega tulemuseks ainust B elemendid.
muutuja väärtuse, mida väärtusparameeter ei tee ja muutujaparameetrite mehhanismi võimalik 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.
litsentsitüüpidest (vabavaralised (gpl vs mit ja bsd) ja mitte-vabavaralised), gpl-i põhipoindid. OSadmini kohta küsimusi ei tule. 10. Nädal Eksamiks: mis on http, https, html, css, javascript, ajax, json, xml, kuidas üldjoontes töötab klassikaline veebirakendus ja kuidas single-page app (koodinäiteid / nende detaile ei küsita). Robootika kohta ainus küsimusetüüp: kas mingit sorti ülesannet praegused robotid suudavad täita või ei. 11. Nädal Eksamiks: rekursiooni äratundmine, baasjuht ja rekursiivne juht, rekursiooni ekvivalentsus tsükliga, arusaamine funktsionaalse keele näitejuppidest loengus: mida mingi näitekood teeb / mis on rehkendamise tulemus. Mis on lambda-arvutus. Proloogi näide tuleb ära tunda (et on Prolog). Mis on andmebaasid ja mis on sql. Detailseid sql- küsimusi ei tule. Sql näidet tuleks ära tunda (et on sql keeles). 12. Nädal Eksam: lahenduvus teoreetilises ja tavamõttes, mis on lahenduvad ülesanded
kasutatavate võrguseadmete vahel Tcp (transfer control protocol) – põhiprotokoll, mis kasutab IP-d. Toimub kontroll, kas info jõudis pärale -> kindlam, aeglane Udp (user datagram protocol) – põhiprotokoll, mis kasutab IP-d. Ei kontrollita, kas info jõudis pärale -> kiirem, osad võivad kaduda Kapseldamine (mis mille sees) - saadetud informatsioon on kihtides (siht, transport, data) 10. nädal • Eksamiks: rekursiooni äratundmine, baasjuht ja rekursiivne juht, rekursiooni ekvivalentsus tsükliga, arusaamine funktsionaalse keele näitejuppidest loengus: mida mingi näitekood teeb / mis on rehkendamise tulemus. Mis on lambda-arvutus. Prologi näide tuleb ära tunda (et on Prolog). Arendusprojektide kohta küsimusi ei tule. Puhtas funktsionaalses keeles – Haskell, Hope, Miranda, FP – ei ole programmeerijal
..); Joonis 1. Rekursioon ehk iseenesessepöördumine Rekursioon: magasini kasutamisnäide On teada, et alamprogrammi rekursiivsetel väljakutsetel loodavad lokaalmuutujate pôlvkonnad paigutatakse pinudesse ja need hävitatakse tagasipöördumistel alamprogrammist. Järgnevas vaatleme pinumehhanismi lähemalt. Me teeme seda lihtsa alamprogrammi -- rekursiivse faktoriaalfunktsiooni näitel. Rekursiooni käsitlust alustame üldisemast. Rekursiivsed definitsioonid ja algoritmid Rekursiivsel defineerimisel määratletakse defineeritav objekt (suurus) iseenda "lihtsama" ("väiksemamastaabilise") eksemplari kaudu. Selline definitsioon määrab protsessi. Selleks, et protsess oleks lôplik, peab definitsioonis esinema lihtne mitterekur- siivne erijuht. Faktoriaalfunktsiooni rekursiivse definitsiooni vôime anda järgmisena: 1, kui n = 0, n! = n*(n - 1)!, kui n > 0
4) Laiuti - juur-vasak-parem 2,3,4 kõik rekursiivsed. Külastuse eesmärgiks külastatav tipp hävitada ja et üldse puu mälust likvideerida, kõik tipud vabaks lasta sellisel juhul tuleb külastada süviti strateegia järgi. Proge antakse sisse viit puu juurele. Sorditud loendi moodustamine puu põhjal. Puu läbikäik sümmeetriliselt, aga mitte rekursiivselt. Kasutatud on stacki. Puu läbikäik(3). - läbi vaadata see näide. Kaval progeja kasutab rekursiooni ikka siis, kui ta leiab, et see talle midagi annab. Mida teha siis, kui ei ole tegemist kahendpuuga, vaid tütarde arv ei ole piiratud. Viit vektorile ning see viitab omakorda tütardele. Viidad tütardele on ühes vektoris, kui üks tütar tuleb juurde, siis tuleb seda vektorit pikendada. Ei ole kõige parem lahendus. Parem lahendus. Teha tipp selliselt, et seal on viit kirjele. Tütarde puhul on viit ainult kõige vasakpoolsemale tütrele ning temast vahetult paremale asuvale õele
xml Eksam– EksameXtensible EksamMarkup EksamLanguage Eksam– EksamStruktureeritud txt-esitamise formaat kuidas Eksamüldjoontes Eksamtöötab Eksamklassikaline Eksamveebirakendus Eksam– Eksamserver ehitab html texti kuidas Eksamsingle-page Eksamapp Eksam– Eksamserver ehitab datat: json teksti, JS browseris muudab/ehitab html txt otse brauseris (koodinäiteid / nende detaile ei küsita). 9 Eksamiks: rekursiooni Eksamäratundmine, - A subroutine is said to be recursive if it calls itself, either directly or indirectly baasjuht Eksamja Eksamrekursiivne Eksamjuht, rekursiooni Eksamekvivalentsus Eksamtsükliga, arusaamine Eksamfunktsionaalse Eksamkeele Eksamnäitejuppidest Eksamloengus: mida mingi näitekood teeb / mis on rehkendamise tulemus. Mis on lambda-arvutus Eksam– Eksamlihtne ja universaalne meetod funktsioonide kirjapanekuks, pmst progekeel
ärajätmise teel. Tõene Full graph is a simple graph. Iga täisgraaf on lihtgraaf. Tõene Each weakly connected digraph is strongly connected. Iga nõrgalt sidus graaf on tugevalt sidus. Väär If there is a cycle in a graph it is impossible to find the topological order of vertices. Kui graafis esineb tsükkel, siis ei saa graafi tippe topoloogiliselt järjestada. Tõene It is possible to convert recursion to loops using stack. Rekursiooni saab magasini abil teisendada tsükliteks. Tõene Exhaustive search algorithms tend to have exponential time complexity. Ammendava otsingu algoritmid on üldjuhul eksponentsiaalse ajalise keerukusega. Tõene Smaller height of the binary search tree leads to more effective search. Mida väiksem on kahendotsimise puu kõrgus, seda efektiivsem on otsimine. Tõene It is possible to express the prefix code using code tree. Koodipuu abil saab kirjeldada prefikskoodi. Tõene
raskesti lahenduvaks (näiteks seljakoti ülesanne). Algoritmi nende osade ajaline keerukus, mis ei sõltu n-st on O(1). Iteratiivse algoritmi ajalise keerukuse hindamiseks leitakse tsüklite kordamise käigus sooritatavate põhioperatsioonide arv. Nii saame lineaarse tsükli ajalise keerukuse hinnanguks O(n) (tsüklis eeldatakse üks põhitehe). Ülesanne: Leida ajalise keerukuse hinnang lihtsale kahekordsele tsüklile, mis sisaldab ühte põhitehet. Rekursiooni sisaldava algoritmi täitmiseks kuluv aeg avaldatakse rekurentse võrrandina. Näide: Algoritm, mille kohaselt lähteülesanne mahuga n jaotatakse kaheks alam- ülesandeks (kumbki mahuga n/2), mis lahendatakse mõlemad samal meetodil. Tulemuste kokkupanekuks alamülesannete lahendustest kulub veek n operatsiooni. Võrrandiks saame f(n)=2*f(n/2)+n (f(1)=0) Def. Algoritmi keskmine ajaline keerukus A(n) konkreetse ülesande lahendamiseks kuluv keskmine operatsioonide arv. Def
kaustaInfo = [] if isdir(kaustaAsukoht): for item in listdir(kaustaAsukoht): #print(kaustaAsukoht + "\" + item) kaustaList = tagastaKaustaInfo(kaustaAsukoht + "\" + item) if len(kaustaList) != 0: kaustaInfo.append(kaustaList) else: kaustaInfo.append(item) return kaustaInfo 2. Arvamismäng Realiseeri 3. peatükis tutvustatud arvamismäng kasutades tsüklite asemel rekursiooni. Programm peaks pidama arvet arvamiste arvu üle ja lõpetama töö, kui kasutaja on juba n korda ebaõnnestunult arvanud. from random import randint def kontrolliArvamus(arv, arvamus, lubatud, kordi): if arv != arvamus: if kordi == lubatud: print("Rohkem ei saa arvata!") else: arvamus = int(input("Arva, millist tuhandest väiksemat arvu ma mõtlen: ")) kontrolliArvamus(arv, arvamus, lubatud, kordi+1) else: print("Õige!")
25. Minimeerimisoperaator. Osaliselt rekursiivsed funktsioonid.
Ütleme, et n-kohaline f.n f on saadud n+1-kohalisest funktsioonist g
minimeerimisoperaatori y abil f = y[g] abil, kui kogu määramispiirkonnas
y, kus y on min element, et g(x1,..xn,y) = 0, kusjuures iga z
hostinimi. * MX-kirje – nimeks hostinimi ja väärtuseks sellele hostinimele vastav mailiserver. DNS-i päringu ja vastuse sõnumid on samas formaadis (vt. joonist), neid eristatakse ühebitise flagi abil – päringu puhul 0 ja vastuse puhul 1. Esimesed 12 baiti on mitme väljaga päis, siis 16-bitine päring, mis jäetakse ka päringu vastusesse, vastus, info autoritatiivsete serverite kohta ja lisainfo. Flagidega eristatakse ka soovi teha päring rekursiivselt, rekursiooni võimalikkust ning autoritatiivset päringut. 20. Töökindel andmeedastus Töökindel andmeedastus on oluline transpordi-, rakendus- ja kanalikihi jaoks. On üks olulisemaid probleeme võrgunduses üldse. Töökindel kanal tagab selle, et ükski bitt ei muunduks või ei läheks kaduma ning bittide järjekord jääks samaks. Töökindel andmeedastusprotokoll (reliable data transfer protocol) peab läbi viima andmeedastuse kanalisse ja andmed kanalist vastu võtma
annaabi.ee 
