Algoritmy a datové struktury II

Cvičení k přednášce Algoritmy a datové struktury II [NTIN061] v zimním semestru 2021/2022. Probíhá ve středu od 12:20 v S10.

Požadavky na zápočet

Domácí úkoly

Domácí úkoly můžete řešit kolektivně, ale řešení musí každý zformulovat a sepsat sám za sebe. Nápadně podobná řešení budou podrobena bližšímu zkoumání.

Řešením domácího úkolu se myslí navrhnutí algoritmu nebo dokázání nějakého tvrzení. Důkaz by měl být korektní, srozumitelný a přehledný. Tvrzení a algoritmy z přednášky můžete používat bez důkazu. Hezký návod jak psát domácí úkoly sepsal Václav Končický.

Úkoly preferuji psané na počítači, pokud možno ve fomátu PDF (ideálně sázejte v $\LaTeX \text{u}$), v případě rukou psaných řešení odevzdávaných digitálně použijte scan nebo kvalitní fotku (existuje spousta skenovacích aplikací pro Android i iPhone). Pro lehké začátky s $\LaTeX\text{em}$ můžete vyzkoušet hackmd.io (Markdown + $\LaTeX$), pokud byste měli problém rozchodit $\LaTeX$ u sebe můžete vyzkoušet overleaf.com.

Co jsme dělali

29. 9. 2021
Organizace a opakování. Naivní hledání je pomalé. Hledání slova jako nesouvislého podřetězce. [Příklady]
6. 10. 2021
Algoritmus KMP a konstrukce zpětných hran. Detekce rotace a periodicity slova. Pěstujeme stromy. [Příklady]
13. 10. 2021
Algoritmus AC a co je navíc v konstrukci automatu oproti KMP. Proč časová složitost závisí na počtu výskytů, k čemu slouží zkratkové hrany a proč nestihneme předpočítat množiny slov k ohlášení. Frekvence slov a hledání ve 2D. [Příklady 1-6]
20. 10. 2021
Algoritmus Rabin-Karp a jeho aplikace na hledání v textu. Toky v sítích a Ford-Fulkersonův algoritmus na hledání maximálního toku. Použití toků na hledání hranově a vrcholově disjunktních cest. [Příklady 1-6]
27. 10. 2021
Toky v sítích. Dinicův algoritmus. Věže na šachovnici. [Příklady]
3. 11. 2021
Cvičení odpadlo z důvodu nemoci.
10. 11. 2021
Goldbergův algoritmus. Zaokrouhlení matice. [Příklady]
21. 11. 2021
Fourierova transformace. Fourierovy obrazy jednoduchých vektorů. [Příklady]

Užitečné odkazy