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.
|
-
Anany Levitin. (2003). The design & Analysis of Algorithms.
-
Bhargava, A. Y. (2016). Algorithms.. Manning Publications Co.
-
CORMEN, T. H., LEISERSON C. E., RIVEST D. L., STEIN C. (2001). Introduction to Algorithms, Second Edition.
-
Dasgupta, S., Papadimitriou, C. H., Vazirani U. (2006). Algorithms. McGraw.
-
Kleinberg J., Tardos, E. (2006). Algorithm design. Pearson Education.
-
Kozen, D.C. (1992). The design and analysis of algorithms.
-
Manber U. (1989). Introduction to Algorithms. A creative approach.. Addison.
-
Skiena, S.S. (2012). The Algorithm Design Manual. Springer.
|