Algoritmy a datové struktury II
Přednáška z Algoritmů a datových struktur II [NTIN061] se koná v ZS 2021/2022 v pondělky od 15:40 v N1.
Můžete sledovat přímý přenos z přednášek.
Kdybyste čemukoliv nerozuměli, rád si s vámi domluvím konzultaci. Ozvěte se mi prosím na adresu mares+ads2@kam.mff.cuni.cz.
| datum | co se přednášelo | záznam |
|---|---|---|
| 4. 10. |
Vyhledávání v textu: značení okolo řetězců, naivní algoritmy,
algoritmus KMP (Knuth, Morris, Pratt) a jeho analýza. Jak hledat
více řetězců?
Pokud vám nefungují videa, vypněte si AdBlock. Jedno z jeho
pravidel zakazuje všechna URL s podřetězcem /ads2/ :D
| video |
| 11. 10. | Vyhledávaní v textu: algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hešování à la Rabin-Karp. Lemmata o polynomech a důsledky pro hešování řetězců. | video |
| 18. 10. | Toky v sítích: Opakování definic a základních tvrzení o tocích. Fordův-Fulkersonův algoritmus a důkaz jeho správnosti pomocí řezů. Ekvivalentní definice: čisté toky. Celočíselné sítě a celočíselné toky. Převod párování v bipartitním grafu na celočíselný tok. | video |
| 25. 10. | Toky: Dinicův algoritmus a jeho analýza. Základní myšlenky Goldbergova algoritmu. | video |
| 1. 11. | Toky: Goldbergův algoritmus, jeho analýza a animace průběhu výpočtu. | video |
| 8. 11. | Goldbergův algoritmus s výběrem nejvyššího vrcholu. Násobení polynomů: reprezentace polynomu grafem, nástin rekurzivního algoritmu. Opakování operací s komplexními čísly z mateřské školky (slidy). | video |
| 15. 11. | Násobení polynomů: rychlá Fourierova transformace (algoritmus FFT) a její inverze. Obvod pro FFT a nerekurzivní FFT. Poznámky k FFT (slajdy): spektrální analýza, zpracování signálu, algebraická interpretace. | video |
| 22. 11. | Paralelní programování pomocí hradlových sítí: sčítání přirozených čísel booleovským obvodem. Bitonické třídění komparátorovou sítí. | video |
| 29. 11. | Komparátorové sítě: konstrukce separátoru. Geometrické algoritmy v rovině: konvexní obal, průsečíky úseček zametáním roviny. | video |
| 6. 12. | Voroného diagramy a lokalizace bodu pomocí persistentních datových struktur. Rozhodovací problémy a převody mezi nimi. | video |
| 13. 12. | Převody problémů: SAT, 3-SAT, nezávislá množina a klika v grafu, 3,3-SAT a 3D-párování. Třídy problémů P a NP. | video |
| 20. 12. | Třídy P a NP, NP-těžké a NP-úplné problémy a jejich základní vlastnosti. Cookova věta o NP-úplnosti SATu s náznakem důkazu: booleovské obvody pro problémy z P, důkaz NP-úplnosti obvodového SATu, převod obvodového SATu na CNF-SAT. Zoo klasických NP-úplných problémů. První pomoc při setkání s těžkým problémem. | video |
| 3. 1. | Jak si poradit s NP-těžkým problémem. Řešení speciálních případů: nezávislá množina ve stromech, barvení intervalových grafů, pseudopolynomiální algoritmus pro problém batohu. Aproximační algoritmy: obchodní cestující v metrickém prostoru (2-aproximace), neaproximovatelnost verze bez trojúhelníkové nerovnosti, aproximační schéma pro problém batohu. | video |
Cvičení
K přednášce existuje několik cvičení a jelikož letos existuje jediná paralelka, všechna cvičení by měla být ekvivalentní. Podmínky k udělení zápočtu určuje cvičící.
Studentům kombinovaného studia doporučuji vybrat si libovolného cvičícího a domluvit se s ním na získání zápočtu za domácí úkoly. Účast na cvičení není nutná, ale hodí se alespoň občas se tam stavit, abyste měli přehled, co se dělá. Za mnou samozřejmě můžete přijít na konsultaci, domluvte se e-mailem.
Zkoušky
Termíny jsou vypsány v SISu, zapisujte se, prosím, tam. Zkouším prezenčně, ale kdybyste nemohli na zkoušku přijet (třeba proto, že jste zrovna v karanténě), ozvěte se mi prosím e-mailem. Pokud se termíny zaplní, vypíši další.
Zkouška bude ústní s písemnou přípravou: Na začátku zadám otázky. Vy si odpovědi rozmyslíte (času bude dost) a sepíšete. Pak si o nich spolu popovídáme a na základě toho dostanete buďto známku, nebo nápovědu k další práci. Cílem je, aby každý vyřešil všechno, a známka se bude odvíjet od toho, jak moc jsem vám musel napovídat :)
Ke zkoušce je potřeba:
- Znalost teorie z přednášky – viz požadavky.
- Schopnost řešit algoritmické úlohy podobné těm, jež jsme dělali na cvičení.
- Zápočet není povinné získat předem, ale je to doporučené.
- Doporučuji čistou mysl a dobrou náladu :)
Zdroje
- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů
- Mé minulé přednášky z let 2018, 2017, 2015, 2013, 2011, 2009, 2007 a zápisy z nich.
- Dasgupta, Papadimitriou, Vazirani: Algorithms (velice pěkná knížka pokrývající část přednášky, navíc dostupná online)
- Programátorská kuchařka KSP (nepříliš formální textíky o různých algoritmech)
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd Edition), Mc Graw Hill 2001 (vpravdě monumentální dílo pokrývající většinu přednášky)
Ostatní zajímavé knihy:
- Jiří Demel: Grafy a jejich aplikace (grafové algoritmy)
- Luděk Kučera, Jaroslav Nešetřil: Algebraické metody diskrétní matematiky (FFT a paralelní sčítání)
- Martin Mareš: Krajinou grafových algoritmů (lahůdky pro pokročilé a zvídavé; v první kapitole teorie toků v sítích)
- Lecture notes Davida Mounta o geometrických algoritmech.
- De Berg et al.: Computational Geometry: algorithms and applications (trochu pokročilejší knížka o geometrických algoritmech)
Animovaný výklad algoritmů v Algovision kolegy Kučery.
Sbírky příkladů: