Algoritmy a datové struktury II
Přednáška z Algoritmů a datových struktur II [NTIN061] se koná v ZS 2025/2026 ve čtvrtky od 15:40 v N1.
Můžete sledovat přímý přenos z přednášek.
Kdybyste chtěli cokoliv konzultovat, rád si s vámi popovídám. Ozvěte se mi prosím na adresu mares+ads2@kam.mff.cuni.cz.
| datum | co se přednášelo | záznam |
|---|---|---|
| 2. 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 |
| 9. 10. | Vyhledávaní v textu: algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hešování à la Rabin-Karp. Lemma o kořenech polynomů a důsledky pro hešování řetězců. | video |
| 17. 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ů. | video |
| 23. 10. | Toky: Celočíselné sítě a celočíselné toky. Převod párování v bipartitním grafu na celočíselný tok. Reformulace pomocí průtoků. Síť rezerv a skládání toků. Dinicův algoritmus a jeho analýza. | video |
| 30. 10. | Plán: Toky: Goldbergův algoritmus a jeho analýza. Vylepšená verze s výběrem nejvyššího vrcholu. Animace průběhu výpočtu. |
Cvičení
K přednášce existuje několik cvičení a jelikož letos existuje jediná česká paralelka, všechna cvičení by měla být ekvivalentní. Podmínky k udělení zápočtu určuje cvičící.
Zdroje
- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů
- Mé minulé přednášky z let 2023, 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 (4th Edition), Sathya Publishers 2023 (vpravdě monumentální dílo)
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ů: