od Speedding » 7. 2. 2018 11:16
1)
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)
-
https://en.wikipedia.org/wiki/Ford%E2%8 ... al_example
2) Aho-Corasick, popis vyhledávacího algoritmu a důkaz složitosti
- Hricova prezentace strana 7, 9
3) 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)
4)
A) Definice - rozhodovací problém, polynomiální převoditelnost, P, NP, NPÚ
- Hricova prezentace strana 58, 59, 62
B) Převod SAT na 3-SAT
- Marešovy skripta strana 435
1)
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)
- https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm#Integral_example
2) Aho-Corasick, popis vyhledávacího algoritmu a důkaz složitosti
- Hricova prezentace strana 7, 9
3) 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)
4)
A) Definice - rozhodovací problém, polynomiální převoditelnost, P, NP, NPÚ
- Hricova prezentace strana 58, 59, 62
B) Převod SAT na 3-SAT
- Marešovy skripta strana 435