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 17:20 v S6.

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

30. 9. 2021
Organizace a opakování. Naivní hledání je pomalé. Hledání slova jako nesouvislého podřetězce. [Příklady]
7. 10. 2021
Algoritmus KMP a konstrukce zpětných hran. Detekce rotace a periodicity slova. Pěstujeme stromy. [Příklady]
14. 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]
21. 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]
4. 11. 2021
Toky v sítích. Dinicův algoritmus. Věže na šachovnici. [Příklady]
11. 11. 2021
Goldbergův algoritmus. Zaokrouhlení matice. [Příklady]
18. 11. 2021
Cvičil Jan Hric. Fourierova transformace. Fourierovy obrazy jednoduchých vektorů. [Příklady]
25. 11. 2021
Hradlové sítě. Počítání obecných booleovských funkcí, a proč potřebujeme velkou síť. Násobení dvou binárních čísel. Nalezení nejvyššího bitu. [Příklady]

Užitečné odkazy