Algoritmy a automaty pro učitele v ZS 24/25 (pátek 10:40-13:50, S10)

V zimním semestru 2023/2024 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ě S10 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.
4. 10. Hledání jehel v kupce sena (tedy řetězců v textu). Algoritmus KMP (Knuth, Morris, Pratt) pro jednu jehlu a algoritmus Aho-Corasickové pro více jehel (bez konstrukce automatu). Viz [Pruv 13.1-13.3] (včetně části příkladů).
Úkol: Na vstupu jsou dva řetězce. Jak v lineárním čase poznat, jestli je jeden řetězec rotací druhého řetězce? (10 b, odevzdejte přes email do 14 dnů.)
11. 10. Dokončení AC algoritmu pro hledání více jehel najednou (hlavně konstrukce automatu) [Pruv 13.3]. Stručně Rabin-Karpův algoritmus pro jednu jehlu založený na hešování (nebude se zkoušet) [Pruv 13.4]. Úvod do toků v sítích: definice a Ford-Fulkersonův algoritmus (bez analýzy) [Pruv 14.1-2].
Úkol: počítání frekvence výskytů (viz příklad č. 4 na cvičení z ADS2 loni) (10 b, odevzdejte přes email do 14 dnů.)
18. 10. Toky v sítích a jejich aplikace: opakování definice a Ford-Fulkersonova algoritmu, analýza F-F algoritmu přes řezy, věta o max. toku a min. řezu. Celočíselné sítě a celočíselné toky. Převod párování v bipartitním grafu na celočíselný tok. Edmondsův-Karpův algoritmus (Ford-Fulkerson s nejkratší cestou). [Pruv 14.1-3]. Příklady na toky. 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, odevzdejte přes email do 21 dnů.)
25. 10. Geometrické problémy v rovině: konvexní obal a průsečíky úseček zametáním roviny přímkou [Pruv 16.1 a 16.2]. První tři příklady na geometrické algoritmy (pro oddělení dvou množin bodů jsme si ukázali provázkovou metodu). Zmínka o lokalizaci bodu v rovině pomocí Voroného diagramu a persistentního vyhledávacího stromu (nezkouší se).
Úkol: Ukažte, že výpočet konvexního obalu je alespoň tak těžký jako třídění reálných čísel. Tedy umíme-li vypočítat konvexní obal množiny n bodů v rovině v čase T(n), lze třídit n reálných čísel v čase O(T(n)). Vypočtením konvexního obalu přitom myslíme nejen stanovení, které body na obalu leží, ale i v jakém pořadí. (10 b, odevzdejte přes email do 14 dnů.) (PS: Nemusíte se zaobírat detaily výpočetního modelu -- o něm teď tiše předpokládáme, že se do jedné paměťové buňky vejde reálné číslo a že s reálnými čísly umíme základní aritmetické a logické operace v konstantním čase. Tento model se nazývá Real RAM].)
1. 11. Odpadá
8. 11. Úvod do výpočetní složitosti [Pruv 19.1 a 19.2].: co je efektivní algoritmus, třída P, rozhodovací problémy, převody problémů (zmínka o třídě NP a NP-úplnosti/těžkosti -- podrobněji příště). Ukázka převodů: SAT na 3-SAT, 3-SAT na nezávislou množinu, nezávislá množina na SAT, nezávislá množina a klika mezi sebou, barvení na SAT (barvení na SAT se nezkouší). Příklady na převody problémů + katalog (prošli jsme řešení prvního příklad a 2.a)
Úkol: Mějme černou skříňku (neboli orákulum) pro rozhodovací verzi problému dvou loupežníků (viz katalog NP úplných problémů). Ta nám tedy pouze řekne, jestli lze danou množinu čísel rozdělit na dvě části se stejným součtem, ale neprozradí nám nic o validním rozdělení (pokud vůbec existuje). Jak pomocí této černé skříňky nalézt rozdělení mezi loupežníky? Zde se jedná o to najít řešení, pokud můžeme položit polynomiálně mnoho dotazů orákulu na rozhodovací verzi loupežníků. (10 b, odevzdejte přes email do 14 dnů.)
15. 11. Převody problémů [Pruv 19.2]: 3-SAT na 3,3-SAT a ten na 3D párování. Třídy P a NP, NP-těžké a NP-úplné problémy a jejich základní vlastnosti [Pruv 19.3]. Cookova věta o NP-úplnosti SATu (důkaz jen naznačen, nezkouší se). Katalog klasických NP-úplných problémů. Rozebrány možnosti, co si počít s NP-těžkými problémy [Pruv 19.5]. Řešení speciálních případů: nezávislá množina ve stromech (nevážená i vážená) a pseudopolynomiální algoritmus pro problém batohu. Příklady na převody problémů + katalog (prošli jsme řešení bodů c) a d) druhého příkladu)
Úkol: převeďte 3D párování na SAT (10 bodů, termín 5.12. kvůli pozdnímu zadání). Bonus za 3 body: převeďte 3D párování na 0/1 rovnice. Definice problémů viz katalog.
22. 11. Aproximační algoritmy [Pruv 19.6]: 2-aproximace problému obchodního cestujícího (TSP) a aproximační schéma na batoh (pomocí pseudopolynomiálního algoritmu). Příklady na aproximační algoritmy, z nichž jsme prošli hlavně MaxCut a stručně MaxSAT. Úvod do automatů a regulárních jazyků [Aut 1.1 a 1.2]: motivace, příklad na jazyk slov začínajících a končících nulou, definice deterministického konečného automatu (DFA), převod KMP automatu na DFA, konečné jazyky a příklad neregulárního jazyka (0n1n).
Úkol: sestrojte konečný automat na binární abecedou, který přijme právě binární zápisy čísel dělitelných sedmi (10 bodů, termín 12.12. kvůli pozdnímu zadání). Bonus (+3 body): jak pro libovolné k sestrojit konečný automat přijímající právě binární zápisy čísel dělitených k?
29. 11. Konečné automaty [Aut 1.2 a 1.3]: příklady regulárních (neklesající posloupstnosti a řetězce délky dělitelné třemi) a neregulárních jazyků (řetězce dlouho jako kvadrát celého čísla). Iterační (pumping) lemma jako důsledek principu o opakování stavů při výpočtu na dost dlouhém slově a jeho použití na důkazy, že jazyk není regulární (např. jazyk prvočísel). Průnik, sjednocení a doplňky regulárních jazyků jsou opět regulární. Nedeterministické konečné automaty (NFA), strom výpočtů NFA a převod NFA na DFA s exponenciálně mnoho stavy. Epsilon-přechody a jak se jich nakonec zbavit pomocí epsilon-uzávěrů. Další operace s jazyky [Aut 1.4]: zřetězení, (libovolná a pozitivní) iterace a proč zachovávají regularitu.
Úkol: Pro regulární jazyk L dokažte, že jeho otočení LR je také regulární. Otočení slova znamená obrácení pořadí znaků a otočení jazyka L obsahuje pro každé slovo S z L jeho otočení (10 bodů, termín 12.12.).
6. 12. Dokončení regulárních jazyků [Aut 1.4]: Regulární výrazy a jejich převod na DFA. Převod DFA na regulární výrazy a tím důkaz Kleeneho věty, že regulární výrazy generují právě regulární jazyky. Gramatiky [Aut 2.1]: definice, odvozování/derivace, příklady včetně generování neregulárního jazyka (lineární gramatikou). Pravé lineární gramatiky a jejich ekvivalene s DFA (podobně pro levé lineární gramatiky) [Aut 2.2]. Bezkontextové jazyky, derivační (syntaktické) stromy a jejich možná nejednoznačnost [Aut 2.3]. Chomského hierarchie tříd jazyků.
Úkol: Mějme regulární výraz délky m a slovo délky n, obojí nad konstantně velkou abecedou. Najděte algoritmus, který otestuje, jestli je dané slovo generované regulárním výrazem (10 bodů, termín 19.12.). Hint: dynamické programování, tedy nejdřív najděte rekurzivní algoritmus s exponenciální složitostí.
13. 12. Bezkontextové gramatiky a jazyky [Aut 2.3]: převod do Chomského normální formy, algoritmus CYK na rozpoznání, jestli je slovo generované bezkontextovou gramatikou, a hledání syntaktických (derivačních) stromů. Bezkontextové iterační lemma (skeč důkaz obrázkem, tedy bez detailů, nezkouší se) a jeho použití na jazyk anbncn. Diskuse o rozhodnutelnosti a formálních výpočetních modelech (Church-Turingovat teze) [Aut 3.3]. Turingovy stroje (TM) [Aut 3.1]: definice, příklad na jazyku 0n1n, definice konfigurace, výpočtu, přijímaných slov a tříd jazyků RE (částečně rozhodnutelné) a R (rozhodnutelné).
Úkol: vytvořte gramatiku pro jazyk "čtverců", tedy slov αα, kde α je libovolný řetězec nad binární abecedou (12 bodů, termín 10.1.). Hint: tato gramatiku už nebude bezkontextová, tedy bude potřeba použít pravidla s delší levou stranou.
20. 12. Varianty TM (vícepáskový, nedeterministický, s jednosměrmě nekonečnou páskou) a jejich ekvivalence se základním TM [Aut 3.2]. Ekvivalence TM a obecných gramatik (a stručně také TM a RAMu) [Aut 3.3]. (U těchto ekvivalencí stačí znát základní myšlenku, detaily se nezkouší.)
10. 1. Problémy a jazyky, pro které neexistuje algoritmus [Aut 3.4 a 3.5]: nerozhodnutelné problémy (např. problém zastavení) a problémy, které nejsou ani částečně rozhodnutelné. 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ů.
Úkol: ukažte, že iterace rozhodnutelného jazyka je rozhodnutelná. Poté dokažte, že iterace částečně rozhodnutelného jazyka je částečně rozhodnutelná
(12 bodů).

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í).

Termíny zkoušek: vyzkoušet vás mohu téměř libovolně v pracovní den v lednu, první týden února budu pryč (tj. od 2.2. do 7.2.) a druhý týden je ještě nejistý. Ozvěte se mi prosím, kdy by se vám hodilo se nechat vyzkoušet (např. rozsah 2-3 dní týden předem).

Body na zápočet:

IDrozpis bodůcelkem
M3+10+3+3+7+9+3+10+3++3+3+10+13+3+3> 80
P3+3+10+10+26
Š3+10+3+3+3+10+3+3+10+13+3+3+3+10+80

Literatura a zdroje

Knihy o algoritmech v angličtině: