Eksamil tuleb
- teada järgmisi definitsioone:
- Algoritmi ajaline keerukus. Suur O, Teeta ja Oomega.
- Algoritmi amortiseeritud keerukus. Potentsiaali mõiste.
- Puu. Kahendpuu. (Suunatud) graaf.
- Puu naturaalesitusele vastav kahendpuu.
- Dünaamiline järjend. Magasin. Järjekord.
- Kahendotsimise puu.
- AVL-puu.
- m-rajaline otsimispuu.
B-puu.
- Kuhjaomadus puus.
- Binomiaalpuu. Binomiaalkuhi.
- Sorteerimismeetodi stabiilsus.
- Sõne. Alamsõne. Sõne pikkus.
Alamsõne esinemine teatavas positsioonis. Prefiks. Sufiks.
Osasõne.
- Prefiksfunktsioon.
- Kood. Prefikskood. Koodi kujutamine kahendpuuna. Huffmani kood.
- Graafi aluspuu. Graaif minimaalse kaaluga aluspuu.
- Kahe tipu vaheline kaugus graafis.
- Suunatud tsükliteta graaf. Graafi tippude topoloogiline
järjestus.
- Tugevalt sidus graaf.
- Graafi tugevalt sidusad komponendid ja komponentgraaf.
- detailselt teada järgmisi
algoritme ja andmestruktuure:
- Puu ja kahendpuu naturaalesitused.
- Puu läbimine eesjärjestuses ja
lõppjärjestuses.
- Kahendpuu läbimine keskjärjestuses.
- Graafi kujutamine mälus tippude ahela ja igast tipust
väljuvate servade ahelate abil.
- Graafi läbimine laiuti ja sügavuti.
- Otsimine kahendotsimise puust ja lisamine sinna.
- Otsimine m-rajalisest
otsimispuust.
- Kahendkuhi. Esitus massiivina. Mis operatsioone toetab?
Operatsioonide realisatsioonid. Operatsioonide keerukused.
- Kahendpuu teisendamine kahendkuhjaks.
- Sorteerimine pistemeetodil.
- Sorteerimine kiirmeetodil.
- Randomiseeritud kiirmeetod.
- Sorteerimine ühildusmeetodil.
- Sorteerimine kuhjameetodil.
- Sorteerimine loendamismeetodil ja positsioonimeetodil.
- Mida sorteeritavate elementide kohta eeldavad?
- Rabin-Karpi alamsõne otsimise algoritm.
- Bellman-Fordi algoritmi lühimate teede leidmiseks graafi
ühest tipust teistesse tippudesse. Nende teede pikkuste ja nende
teede eneste leidmine.
- Dijkstra algoritm lühimate teede leidmiseks graafi
ühest tipust teistesse tippudesse.
- Lühimate teede pikkuste leidmine graafi kõigi
tipupaaride vahel graafi naabrusmaatriksi korduva ruututõstmise
teel.
- Floyd-Warshalli algoritm lühimate teede pikkuste
leidmiseks graafi kõigi tipupaaride vahel.
- Graafi tippude topoloogiline sorteerimine.
- Klasside kujutamine. Toetatavad operatsioonid ja nende
keerukused.
- Operatsioonide keerukushinnangute tõestusi ei ole vaja
teada.
- Paisktabel.
- Välisahelate meetod põrgete lahendamiseks.
Toetatavad operatsioonid ja nende keerukused.
- Lahtise adresseerimise meetod põrgete lahendamiseks.
Toetatavad operatsioonid ja nende keerukused.
- teada järgmiste algoritmide ja
andmestruktuuride töötamispõhimõtteid:
- Kustutamine kahendotsimise puust.
- AVL-puu muutmisoperatsioonid.
- B-puu muutmisoperatsioonid.
- Sorteerimismeetodi stabiliseerimine.
- Sorteerimine kimbumeetodil.
- Mida sorteeritavate elementide kohta eeldavad?
- k-nda elemendi
leidmine n-elemendilisest
massiivist randomiseeritud kiirmeetodiga sarnasel viisil.
- Deterministlik kiirmeetod keerukusega O(n log n).
- Knuth-Morris-Pratti alamsõne otsimise algoritm.
Prefiksfunktsiooni arvutamine.
- Boyer-Moore'i alamsõne otsimise algoritm. Kasutatavad
heuristikad.
- Huffmani koodide leidmine.
- Kahe sõne pikima ühise osasõne leidmine dünaamilise
algoritmiga.
- Kruskali ja Primi algoritmid graafi min. kaaluga aluspuu
leidmiseks.
- Lühimate teede leidmine graafi ühest tipust teistesse
tippudesse, kui on antud nende teede pikkused.
- Johnsoni algoritm lühimate teede pikkuste leidmiseks
graafi kõigi tipupaaride vahel.
- Lühimate teede leidmine suunatud tsükliteta graafi
mingist tipust teistesse tippudesse.
- Graafi tugevalt sidusate komponentide leidmine.
- Kahe sirglõigu lõikumise kontroll.
- Punktihulga kumera katte leidmine Grahami seiremeetodil ja
Jarvise mähkimismeetodil.
- Teineteisele lähima punktipaari leidmine punktihulgast.
- Tuleb ka osata põhjendada, et "keskmise" riba
läbivaatamisel piisab, kui kontrollime iga punkti kaugust ainult
kuuest talle järgnevast punktist.
- Punkti hulknurka kuulumise kontroll.
- Punkti kumerasse hulknurka kuulumise kontroll.
- Hulknurga pindala leidmine.
- teada järgmiste algoritmide ja
andmestruktuuride olemasolust ning vastavate operatsioonide keerukusi:
- Binomiaalkuhja toetatavad operatsioonid ja nende keerukused.
- k-nda elemendi
leidmine n-elemendilisest
massiivist lineaarses ajas.
- Kahe vektori suuna võrdlemine (üks on teisest
paremal/vasakul).
- Kontrollimine, kas antud sirglõikude hulgas leidub
teineteist lõikavaid lõike.
- Teineteisest kaugeima punktipaari leidmine punktihulgast.
- teada järgmisi teoreeme koos
tõestustega:
- Sorteerimismeetodite keerukused (halvimal juhul).
- Elementide võrdlemisel põhineva sorteerimise
keerukuse alamtõke.
- Kasutatavat arvutusmudelit tuleb osata täpselt
kirjeldada.
- Vajalike võrdlemiste arv massiivi minimaalse elemendi
leidmiseks.
- Knuth-Morris-Pratti algoritmi keerukus.
- Graafi kahe tipu vahelise lühima tee leidmise
ülesande optimaalne alamstruktuur.
- teada järgmiste teoreemide
sõnastusi:
- AVL-puu kõrgus on logaritmiline tema tippude arvu suhtes.
- Kahendpuu kuhjastamise keerukus.
- Randomiseeritud kiirmeetodi keerukus.
- Loendamis- positsiooni- ja kimbumeetodil sorteerimise keerukus.
- Vajalike võrdlemiste arv massiivi minimaalse ja
maksimaalse elemendi üheaegseks leidmiseks.
- Graafi komponentgraaf on suunatud tsükliteta.
- osata materjale kasutades lahendada
järgmist tüüpi ülesandeid:
- Praktikumis tehtud ülesanded...
- Algoritmide keerukuse ja/või amortiseeritud keerukuse
leidmine (näide).
- Alternatiivne sõnastus: tõesta, et antud
algoritmil on järgmine (amortiseeritud) keerukus.
- Potentsiaali kohta võib olla antud vihjeid.
- Muuhulgas tuleb osata
- suurte O-de, Teetade ja Oomegatega arvutada,
- põhiteoreemi kasutada.
- Teatavate ülesannete lahendusalgoritmide keerukuse
alamtõkete leidmine, kui lahenduses tohib kasutada ainult teatud
tüüpi operatsioone (näide).
- Vihjeid võib olla antud selle kohta, kuidas oraakel
käituma peab, et lahendaja võimalikult palju tööd
tegema peaks.
- Dünaamilise programmeerimise ülesannete lahendamine (näide).
- Alamülesannete ruumi kohta võib olla antud
vihjeid.
- Ahnete algoritmide koostamine ülesannete jaoks, millel
sellised algoritmid leiduvad (näide).
- Ahne valiku kohta võib olla antud vihjeid.
- Tuleb osata tõestada, et tehtud ahne valik korrektse
algoritmi annab.
- Ülesannete taandamine loengutes uuritud ülesannetele.
- Näiteks lühimate teede leidmisele mingis graafis.
- Programmide korrektsuse formaalne tõestamine.
- Näiteid: minimaalse / maksimaalse elemendi leidmine massiivist,
massiivi elementide summa leidmine. Iteratiivsed ja rekursiivsed algoritmid nende jaoks.
- Võib (aga ei pruugi) olla antud vihjeid
tsükliinvariantide kuju kohta.