Algoritmy a automaty pro učitele
V zimním semestru 2025/2026 přednáším Algoritmy a automaty pro učitele [NUIN021]. To předmět, který spojuje části Algoritmů a datových struktur 2 [NTIN061] a Automatů a gramatik [NTIN071]. Primárně je určený pro posluchače studia učitelství, ale může být zajímavý i pro studenty neinformatických oborů, kteří už absolvovali nějaký základní kurs programování a algoritmů (například v podobě Programování 1 a 2 pro matematiky).
Přednáška se koná ve středy od 15:40 v S11, cvičení následuje po přednášce.
Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares@kam.mff.cuni.cz a domluvíme se.
| datum | co se přednášelo |
|---|---|
| 1. 10. | Toky v sítích: Formulace problému. Fordův-Fulkersonův algoritmus a důkaz jeho správnosti pomocí řezů. Celočíselné sítě a celočíselné toky. |
| 8. 10. | Toky v sítích: Edmondsův-Karpův algoritmus (Ford-Fulkerson s nejkratší cestou). Převod párování v bipartitním grafu na celočíselný tok. Vyhledávání v textu: značení okolo řetězců, naivní algoritmy, algoritmus KMP (Knuth, Morris, Pratt). |
| 15. 10. | Virtuální přednáška: podívejte se na video. Vyhledávání v textu: Algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hešování à la Rabin-Karp. |
| 22. 10. | Geometrické algoritmy v rovině: konvexní obal, průsečíky úseček zametáním roviny. Zmínka o lokalizaci bodu v rovině pomocí Voroného diagramu a persistentního vyhledávacího stromu. |
| 29. 10. | Rozhodovací problémy. Převody problémů: SAT, 3-SAT, nezávislá množina. |
| 5. 11. |
Převody problémů: 3,3-SAT, 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 (bez důkazu).
Zoo klasických NP-úplných problémů.
Úkoly: (1) SAT pro obecné formule převést na SAT v CNF, (2) ukázat NP-úplnost existence řešení soustavy 0/1 lineárních rovnic (koeficienty a vektor pravých stran jsou přirozená čísla, za proměnné smíme dosazovat jen 0 a 1). |
| 12. 11. | Přednáška i cvičení odpadají, tento ten je děkanský sportovní. |
| 19. 11. | Pozor, přednáška i cvičení se výjimečně konají v pracovně S322. Plán: První pomoc při setkání s 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 grafu s trojúhelníkovou nerovností (2-aproximace), neaproximovatelnost bez trojúhelníkové nerovnosti, aproximační schéma pro problém batohu. |
Zdroje
- Verze přednášky z roku 2023
- Verze 2021 s videozáznamy
- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů
- Martin Mareš: Úvod do automatů
- Má přednáška z ADS2
- 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:
- 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ů: