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

13. 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. Převeďte 3D-párování na SAT.

13. 1 odpoledne

  1. Třídění pomocí komparátorů
  2. Mějme děravou šachovnici. Jak ji pokrýt kostkami 1× 2 políčka?
  3. Maximální tok v síti, jejíž hrany mají celočíselné kapacity mezi 0 a C.

15. 1 dopoledne

  1. Fourierova transformace: definice DFT, algoritmus FFT.
  2. Odčítání hradlovou sítí.
  3. 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í.

15. 1 odpoledne

  1. Průsečíky úseček.
  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. 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í?

20. 1 dopoledne

  1. Algoritmus Aho-Corasicková a jeho analýza
  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.

20. 1 odpoledne

  1. Dinicův algoritmus.
  2. Navrhněte hradlovou síť co nejmenší hloubky, která pro dvě n-bitová čísla rozhodne, zda je první menší než druhé.
  3. Převeďte obarvitelnost grafu třemi barvami na SAT.

22. 1 dopoledne

  1. Třídy P a NP. NP-úplné problémy. Převod nezávislé množiny na SAT.
  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. Pro zadané dva mnohoúhelníky zjistěte, zda jsou jejich vnitřky disjunktní.

22. 1 odpoledne

  1. Třídění pomocí komparátorů
  2. Najděte ve slovníku dvojici slov s co nejdelším překryvem (prefix jednoho slova je suffixem druhého; slovo se může překrývat i se sebou samým, ovšem pouze částí své délky).
  3. 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?

27. 1 dopoledne

  1. Goldbergův algoritmus
  2. Navrhněte hradlovou síť, která dostane posloupnost n bitů a rozhodne, zda v ní je stejně nul jako jedniček.
  3. Pro daný řetězec α najděte nejdelší řetězec β≠α takovy, že β je prefixem i suffixem řetězce α.

29. 1 dopoledne

  1. Průsečíky úseček.
  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í?

29. 1 odpoledne

  1. Fourierova transformace: definice DFT, algoritmus FFT.
  2. Navrhněte hradlovou síť na nalezení pozice nejlevějšího jedničkového bitu v posloupnosti N bitů.
  3. 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. 2 dopoledne

  1. Maximální tok a Fordův-Fulkersonův algoritmus.
  2. Latinský obdélník a×n rozšiřte na (a+1)×n.
  3. Najděte největší nezávislou množinu v intervalovém grafu.

Minulé roky

Stránku spravuje Martin Mareš