Sylabus
Volitelná témata v hranatých závorkách, zbytek je povinný.
1. Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami - měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat - výpočetní model RAM - asymptotická notace
2. Stromové datové struktury - binární vyhledávací stromy - AVL stromy - (a,b)-stromy - [červeno-černé stromy]
3. Hešování - popis jednoduchých strategií řešení kolizí - analýza průměrné časové složitosti vyhledávání - univerzální hešování
4. Třídění - analýza průměrného případu pro Quicksort, randomizovaný Quicksort - dolní odhad složitosti porovnávacích třídících algoritmů (rozhodovací stromy)
5. Základní grafové algoritmy - prohledávání do hloubky na neorientovaném grafu, detekce mostů a artikulací - prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování - [detekce komponent silné souvislosti v lineárním čase]
6. Extremální cesty v grafech - extremální cesty v acyklickém orientovaném grafu, metoda kritické cesty - Dijkstrův algoritmus (zopakování binární haldy, srovnání implementace polem a binární haldou) - Bellmanův-Fordův algoritmus (hledání záporných cyklů) - [Floydův-Warshallův algoritmus]
7. Minimální kostra grafu - Jarníkův a Borůvkův algoritmus - [Kruskalův algoritmus a datová struktura pro Union-Find]
8. Metoda rozděl a panuj - obecné schéma algoritmů typu rozděl a panuj, souvislost jejich složitosti s rekurentními rovnicemi - substituční metoda řešení rekurentních rovnic a „master theorem (kuchařka)“ - jednoduché aplikace: binární vyhledávání, Merge sort, násobení čísel (Karatsuba-Ofman) - složitější aplikace: Strassenovo násobení matic, [hledání mediánu v lin. čase v nejhorším případě]
9. Dynamické programování - obecný princip dynamického programování - editační vzdálenost řetězc ů - [optimální vyhledávací stromy]
Anotace
Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Navazuje na výklad v přednášce NPRG062 Algoritmizace v předchozím semestru.