# **NTIN061** Algoritmy a datové struktury 2

<{Box(infobox)}>
|-----|-----|
| **Učitel:** | [Medvěd 🐻‍❄️ (Martin Mareš)](https://mj.ucw.cz/) |
| **Odkaz do SISu:** | [NTIN061](https://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=NTIN061) |
| **Diskuze:** | [Discord kanál](https://discord.com/channels/625428723302137876/758681949539008522) |
| **Stránka předmětu:** | [Web](https://mj.ucw.cz/vyuka/2526/ads2/) |
<{/Box}>

## Studijní materiály
### Skripta
- [Průvodce labyrintem algoritmů](https://pruvodce.ucw.cz/static/pruvodce.pdf)
- [Visualgo](https://visualgo.net/en)
- [Algovision](https://algovision.org/)
- [Dinicův algoritmus](https://www.youtube.com/watch?v=M6cm8UeeziI)
- [Ford–Fulkersonův algoritmus](https://www.youtube.com/watch?v=LdOnanfc5TM)

### Poznámky
- [Poznámky Kačky Doubkové](https://kahann.cz/notes/ads2/)
- [Poznámky Kuby Smolíka](https://couleslaw.github.io/mff-notes/03/ADS-2.pdf) - ručně psané

### Záznamy
- [Mareš 25/26 ](http://mj.ucw.cz/vyuka/2526/ads2/)
- [Mareš 23/24 ](http://mj.ucw.cz/vyuka/2324/ads2/)
- [Čepek 26/27 ](https://cunicz-my.sharepoint.com/:f:/g/personal/93077265_cuni_cz/IgBYBXHWTVbMQqDq_YnK-bNRAQmTDJbiS8ma_kRazSTkQ-s?e=rgCsfy) - za CAS loginem, stejným jako email

## Zakončení předmětu

### Zkoušky

- 2025/2026: [Medvěd otázky](https://mj.ucw.cz/vyuka/2526/ads2/zk.html)
- 2023/2024: [Medvěd otázky](https://mj.ucw.cz/vyuka/2324/ads2/zk.html)

<<ExamList()>>

## 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).
<{Details(Řešení)}>
Uvědomte si kam vedou zpětné hrany z koncových stavů
<{/Details}> 
- Je dáno seno a jehly. Pro každý znak sena najděte co nejdelší výskyt jehly, který tam začíná.
<{Details(Řešení)}>
Otočte si seno a jehly
<{/Details}>


#### 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í
<{Details(Řešení)}>
Toky
<{/Details}>
- 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.
<{Details(Řešení)}>
Koukněte na nenasycené hrany
<{/Details}>
- Mějme děravou šachovnici. Jak ji pokrýt kostkami 1x2 políčka?
<{Details(Řešení)}>
Toky
<{/Details}>
- 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.
<{Details(Řešení)}>
Zkuste si to setřídit
<{/Details}>
- 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.
<{Details(Řešení)}>
Prvek si umístěte doprostřed posloupnosti.
<{/Details}>

#### 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
<{Details(Řešení)}>
Udělejte si proměnnou $x_{i,j,k}$
<{/Details}>