# 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)