Eksamile pääsemiseks peab praktikum olema arvestatud ja
vähemalt 1 kontrolltöö arvestatud.
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. Samas tuleb teha võlgu olev kontrolltöö.
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.
- 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.