AG.md



Automaty a složitost (návrh)

Sylabus


Konečné automaty (1.5 přednášky)

základní pojmy: abeceda, slovo, jazyk (rozhodovací problém)
definice konečného automatu (DFA), syntaxe a sémantika, regulární jazyk
příklad: 0^n1^n není regulární, důkaz principem holubníku
příklad: v KMP uvážíme uzávěr zpětných hran a máme DFA
regulární pumping lemma (zobecnění myšlenky předchozího důkazu)
příklad: 1^{prvočíslo} není regulární
součin automatů


Regulární výrazy (1 přednáška)

nedeterministický konečný automat (NFA)
ekvivalence DFA  NFA
ε-přechody, ekvivalence ε-NFA  NFA
uzavřenost na množinové operace
regulární výrazy popisují právě regulární jazyky


Gramatiky (1.5 přednášky)

bezkontextové gramatiky, derivační stromy, generované jazyky
pravé a levé lineární gramatiky generují regulární jazyky
obecné lineární gramatiky generují i neregulární jazyky
jednoznačnost gramatiky
Chomského normální forma
algoritmus testující příslušnost slova do bezkontextového jazyka
pomocí dynamického programování
iterační lemma pro bezkontextové jazyky


Turingovy stroje (1 přednáška)

Turingův stroj (TM) a jeho výpočet
TM může příjímat zastavením (částečně rozhodnutelné jazyky), přijímat stavem
(rozhodnutelné jazyky) nebo vydávat výstup na pásce (vyčíslitelné funkce)
varianty TM:

páska jen pro čtení => obousměrný konečný automat
Důkaz ekvivalence s klasickým DFA.
více pásek: důkaz ekvivalence s jednopáskovým TM
nedeterministický TM


vztah mezi TM a RAMem


Základy vyčíslitelnosti (1 přednáška)

univerzální Turingův stroj, kódování strojů (bez detailů konstrukce)
univerzální jazyk a diagonální jazyk
halting problem je částečně rozhodnutelný, ale není rozhodnutelný
Postova věta => doplněk halting problemu není částečně rozhodnutelný
jazyk je částečně rozhodnutelný <=> jeho slova lze vyjmenovat
převoditelnost jazyků
Riceova věta (bez důkazu)


Polynomiálni složitost a P vs. NP (2.5 přednášky)

třídy DTIME(f)
redukce počtu pásek a univerzální TM zpomalují jen polynomiálně,
stejně tak převody TM <-> RAM => třída P je nezávislá na modelu
třída NP definovaná pomocí certifikátů
převoditelnost v polynomiálním čase
převody mezi problémy:

SAT, 3-SAT, 3,3-SAT
klika, nezávislá množina
3D párování
ZOE (zero-one linear equations)
3-barevnost
hamiltonovská cesta


NP-úplnost
Cookova-Levinova věta
třída co-NP, tautologičnost
TODO: Zmínit obvody, když už je znají z ADS2?


Další složitostní třídy (1 přednáška)

třídy DSPACE(f), PSPACE
nedeterministické třídy NTIME(f), NSPACE(f), NP, NPSPACE
DTIME(f) ⊆ NTIME(f) ⊆ DSPACE(f) ⊆ NSPACE(f) ⊆ DTIME(2^O(f))
důsledek: P ⊆ NP ⊆ PSPACE ⊆ NPSPACE ⊆ DTIME(2^poly(n))
důsledek: DSPACE(log n) ⊆ NSPACE(log n) ⊆ P
věty o hierarchii


Fine-grained složitost (1.5 přednášky)

hypotéza o ortogonálních vektorech (OVH)
hypotézy o exponenciálním čase (ETH a SETH)
fine-grained převoditelnost
OVH implikuje dolní odhad pro simulaci NFA
ETH implikuje dolní odhad pro dominující množínu
SETH implikuje OVH


(celkem 11 přednášek)