Cvičení z Algoritmů a datových struktur II
čtvrtek od 15:40 v S7, ZS 22/23
K přednášce Algoritmy a datové struktury II Jana Hrice vedu cvičení, na kterém se zaměříme na procvičení a hlubší porozumění probírané látky formou řešení příkladů.
Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte při/po cvičení. Také budu rád, když se v průběhu cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se prosím mi emailem.
Co jsme dělali
| 29. 9. | Opakování ADS 1 (asymptotická složitost, rekurence časové složitosti a amortizace). Příklady (stihli jsme probrat první tři, část dalších příště). |
| 6. 10. | Vyhledávání jehly (řetězce) v kupce sena (textu) pomocí KMP automatu. Příklady (prošli jsme prvních pět). První úkol zadán v Sově (pokud nemáte přistupový token, napište mi). |
| 13. 10. | Vyhledávání více jehel (řetězců) v kupce sena (textu) pomocí automatu Aho-Corasickové. Příklady (prošli jsme prvních šest příkladů). |
| 20. 10. | Rabin-Karpův algoritmus a úvod do toků v sítích (Ford-Fulkersonův algoritmus). Příklady (prošli jsme prvních pět příkladů, zbytek bude příště). |
| 27. 10. | Toky v sítích a Dinicův algoritmus. Příklady (prošli jsme první čtyři příklady, pátý ještě necháme na příště). |
| 3. 11. | Toky v sítích a Goldbergův algoritmus. Příklady (probráno vrcholové pokrytí v bipartitním grafu z minula a příklady 1, 2 a 5). Zaskočil M. Koutecký. |
| 10. 11. | Booleovské obvody a třídící sítě. Příklady (probrali jsme první čtyři, násobení je vysvětlené v Průvodci labyrintem algoritmů) |
| 17. 11. | Státní svátek. |
| 24. 11. | Diskrétní Fourierova transformace. Příklady (probrali jsme první čtyři) |
| 1. 12. | Diskrétní Fourierova transformace a její použití na spektrální rozklad, tedy aproximaci funkce navzorkované v n bodech pomocí sumy sinů a cosinů; viz učebnice Průvodce labyrintem algoritmů (sekce 17.4). Příklady: dodělali jsme příklad 5 z minula a počítali Fourierovy obrazy vektorů pro navzorkované siny a cosiny (viz Lemma V v učebnici). |
| 8. 12. | P, NP, NP-těžkost, NP-úplnost a polynomiální převody problémů. Příklady, stihli jsme 1.a) až d), zbytek příště (alespoň z části). |
| 15. 12. | Polynomiální převody problémů: řešení příkladů z minula (kromě 1.g a 3.d, lineární algoritmus nad 2-SAT je popsaný třeba na Wikipedii) Úvod do aproximačních algoritmů (příklady budou příště). |
| 22. 12. | Aproximační algoritmy: 2-aproximace pro MaxCut a MaxSAT hladově i pravděpodobnostně. Pseudopolynomiální algoritmus pro batoh (popsán i v Průvodci). Příklady (probrali jsme první tři) |
| 5. 1. | Geometrické algoritmy a zametání roviny přímkou. Příklady (probrali jsme první čtyři) |
Podmínky zápočtu
Zápočet bude za 2/3 bodů ze standardních úkolů (budou zadány i bonusové). Na každý úkol (typicky algoritmickou úlohu) je čas cca 13 dní, tj. do začátku cvičení za dva týdny. I poté je možné řešení odevzdat, jen dostanete max. polovinu bodů (ale zase vám mohu poskytnout nějakou nápovědu). Úkoly jsou zadávány a odevzdávají se přes Sovu; pokud nemáte přístupový token, dejte mi vědět (pokud byste chtěli odevzdávat na papíře před cvičením, mohlo by to být také možné). Nebudete-li mít na konci semestru dostatek bodů, ale nějaké přece (alespoň polovinu), můžeme se dohodnout na zápočtovém programu (tj. implementaci nějakého algoritmu).
Standardní úkoly byly zadány za 100 bodů, zápočet je tedy za alespoň 66,666... bodů.
Pokud máte rádi soutěže, můžete získat bonusové body za úspěchy v programovací soutěži ACM ICPC (až 5 bodů za vyřešenou úlohu).
Zápočtový program
Body můžete rozněž získat za zápočtový program, který spočívá v implementaci zvoleného algoritmu či datové struktury. Programovací jazyk neomezuji, ale pokud chcete použít jiný než C, C++, C#, Python či Javu, nejprve mi napište. Algoritmus či DS by měly být implementovány v daném jazyce tak, aby mohly být snadno použitelné v jiném programu (např. přes #include v C či C++). Samozřejmostí je rozumné okomentování kódu, které by mělo obsahovat i časovou složitost jednotlivých procedur (stačí stručně). K programu navíc vytvořte 5-10 testovacích sad, které ověří správnost implementace včetně různých speciálních případů. Dodejte mi také prosím program, který spustí algoritmus na datech v zadaném souboru, abych ho mohl otestovat.
Před tím, než začnete něco programovat, pošlete mi email s tématem zápočťáku a počkejte na schválení. Témata musejí být různá a může se jednat o implementaci těžšího algoritmu či DS z přednášky, případně (lépe) o jejich aplikaci či o úpravu na nějaký daný problém. K inspiraci můžete využít nápady od Martina Mareše. Kdybyste chtěli téma mimo přednášku, můžeme se na tom domluvit.
Konkrétní bodové ohodnocení zápočtového programu závisí na vybraném tématu, u středně obtížných témat to bude okolo 50 bodů. Také můžete získat nějaké bonusové body za pěkné zpracování (implementaci).