Algoritmid ja andmestruktuurid eksamiks kordamine (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

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

25

pdf

ICD0001 Algoritmid ja andmestruktuurid kodutöö 6 - aruanne

.................................................................................................................. 4 3 Muudatused etteantud klassides .................................................................................... 4 3.1 Klass Vertex ........................................................................................................... 4 3.2 Klass Graph ............................................................................................................ 5 4 Algoritmi kirjeldus ........................................................................................................ 5 5 Programmi kasutusjuhend ............................................................................................. 6 6 Testimiskava .................................................................................................................. 7 7 Algoritmi testimine suure koguse andmetega ............................................................. 10 Kasutatud allikad .

Algoritmid ja andmestruktuurid

55

pdf

Algoritmid kokkuvõte

Algoritmid ja andmestruktuurid Ülevaades sellest kuhu oleme jõudnud Ja kuidas edasi minna 1/55  Eksamid ja konsultatsioonid Eksamid ⚫ 18. detsember kell 14 ⚫ 11. jaanuar kell 14 ⚫ 20. jaanuar kell 14 2/55  Mis on algoritm? Probleem Algoritm Andmed Programm Tulemus 3/55  Algoritmide loomise paradigmasid ⚫ jaga ja valitse – lahendame väiksemateks ülesanneteks jagamisega ⚫ ahne algoritm – lokaalne valikukriteerium annab globaalse tulemuse – taandame ülesande ühele väiksemale alamülesandele ⚫ dünaamiline planeerimine – paneme alamülesannete lahendustest kokku suurema ülesande

Algoritmid ja andmestruktuurid

6

pdf

Algoritmid ja andmestruktuurid: transfers

Output of non-deterministic algorithm may be different for different runs with the same input data Mittedetermineeritud algoritmi tulemus samade lähteandmete korral võib erinevatel lahenduskordadel olla erinev. Tõene Partial algorithm terminates for any set of input data. Osaline algoritm peatub mistahes sisendandmete korral. Väär Average time complexity of binary search is O(log n). Kahendotsimise keskmine ajaline keerukus on O(log n). Tõene Worst case time complexity of merge sort is O(n). Ühildusmeetodi (merge sort) halvima juhu ajaline keerukus on O(n). Väär (it is O(n log n)) Sorting method is quick if it has average time complexity O(n lon n). Järjestamismeetod on kiire, kui selle keskmine ajaline keerukus on O(n log n). Tõene Jah, üldjuhul ei saa kiiremini

Algoritmid ja andmestruktuurid

4

doc

Graafid

Graafid Graaf koosneb tippudest(sõlmedest) ja neid ühendavatest kaartest. Kaarega võib ühendada suvalisi graafi tippe, sealhulgas on võimalik kaar samale tipule (iseendale). Iga kaar on määratud kahe tipuga. Orienteeritud graaf: kaared on järjestatud tipupaarid. Def: Graaf on paar (V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad. Näide lk 47 (Palm) Tipu aste ­ tipust väljuvate servade arv. Teoreem: Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. Järeldus: Igas graafis on paaritu astemga tippe paarisarv. Ahel graafis ­ tippude järjend, kus iga kaks järjestikust tippu on servaga ühendatud (esimene ja viimane on otstipud vahepeal sisetipud). Ahela pikkus on k kui selles on k+1 tippu. Ahel võib läbida mõnda tippu mitu korda. Lihtahel ­ kõik tipud läbitakse üks kord. Tippude u ja v vaheline kaugus - tippude u ja v vahelise lihtahela pikkus Tsükkel ­ ahel mis lõpeb sama

Matemaatika ja statistika

21

docx

Graafid ja matemaatiline loogika eksamimaterjal

.., 1n), (21, ..., 2n), ..., (m1, ..., mn) ja väär kõigil ülejäänud väärtustustel o TDNK-le viimine: Koostame valemi põhjal tõeväärtustabeli Vaatame vaid neid ridu, mil valem on tõene Koostame konjuktsioonid ridadele vastavatest elementide tõeväärtustest (nt kui X=t, Y=t ja Z=v, siis saame X&Y&¬Z) Ühendame saadud konjuktsioonid ühiseks disjunktsiooniks o TDNK-le viimise algoritm: Elimineerida implikatsioonid ja ekvivalentsid Viia eitused vahetult lausemuutujate ette (st konjunktsioonide ja disjunktsioonide sisse) Korrutada disjunktsioonid läbi (distributiivsuse seaduse abil) Kaotada samaselt väärad konjunktsioonid ja sama liikme mitmekordsed esinemised konjunktsioonides Lisada konjunktsioonidele puuduvad muutujad

Algebra I

Meedia

Kommentaarid (0)