# NTIN060: Algoritmy a datové struktury I ## 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 „Algoritmizace“ v předchozím semestru. ## Sylabus (volitelná témata _kurzívou_, zbytek je povinný; hodinové dotace jsou orientační) 1. Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami (1 přednáška) * měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat * výpočetní model RAM * asymptotická notace 1. Základní grafové algoritmy (1 přednáška) * 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_ 1. Extremální cesty v grafech (2 přednášky) * 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_ 1. Minimální kostra grafu (1 přednáška) * Jarníkův a Borůvkův algoritmus * _Kruskalův algoritmus a datová struktura pro Union-Find_ 1. Stromové datové struktury (1.5 přednášky) * binární vyhledávací stromy * AVL stromy * (a,b)-stromy * _červeno-černé stromy_ 1. Hešování (1 přednáška) * popis jednoduchých strategií řešení kolizí * analýza průměrné časové složitosti vyhledávání * univerzální hešování 1. Metoda rozděl a panuj (2.5 přednášky) * 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í, Mergersort, 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ě_ 1. Dynamické programování (1 přednáška) * obecný princip dynamického programování * editační vzdálenost řetězců * _optimální vyhledávací stromy_ 1. Třídění (1 přednáška) * 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)