KMI/ALGO3 — Algoritmy 3

Sylabus

1. Návrh algoritmu — specifikace, korektnost, invariant, terminace; stabilní párování (Gale–Shapley); asymptotická notace, velikost vstupu.
2. Hladové algoritmy — intervalové plánování, protipříklady, výměnný argument, „zůstává napřed“; minimalizace zpoždění; Huffmanovo kódování.
3. Hladové algoritmy na grafech — vlastnost řezu; minimální kostra (Borůvka, Jarník–Prim, Kruskal), union-find; Dijkstra, A*, přípustná heuristika.
4. Rozděl a panuj — binární vyhledávání, mergesort, počítání inverzí; rekurence, rekurzivní strom, substituce, Masterova věta; dolní mez třídění.
5. Rozděl a panuj II — Karatsubovo násobení; lineární výběr k-tého prvku (medián mediánů); nejbližší dvojice bodů; FFT.
6. Dynamické programování I — překryv podproblémů, memoizace, tabulace, návrh stavu; vážené intervaly; cesty v DAG; rekonstrukce řešení.
7. Dynamické programování II — 0/1 batoh a pseudopolynomiální čas; editační vzdálenost a zarovnání; optimální BST; úspora paměti.
8. Toky v sítích — reziduální síť, zvětšující cesta, Ford–Fulkerson, Edmonds–Karp; max-flow/min-cut; párování, disjunktní cesty, výběr projektů.
9. Systematické prohledávání — stavový strom, backtracking, bezpečný ořez; n dam; splňování omezení, propagace, heuristika MRV; SAT a DPLL.
10. Branch-and-bound — incumbent, meze, relaxace, výběr uzlu, mezera optimality; celočíselné programování; P a NP, redukce, NP-úplnost.
11. Adversariální návrh — herní strom, minimax, alfa-beta, negamax, pořadí tahů; omezená hloubka, hodnoticí funkce, transpoziční tabulky.
12. Aproximace a heuristiky — aproximační poměr; vrcholové pokrytí, set cover, metrické TSP; PTAS/FPTAS; lokální hledání, simulované žíhání.
13. Randomizace a syntéza — Las Vegas a Monte Carlo, linearita očekávání; randomizovaný quicksort, Kargerův min-cut; volba návrhové metody.

Doporučená literatura

• Kleinberg, J., Tardos, É. (2006). Algorithm Design. Pearson Education.

Výukové materiály

Budou doplňovány v průběhu semestru.