Automaty a výpočetní složitosti

V zimním semestru 2023/2024 vedu kurz o výpočetních modelech, vyčíslitelnosti a výpočetní složitosti pro magisterské studenty matematiky [NMMB415]. Přednáška a cvičení se konají v úterky od 12:20 do 15:30 v posluchárně K12.

Přednášky se pokouším nahrávat (odkazy níže), uvidíme, co technika zvládne.

datum témata zdroje
3. 10. Architektura moderních počítačů. Reprezentace dat v paměti. Procesor a jeho instrukce (viz příklad). Operační systémy a virtualizace paměti. Triky na zrychlení procesorů: kešování, pipelining, paralelní provádění instrukcí, predikce skoků a spekulace. Paralelní počítače: symetrický multi-procesing a vícejádrové procesory. video
10. 10. Cesta za formálním modelem výpočtu. Abecedy a řetězce. Turingovy stroje, jejich syntaxe a sémantika. Vyčísitelné a částečně vyčíslitelné funkce a množiny. Příklad: rozpoznávání 0n1n. Varianty Turingových strojů: jednostranně nekonečná páska, více pásek.
Cvičení: rozpoznávejte binarní řetězce se sudým počtem jedniček, otočte binární řetězec, sčítejte a násobte binární čísla. 		video
17. 10. Random access machine a jeho ekvivalence s Turingovým strojem. Rozhodnutelné a částečně rozhodnutelné množiny, třídy R a RE. Enumerovatelné množiny jsou právě ty částečně rozhodnutelné. Univerzální a diagonální jazyk.
Cvičení: Monotónně enumerovatelné množiny jsou právě ty rozhodnutelné. Třídy R i RE jsou uzavřené na sjednocení a průniky. 		video
24. 10. Postova věta. Další příklady nerozhodnutelných jazyků. Redukce, těžkost a úplnost. Nerozhodnutelnost sémantických vlastností: Riceova věta (bez důkazu). Relativní vyčíslitelnost, R[A], RE[A]. Aritmetická hierarchie: třídy Σn, Πn a Δn, souvislosti s kvantifikovanými formulemi (bez důkazu). Čas běhu programu, časová složitost a asymptotická notace.
Cvičení: najděte redukce mezi jazyky Lhalt, Lempty, Ltotal, Leq, Lfin a jejich doplňky. Zařaďte tyto jazyky do aritmetické hierarchie. 		video
31. 10. Čas vs. počet pásek: dolní odhad Ω(n2) pro rozpoznávání palindromů 1-páskovým strojem, redukce k-páskových strojů na 1-páskové v čase O(T(n)2), redukce k-páskových na 2-páskové v čase O(T(n) log T(n)) [bez důkazu]. Třídy časové složitosti DTIME(f), P, DTIMEF(f), PF. Redukce v polynomiálním čase: SAT na Nezávislou množinu a zpět, SAT přes 3-SAT a 3,3-SAT na 3D-párování. video
7. 11. Třída NP a NP-úplnost, Cookova-Levinova věta. Odbočka k obvodům, zejména booleovským: 2-vstupová booleovská hradla jsou BÚNO; otázka uniformity. Problémy v P mají uniformní obvody polynomiální velikosti. Obvodový SAT a důkaz Cookovy-Levinovy věty.
Cvičení: Redukce 3-obarvení na SAT, Nezávislé množiny na Kliku a zpět, 3D-párování na ZOE, Nezávislé množiny na Vrcholové pokrytí. E3,E3-SAT je triviální. 		video
14. 11. Třída co-NP a tautologičnost. Celkový pohled na NP, co-NP a příbuzné třídy. Nedeterministické Turingovy stroje, třída NTIME(f) a (re)definice NP jako NTIME(poly(n)). Prostorová složitost: třídy DSPACE(f), NSPACE(f), (N)PSPACE, (N)L, and (N)EXPTIME. Metoda dosažitelnosti: odhady složitosti problému REACH implikují vztahy mezi třídami složitosti. Skládání prostorově omezených strojů. Savičova věta, PSPACE=NPSPACE.
Cvičení: Booleovské obvody (a jejich složitost) pro operace s n-bitovými čísly: parita, rovnost, x>y, x+y, x*y. 		video
21. 11. Přednáška se nekoná: Den otevřených dveří
28. 11. Prostorová složitost: QBF je PSPACE-úplný. Intuice o třídě PSPACE. Alternující Turingovy stroje, třídy ATIME, AP=PSPACE. Polynomiální hiearchie, Σk-SAT a Πk-SAT, PH ⊆ PSPACE, kolaps PH. Immermanova-Szelepcsényiho věta: NSPACE(f)=co-NSPACE(f).
Cvičení: Pokud existuje PH-úplný problém, pak PH zkolabuje. 		video
5. 12. Uvnitř P: třídy L a NL, log-space redukce, REACH is NL-úplný, vyhodnocení obvodu je P-úplné. 2-SAT: implikační grafy a NL-úplnost. Věty o hierarchii pro deterministický prostor a čas. Relativizující techniky nemohou oddělit P od NP: existují orákula A a B taková, že P[A]=NP[A] and P[B]≠NP[B].
Cvičení: Log-space algoritmy na binární sčítání a násobení, na počítání cyklů permutací, dosažitelnost v lesích, vzdálenost ve stromech. 		video1 video2 (nic moc)
12. 12. Obvodová složitost: třídy SIZE(f), horní a dolní odhady složitosti booleovských funkcí. Stroje s nápovědou, třídy DTIME(f)/g a P/poly. Existují jazyky v EEXP \ P/poly. NP ⊆ P/poly implikuje kolaps PH (bez důkazu). Randomizované algoritmy: pravděpodobnostní Turingovy stroje, třídy BPP, RP, co-RP, ZPP. Amplifikace pravděpodobnosti v RP a BPP. P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PSPACE, RP ⊆ NP, ZPP = RP ∩ co-RP. BPP ⊆ P/poly.
Cvičení: Booleovskou funkci jde počítat obvodem velikosti O(2n). Ověřování násobení matic, xTy je rovnoměrně náhodný bit pro x pevné a y rovnoměrně náhodný (nad Z2). 		video
19. 12. Konečné automaty (DFA) a regulární jazyky. Iterační (pumping) lemma. Nedeterministické automaty (NFA), ε-NFA a jejich převod na DFA. Uzavřenost regulárních jazyků na doplněk, průnik, sjednocení, zřetězení a iteraci, Kleeneho věta. Obousměrné automaty, DSPACE(1) a NSPACE(1) jsou třída regulárních jazyků.
Cvičení: {xαx} nad abecedou {a,b} je regulární, {αα} nad abecedou {a,b} není regulární, "0n pro n čtverec" není regulární, DFA pro jazyk "binární zápisy čísel dělitelných 3" a použití Kleeneho věty na něj. 		video
9. 1. Jemnozrnná složitost. Hypotéza o ortogonálních vektorech (OVH), hypotéza o exponenciálním čase (ETH) a její silná verze (SETH). OVH implikuje dolní odhady na přijímání slova NFA. ETH implikuje dolní odhady na dominující množinu. SETH implikuje OVH. OVH implikuje dolní odhady na nejdelší společnou podposloupnost (důkaz toliko načrtnut). video

Hodnocení

K úspěšnému dokončení předmětu potřebujete získat zápočet a složit zkoušku (v jakémkoliv pořadí).

Zkouška pokrývá přednesenou teorii: definice, věty, jejich důkazy a použití (viz seznam požadavků). Smíte využívat tahák rozměrů jedné strany A4, který jste si sami napsali (rukou nebo na počítači).

Zápočet získáte za vyřešení domácích úkolů za alespoň 100 bodů. Během semestru vypíši několik sad úkolů, celkem za alespoň 150 bodů. Úkoly se odevzdávají pomocí Poštovní sovy.

Zdroje

Stránku spravuje Martin Mareš