Algoritmy a datové struktury II
Přednáška z Algoritmů a datových struktur II [NTIN061] se koná v ZS 2023/2024 ve čtvrtky od 10: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
Omlouvám se za chybějící zvuk v prvních 4 minutách záznamu.
| 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: Definice a základní tvrzení o tocích. Fordův-Fulkersonův algoritmus a důkaz jeho správnosti pomocí řezů. 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: Reformulace pomocí průtoků. Síť rezerv a skládání toků. Dinicův algoritmus a jeho analýza. Základní myšlenky Goldbergova algoritmu a animace průběhu výpočtu. | video |
| 2. 11. | Místo přednášky se koná cvičení (tedy děkanský sportovní den). | |
| 9. 11. | Toky: Goldbergův algoritmus a jeho analýza. Vylepšená verze s výběrem nejvyššího vrcholu. | video |
| 16. 11. | Násobení polynomů: reprezentace polynomu grafem, nástin rekurzivního algoritmu. Opakování operací s komplexními čísly (slidy). Rychlá Fourierova transformace (algoritmus FFT) a její inverze. | video |
| 23. 11. | Důkaz lemmatu o inverzi DFT z minulé přednášky. Poznámky k FFT (slidy): nerekurzivní verze, spektrální analýza, zpracování signálu. Paralelní programování pomocí hradlových sítí: sčítání přirozených čísel booleovským obvodem. | video |
| 30. 11. | Hradlová síť pro násobení čísel. Bitonické třídění komparátorovou sítí. Geometrické algoritmy v rovině: konvexní obal. | video |
| 7. 12. | Geometrické algoritmy v rovině: průsečíky úseček zametáním roviny, zmínka o Voroného diagramech, lokalizace bodu pomocí persistentních datových struktur. Úvod do rozhodovacích problémů. | video |
| 14. 12. | Rozhodovací problémy a převody mezi nimi: SAT, 3-SAT, nezávislá množina a klika v grafu, 3,3-SAT. | video |
| 21. 12. | Převod 3,3-SATu na 3D párování. 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 SAT pro CNF. Zoo klasických NP-úplných problémů. | video |
| 4. 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). | video |
| 11. 1. | Obchodní cestující: neaproximovatelnost verze bez trojúhelníkové nerovnosti. Aproximační schéma pro problém batohu. Pravděpodobnostní testy prvočíslosti: Fermatův a Rabinův-Millerův test (nezkouší se) | 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í.
Zkoušky
Termíny jsou vypsány v SISu, zapisujte se, prosím, tam.
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 :)
Pokud byste z nějakého důvodu zkoušku nestihli složit, mohu vás vyzkoušet i později – během letního zkouškového, během semestru, případně i o prázdninách. Na to už obvykle termíny nevypisuji, vše je na individuální domluvě. Tuto možnost nicméně doporučuji využít spíš v nouzi, než si tak rovnou zkoušku plánovat.
Zdroje
- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů
- Mé minulé přednášky z let 2021, 2018, 2017, 2015, 2013, 2011, 2009, 2007 a záznamy/zápisy z nich
- Minulá přednáška z ADS1
- 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ů: