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: 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: 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. 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ů: 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. Cookova věta o NP-úplnosti SATu. Katalog klasických NP-úplných problémů. Rozebrány možnosti, co si počít s NP-těžkými problémy. Ř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.

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, tak z úloh podobných úlohám řešeným na cvičení (dvě úlohy). Na začátku tedy zadám úlohy 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í).

Body na zápočet:

IDrozpis bodůcelkem
M3+10+3+3+7+9+3+10+3+354
P3+3+10+10+26
Š3+10+3+3+3+10+3+3+38

Literatura a zdroje

Knihy o algoritmech v angličtině: