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).