Zkoušky z ADS2

20. 1.

1. Algoritmus RSA.
2. Rabinův-Karpův algoritmus.
3. Jsou dány dva pěstované stromy, zjistěte, jestli je jeden podstromem druhého. (Definice: pěstovaný strom má určen kořen a v každém vrcholu pořadí jeho synů; podstrom je určen vrcholem a obsahuje všechny jeho potomky.)
4. Mějme posloupnost N dominových kostek, na každé jsou dvě čísla v rozsahu 0 až T – horní a dolní číslo. Určete, které kostky otočit (prohodit horní a dolní číslo), aby se součet všech horních a všech dolních čísel lišily co nejméně.

27. 1.

1. Goldbergův algoritmus (formulace a každý svou část analýzy).
2. Spočítejte diskrétní Fourierovu transformaci vektoru (2,1,2,1,2,1,2,1).
3. Navrhněte hradlovou síť, která dostane dvě N-bitová binární čísla A a B a rozhodne, zda A>B.
4. Rozhodněte, zda je následující problém v P nebo NP-úplný: "Je dán graf, jehož všechny vrcholy mají stupeň nejvýše 4, a číslo K. Existuje v grafu nezávislá množina o alespoň K vrcholech?"

3. 2.

1. Algoritmus Aho-Corasicková pro vyhledávání v textu.
2. 2-aproximace problému obchodního cestujícího.
3. Je dána množina parabol tvaru y=ax²+bx+c, kde a>0. Nalezněte jejich průsečíky.
   (*) Co když může být koeficient a také záporný?
4. Nalezněte polynomiální algoritmus pro následující problém: Mějme šachovnici m×n s některými políčky děravými. Lze ji pokrýt kostkami 1×2 tak, aby kostky nezasahovaly do děr a všechna ostatní políčka byla pokryta právě jednou kostkou? (Kostky je možno otáčet.)

10. 2.

1. Dinicův algoritmus.
2. Definice: třídy P a NP, NP-úplné problémy. Cookova věta.
3. Navrhněte komparátorovou síť pro zatřídění jednoho prvku do setříděné poslopnosti.
4. Je dán text a číslo K. Nalezněte podřetězec délky K, který se v textu vyskytuje nejčastěji.
5. (*) Spočtěte 2↑n mod 13 (přičemž 2↑1=2, 2↑(n+1) = 2^2↑n).

17. 2.

1. Problém batohu: pseudopolynomiální algoritmus a aproximační schéma.
2. Spočítejte diskrétní Fourierovu transformaci vektoru (i,-1,-i,1,i,-1,-i,1).
3. Algoritmus na výpočet obsahu n-úhelníku (ne nutně konvexního).
4. Ukažte, jak převést SAT na řešitelnost soustavy kvadratických rovnic (polynomy stupně 2 v libovolně mnoha proměnných, řešitelnost v reálných číslech).

9. 4.

1. Goldbergův algoritmus.
2. Rabinův-Karpův algoritmus.
3. Jsou dány dva řetězce. Zjistěte, zda je jeden rotací druhého.
4. Je dáno N množin bodů v rovině. Zjistěte, zda jsou jejich konvexní obaly disjunktní.
5. (*) Spočtěte kombinační číslo "n nad k" modulo 42.