Zkouškové otázky z Algoritmů a datových struktur II
22. 12. (předtermín)
- Algoritmus Aho-Corasicková a jeho analýza
- Poslanci jsou členy mnoha různých komisí. Každé komisi chceme vybrat předsedu a tajemníka tak, aby žádný poslanec nezastával více funkcí.
- Převeďte 3D párování na SAT.
5. 1. (předtermín)
- Fourierova transformace a její aplikace
- Je dán text a slovník. Zjistěte pro každé slovo ve slovníku, kolikrát se v textu vyskytuje jako podřetězec.
- Navrhněte hradlovou síť, která dostane posloupnost n bitů a rozhodne, zda v ní je stejně nul jako jedniček.
12. 1. (předtermín)
- Goldbergův algoritmus
- Pro zadané N, abecedu a množínu jehel sestrojte řetězec délky N, který neobsahuje žádnou jehlu.
- Pro mnohoúhelníky A a B zjistěte, zda A je celý uvnitř B.
16. 1 dopoledne
- Průsečíky úseček.
- Najděte v daném bipartitním grafu co nejmenší vrcholové pokrytí (to je množina vrcholů, se kterou se protne každá hrana). Hint: toky.
- Navrhněte komparátorovou síť pro zatřídění prvku do setříděné posloupnosti.
16. 1 odpoledne
- Maximální tok a Fordův-Fulkersonův algoritmus.
- Cenzor (cvičení 13.3.10 z Průvodce)
- Dokažte, že problém Nezávislá množina zůstane NP-úplný, pokud ho omezíme na grafy s vrcholy stupně nejvýše 4.
18. 1. dopoledne
- Dinicův algoritmus.
- Vymyslete pseudopolynomiální algoritmus pro {\sit problém tří loupežníků:} Dostaneme posloupnost přirozených čísel, lze ji rozdělit na 3 části se stejným součtem?
- Navrhněte hradlovou síť co nejmenší hloubky, která pro dvě n-bitová čísla rozhodne, zda je první menší než druhé.
18. 1. dopoledne
- Algoritmus Aho-Corasicková.
- 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.
- Převeďte 3D-párování na SAT.
23. 1 dopoledne
- Sčítání hradlovou sítí.
- Mějme děravou šachovnici. Jak ji pokrýt kostkami 1× 2 políčka?
- V daném řetězci nad abecedou {a,b} chceme nalézt nejdelší Fibonacciho podslovo. Fibonacciho slova jsou definována takto: F1=a, F2=b, Fn+2=FnFn+1.
- (*) V daném řetězci nad obecnou abecedou chceme najít co nejdelší podslovo isomorfní s nějakým Fibonacciho slovem (tedy stejné až na přejmenování abecedy).
23. 1 odpoledne
- Třídy P a NP, NP-úplnost.
- Jsou dány množiny bodů v rovině: červené a zelené. Sestrojte přímku takovou, aby na jedné její straně ležely všechny červené body, zatímco na druhé všechny zelené.
- Najděte pro daný řetězec co nejdelší podřetězec, který je současně prefixem i suffixem (vlastním).
25. 1 dopoledne
- Goldbergův algoritmus.
- Je dáno seno a jehly. Pro každý znak sena najděte co nejdelší výskyt jehly, který tam začíná.
- Implementujte pomocí booleovských hradel komparátor n-bitových čísel.
25. 1 odpoledne
- Fourierova transformace.
- Maximální tok v síti, jejíž hrany mají celočíselné kapacity mezi 0 a C.
- Najděte největší nezávislou množinu v intervalovém grafu.
30. 1 dopoledne
- Třídění pomocí komparátorů
- Je dán mnohoúhelník v rovině (ne nutně konvexní). Spočítejte jeho obsah.
- Maximální tok v síti, jejíž hrany mají celočíselné kapacity mezi 0 a C.
30. 1 odpoledne
- Problém batohu: formulace, pseudo-polynomiální algoritmus, aproximační schéma.
- Je dán mnohoúhelník v rovině (ne nutně konvexní). Najděte nejdelší vodorovnou úsečku, která leží celá uvnitř něj.
- Máme šachovnici N×N bez některých políček. Na zbývající políčka chceme rozestavět co nejvíce šachových věží tak, aby se žádné dvě neohrožovaly.
1. 2 dopoledne
- Dinicův algoritmus.
- Je dáno seno a jehly. Pro každý znak sena najděte co nejdelší výskyt jehly, který tam začíná.
- Jak se změní obtížnost problemu Nezávislá množina, pokud ho omezíme na grafy s vrcholy stupně nejvýše 4, případně 2. Bude stále NP-úplný, nebo už polynomiální?
1. 2 odpoledne
- Sčítání hradlovou sítí.
- Je dáno seno a jehly. Pro každou jehlu spočítejte, kolikrát se vyskytuje v seně. Snažte se o lineární časovou složitost vzhledem k velikosti vstupu, nezávisle na počtu výskytů.
- Převeďte obarvitelnost grafu třemi barvami na SAT.
6. 2 dopoledne
- Problém batohu: formulace, pseudo-polynomiální algoritmus, aproximační schéma.
- V daném řetězci nad abecedou {a,b} chceme nalézt nejdelší Fibonacciho podslovo. Fibonacciho slova jsou definována takto: F1=a, F2=b, Fn+2=FnFn+1.
- Navrhněte hradlovou síť na nalezení pozice nejlevějšího jedničkového bitu v posloupnosti N bitů.
6. 2 odpoledne
- Dinicův algoritmus.
- Najděte ve slovníku dvojici slov s co nejdelším překryvem (prefix jednoho slova je suffixem druhého).
- Odčítání hradlovou sítí.
8. 2 odpoledne
- Fourierova transformace.
- V rovině je S svišťů a D děr. Přiřaďte každému svišti jinou díru vzdálenou nejvýše δ.
- Navrhněte komparátorovou síť pro zatřídění prvku do setříděné posloupnosti.
13. 2 dopoledne
- Průsečíky úseček.
- Najděte v daném řetězci nejdelší palindromický prefix.
- Převeďte 3D-párování na SAT.
13. 2 odpoledne
- Třídění pomocí komparátorů
- Je dáno seno a jehly. Pro každou jehlu spočítejte, kolikrát se vyskytuje v seně. Snažte se o lineární časovou složitost vzhledem k velikosti vstupu, nezávisle na počtu výskytů.
- Ukažte, že pokud umíte najít konvexní obal množiny n bodů v rovině v čase T(n), jde setřídit n reálných čísel v čase O(T(n) + n).
15. 2 dopoledne
- Algoritmus Aho-Corasicková a jeho analýza
- Najděte nejmenší řez v daném souvislém neorientovaném grafu (řezem myslíme množinu hran, jejímž odebráním se graf stane nesouvislým).
- Implementujte pomocí booleovských hradel komparátor n-bitových čísel.