Zkoušky z ADS2

15. 1 dopoledne.

  1. Goldbergův algoritmus a jeho implementace.
  2. Najděte pro daný řetězec co nejdelší podřetězec, který je současně prefixem i suffixem (vlastním).
  3. 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é.

15. 1. odpoledne

  1. Rychlá Fourierova transformace.
  2. Mějme děravou šachovnici. Jak ji pokrýt kostkami 1× 2 políčka?
  3. Je dána množina bodů v rovině. Oploťte ji dvěma uzavřenými ploty tak, aby celková spotřeba pletiva byla minimální.

22. 1. dopoledne

  1. Průsečíky úseček.
  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.
  4. (*) Zesilme definici 3,3-SATu tak, že každá klauzule obsahuje právě 3 různé proměnné a každá proměnná se nachází v právě 3 klauzulích. Dokažte, že o NP-úplnost přijdeme pozoruhodným způsobem, totiž tak, že každá formule bude splnitelna.

22. 1. odpoledne

  1. Sčítání čísel hradlovou sítí.
  2. Pro daný neorientovaný graf chceme nalézt největší k takové, že graf je hranově k-souvislý.
  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).

28. 1.

  1. Problém batohu: pseudopolynomiální algoritmus a aproximační schéma.
  2. Jsou dány dva mnohoúhelníky. Protínají se (ne nutně hranicí)?
  3. Implementujte pomocí booleovských hradel komparátor n-bitových čísel.
  4. (*) U úlohy 2 průnik i sestrojte.

6. 2.

  1. Dinicův algoritmus.
  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 hradlovou síť, která testuje, zda se v n-bitové posloupnosti vyskytuje nějaký pevný vzorek. Výstupem nechť je ano/ne.
  4. (*) Navrhněte dynamickou datovou strukturu pro vyhledávání v textu. Jehla je pevná, v seně lze průběžně měnit jednotlivé znaky a struktura má odpovídat, zda se v seně právě vyskytuje jehla.

12. 2.

  1. Algoritmus Aho-Corasicková.
  2. Je dán neorientovaný graf a číslo k. Zjistěte, zda graf je vrcholově k-souvislý.
  3. Vymyslete pseudopolynomiální algoritmus pro "problém tří loupežníků": Je dána posloupnost přirozených čísel, lze ji rozdělit na 3 části se stejným součtem?
  4. (*) Navrhněte datovou strukturu, která dostane množinu obdélníků v rovině (v osové poloze) a bude umět rychle odpovídat na dotazy typu "v kolika obdélnících z množiny se nachází tento bod?".
Stránku spravuje Martin Mareš