Operaatori abil (*)-arvutatavatest funktsioonidest saadud funktsioonide (*)-arvutatavus Tallinn 2014 Sissejuhatus Käesolevas referaadis keskendume operaatori abil saadud funktsioonide (*)-arvutatavusele, need funktsioonid on osaliselt rekursiivsed. Selleks, et uurida selliseid protsesse toome sisse vajalikud mõisted ja definitsioonid ning tõestame lemma, mis tõestab, et (*)-arvutatavatest funktsioonidest operaatori abil saadud funktsioonid on samuti (*)-arvutatavad. Anname ka sellise teoreemi tõestamise idee, mis ütleb, et iga osaliselt rekursiivne funktsioon on Turingi mõttes arvutatav ehk antud juhul (*)-arvutatav. 1. Osaliselt rekursiivsed funktsioonid. Operaatori µ abil saadud funktsioonide (*)-arvutatavus.
..); 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 Mitterekursiivseks erijuhuks on siin 0! = 1
Kui nende väärtustega alamprogrammis midagi juhtub, siis peaprogrammi tagasi tulles need muudatused kaasa ei tule. Teine on vastuste saamiseks alamprogrammist (kuid ka nende andmete viimiseks alamprogrammi, mis seal oma väärtust muutma peavad). Muudatused nende väärtustes jõuavad ka peaprogrammi. Mõlemad on andmete viimiseks alamprogrammi, aga väärtusparameetri puhul tagasi tulles peaprogrammi muudatused kaasa ei tule. rekursiivne funktsioon Rekursiivsed võivad olla ka iseseisvad alamprogrammid, milles toimub iseenda poole pöördumine e. iseenda väljakutsumine. Täpsemalt öeldes nimetatakse rekursiooniks niisugust algoritmi kirjeldamise viisi, kui see kirjeldatakse iseenda poolt kirjeldatud tegevuste järgnevustega, kuid ainult teistel parameetrite väärtustel.
Puu on rekursiivne, seega ka enamik algoritme, mis temaga rakendada, on rekursiivsed. Kuid iga rekursiivset algoritmi saab esitada ka iteratiiselt, nagu enne juttugi oli. Kui juur välja jätta, siis kõigil teistel tipul on olemas ematipp ja ematippudel(parent) on omakorda tütartipud(child). Sama emaga tipud on õed(siblings). Kui meil on mitu puud, võime rääkida metsast(forest). Luline on rääkida veel puu kõrgusest. Puu jaguneb nivoodeks. Nivoode hulk on puu kõrgus. Mõnes õpikus võib näha ka teistsugust definitsiooni puu kõrguse kohta.
..,xn),...,hm(x1,...,xn)). Funktsiooni f esitatakse sel juhil operaatortermi abil järgmiselt: f = Sm+1[ g, h1,…, hm] (h-sid m tk + g = m+1 funktsiooni) DEF: (funktsiooni väärtust kasutatakse iseenda argumendina) Funktsioon f on saadud funktsioonist g ja funktsioonidest h rekursioonioperaatori R abil, kui kõikide väärtuste x1,...,xn ∈ N ja y ∈ N korral kehtivad seosed f(x1,…,xn,0) = g(x1,...,xn) ja f(x1,...,xn,y+1) = h( x1,…,xn, y, f(x1,…,xn,y) ). f =R[g,h] Teoreem: Rekursiivsed funktsioonid on Turingi masinal arvutatavad. T: Elementaarfunksioonid Registermasinal: On =0 on CLR, s(x)=x+1 on INC, Inm= xm on R → R. Ja ka Sm+1, R ja μy on reg.masinal arvutatavad. Neist saab konstrueerida kõik rek. funktsioonid. Ja reg.masin ja TM lahendavad samu asju. Teoreem: Iga registermasinal realiseeritav funktsioon on (osaline) rekursiivne funktsioon. Seega: Osaliselt rekursiivsete funktsioonide hulk langeb kokku Turingi mõttes arvutatavate funktsioonide hulgaga.
-n, mille väärtuste piirkond on kahendväärtus.
Kui g on arvutatav f.-n ja h1..hm on n-kohalised arvutatavad f.-nid, siis on ka f =
Sm+1[g,h1,..,hm] arvutatav.
Tõestus: eksisteerib registermasina programm
Kui g on n-kohaline arvutatav f.-n ja h on n+2 kohaline arvutatav f.-n, siis f =
R[g,h] on n+1-kohaline arvutatav f.-n.
Tõestus: eksisteerib registermasina programm
Neist kahest järeldub, et kõik lihtrekursiivsed funktsioonid on arvutatavad.
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
Selliste andmete töötlemine filtreerimisalgoritmi abil võimaldab siluda saadud tulemusi ja on tehtav soovi korral erisuguste algoritmidega 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
Kõrvallauset osutab sageli alistussidend (et, sest, kui...). Vastavalt sellele, kuhu kõrvallause on matriitlauses sisestatud, võib rääkida algussisestusest, kesksisestusest ja lõpusisestusest. Lõpusisestus on kõige tavalisem ja loomulikum sisetuse tüüp. Paremale hargnevad - lõpus asuvale kõrvallausele lisatakse järgmine kõrvallause. Reeglite rekursiivsus - reegli korduv kasutamine nii, et reegel kordab iseennast. (nt paremale hargnevate lausete puhul) Rekursiivsed algus- ja kesksisestused on praktiliselt võimatud, kuna nende valmistamine ja mõistmine on väga keeruline. 39. Süntaktilised transformatsioonid. Tekstilaused e pindlaused Tuumlausete muutmist kirjeldatakse süntaktiliste transformatsioonide abil. Kõik ühtekuuluvad pindlaused moodustatakse süntaktiliste transformatsioonide abil ühest ja samast süntakilisest süvastruktuurist. Markeerimata pindlause on kõige lähemal süvastruktuurile, kuid pole identne. SÕNAVARA 40
efektiivsus 2.3.2 Tugevad küljed: • Konseptuaalselt raskete probleemide lahendamine • Paralleelsus – mitmetuumaliste protsessorite rakendamisel • Aitab avastada efektiivseid algoritme • Cachemälu kasutamine on efektiivsem 2.3.3 Nõrgad küljed: • Tugevate külgede vastandid 2.3.4 Näide kasutamisest: • Kiirsorteerimine ja mestimisega sorteerimine. Mõlemad algoritmid on rekursiivsed ja jaotavad mingi skeemi järgi kogu ülesannet tükkideks, et need sorteerida ja hiljem osad ühendada. • Jaga ja valitse tüüpi strateegiat kasutavad ka otsimiskahendpuu ja kahendotsimise algoritmis. 3. Andmestruktuur. Andmestruktuuri loogiline tase ja realisatsiooni tase. 3.1 Andmestruktuur • Andmete talletamise ja organiseerimise viis • Vahend suure hulga andmete organiseerimiseks ja salvestamiseks arvutis ning neile efektiivse
Seepärast nimetame andmemudelit nüüd (loogiliseks) andmebaasiskeemiks. Kirjeldatakse kõik andmeväljad, määratakse (standardsed, mitte konkreetse tarkvaraga seotud) andmetüübid ning väljapikkused. Relatsioonilise andmebaasi loogilise disaini tegevused on: 1. Detailanalüüsi andmemudeli teisendamine - relatsioonilise mudeliga kokkusobimatute konstruktsioonide eemaldamine andmemudelist (valikuline). Eesmärgid: - Eemaldada binaarsed mitu-mitu (M:N) suhted. - Eemaldada rekursiivsed mitu-mitu (M:N) suhted. - Eemaldada suhte tüübid kus osaleb kolm või rohkem olemit. - Eemaldada mitmeväärtuselised atribuudid. 2. Tabelite leidmine. 3. Võtmete leidmine 4. Tabelite viimine kolmandale normaalkujule. Connolly ja Begg põhjal on normaliseerimise põhjuseks: - kaob andmete liiasus; - kaovad andmete muutmisest tingitud anomaaliad; 32
if ($n == 0) { return 1; } return($n * fact($n-1)); } ?> Näide 2.4.2 greatest_common_divisor.php Näide 2.4.3 Lisalugemist Rekursiivsed funktsioonid (www) - inglise keeles PHP matemaatilised funktsioonid (www) - inglise keeles PHP sõnede funktsioonid (www) - inglise keeles Video Funktsioonid (osa1, osa1 , osa1 ) - inglise keeles Scribd PHP Funktsioonid (www) - inglise keeles 3.1 If-else Kõik programmid, mis meie oleme vaadelnud olid hästi lihtsad selles mõttes, et käske käivitatakse algusest lõpuni. Keerukamate programmide kirjutamisel on vaja käske valikuliselt täita või siis isegi täitmata jätta
mitteilmse definitsiooniga. Definitsioone kasutatakse väga erinevates kontekstides ning nende esitamise eesmärk ja esitusviis võib olla vägagi erinev. Tavapraktikas võib eristada mitmeid defineerimise tüüpe (need ei välista üksteist): 1) sätestavad ehk kokkuleppelised (stipulative 'sätestav'); 2) leksikaalsed ehk sõnavaralised (lexical); 3) täpsustavad (precising); 4) teoreetilised ehk teaduslikud (theoretical); 5) operatsionaalsed (operational); 6) rekursiivsed (recursive); 7) veenvad (persuasive veenev, keelitav'). 1) Sätestav definitsioon on korraldavat või deklaratiivset laadi, sellega omistatakse mingile terminile või sümbolile tähendus. Tegemist võib olla juba kasutuses olevale sõnale või sümbolile uue tähenduse andmisega või täiesti uue sõna tähenduse määratlemisega. Laialt kasutuses oleva väljendi võib mingis teadusharus võtta kasutusele kui erialatermini, kasutades sätestavat definitsiooni
mitteilmse definitsiooniga. Definitsioone kasutatakse väga erinevates kontekstides ning nende esitamise eesmärk ja esitusviis võib olla vägagi erinev. Tavapraktikas võib eristada mitmeid defineerimise tüüpe (need ei välista üksteist): 1) sätestavad ehk kokkuleppelised (stipulative 'sätestav'); 2) leksikaalsed ehk sõnavaralised (lexical); 3) täpsustavad (precising); 4) teoreetilised ehk teaduslikud (theoretical); 5) operatsionaalsed (operational); 6) rekursiivsed (recursive); 7) veenvad (persuasive veenev, keelitav'). 1) Sätestav definitsioon on korraldavat või deklaratiivset laadi, sellega omistatakse mingile terminile või sümbolile tähendus. Tegemist võib olla juba kasutuses olevale sõnale või sümbolile uue tähenduse andmisega või täiesti uue sõna tähenduse määratlemisega. Laialt kasutuses oleva väljendi võib mingis teadusharus võtta kasutusele kui erialatermini, kasutades sätestavat definitsiooni
Näiteks soovime tegelda ainult Tallinnas (kood 1) sündinud lastega. 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 
