Algoritmy a automaty pro učitele v ZS 26/27 (pátek 10:40-13:50, N9)

V zimním semestru 2026/2027 přednáším Algoritmy a automaty pro učitele [NUIN021]. Tento předmět 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 a cvičení se konají v pátek od 10:40 do 13:50 v učebně N9 na Malé Straně.

Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte během výuky nebo po ní. Také budu rád, když se během výuky budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi emailem nebo před/po přednášce, vhodný čas může být třeba po výuce. Někdy mě můžete též najít v kanceláři S326 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře naproti učebně S3), ale je lepší se ozvat předem.

Co jsme dělali / plán

U každého tématu jsou odkazy na učebnice.
2. 10. Hledání jehel v kupce sena (tedy řetězců v textu). Algoritmus KMP (Knuth, Morris, Pratt) pro jednu jehlu. Příklady na KMP algoritmus (stihli jsme první tři a část čtvrtého). Algoritmus Aho-Corasickové pro více jehel: pouze úvod (trie a zpětná funkce; zbytek doděláme příště). Zdroj: [Pruv 13.1-13.3].
Úkol: spočítejete počet výskytů jehly J v textu S jako podposloupnosti (znaky J se tedy v S nemusí vyskytovat hned po sobě, ale musí být zachováno pořadí). Například pro J=abc a S=abcbac je výsledek 3. Můžete předpokládat, že se vám výsledek vejde do jedné paměťové buňky. Snažte se dosáhnout času O(|S|*|J|), ale za horší časovou složitost bude též část bodů. Za 10 bodů, odevzdání přes AI Socratic nebo emailem, termín 16.10. před přednáškou.
9. 10. Automat a algoritmus Aho-Corasickové pro hledání více jehel najednou [Pruv 13.3]. Příklady na AC algoritmus (stihli jsme první tři, stručně i pátý). Stručně: Rabin-Karpův algoritmus pro jednu jehlu založený na hešování (nebude se zkoušet) [Pruv 13.4].
Úkol: počítání frekvence výskytů (viz příklad č. 4), za 10 bodů, odevzdání přes AI Socratic nebo emailem, termín 23.10. před přednáškou.
18. 10. Toky v sítích: definice a Ford-Fulkersonův algoritmus, analýza F-F algoritmu přes řezy, věta o max. toku a min. řezu. Celočíselné sítě a celočíselné toky. [Pruv 14.1-2]. Příklady na toky, z nichž jsme prošli první čtyři. Pro zajímavost (nebude se zkoušet): příklad, na kterém se Ford-Fulkersonův algoritmus nezastaví, je např. na těchto slajdech (hodnota r je zlatý řez :-)
Úkol: Je dána děravá čtvercová šachovnice o straně délky N. Umístěte na ní co nejvíce věží tak, aby nestály na dírách a žádné dvě se vzájemně neohrožovaly, přičemž dvě věže se ohrožují, když jsou na stejném řádku či sloupci, nezávisle na tom, jestli jsou mezi nimi díry. Můžete použít libovolný algoritmus pro hledání maximálního toku, časovou složitost pak stačí vyjádřit vzhledem k počtu volání tohoto algoritmu (10 b, termín 30.10. před přednáškou).

Zápočet a zkouška

Zápočet bude za 80 bodů za domácí úkoly a aktivitu při cvičení. Zkouška bude ústní s písemnou přípravou a to jak z teorie z přednášky (kromě toho, u čeho je napsáno, že se nebude zkoušet), tak z jednodušších úloh řešených během výuky nebo v domácích úkolech. Na začátku zadám 2 otázky a 1 úlohu a poté budete mít dostatek času (a papíru) na rozmyšlení a sepsání odpovědí. Nemusíte sepisovat detaily (např. detailní pseudokódy), jde mi o to, jestli rozumíte tomu, jak dané algoritmy nebo výpočetní modely fungují, jak ukázat jejich správnost a časovou složitost. Až budete připraveni (nebo s blížícím se koncem zkoušky) se o teorii i řešení úloh pobavíme, popř. vám dám nějakou nápovědu k řešení (která se ovšem promítne do hodnocení).

Úkoly se odevzdávají přes AI Socratic od Hanse Raje Tiwaryho (preferovaná možnost) nebo emailem. Standardně bude termín odevzdání 14 dní od zadání.

Termíny zkoušek: bude upřesněno ke konci semestru

Literatura a zdroje

Knihy o algoritmech v angličtině: