Zkoušky z ADS2

21. 12.

1. Spočítejte diskrétní Fourierovu transformaci vektoru (1,-1,1,-1,1,-1,1,-1).
2. Navrhněte hradlovou síť pro porovnání dvou n-bitových binárních čísel (výstupem je 1 právě tehdy, je-li první číslo menší než druhé).
3. Převeďte SAT na nezávislou množinu.
   (*) v grafech s maximálním stupněm 4.

4. 1.

1. Popište Goldbergův algoritmus, dokažte jeho správnost a rozeberte jeho implementaci a časovou složitost pro sítě s jednotkovými kapacitami.
2. Navrhněte komparátorovou síť s co nejmenší hloubkou pro zatřídění prvku do setříděné posloupnosti.
   (*) a dokažte, že má asymptoticky optimální hloubku.
3. Mějme předměty o velikostech x₁, …, x_n a tři přihrádky o kapacitě K. Vymyslete algoritmus, který zjistí, zda je možné předměty roztřídit do přihrádek tak, aby součet velikostí předmětů v každé přihrádce byl nejvýše K. Algoritmus by měl mít časovou složitost polynomiální v n a K.
   (*) dokažte, že bez omezení na K je tento problém NP-úplný.

11. 1.

1. Mějme (nekonvexní) mnohoúhelník, jehož vrcholy mají celočíselné souřadnice a hrany jsou rovnoběžné s osami souřadnic a je zadaný seznamem vrcholů při obcházení po směru hodinových ručiček. Vymyslete co nejefektivnější algoritmus, který spočítá jeho obsah.
2. Navrhněte hradlovou síť, která zjistí, zda je zadané n-bitové dvojkové číslo dělitelné třemi.
3. Popište Dinicův algoritmus, dokažte jeho spravnost a rozeberte časovou složitost.

17. 1.

1. Spočítejte diskrétní Fourierovu transformaci vektoru (1,i,-1,-i,1,i,-1,-i).
2. Je zadán slovník a text. Navrhněte algoritmus, který spočítá, kolikrát se které slovo vyskytuje v textu jako podřetězec.
3. Popište komparátorovou síť pro třídění.

24. 1.

1. Popište Goldbergův algoritmus, dokažte jeho správnost a rozeberte jeho časovou složitost.
2. Je následující problém řešitelný polynomiálně nebo NP-úplný? Je dána nula-jedničková matice A a celočíselný vektor b. Existuje nula-jedničkový vektor x takový, že Ax=b?
   (*) jak se problém změní, pokud vyžadujeme, aby b byl také 0-1?
3. 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.)

31. 1.

1. Navrhněte hradlovou síť polylogaritmické hloubky pro násobení dvou n-bitových čísel.
   (*) s hloubkou O(log n).
2. Popište aproximační schéma pro problém batohu.
3. Vymyslete polynomiální algoritmus pro nalezení minimálního vrcholového pokrytí bipartitního grafu (to je množina vrcholů, která má neprázdný průnik s každou hranou).

7. 2.

1. Spočítejte inverzní diskrétní Fourierovu transformaci vektoru (4,0,0,0,4,0,0,0).
2. Definujte Voroného diagram a popište algoritmus na jeho konstrukci.
3. Mějme zakořeněný uspořádaný (ZU) strom (u každého vrcholu je určeno pořadí jeho potomků). Osekání ZU stromu definujme tak, že vezmeme podstrom určený nějakým vrcholem a souvislým úsekem hran, které z něj vedou. Navrhněte co nejefektivnější algoritmus, který dostane dva ZU stromy A a B a rozhodne, zda je možno osekat strom A tak, aby vznikl strom B.

14. 2.

1. Je dán orientovaný graf a dva jeho vrcholy x, y. Vymyslete co nejefektivnější algoritmus, který zkonstruuje maximální možný počet vrcholově disjunktních cest z x do y.
2. Vymyslete lineární algoritmus, který pro dva řetězce rozhodne, zda je jeden rotací druhého.
3. Popište algoritmus Aho-Corasicková pro hledání podřetězců.
4. (*) Navrhněte hradlovou síť, která počítá tranzitivní uzávěr orientovaného grafu. (Na vstupu je matice sousednosti, na výstupu matice taková, že na pozici (i,j) je jednička právě tehdy, když v grafu existuje orientovaná cesta z vrcholu i do vrcholu j).