.. -------P(...); 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:
Millised neljast omadusest: on rekursiivne on rekursiivselt loenduv omab rekursiivst täiendit omab rekursiivselt loenduvat täiendit on antud hulkade põhjal 1. A = {x | x on paarisarv} 2. B = {x | x on väiksem kui 100} 3. C = {x | x on algarv} 4. D = {x | Wx on tühi} 5. E = {x | Wx sisaldab vähemalt 3 elementi} Lahendus Alusteooria Hulk on rekursiivselt invariantne, kui iga bijektiivse ja rekursiivse junktsiooni f korral, kui hulgal A on omadus P, siis ka hulgal f (a) on omadus P. 1 , kui x A Hulk A on rekursiivne, kui tal leidub karakteristlik funktsioon Xa x . 0 , kui x A Hulk A on rekursiivselt loenduv, kui A või leidub totaalne arvutataf funktsioon f , nii et A range f .
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
koos indeksitega.
Programmi kood C keeles
#include
muutujaparameetrile alamprogrammis omistatud uus väärtus muudab ka põhiprogrammi 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.
ka (*)-arvutatavad. Need funktsioonid, millega me tegeleme, on kõik osaliselt rekursiivsed funktsioonid ja neil on argumenti. Seetõttu järgmise teoreemiga: Teoreem. ([1], 24) Iga osaliselt rekursiivne funktsioon on arvutatav Turingi mõttes. See, et funktsioon on arvutatav Turingi mõttes, tähendabki antud juhul, et see funktsioon on (*)-arvutatav. Tõestuse idee. See teoreem tõestatakse induktsiooniga osaliselt rekursiivse funktsiooni definitsiooni järgi, s.t. näidatakse, et 1) iga algfunktsioon on arvutatav, 2) kui defineerime skeemide abil uusi funktsioone, siis arvutatavus kandub edasi. Antud teoreemi sees on vaja tõestada järgmised lemmad: Lemma 1. ([1], 25) Algfunktsioonid , ja on (*)-arvutatavad. Lemma 2. ([1], 26) Olgu funktsioonid ja (*)-arvutatavad ning , siis on ka funktsioon (*)-arvutatav. Lemma 3
Klassidiagramm, nool on valge otsaga, valge pool läheb kõrgema klassi poole. Cons - Ei tööta hästi, kui on palju ühist (struktuuri või käitumist) organisatsiooni/osade tüüpide vahel. Kannavad olemasolevaid organisatsioonilisi kategooriaid (tarkvara) disaini - kui otsustatakse lisada regioonid osakondade ja divisjonide vahele, on vaja muuta mudelit. b) Organisatsiooni hierarhia - probleemide lahenduseks on supertüübile Organisatsioon vastava klassi loomine koos rekursiivse Organisatsiooni Hierarhia seosega. Kui keegi saab aru dafuk did this mean, siis lahe, öelge mulle ka pls, sest see ja järgmine diagramm on imo täiesti erinevad asjad...? Organisatsiooni hierarhia on parem, kui struktuurid käituvad üpris sarnaselt (atribuudid ja seosed kattuvad). TTÜ näites instituudid teevad tegelt suht samu asju, lihtsalt eriala erineb. Uute organisatsiooni tüüpide lisamine on ka lihtsam
nullid, siis saame lõpmatu siirdega (IIR) voi pmtm() aknad aknafunktsioon. See meetod samuti nagu Burg'i MatLab'is var(). Jaotusseadus(vt. 1). Kõige spekter. rekursiivse (ainult tagasisidega) susteemi: 15. Mudeli valik ja selle hindamine, järgu valiku meetod annab alati stabiilse mudeli, kuid on halb levinumad on ühtlane-, normaalne(Gaussi)- ja 11. Mitteparameetrilised meetodid: Blackman- kriteeriumid lühikeste andmeridade korral
● Nüüd võetakse valimisse ka järgmine vaatlus ning leitakse parameetrite hinnangud 1 võrra suurema valimi põhjal. ● Leitakse järgmise vaatluse jääkliige. ● Niimoodi jätkatakse, kuni kõik vaatlused on kaasa haaratud. ● Saab kasutada aegridade korral ja mingi tunnuse abil järjestatud ristandmete korral. ● Tulemusi saab uurida visuaalselt. ● Testimiseks on olemas sobivad statistikud CUSUM test Gretlis mudeli aknas Tests>CUSUM test Rekursiivse hindamise alusel on välja töötatud CUSUM test. Test põhineb rekursiivse hindamise jääkliikmete ut normaliseeritud kumulatiivsel summal. se - mudeli standardviga (terve valimi põhjal) r - mudeli parameetrite arv n - valimi maht Kui struktuurseid muutusi pole, siis summad Wp alluvad normaaljaotusele keskväärtusega 0: Wp ~ N(0, p-r) Testimiseks Harvey-Collier statistik. H0 : struktuursed muutused puuduvad
nii palju kordi, kui vajatakse. Suurem osa selliseid algoritme põhineb Fourier' meetoditel, mis nõuab ulatuslikku matemaatilise aparaadi kasutamist ja kuulub andmetöötluse valdkonda. 16 Eristatakse kahte klassi digitaalfiltreid [41]: rekursiivsed ja mitterekursiivsed. Mitterekursiivse filtri iga väljastatav väärtus sõltub jooksvast ja eelnevatest sisendväärtustest. Rekursiivse filtri väljund põhineb eelnevatel väljundväärtustel ja jooksval sisendväärtusel. Tähistades sisendväärtused (mõõtetulemused) xk ja filtri väljastatavad väärtused yk, kus k on iteratsiooni järjekorra number, saab mitterekursiivset filtrit kirjeldada valemiga Mitterekursiivse filtri üheks sageli kasutatavaks variandiks on kaalumata libiseva keskmise filter (ingl unweighted moving average filter), mida sageli nimetatakse ka lihtsalt libiseva keskmise filtriks
- nideks. Operaatorterm: · funktsioonisümbol · avaldis kujul E(t1,t2,..tn), kus E on n-kohaline operaator ja ti on operaatortermid · muid op-terme pole Kui g on n-kohaline arvutatav f.-n, siis f = y[g] on n-1-kohaline osaliselt rekursiivne f.-n. Tõestus: eksisteerib registermasina programm Seega on osaliselt rekursiivsed f.-nid arvutatavad. 26. Turingi mõttes arvutatavate funktsioonide rekursiivsus. Iga registermasina programm realiseerib rekursiivse f.-ni. x programmi kood P y registrite sisu P täitmisel Kuna instruktsioonid saame Cantori numbritega kodeerida .. proge kood aga on instruktsioonide jada (lõplik korteezh naturaalarvudest), leidub ka sellele Cantori number. Iga registermasinal realiseeritav f.-n on osaliselt rekursiivne f.-n. Osaliselt rekursiivsete funktsioonide hulk langeb kokku Turingi mõttes arvutatavate funktsioonide hulgaga see tähendab, et ainult osaliselt rekursiivsed f.-nid on raalil arvutatavad
Kui see vastust ei tea, siis kohalik server küsib vastust juurserveri käest, mis tagastab nimeserverite IP aadressid, kes on vastutavad selle teise hosti IP eest. Peale seda valib lokaalne server välja ühe nimeserveri aadressi ja küsib sealt, mille peale nimeserver tagastab autoratiivse serveri IP, kes teab selle hosti aadressi ja lõpuks küsib lokaalne server autoratiivse serveri käest ja saab vastuse IP näol ning see edastatakse hostile, kes pöördus lokaalse DNS serveri poole. Rekursiivse päringu puhul toimub vastuse saamine järgmiselt: host loob päringu lokaalsesse DNS serverisse->lokaalne server edastab päringu juurserverisse->juurserver nimeserverisse->nimeserver autoratiivsesse->ja siis liigub vastus sama teed mööda tagasi päringu koostajani. Vastuste kiiremaks kättesaamiseks ja serverite koormuste vähendamiseks kasutatakse cahce'mist. Cache'mise puhul jätab lihtsalt (ükskõik milline) DNS server vastused meelde ja kustutab need kui TTL (time to live) aegub
Kui see vastust ei tea, siis kohalik server küsib vastust juurserveri käest, mis tagastab nimeserverite IP aadressid, kes on vastutavad selle teise hosti IP eest. Peale seda valib lokaalne server välja ühe nimeserveri aadressi ja küsib sealt, mille peale nimeserver tagastab autoratiivse serveri IP, kes teab selle hosti aadressi ja lõpuks küsib lokaalne server autoratiivse serveri käest ja saab vastuse IP näol ning see edastatakse hostile, kes pöördus lokaalse DNS serveri poole. Rekursiivse päringu puhul toimub vastuse saamine järgmiselt: host loob päringu lokaalsesse DNS serverisse->lokaalne server edastab päringu juurserverisse->juurserver nimeserverisse->nimeserver autoratiivsesse->ja siis liigub vastus sama teed mööda tagasi päringu koostajani. Vastuste kiiremaks kättesaamiseks ja serverite koormuste vähendamiseks kasutatakse cahce'mist. Cache'mise puhul jätab lihtsalt (ükskõik milline) DNS server vastused meelde ja kustutab need kui TTL (time to live) aegub
summale: 01100001 (8-bitine summa; 9-bitisest summast jäta 8 bitti alles) +00000001 (ülekanne väikseimasse järku) 01100010 Kui kõik baidid on kokku liidetud, siis inverteeritakse vastus. Kui meil oli kogu paketi sisu ainult 3 baiti, siis praegusel juhul checksum tuleks viimase summa inversioon ehk 01100010 -> 10011101. Vastuvõtja poolel kontrollitakse, kas pakett on vigane nii, et liidetakse kõik baidid (jällegi rekursiivse ülekandega) ja checksum. Vastuses ei tohi olla ühtki 0-i. 11000111 (1. bait) +00010101 (2. bait) +10000101 (3. bait) +10011101 (checksum) 11111111 (kui siin on mõni 0, siis pakett jõudis vigasena kohale) Kanalikihis on mitmeid meetodeid kasutusel vigade avastamiseks. 1. Paarsuskontroll (Parity Check) - loetakse üle, kas kaadris (kanalikihi paketis) on paaris- või paaritu arv bitte ning vastavalt sellele seatakse paarsusbitt (Parity Bit) üheks või nulliks
Igal ISP-l (internetiteenuse pakkujal) on oma nimeserver. Päringu tegemisel küsitaksegi kõigepealt kohaliku nimeserveri käest. Kui see vastust ei tea, edastatakse päring juurserverile, mis omakorda küsib autoritatiivse nimeserveri käest (teab autoritatiivse nimeserveri aadressi) ja siis edastab selle kohalikule nimeserverile. Autoritatiivne nimeserver säilitab hosti jaoks hostinime ja IP-aadressi ning käitub enamasti ka kohaliku nimeserverina. Rekursiivse päringu korral küsib nimeserver juurserveri käest, see omakorda teise nimeserveri käest ning info kättesaamisel liigub see täpselt sama teed pidi tagasi. Iteratiivse päringu korral edastab juurserver nimeserverile vaid serveri, kes antud aadressi teab. Selline päring koormab juurserverit vähem. 11 Serverite koormuse vähendamiseks ja päringute kiiremaks tegemiseks kasutatakse ka
DNS serveri käest ja kui see vastust ei tea, siis kohalik server küsib vastust juurserveri käest, mis tagastab nimeserverite IP aadressid. Peale seda valib lokaalne server välja ühe nimeserveri aadressi ja küsib sealt, mille peale nimeserver tagastab autoratiivse serveri IP, kes teab selle hosti aadressi. Lõpuks küsib lokaalne server autoratiivse serveri käest ja saab vastuseks IP, mis edastatakse hostile, kes pöördus lokaalse DNS serveri poole. Rekursiivse päringu puhul toimub vastuse saamine nii, et host loob päringu lokaalsesse DNS serverisse ja lokaalne server edastab päringu juurserverisse ning juurserver nimeserverisse ja see omakorda autoratiivsesse serverisse ja siis liigub vastus sama teed mööda tagasi päringu sooritajani. Vastuste kiiremaks kättesaamiseks ja serverite koormuste vähendamiseks kasutatakse vahemälude süsteemi. Vahemälu puhul jätab DNS server vastused meelde ja kustutab need kui TTL aegub
F(2) = 1esimeste jäneste muretu lapsepõlv F(3) = 2esimene paar järeltulijaid F(4) = 3teine paar järeltulijaid F(5) = 5esimesed lapselapsed ... •Üldkujul F(n) = F(n-1) + F(n-2): –Kõik senised paarid on elus F(n-1) –Iga vähemalt kahe aasta vanuse paari kohta tuleb uus paar F(n-2) ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 8 Näide jätkub •Näide int fib(int n) { if( n <= 2) return 1 else return fib(n-1) + fib(n-2) } •Tegemist on rekursiivse algoritmiga –lõpetamistingimuse täitmisel algoritm peatub –muul juhul kutsub funktsioon välja iseenda muudetud argumendiga ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 9 Näide ikka jätkub •Iga fib funktsiooni väljakutse on kas 1 või 2 rida –n <= 2 korral üks rida –n = 3 korral 2 rida + 1 rida kummagi uue väljakutse kohta: 4 –n = 4 korral 2 + 4 + 1 = 7 –n = 5 korral 2 + 7 + 4 = 13 •Keerukuse rekurrentne võrrand time(n) = 2 + time(n-1) + time(n-2)
Sellisel juhul saame endale kirjeldada CTE, milles sisalduvad vaid Tallinna lapsed ning kasutada seda oma päringus nagu iga teist tabelit või vaadet: WITH TallinnaLapsed AS ( SELECT * FROM dbo.Laps_tbl WHERE SynniLinn = 1 ) SELECT * FROM TallinnaLapsed ORDER BY Nimi CTE tõeline jõud tuleb aga ilmsiks kui läbi rekursiivsete päringute. Rekursiivsed SQL päringud olid ka põhiline idee CTE loomise taga. Rekursiivse päringu loomiseks tuleb CTE tekitada UNION päringu abil, milles on kaks liiget ankur (alguspunkt päringule) ning rekursiivne liig (iseendale viitav päring). Et seda katsetada teeme mõned täiendused oma Laste tabelisse ning lisame sinna uue välja Rühmajuht ning määrame igale lapsele sobiva juhi: -- Lisame tabelisse uue välja ALTER TABLE dbo.Laps_tbl ADD Ryhmajuht INT NULL REFERENCES dbo.Laps_tbl (LapsID) GO
annaabi.ee 
