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

<{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/)

## Zakončení předmětu
### Zkoušky

#### 2025/2026
- [Medvěd](https://mj.ucw.cz/vyuka/2526/ads2/zk.html)

#### 2023/2024
- [Medvěd](https://mj.ucw.cz/vyuka/2324/ads2/zk.html)

- [Zkouška Mareš 22.12. 2023](/NTIN061/Zkouška Mareš 22.12. 2023)
- [Zkouška Mareš 20.01. 2022](/NTIN061/Zkouška Mareš 20.01. 2022)
- [Zkouška Mareš 18.01. 2022](/NTIN061/Zkouška Mareš 18.01. 2022)
- [Zkouška Mareš 13.01. 2022](/NTIN061/Zkouška Mareš 13.01. 2022)
- [Zkouška Mareš 07.01. 2022](/NTIN061/Zkouška Mareš 07.01. 2022)
- [Zkouška Mareš 22.12. 2021](/NTIN061/Zkouška Mareš 22.12. 2021)
- [Zkouška Mareš 21.12. 2021](/NTIN061/Zkouška Mareš 21.12. 2021)
- [Zkouška Hubička 15.02. 2021](/NTIN061/Zkouška Hubička 15.02. 2021)
- [Zkouška Hubička 16.12. 2020](/NTIN061/Zkouška Hubička 16.12. 2020)
- [Zkouška Hubička 29.01. 2020](/NTIN061/Zkouška Hubička 29.01. 2020)
- [Zkouška Hubička 28.01. 2020](/NTIN061/Zkouška Hubička 28.01. 2020)
- [Zkouška Hubička 22.01. 2020](/NTIN061/Zkouška Hubička 22.01. 2020)
- [Zkouška Hubička 20.12. 2019](/NTIN061/Zkouška Hubička 20.12. 2019)
- [Zkouška Hubička 18.12. 2019](/NTIN061/Zkouška Hubička 18.12. 2019)
- [Zkouška Hubička 13.12. 2019](/NTIN061/Zkouška Hubička 13.12. 2019)
- [Zkouška Hubička 11.12. 2019](/NTIN061/Zkouška Hubička 11.12. 2019)
- [Zkouška Mareš 04.02. 2019](/NTIN061/Zkouška Mareš 04.02. 2019)
- [Zkouška Mareš 28.01. 2019](/NTIN061/Zkouška Mareš 28.01. 2019)
- [Zkouška Čepek 22.01. 2019](/NTIN061/Zkouška Čepek 22.01. 2019)
- [Zkouška Mareš 21.01. 2019](/NTIN061/Zkouška Mareš 21.01. 2019)
- [Zkouška Mareš 21.01. 2019 odpoledne](/NTIN061/Zkouška Mareš 21.01. 2019 odpoledne)
- [Zkouška Mareš 15.01. 2019](/NTIN061/Zkouška Mareš 15.01. 2019)
- [Zkouška Mareš 14.01. 2019](/NTIN061/Zkouška Mareš 14.01. 2019)
- [Zkouška Mareš 11.01. 2019](/NTIN061/Zkouška Mareš 11.01. 2019)
- [Zkouška Mareš 08.02. 2018](/NTIN061/Zkouška Mareš 08.02. 2018)
- [Zkouška Hric 07.02. 2018](/NTIN061/Zkouška Hric 07.02. 2018)
- [Zkouška Hric 01.02. 2018](/NTIN061/Zkouška Hric 01.02. 2018)
- [Zkouška Hric 25.01. 2018](/NTIN061/Zkouška Hric 25.01. 2018)
- [Zkouška Čepek 20.01. 2017](/NTIN061/Zkouška Čepek 20.01. 2017)
- [Zkouška Mareš 21.01. 2016](/NTIN061/Zkouška Mareš 21.01. 2016)
- [Zkouška Mareš 15.01. 2016](/NTIN061/Zkouška Mareš 15.01. 2016)
- [Zkouška Mareš 08.01. 2016](/NTIN061/Zkouška Mareš 08.01. 2016)
- [Zkouška Čepek 11.02. 2015](/NTIN061/Zkouška Čepek 11.02. 2015)
- [Zkouška Čepek 23.01. 2015](/NTIN061/Zkouška Čepek 23.01. 2015)
- [Zkouška Kučera 20.01. 2015](/NTIN061/Zkouška Kučera 20.01. 2015)
- [Zkouška Čepek 18.12. 2014](/NTIN061/Zkouška Čepek 18.12. 2014)
- [Zkouška Mareš 10.01. 2014](/NTIN061/Zkouška Mareš 10.01. 2014)
- [Zkouška Kučera 31.01. 2013](/NTIN061/Zkouška Kučera 31.01. 2013)
- [Zkouška Kučera 03.01. 2013](/NTIN061/Zkouška Kučera 03.01. 2013)
- [Zkouška Mareš 15.02. 2012](/NTIN061/Zkouška Mareš 15.02. 2012)
- [Zkouška Mareš 22.12. 2011](/NTIN061/Zkouška Mareš 22.12. 2011)
- [Zkouška Kučera 26.01. 2011](/NTIN061/Zkouška Kučera 26.01. 2011)
- [Zkouška Kučera 24.01. 2011](/NTIN061/Zkouška Kučera 24.01. 2011)
- [Zkouška Čepek 21.01. 2011](/NTIN061/Zkouška Čepek 21.01. 2011)
- [Zkouška Kučera 19.01. 2011](/NTIN061/Zkouška Kučera 19.01. 2011)
- [Zkouška Kučera 17.01. 2011](/NTIN061/Zkouška Kučera 17.01. 2011)
- [Zkouška Čepek 13.01. 2011](/NTIN061/Zkouška Čepek 13.01. 2011)
- [Zkouška Čepek 11.01. 2011](/NTIN061/Zkouška Čepek 11.01. 2011)
- [Zkouška Mareš 10.02. 2010](/NTIN061/Zkouška Mareš 10.02. 2010)
- [Zkouška Hric 08.02. 2010](/NTIN061/Zkouška Hric 08.02. 2010)
- [Zkouška Mareš 27.01. 2010](/NTIN061/Zkouška Mareš 27.01. 2010)
- [Zkouška Mareš 20.01. 2010](/NTIN061/Zkouška Mareš 20.01. 2010)
- [Zkouška Hric 11.02. 2009](/NTIN061/Zkouška Hric 11.02. 2009)
- [Zkouška Kučera 10.02. 2009](/NTIN061/Zkouška Kučera 10.02. 2009)
- [Zkouška Hric 03.02. 2009](/NTIN061/Zkouška Hric 03.02. 2009)
- [Zkouška Kučera 03.02. 2009](/NTIN061/Zkouška Kučera 03.02. 2009)
- [Zkouška Kučera 27.01. 2009](/NTIN061/Zkouška Kučera 27.01. 2009)
- [Zkouška Mareš 14.02. 2008](/NTIN061/Zkouška Mareš 14.02. 2008)
- [Zkouška Čepek 16.01. 2008](/NTIN061/Zkouška Čepek 16.01. 2008)
- [Zkouška Mareš 11.01. 2008](/NTIN061/Zkouška Mareš 11.01. 2008)
- [Zkouška Mareš 04.01. 2008](/NTIN061/Zkouška Mareš 04.01. 2008)
- [Zkouška Mareš 20.12. 2007 17:00](/NTIN061/Zkouška Mareš 20.12. 2007 17:00)
- [Zkouška Mareš 20.12. 2007 14:00](/NTIN061/Zkouška Mareš 20.12. 2007 14:00)
- [Zkouška Kučera 24.04. 2007](/NTIN061/Zkouška Kučera 24.04. 2007)
- [Zkouška Hric 13.02. 2007](/NTIN061/Zkouška Hric 13.02. 2007)
- [Zkouška Kučera 01.02. 2007](/NTIN061/Zkouška Kučera 01.02. 2007)
- [Zkouška Hric 31.01. 2007](/NTIN061/Zkouška Hric 31.01. 2007)
- [Zkouška Hric 25.01. 2007](/NTIN061/Zkouška Hric 25.01. 2007)
- [Zkouška Hric 06.08. 2006](/NTIN061/Zkouška Hric 06.08. 2006)
- [Zkouška Kučera 14.02. 2006](/NTIN061/Zkouška Kučera 14.02. 2006)
- [Zkouška Kučera 06.02. 2006](/NTIN061/Zkouška Kučera 06.02. 2006)
- [Zkouška Čepek 26.01. 2006](/NTIN061/Zkouška Čepek 26.01. 2006)
- [Zkouška Čepek 25.01. 2006](/NTIN061/Zkouška Čepek 25.01. 2006)


## 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}>