Algoritmid ja andmestruktuurid konspekt - puud (0)

Sarnased õppematerjalid

16

pdf

Algoritmid

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

Analüütiline geomeetria

80

pdf

Algoritmid ja andmestruktuurid eksamiks kordamine

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.

Informaatika

22

docx

Algoritmid ICD0001 - kordamisküsimused

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)

Algoritmid ja andmestruktuurid

22

pdf

Algoritmid ja andmestruktuurid: puud, kuhjad

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.

Matemaatika

37

doc

Teoreetilibe informaatika kordamisküsimused

.,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:

Teoreetiline informaatika

21

docx

Graafid ja matemaatiline loogika eksamimaterjal

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

Algebra I

92

docx

Diskreetse matemaatika elemendid

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 ¬)

Diskreetne matemaatika

58

docx

Molekulaarne evolutsioon

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,

Geneetika

Kommentaarid (0)