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á v úterý od 09:00 v S11.

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

Co jsme dělali

29. 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 1-4]
13. 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]
20. 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]
27. 10. 2020
Toky v sítích. Ford-Fulkersonův a Dinicův algoritmus. Hledání hranově a vrcholově disjunktních cest. [Příklady 1-4]
3. 11. 2020
Goldbergův algoritmus a jeho analýza. Další aplikace toků. [Příklady]
10. 11. 2020
Třídící sítě. Hledání maxima a dotřiďování prvku. [Příklady]
24. 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]
1. 12. 2020
Fourierova transformace. Fourierovy obrazy jednoduchých vektorů. [Příklad 1]
8. 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]
15. 12. 2020
Převody mezi různými problémy. [Příklady 1-2]
22. 12. 2020
Jak se vypořádat s těžkými problémy. Omezené vstupy a aproximace. [Příklady]
5. 1. 2021
Geometrické algoritmy. Konvexní obal a hledání průsečíků úseček. [Příklady 1-2]

Domácí úkoly

Úkoly odevzdávejte na Moodlu, čas odevzdání je obvykle do úterý 01:00. Pokud je to alespoň trochu možné, neodevzdávejte, prosím, naskenované ruční řešení (ideálně sázejte v $\LaTeX \text{u}$).

Užitečné odkazy