Zkouškové otázky z Algoritmů a datových struktur II

22. 12. (předtermín)

  1. Algoritmus Aho-Corasicková a jeho analýza
  2. 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í.
  3. Převeďte 3D párování na SAT.

5. 1. (předtermín)

  1. Fourierova transformace a její aplikace
  2. 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.
  3. 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)

  1. Goldbergův algoritmus
  2. Pro zadané N, abecedu a množínu jehel sestrojte řetězec délky N, který neobsahuje žádnou jehlu.
  3. Pro mnohoúhelníky A a B zjistěte, zda A je celý uvnitř B.

16. 1 dopoledne

  1. Průsečíky úseček.
  2. 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.
  3. Navrhněte komparátorovou síť pro zatřídění prvku do setříděné posloupnosti.

16. 1 odpoledne

  1. Maximální tok a Fordův-Fulkersonův algoritmus.
  2. Cenzor (cvičení 13.3.10 z Průvodce)
  3. 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

  1. Dinicův algoritmus.
  2. 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?
  3. Navrhněte hradlovou síť co nejmenší hloubky, která pro dvě n-bitová čísla rozhodne, zda je první menší než druhé.

18. 1. dopoledne

  1. Algoritmus Aho-Corasicková.
  2. 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.
  3. Převeďte 3D-párování na SAT.

23. 1 dopoledne

  1. Sčítání hradlovou sítí.
  2. Mějme děravou šachovnici. Jak ji pokrýt kostkami 1× 2 políčka?
  3. 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.
  4. (*) 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

  1. Třídy P a NP, NP-úplnost.
  2. 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é.
  3. Najděte pro daný řetězec co nejdelší podřetězec, který je současně prefixem i suffixem (vlastním).

25. 1 dopoledne

  1. Goldbergův algoritmus.
  2. Je dáno seno a jehly. Pro každý znak sena najděte co nejdelší výskyt jehly, který tam začíná.
  3. Implementujte pomocí booleovských hradel komparátor n-bitových čísel.

25. 1 odpoledne

  1. Fourierova transformace.
  2. Maximální tok v síti, jejíž hrany mají celočíselné kapacity mezi 0 a C.
  3. Najděte největší nezávislou množinu v intervalovém grafu.

30. 1 dopoledne

  1. Třídění pomocí komparátorů
  2. Je dán mnohoúhelník v rovině (ne nutně konvexní). Spočítejte jeho obsah.
  3. Maximální tok v síti, jejíž hrany mají celočíselné kapacity mezi 0 a C.

30. 1 odpoledne

  1. Problém batohu: formulace, pseudo-polynomiální algoritmus, aproximační schéma.
  2. Je dán mnohoúhelník v rovině (ne nutně konvexní). Najděte nejdelší vodorovnou úsečku, která leží celá uvnitř něj.
  3. 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

  1. Dinicův algoritmus.
  2. Je dáno seno a jehly. Pro každý znak sena najděte co nejdelší výskyt jehly, který tam začíná.
  3. 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

  1. Sčítání hradlovou sítí.
  2. 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ů.
  3. Převeďte obarvitelnost grafu třemi barvami na SAT.

6. 2 dopoledne

  1. Problém batohu: formulace, pseudo-polynomiální algoritmus, aproximační schéma.
  2. 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.
  3. Navrhněte hradlovou síť na nalezení pozice nejlevějšího jedničkového bitu v posloupnosti N bitů.

6. 2 odpoledne

  1. Dinicův algoritmus.
  2. Najděte ve slovníku dvojici slov s co nejdelším překryvem (prefix jednoho slova je suffixem druhého).
  3. Odčítání hradlovou sítí.

8. 2 odpoledne

  1. Fourierova transformace.
  2. 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 δ.
  3. Navrhněte komparátorovou síť pro zatřídění prvku do setříděné posloupnosti.

13. 2 dopoledne

  1. Průsečíky úseček.
  2. Najděte v daném řetězci nejdelší palindromický prefix.
  3. Převeďte 3D-párování na SAT.

13. 2 odpoledne

  1. Třídění pomocí komparátorů
  2. 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ů.
  3. 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

  1. Algoritmus Aho-Corasicková a jeho analýza
  2. 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).
  3. Implementujte pomocí booleovských hradel komparátor n-bitových čísel.

Minulé roky

Stránku spravuje Martin Mareš