Algoritmy a datové struktury II

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

Průběh virtuálního cvičení

V čase dle rozvrhu se sejdeme virtuálně skrz platformu Zoom. Odkaz, který zůstává po celý semestr stejný, jsem posílal emailem. Pakliže se vám ztratí, ozvěte se a já ho pošlu znovu. Do místnosti se bude dát připojit již před oficálním začátkem cvičení.

Cvičení bude probíhat obdobně jako prezenčně - na začátku si trochu zopakujeme potřebnou látku z přednášky, poté budete řešit úlohy ve skupinkách po 3-4 studentech a na konci si pak společně zrekapitulujeme řešení. Zadání úloh zveřejním se začátkem cvičení na webu. Pokud se nemůžete zúčastnit virtuálního cvičení, velmi doporučuji zamyslet se nad úlohami samostatně.

Pokud si s čímkoliv nebudete vědět rady, budete tápat nebo jen chtít popostrčit správným směrěm, neváhejete se ozvat. Rád odpovím na dotazy mailem, na Discordu nebo cokoliv (do)vysvětlím ať už individuálně nebo skupinově na Zoomu.

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í 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. 2020
Organizace a opakování. Naivní hledání je pomalé. Hledání slova jako nesouvislého podřetězce. [Příklady]
6. 10. 2020
Algoritmus KMP a konstrukce zpětných hran. Detekce rotace a periodicity slova. Pěstujeme stromy. [Příklady]
14. 10. 2020
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í. [Příklady 1-4]
21. 10. 2020
Algoritmus Rabin-Karp a jeho aplikace na hledání v textu. Jak spočítat výskyty v lineárním čase a hledání ve dvou dimenzích. [Příklady 1-4]
4. 11. 2020
Toky v sítích. Ford-Fulkersonův a Dinicův algoritmus. Hledání hranově a vrcholově disjunktních cest. Věže na šachovnici. [Příklady 1-6]
11. 11. 2020
Goldbergův algoritmus a jeho analýza. Další aplikace toků. [Příklady]
18. 11. 2020
Třídící sítě. Hledání maxima a dotřiďování prvku. [Příklady]
25. 11. 2020
Hradlové sítě. Počítání obecné boolevoské funkce a proč nám nestačí malá síť. Sčítání a násobení. [Příklady 1-5]
2. 12. 2020
Fourierova transformace. Fourierovy obrazy jednoduchých vektorů. [Příklad 1]
9. 12. 2020
Pokračování Fourierovy transformace. Intuice za souvislostí se spektrálním rozkladem. Inverzní Fourierova transformace. Úvod do rozhodovacích problémů a složitosti. [Příklady 1-6]
16. 12. 2020
Převody mezi různými problémy. [Příklady 1-2]

Užitečné odkazy