Eeldused
Eksamile saamiseks peavad olema arvestatud
neli kontrolltööd
ja praktilised tööd (kellel programmeerimine II
sooritatud, sellel ainult kaks esimest).
Aeg ja koht
11. juuni, kl. 9, Van108
21. juuni, kl. 9, Van108
Korraldus
Piletis on kaks punkti.
Kohe tuleb suuliselt anda ülevaade nendest teemadest.
Sõltuvalt vastusest:
hinne 5, või
hinne 2, või
hinde (2..5) täpsustamiseks vastata kirjalikult (alam)teema(de)
kohta.
Teemad
- Algoritmi ajalise keerukuse mõiste.
- Funktsiooni asümptootilised hinnagud.
- Puu ja kahendpuu. Algoritmid kahendpuu ja vastava hariliku puu
töötlemiseks.
- Kahendotsimise puu. AVL-puu.
- B-puu.
- Paisksalvestus. Välisaheate, siseahelate ja lahtise
adresseerimise meetodid.
- Kahendkuhi.
- Binomiaalkuhi.
- Sorteerimise ühildusmeetod.
- Sorteerimise erimeetodid.
- Sorteerimisülesande ajalise keerukuse alampiir.
- Knuth-Morris-Pratti algoritm.
- Rabin-Karpi algoritm.
- Teksti pakkimine. Huffmani algoritm.
- Pikima ühise osasõna otsimine.
- Graafi tippude topoloogiline sorteerimine. Eeldusgraafi
analüüs.
- Lühimad teed graafis.
- Kõigi lihtteede leidmine graafi sügavuti
läbimisel.
- Graafi laiuti läbimine.
- Kruskali algoritm.
- Primi algoritm.
- Pseudo-tõusunurga ja pöörde suuna leidmine.
- Punkti hulkurka kuuluvuse kontrollimine.
- Grahami seiremeetod.
- Vähima vahemaaga punktipaari leidmine.
- Algoritmi osalise korrektsuse tõestamine.
- Tsükli lõplikkuse tõestmine.