MTAT.03.003. Algoritmid ja andmestruktuurid (5ap)
L64+P32
Annotatsioon
Algoritmi struktuur ja korrektsus. Ajaline keerukus. Andmestruktuurid ja
nende realiseerimine.
Sorteerimise, sõnetöötluse,
graafitöötluse ja planimeetria algoritmid.
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.
Kirjandus
1. J.Kiho. Algoritmid ja andmestruktuurid. Tartu, 1997, 124 lk.
2. T.H.Cormen, C.E.Leierson, L.Rivest. Introduction to Algorithms.
MIT, 1990, 1028 lk.