Přednášky se zaměřují na formální popis algoritmů a příklady jejich uplatnění v praxi (přednášky v poslední části předmětu jsou vedeny či připraveny vyučujícími, kteří příslušné algoritmy využívají v rámci svých vědeckých či odborných aktivit). V průběhu cvičení jsou jednotlivé algoritmy implementovány, či je diskutována jejich implementace ve standardních knihovnách (srovnání efektivity implementace) a je naznačeno jejich praktické využití. 1. Teoretické základy algoritmizace: asymptotická složitost (Landauovy asymptotické notace), princip lokality (důsledky pro mezipaměti) 2. Datové struktury: základní principy, lineární datové struktury, hashovací tabulky (hashovací funkce), řídká pole 3. Datové struktury: stromové struktury (binární uspořádané stromy, haldy), vyvažování stromů 4. Datové struktury: grafy (Fibonacciho haldy, ohodnocené grafy) 5. Rekurzivní algoritmy: rozděl a panuj (quick sort, merge sort, nejbližší dvojice bodů) 6. Rekurzivní algoritmy: dynamické programování 7. Hladové algoritmy: deterministické hladové algoritmy (např. hledání kostry grafu) 8. Hladové algoritmy: heuristiky (problém obchodního cestujícího) 9. Pravděpodobnostní algoritmy: generátory pseudonáhodných čísel, randomizované datové struktury a klasické algoritmy, Monte Carlo metody 10. Výpočetní geometrie: konvexní obálka, Delaunayova triangulace, Voroného diagram 11. Výpočetní geometrie: BSP tree, quadtree/octree a R-tree, Minkowského suma a její uplatnění 12. Shluková analýza: hierarchické shlukování, hustotní shlukování (DBSCAN), centroidní shlukování (k means), grafové algoritmy (kliky) 13. Zpracování textů (suffix trees, string distance, approximate pattern matching)
|
Předmět je zaměřen na teoretické i praktické seznámení s běžně používanými datovými strukturami a algoritmy nad těmito strukturami. Předmět je zahájen přednáškou, která je věnována formalismu asymptotické složitosti a optimálnímu využívání počítačové paměti. Následuje popis základních i pokročilých datových struktur včetně elementárních operací nad nimi (vkládání, vyhledávání, vymazání). Nejrozsáhlejší část předmětu je věnována třem základním algoritmickým přístupům (rekurzivní algoritmy, hladové algoritmy a pravděpodobnostní algoritmy) s příklady běžně používaných obecných algoritmů. Poslední část předmětu je věnována stručnému přehledu a prezentaci algoritmů a datových struktur v oblastech, u nichž se předpokládá aplikace v rámci semestrálních projektů.
|