Algoritmy a automaty pro učitele
V zimním semestru 2023/2024 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 pro matematiky).
Přednáška se koná v pondělky od 9:00 v N6, 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 |
|---|---|
| 2. 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. |
| 9. 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,
úvod k algoritmu KMP (Knuth, Morris, Pratt).
Cvičení: Vrcholově a hranově disjunktní cesty. |
| 16. 10. | Vyhledávání v textu: Algoritmus KMP a jeho analýza. Algoritmus Aho-Corasicková pro hledání více řetězců. |
| 23. 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. |
| 30. 10. | Rozhodovací problémy. Převody problémů: SAT, 3-SAT, nezávislá množina. |
| 6. 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. Zoo klasických NP-úplných problémů. |
| 13. 11. | 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. |
| 20. 11. | Konečné automaty (DFA): definice, výpočet, jazyk přijímaný automatem, regulární jazyky. Iterační (pumping) lemma. Součin automatů. Uzavřenost regulárních jazyků na průniky. |
| 27. 11. | Nedeterministické konečné automaty (NFA): definice, výpočet, ekvivalence s DFA, ε-přechody. Algoritmické otázky ohledně automatů. Uzavřenost regulárních jazyků na operace. Regulární výrazy: definice, Kleeneho věta. |
| 4. 12. | Gramatiky: definice, derivace, generovaný jazyk. Zmínka o Chomského hierarchii. Lineární gramatiky: levé, pravé, obecné a jejich souvislost s regulárními jazyky. Bezkontextové gramatiky: derivační stromy a jejich (ne)jednoznačnost, Chomského normální forma. |
| 11. 12. | Algoritmus CYK pro náležení slova do bezkontextového jazyka. Bezkontextové iterační lemma (důkaz jen naznačen). Turingův stroj (TM): definice, výpočet. |
| 18. 12. | Turingův stroj: přijímání zastavením (částečně rozhodnutelné jazyky), přijímání koncovým stavem (rozhodnutelné jazyky), výstup na pásce (vyčíslitelné funkce). Varianty TM: pohyb jen doprava (konečný automat), nepřepisující (obousměrný automat), vícepáskový (lze simulovat jednopáskovým). Vztah mezi TM a RAMem. |
| 8. 1. | Obecné gramatiky generují částečně rozhodnutelné jazyky. Nedeterministický TM je stejně silný jako deterministický. Kódování strojů, univerzální jazyk a jeho vlastnosti. Univerzální Turingův stroj (bez detailů konstrukce). Nerozhodnutelnost univerzálního jazyka a jeho doplňku. Postova věta. Vztahy mezi třídami jazyků. |
Zkoušky
Termíny jsou vypsány v SISu, buď se zapište tam, nebo se e-mailem domluvte na jiném termínu.
Ke zkoušce je potřeba:
- Znalost teorie z přednášky (definice, algoritmy a jejich rozbor, věty a jejich důkazy)
- Schopnost řešit úlohy podobné těm, jež jsme dělali na cvičení.
- Doporučuji čistou mysl a dobrou náladu :)
Zdroje
- Loňský běh přednášky
- Předloňský běh přednášky 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ů: