Zkoušky z ADS2

23. 12.

1. Goldbergův algoritmus.
2. Uvažujme problém "Je dána soustava lineárních rovnic v celých číslech. Existuje vektor složený z nul a jedniček, který ji řeší?" Dokažte, že tento problém je NP-úplný.
3. Náhrdelník je cyklický řetězec, který nemá určený ani začátek, ani směr čtení. Jak rozhodnout, zda jsou si dva náhrdelníky rovny?
4. (*) Je dáno více náhrdelníků, rozdělte je na ekvivalenční třídy.

13. 1.

1. Násobení polynomů pomocí Fourierovy transformace.
2. Hradlová síť, která o dvojici binárních čísel zjistí, zda je první větší než druhé.
3. Hledání největší nezávislé množiny v intervalovém grafu (to je graf, jehož vrcholy jsou intervaly a hrany spojují dvojice intervalů mající neprázdný průnik).

18. 1. dopoledne

1. Třídící sítě.
2. Je dán slovník a text. Navrhněte algoritmus, který pro každé slovo ze slovníku spočte, kolikrát se v textu vyskytuje jako podřetězec.
3. Mějme strom, jehož vrcholy jsou opatřeny celočíselnými vahami. Chceme nalézt nezávislou množinu, jejíž součet vah je největší možný.
4. (*) Uvažujme funkci f(x) = a sin(kx) + b cos(lx) navzorkovanou v N bodech rovnoměrně rozmístěných v intervalu [0,2π). Jak z vektoru vzorků poznat hodnoty a, b, k, l?

18. 1. dopoledne

1. NP-úplnost 3D-párování.
2. Jak zjistit, jestli je zadaný řetězec periodický? Tedy zda pro daný řetězec α existuje řetězec β a číslo k>1 tak, že α = β^k.
3. Je dán orientovaný graf a jeho vrcholy u, v. Chceme nalézt co nejvíce hranově disjunktních cest z u do v.
4. (*) Stejně jako dopoledne.

25. 1. dopoledne

1. NP-úplnost: definice tříd, Cookova věta, důkaz NP-úplnosti vybraného problému.
2. Mějme děravou šachnovnici. Jak ji pokrýt co nejvíce kostkami 1× 2 políčka?
3. Najděte pro daný řetězec co nejdelší podřetězec, který je současně prefixem i suffixem (vlastním).

1. 2. dopoledne

1. Problém batohu – pseudopolynomiální algoritmus a aproximační schéma.
2. Jak nalézt průsečíky zadaných parabol (tvaru ax²+bx+c pro a>0)?
   (*) Bez omezení na a.
3. Definujme permanent matice stejně jako determinant, ale bez znaménkového pravidla (všechny členy přispívají kladně). Chceme pro danou nula-jedničkovou matici zjistit, zda má nenulový permanent.

1. 2. odpoledne

1. Algoritmus na nalezení všech průsečíků zadaných úseček.
2. Jak nalézt průsečíky zadaných parabol (tvaru ax²+bx+c pro a>0)?
3. Je dán řetězec a číslo K. Který podřetězec délky K je nejčetnější?
4. (*) Je dána množina bodů v rovině. Lze ji rozdělit na dvě disjuktní středově symetrické podmnožiny?

10. 2. dopoledne

1. Algoritmus Knuth-Morris-Pratt.
2. Nalezněte polynomiální algoritmus, který v daném bipartitním grafu najde nejmenší vrcholové pokrytí.
3. Navrhněte hradlovou síť pro výpočet dvojkového logaritmu (jinými slovy nalezení pozice nejlevější jedničky ve dvojkovém čísle).
4. (*) V daném řetězci nad abecedou {a,b} chceme nalézt nejdelší Fibonacciho podslovo. Fibonacciho slova jsou definována takto: F₁=a, F₂=b, F_n+2=F_nF_n+1.

10. 2. odpoledne

1. Goldbergův algoritmus a jeho chování pro jednotkové kapacity.
2. Uvažujme problém nezávislé množiny v grafech s maximálním stupněm 4 resp. 2. Rozhodněte, zda tento problém patří do P nebo je NP-úplný.
3. Navrhněte algoritmus, který pro dva zadané (ne nutně konvexní) mnohoúhelníky zjistí, zda mají nějaký společný bod.
4. (*) Dokažte, že vektor y, který je diskrétní Fourierovou transformací n-složkového reálného vektoru, platí, že y_j a y_n-j jsou komplexně sdružené (pro všechna j).

15. 2. dopoledne

1. NP-úplnost: definice tříd, Cookova věta, důkaz NP-úplnosti vybraného problému.
2. Navrhněte algoritmus, který pro zadaný mnohoúhelník (ne nutně konvexní) najde nejdelší úsečku rovnoběžnou s osou x, která je v něm obsažená.
3. Jak zjistit, jestli je zadaný řetězec periodický? Tedy zda pro daný řetězec α existuje řetězec β a číslo k>1 tak, že α = β^k.
4. (*) Jsou dány permutace α a β na množině {1,…n}. Existuje k takové, že α = β^k? (Mocněním permutace se myslí k-násobné složení se sebou samou.)

15. 2. odpoledne

1. Dinicův algoritmus
2. Hradlová síť, která o dvojici binárních čísel zjistí, zda je první větší než druhé.
3. Jsou dány Fourierovy obrazy dvou vektorů. Jak podle nich rozhodnout, zda je jeden vektor rotací druhého?
4. (*) Stejně jako dopoledne.