A) Hledání toku metodou zlepšující cesty
Hricova prezentace strana 21, 22
B) Vymyslet konkrétní graf s max 10 hranami, kde se zlepšující cesta najde až 1000x, dokud se nenalezne maximální tok (a popsat zvolenou strategii volby cest)
Aho-Corasick, popis vyhledávacího algoritmu a důkaz složitosti
Hricova prezentace strana 7, 9
DFT pro (1,3,1,3,1,3,1,3)
Jednoduše pomocí FFT, na webu je spousta kalkulaček na ověření. Rozdělím na vektor sudých a lichých členů (3,3,3,3) a (1,1,1,1), na to dál pouštím rekurzi. Pro vektor (k,...,k) platí, že jeho obraz je (kn,0,...,0), proto obraz pro (3,3,3,3) je (12,0,0,0) a pro (1,1,1,1) je (4,0,0,0) - ale do zkoušky by to asi chtělo rozepsat. Ted už stačí jen projet ten for cyklus z prvního volání funkce, ani nemusím počítat omega, protože je vidět, že nenulové budou jen pozice y_0 a y_4. Odtud y_0 = 4 + 12 = 16 a y_4 = 4 - 12 = -8. Proto je odpověď (16,0,0,0,-8,0,0,0)
A) Definice - rozhodovací problém, polynomiální převoditelnost, P, NP, NPÚ
Hricova prezentace strana 58, 59, 62
B) Převod SAT na 3-SATMarešovy skripta strana 435