Algoritmy a automaty pro učitele

V zimním semestru 2021/2022 přednáším Algoritmy a automaty pro učitele [NUIN021]. To je nová přednáška, která spojuje části Algoritmů a datových struktur 2 [NTIN061] a Automatů a gramatik [NTIN071]. Primárně je určena 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 pátek od 12:20 v S4, následuje cvičení tamtéž.

datum co se přednášelo záznam
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. Převod párování v bipartitním grafu na celočíselný tok.
8. 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.
video
15. 10. Pokračování KMP: konstrukce automatu. Algoritmus Aho-Corasicková pro hledání více řetězců. Přístup pomocí hešování à la Rabin-Karp. video
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. video
29. 10. Rozhodovací problémy a převody mezi nimi. Převody problémů: SAT, 3-SAT, nezávislá množina a klika v grafu. video
5. 11. Převody problémů: 3,3-SAT a 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 video
12. 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, pseudopolynomiální algoritmus pro problém batohu. Aproximační algoritmy: obchodní cestující v grafu s trojúhelníkovou nerovností (2-aproximace), aproximační schéma pro problém batohu. video
19. 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 (cvičení: na sjednocení a doplňky). video
26. 11. Nedeterministické konečné automaty (NFA): definice, výpočet, ekvivalence s DFA, λ-přechody. Uzavřenost regulárních jazyků na operace. Regulární výrazy: definice. Algoritmické otázky. video
3. 12. Plán: Kleeneho věta (vztah mezi regulárními výrazy a jazyky). Automaty s výstupem. Gramatiky: definice, generovaný jazyk. Lineární gramatiky: levé, pravé, obecné. Bezkontextové gramatiky: derivační stromy a jejich (ne)jednoznačnost, Chomského normální forma, algoritmus pro náležení slova do jazyka.

Zdroje

Ostatní zajímavé knihy:

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

Sbírky příkladů:

Stránku spravuje Martin Mareš