1. Toky v sitich - Dinitzuv algoritmus:
Dinitzuv algoritmus: znat hlavne, proc nemuze pocitat tak dlouho jako nekdy jine implementace Ford-Fulkersonova algoritmu.
Napoveda: proc hodnota dvojice hodnot (L,H), je v lexikografickem usporadani po kazdem zpracovani cesty mensi
kde L je delka nejkratsi cesty ze zdroje do spotrebice slozena z hran s kladnou rezervou (co to je rezerva hrany?)
a H je pocet hran s rezervou, pres ktere vede cesta ze zdroje do spotrebice slozena z hran s kladnou rezervou
(v appletu L je pocet vrstev a H pocet modrych hran)
( (L1,H1) je lexikograficky mensi nez (L2,H2), jestlize bud L1 < L2 a nebo L1=L2 a soucasne H1 < H2)
2. Toky v sitich - Goldberguv algoritmus Goldberg
na trojku znat algoritmus a popsat jeho funkci zpusobem, ktery je videt z appletu, na dvojku vedet take, proc v okamziku zastaveni je nalezeny tok maximalni mozny na jednicku vedet take, proc se algoritmus vzdy zastavi a po kolika krocich
3. Konvexni obal mnoziny bodu v rovine - umet dokazat, ze pokud jsou body zadany serazeny podle x-ove souradnice, pak vypocet trva pouze O(n) kroku, kde n je pocet bodu
4. Voronoi diagram - Fortunuv algoritmus
znat 3D pohled na algoritmus a vedet, co jsou mistni a kruznicove udalosti)
5. Ocekavane chovani heuristiky pro hledani kliky v grafu (odvozeni 1. a 2. momentu funkce udavajici pocet k-klik v nahodnem grafu, Markovova a Cebysevova nerovnost).
6. Diskretni Fourierova transformace a algoritmus FFT
Nasledujici odkazy se vztahuji k prednasce MI-PAL, jak byla prednasena v predchozich lech - prvni dva pro akademicky rok 2017-18 nejsou potrebne
Voroneho diagram (vizualizace)