NTIN061 Algoritmy a datové struktury II

Skripta

• Průvodce labyrintem algoritmů

• Visualgo

• Algovision

• Dinicův algoritmus

• Ford–Fulkersonův algoritmus

Poznámky

• Poznámky Kačky Doubkové

• Poznámky Kuby Smolíka - ručně psané

Záznamy

• Mareš 25/26

• Mareš 23/24

Zkoušky

2025/2026

• Medvěd

2024/2025

2023/2024

• Medvěd

Marešovy teoretické otázky

Vyhledávání v textu

• Algoritmus Aho–Corasicková a jeho analýza

Toky v sítích

• Maximální tok a Fordův–Fulkersonův algoritmus

• Dinicův algoritmus

• Goldbergův algoritmus

Fourierova transformace / Násobení polynomů

• Fourierova transformace a její aplikace

Hradlové sítě

• Sčítání hradlovou sítí

• Třídění pomocí komparátorů

Geometrické algoritmy

• Průsečíky úseček

NP problémy

• Třídy P a NP, NP-úplnost

• Problém batohu: formulace, pseudo–polynomiální algoritmus, aproximační schéma

Marešovy praktické otázky

Vyhledávání v textu

• 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.

• Pro zadané $N$, abecedu a množinu jehel sestrojte řetězec délky $N$, který neobsahuje žádnou jehlu.

• V daném řetězci nad abecedou {$a$,$b$} chceme nalézt nejdelší Fibonacciho podslovo. Fibonacciho slova jsou definována takto: $F_1=a$, $F_2=b$, $F_{n+2}=F_n F_{n+1}$.

• Najděte pro daný řetězec co nejdelší podřetězec, který je současně prefixem i sufixem (vlastním).

• Je dáno seno a jehly. Pro každý znak sena najděte co nejdelší výskyt jehly, který tam začíná.

Toky v sítích

• 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í

• 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.

• Mějme děravou šachovnici. Jak ji pokrýt kostkami 1x2 políčka?

• 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 $δ$.

Hradlové sítě

• Navrhněte hradlovou síť, která dostane posloupnost $n$ bitů a rozhodne, zda v ní je stejně nul jako jedniček.

• Navrhněte hradlovou síť co nejmenší hloubky, která pro dvě $n$-bitová čísla rozhodne, zda je první menší než druhé.

• 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.

• Implementujte pomocí booleovských hradel komparátor $n$-bitových čísel.

• Navrhněte hradlovou síť na nalezení pozice nejlevějšího jedničkového bitu v posloupnosti $N$ bitů.

• Odčítání hradlovou sítí.

• Navrhněte komparátorovou síť pro zatřídění prvku do setříděné posloupnosti.

Geometrické algoritmy

• Pro mnohoúhelníky $A$ a $B$ zjistěte, zda $A$ je celý uvnitř $B$.

• 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é.

• Je dán mnohoúhelník v rovině (ne nutně konvexní). Spočítejte jeho obsah.

• Je dán mnohoúhelník v rovině (ne nutně konvexní). Najděte nejdelší vodorovnou úsečku, která leží celá uvnitř něj.

NP problémy

• 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$.

• Vymyslete pseudopolynomijální algoritmus pro problém tří loupežníků - dostaneme posloupnost přirozených čísel, lze ji rozdělit na $3$ části se stejným součtem?

• Převeďte obarvitelnost grafu třemi barvami na SAT.

• Najděte největší nezávislou množinu v intervalovém grafu.

• Jak se změní obtížnost problému 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í?

• 3D párování -> SAT