Cvičení z Algoritmů a datových struktur II

pátek od 12:20 v S7, ZS 23/24

K přednášce Algoritmy a datové struktury II Martine Mareše 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ů. Po dobré zkušenosti z minulého roku bude hlavní náplní cvičení řešení algoritmických úloh a příkladů k probíranému tématu ve skupinách po 3-4, které na začátku vyberu náhodně.

Pokud máte nějaký dotaz, pište na vesely (obmotané a) 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é. Po domluvě mohu poskytnout konzultace.

Co jsme dělali

6. 10. Cvičil Vladan Majerech: tržnice datových struktur
13. 10. Vyhledávání jehly v kupce sena dle pánů Knutha, Morrise a Pratta + souvisejícící příklady (rýmy na str. 2 jsme neprošli)
20. 10. Vyhledávání více jehel v kupce sena a automat Aho-Corasickové. Příklady, z nichž jsme prošli prvních šest (zbylé jsou bonusové)
27. 10. Automaty KMP a Aho-Corasickové nad nekonstantně velkou abecedou (řešení pomocí BVS vs. řešení pomocí hešování). Toky v sítích, Ford-Fulkersonův algoritmus a použití na hledání hranově či vrcholově disjunktních cest. Příklady
3. 11. Toky v sítích, Dinicův algoritmus (jednotkové a celočíselné kapacity, příklady těsnosti analýzu) a aplikace toků (bipartitní párování a vrcholové pokrytí, odvodili jsme Königovu větu). Příklady (neprošli jsme pátý a bonusy)
10. 11. Toky v sítích: Goldbergův algoritmus. Příklady (prošli jsme první dva a třetí z části, zbytek třetí příkladu za DÚ :-)
17. 11. Boj za svobodu a demokracii (státní svátek)
24. 11. Diskrétní Fourierova transformace jako lineární zobrazení a matice tohoto zobrazení. Co udává 0-tá a (n/2)-tá složka výsledného vektoru? Převádění vektorů a převod kanonické báze vektorového prostoru nad komplexními čísly (na konci ukázka, jak z toho lze vydedukovat, jak vypadá inverzní zobrazení k DFT). Příklady, z nichž jsme prošli první čtyři.
1. 12. Hradlové a komparátorové (třídící) sítě. Příklady, z nichž jsme prošli prvních pět.
8. 12. Geometrické algoritmy a zametání přímkou nebo provázkem (anebo stěračem). Probrali jsme případy neobecné polohy úseček a jak (ne)ovlivní algoritmus pro hledání průsečíků úseček (a také, co má být jeho výstupem). Oddělení dvou množin bodů pomocí obmotávání konvexního obalu provázkem a výpočet obsahu nekonvexního mnohoúhelníku (lichoběžníkovou metodou a velmi stručně i zametáním). Příklady, z nichž jsme probrali první tři (čtvrtý se řeší zametáním podobně jako třetí).
15. 12. Převody rozhodovacích problémů anebo jak ukázat, že nějaký problém je (pravděpodobně) těžký, tedy nikdo pro něj nezná polynomiální algoritmus. Rozebrali jsme, že řešit rozhodovací problémy stačí i na nalezení optimálního řešení. Převedli jsme si mezi sebou nezávislou množinu a vrcholové pokrytí a barevnost jsme převedli na SAT. Příklady, z nichž jsme probrali první příklad a 2.a) a b).
22. 12. Zrušeno po tragické události na FF.
29. 12. Vánoce
5. 1. Bavili jsme se o převodech problémů (a také jak je využít pro řešení problémů pomocí řešičů na SAT nebo na celočíselné lineární rovnice), o čem je slavný problém P vs. NP, co jsou NP-těžké a NP-úplné problémy. Poté jsme dělali převody z druhého příkladu z minula, kromě bonusových. K třetímu příkladu: první tři problémy by měly být snadné (první dva v lineárním čase, třetí v čase O(n42)), algoritmy pro 2-SAT jsou rozebrány na Wikipedii.
12. 1. Aproximační algoritmy pro přibližná řešení NP-těžkých problémů. Probrané příklady (kromě bonusu).

Podmínky zápočtu

Zápočet bude za 100 bodů. Hlavním zdrojem bodů bude řešení domácích úkolů; celkem bude za úkoly možné získat alespoň 150 bodů. 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; po prvním cvičení pošlu přístupový token (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; viz loňské cvičení).

Body budu rovněž dávat za předvedení řešení během cvičení. Pokud máte rádi soutěže, můžete též získat body za úspěchy v programovací soutěži ACM ICPC (až 5 bodů za vyřešenou úlohu).