Algoritmy a automaty pro učitele

V zimním semestru 2022/2023 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 12:20 v N2, 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.

Další se tu objeví začátkem semestru.

datum co se přednášelo
3. 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. Převod párování v bipartitním grafu na celočíselný tok.
10. 10. Toky v sítích: Edmondsův-Karpův algoritmus (Ford-Fulkerson s nejkratší cestou). Vyhledávání v textu: značení okolo řetězců, naivní algoritmy, algoritmus KMP (Knuth, Morris, Pratt) a jeho analýza.
Cvičení: Vrcholově a hranově disjunktní cesty.
17. 10. Vyhledávání v textu: Algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hešování à la Rabin-Karp. Geometrické algoritmy v rovině: konvexní obal.
24. 10. Geometrické algoritmy: 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. Rozhodovací problémy.
31. 10. Převody problémů: SAT, 3-SAT, 3,3-SAT, nezávislá množina a klika v grafu, 3D párování.
7. 11. 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ů. 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ů.
14. 11. 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. Konečné automaty (DFA): definice, výpočet, jazyk přijímaný automatem, regulární jazyky.
21. 11. Regulární jazyky: Iterační (pumping) lemma. Součin automatů. Uzavřenost regulárních jazyků na průniky, sjednocení a doplňky. Nedeterministické konečné automaty (NFA): definice, výpočet, ekvivalence s DFA, ε-přechody. Algoritmické otázky.
28. 11. Uzavřenost regulárních jazyků na operace. Regulární výrazy: definice, Kleeneho věta. Automaty s výstupem. Gramatiky: definice, derivace, generovaný jazyk. Zmínka o Chomského hierarchii.
5. 12. 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.
12. 12. Plán: 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, 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).

Zdroje

Ostatní zajímavé knihy:

Animovaný výklad algoritmů v Algovision kolegy Kučery.

Sbírky příkladů:

Stránku spravuje Martin Mareš