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.
Järjestatud puu, järjestamata puu. Kui on oluline, mis järjekorras mööda nivood vasakult paremale
liikudes õed mis järjekorras paiknevad, siis järjestatud puu.
Ülespoole järjestatud puud veel jne.
Binary search tree(kahendotsingu puu).
Ehitamisel - Kui järgmine kirje on väiksem, siis vasakule, kui suurem, siis paremale. Kui midagi
ees pole, siis teeme uue kaare ja uue tipu. Jne. Kui on, siis mine mööda seda edasi, kuni enam pole.
Otsimisel - Igas tipus tuleb teha üks võrdlus, sõltuvalt sellest minna kas vasakule või paremale. Kui
satume tühjale kohale, siis otsitavat kirjet ei olegi.
Kui 2 kirjet on võrdsete võtmetega, siis sellisel juhul on 2 lahendust . Primaarsed ja sekundaarsed
võtmed. Need võtmed, mille järgi puud ehitame, on primaarsed. Kui primaarsed võtmed langevad
kokku, siis hakatakse võrdlema sekundaarseid võtmeid ja väiksemaks loetakse see, mille puhul
sekundaarne võti on väiksem. Nt primaarne võti on inimese nimi ja sekundaarne on inimese vanus.
Teine võimalus on see, et paneme teise tipu juurde rohkem kui üks kirjet. See lahendus on halvem ,
teeb puud keerulisemaks.
Kolmas – väiksem-võrdne vasakule, suurem-võrdne paremale.
Tõmbame joone ülalt alla...kõik nrid, mis joonest vasakul on väiksemad nendest nr-test, mis on
joonest paremal. Ükskõik, mis tipu jaoks tõmbame sellise joone, tulemus on ikka sarnane.
Kuidas leida kõige väiksema võtmega kirje. Hakata juurest minema ja liikuda kogu aeg aina
vasakule. Kui enam vasakule minna ei saa, siis ongi leitud. Kõige suurema otsimise puhul paremale
samamoodi.
Andmestruktuurina - Tipp võiks koosneda kolmest viidast...üks viit on kirjele, üks vasakpoolsele
tütrele, teine parempoolsele tütrele.
Operatsioonid – loo tühi puu(ühtki juurt ega tippu). Loo uus kirje puusse. Eemalda kirje ja koos
temaga vastav tipp puust. Puu likvideerimine. Ümber midagi paigutada ei saa, järjekord on
võtmetega täiesti üheselt määratud. Kahendotsingu puu on järjestatud puu, sest vasakpoolse tütre
võti on igal juhul väiksem kui parempoolse.
Teine variant. Left ja right pole enam viidad , vaid indeksid. 0 tähistab olukorda, kus tütartippe pole.
Sügavat mõtet sellisel lahendusel pole. Tuleks kõne alla vaid sellise progemiskeele juures, kus
viitasid ei tunta. Tänapäeval aga selliseid progemiskeeli ei ole. Kaudselt on kõigil olemas, neid
lihtsalt ei nimetata nii. Nim reference 'iks, mitte pointeriks ja viitade aritmeetikat seal teha ei saa (nt
C#).
Kirje eemaldamine – kui ühtki tütartippu kirjel pole, siis peab lihtsalt tema ematipu right viida 0-ks
viima. Kui tahan 32 eemaldada, siis 23 läheb minema ja 30 hakkab viitama 26-le. Kui tahan 30
eemaldada, siis...
Iga puuharu võib vaadelda eraldi puuna, probleem tekib siis, kui tuleb eemaldada juur.
Kui 58 eemaldan, siis tekib 2 omavahel mitte seotud haru. Ühe juuresk 37, teise juureks 75. sinise
haru kõik võtme don rohelise haru kõikidest võtmetest suuremad. Miinimumi leidmiseks liikuda
pidevalt avsakule, järelikult sinise haru miinimumiks on 61. Ikkagi on ta suurem kui mistahes võti
rohelisest harust. Seega võtan terve sinise haru ja terve rohelise haru ning tõmban 61-st kaare 37-
sse. Võttes aluseks parempoolne haru, tõmban kaare selle miinimumist vasakpoolse haru juurtipuu.
Oleks võinud vütta aluseks ka vasakpoolse haru. Mõlemat pidi võib. Praegu lisame lihtsalt 61-le
viide 37-le, kõik muu jääb paika. Väga lihtne. Füüsiliselt midagi ei liiguta .
10 punkti
Autor soovib selle materjali allalaadimise eest saada 10 punkti.
~ 3 lehte
Lehekülgede arv dokumendis
2013-05-30
Kuupäev, millal dokument üles laeti
92 laadimist
Kokku alla laetud
0 arvamust
Teiste kasutajate poolt lisatud kommentaarid
shokohoolik
Õppematerjali autor
1. Algoritm. Algoritmi omadused. Keerukus. Ajalise keerukuse asümptoodiline hinnang. Erinevad keerukusklassid. Algoritm on mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrammi abil. Algoritm peab olema määratud nii täpselt, et seda suudaks täita isegi arvuti. Täidetavaid samme ei tohi olla liiga palju. Algoritm peab lahendama ülesande õigesti erinevate sisendandmete korral. Algoritmi 5 olulist omadust: 1. Lõplikkus. Algoritmi töö peab lõppema peale lõpliku arvu sammude läbimist. 2. Määratletus. Algoritmi iga samm peab olema rangelt ja ühemõtteliselt määratud iga juhu jaoks. 3. Sisend. Algoritmil on sisendandmed, mille hulk võib olla null. 4. Väljund. Algoritmil on vastus(ed), millel on täpselt määratud seos sisendandmetega. 5. Efektiivsus (tulemuslikkus). Algoritm peab olema nii lihtne, et on lõpliku ajavahemiku jooksul pliiatsi ja
1. Algoritm. Algoritmi keerukus. Ajalise keerukuse asümptootiline hinnang. Erinevad keerukusklassid: kirjeldus, näited. 1.1 Algoritm • Mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrogrammi abil. • Algoritm on õige, kui kõigi sisendite korral, mis vastavalt algoritmi kirjeldusele on lubatud, lõpetab ta töö ja annab tulemuse, mis rahuldab ülesande tingimusi. Öeldakse, et algoritm lahendab arvutusülesande. • Selline programm, mis annab probleemile õige vastuse piiratud aja jooksul. • Kindlalt piiritletud sisendi korral vastab ta järgmistele kriteeriumitele: o lõpetab töö piiratud aja jooksul; o kasutab piiratud hulka mälu; o annab probleemile õige vastuse.
kiirmeetod Radix sort, O(n) O(n) Stabiilne. positsioonimeetod Merge sort, O(n logn) O(n logn) On enamasti ühildusmeetod stabiilne. Paisktabel, hash O(1) O(1) table Heap sort, O(n logn) O(n logn) kuhjameetod 1. Algoritmi omadused. Algoritmide asümptootiline analüüs: relatsioonid "suur- O", "väike-o", teeta, "suur-oomega" ja "väike-oomega"; nende definitsioonid ning põhiomadused. Mida miski täpselt tähendab. Algoritm on täpne (üheselt mõistetav) juhis antud ülesande lahendamiseks. Algoritm koosneb lõplikust arvust sammudest, millest igaüks on täidetav lõpliku aja jooksul lõplikke ressursse kasutades. Algoritmi rakendatakse teatavale lähteandmete komplektile (sisend)
1.2 Järjestamise kuhjameetod Järjestikalgoritm Luua tühi kuhi; lisada järjendi kirjed järjekorras sinna. 1 Kahendkuhjad 25 1.2 Järjestamise kuhjameetod Keerukus Kui n tähistab kirjete arvu, siis järjendi pealt kuhja tekitamise keerukus on järjestikalgoritmi puhul halvimal juhul (n log n), keskmisel ja parimal juhul (n); "jaga ja valitse" algoritmi puhul alati (n). 1 Kahendkuhjad 26 1.2 Järjestamise kuhjameetod "Jaga ja valitse" algoritm massiivi puhul · Eeltöö -- kompaktse kahendpuu struktuuri loomine -- on triviaal- ne. Etteantud massiivi võib algusest peale käsitleda nii, nagu ta väl- jendaks kompaktset kahendpuud. Positsioonid massiivis määravad alluva-ülemuse suhted ära.
.,tn) on term, mis tähistab puu T alampuud juurega a Idee poolest sama on lrep(T) asendame lihtsalt tipud neile vastavate märgenditega. Puu kroon Kr(T) = string terminaalsete tippude märgenditest vasakult paremale kirjutades. Puu T1 terminaalse tipu A asendamine puuga T2 tähistatakse t = T1{A/T2} Märgendatud järjestatud elementaarpuid saab esitada kontekstivabade grammatikate produktsioonide esitamiseks. Süntaksipuuks KV-grammatikas G = (,N,P,S) nimetatakse märgendatud järjestatud puud t, kui iga r kuulub E(t) korral r p, p kuulub produktsiooni. Ehk siis kui iga puu kaar esitab produktsiooni. Iga puu on üheselt esitatav oma elementaarpuude nimistuna E(t) (elementaarpuu on puu, mis koosneb vaid juurest ja terminaalsetest tippudest). Märgendatud järjestatud elementaarpuu esitab produktsiooni. Mitteterminaalist A on tuletatav lausevorm parajasti siis, kui grammatikas G leidub tuletuspuu A[]. Näidata, et see on tarvilik ja piisav ja tingimus sõna aktsepteerimiseks:
mingitel väärtustel Ütleme, et valemitest F1, F2, ... , Fn järeldub valem G, kui igas interpretatsioonis valemite vabade muutujate kõikidel väärtustel, kus valemid F1, F2, ... , Fn on tõesed, on ka valem G tõene Valemeid F ja G nimetatakse samaväärseteks, kui nende tõeväärtused on võrdsed igas interpretatsioonis valemite vabade muutujate kõikidel väärtustel Churchi teoreem: ei leidu algoritmi, mis suudaks suvalise predikaatloogika valemi puhul kindlaks teha, kas valem on samaselt tõene Igasuguse lõpliku võimsusega ja loenduva hulga interpretatsioonide vaatlemine on vajalik, sest saab konstrueerida valemi, mis on tõene parajasti siis, kui kandjas on n elementi, ja saab konstrueerida kehtestatava valemi, mis on väär igas lõpliku kandjaga interpretatsioonis Kui signatuur on lõplik või loenduv, siis loenduvast suuremate kandjate
Diskreetse matemaatika elemendid 2013/2014 LAUSEARVUTUS. TÕESTUSED. 1. Lausearvutuse lausetele esitatavad tingimused. [1] o Välistatud kolmanda seadus. Iga lause on kas tõene või väär. o Mittevasturääkivuse seadus. Ükski lause ei saa olla nii tõene kui ka väär. o Nende nõuete põhjal kuuluvad vaadeldavate hulka ainult nii sugused laused, mis midagi väidavad, kusjuures sellel väitel on olemas ühene tõeväärtus. o . Välistatud kolmanda seaduse nõudel jäävad kõrvale kõik küsilaused ja paljud hüüdlaused, samuti kõik käsud ning mõttetud sõnaühendid. Mitte-vasturääkivuse seadus välistab mitmesugused paradoksid, näiteks „See lause siin on väär“, ja muud taolised väited, mille tõeväärtust pole võimalik üheselt määrata. o Tehte tulemuseks saadud lause tõeväärtus sõltub ainult komponentlausete tõeväärtustest. 2. Lausearvutuse tehted. Tehete järjekord. Lausearvutuse valem. [1] Tehted o Eitus (märk ¬)
homoplaasiast tulnud. 9. Tegelik puu ja konstrueeritud puu. Tegelik puu on reaalselt toimunud fülogeneesi kujutis. Evolutsioon Maal on unikaalne protsess ja seda kirjeldab ainult üks puu. Enamasti pole see teada. Konstrueeritud puu on tegeliku puu hinnang, fülogeneesi mudel, hüpotees. Konstrueeritakse olemasolevate andmete põhjal. Võib, kuid ei pruugi olla identne tegeliku puuga. Enamasti saab andmetest tuletada mitu puud. 10. Mis on homoloogia, mis homoplaasia (Tooge näiteid!). Homoloogia – tunnus on kahes Homoplaasia – tunnus on kahes vaadeldavas liigis homoloogne, vaadeldavas liigis homoplaasne, kui see on päritud ühiselt kui see on neil liikidel tekkinud eellaselt. sõltumatult. Nt lüsosüüm – erinevaid Nt paralleelse evolutsiooni lüsosüüme esineb mitmetes käigus tekkinud lendorav,
annaabi.ee 
Sisene Facebook'ga
Sisene Google'ga
Sisene LinkedIn'ga
Kõik kommentaarid