Požadavky ke zkoušce z AVS
Seznam všech definic, vět a důležitých příkladů, které byste měli ke zkoušce umět.
Architektura počítačů
Reprezentace dat v paměti počítače
Strojové instrukce
Vztah mezi vysokoúrovňovými jazyky a hardwarem počítače
Funkce poskytované operačním systémem
Správa paměti
Kešování
Výpočetní modely
Notace pro řetězce
Problémy, jazyky a kódování
Turingův stroj (TM), konfigurace, výpočet
Varianty Turingova stroje: jednostranně nekonečná páska, více pásek, randomizovaný, s orákulem, interaktivní
Random Access Machine
Ekvivalence TM s RAM
Vyčíslitelnost
(Částečná) vyčíslitelnost/rozhodnutelnost funkcí a jazyků
Jazyk je částečně rozhodnutelný, právě když ho jde enumerovat.
Kódování strojů, univerzální jazyk u, univerzální Turingův stroj (UTM)
Lu je částečně rozhodnutelný, ale není rozhodnutelný. Jeho doplněk není částečně rozhodnutelný.
Postova věta
Operace s kódy strojů
Redukce mezi jazyky
Riceova věta (bez důkazu)
Těžkost a úplnost jazyků
Relativní vyčíslitelnost
Aritmetická hierarchie
Vlastnosti aritmetické hierarchie, souvislosti s kvantifikovanými formulemi
Časová složitost
Doba běhu výpočtu, časová složitost stroje
Asymptotická notace: O, Ω, Θ
1-páskový TM potřebuje kvadratický čas na rozpoznávání palindromů.
k-páskový TM jde simulovat 1-páskovým TM s kvadratickým zpomalením.
Třídy DTIME(f), DTIMEF(f), P a PF, EXP
Časově konstruovatelné funkce
P a NP
Redukce v polynomiálním čase
SAT a Nezávislá množina jsou vzájemně převoditelné.
Třída NP (definovaná pomocí certifikátů)
NP-těžkost a NP-úplnost
Pokud je K převoditelný na L a L je v P, pak K je v P. (Uzavřenost třídy P na redukce.)
Pokud je K převoditelný na L a K je NP-těžký, pak L je NP-těžký.
Cookova-Levinova věta (SAT je NP-úplný)
NP-úplnost problémů 3-SAT, 3,3-SAT, 3D-párování, ZOE
Třída co-NP
UNSAT and Tautologičnost jsou co-NP-úplné.
Relativní třídy složitosti DTIME[A](f), P[A], NP[A]
Existují orákula A a B taková, že P[A]=NP[A] and P[B]≠NP[B].
Booleovské obvody
Kombinatorické a booleovské obvody
Výpočet obvodu
Každou booleovskou funkci jde spočítat nějakým obvodem.
Rodiny obvodů a uniformita
Jazyky v P mají uniformní rodiny polynomiálně velkých obvodů.
Obvodový SAT je NP-úplný.
Obvodový SAT je převoditelný na SAT (implikuje Cookovu-Levinovu větu).
Nedeterminismus
Nedeterministický Turingův stroj (NTM)
Třídy NTIME(f), NTIMEF(f)
NP = NTIME(poly(n)).
Prostorová složitost
Vstupní, výstupní a pracovní pásky
Prostor spotřebovaný výpočtem, prostorová složitost stroje
Třídy DSPACE(f), NSPACE(f), DSPACEF(f), NSPACEF(f), PSPACE, NPSPACE
Prostorově konstruovatelné funkce
Základní vztahy: DTIME(f) ⊆ NTIME(f) ⊆ DSPACE(f) ⊆ NSPACE(f)
P ⊆ NP ⊆ PSPACE ⊆ NPSPACE
DSPACE(f) ⊆ DTIME(exp(O(f))) pro všechny f ≥ log n
PSPACE ⊆ EXP
Konfigurační graf NTM
Odhady složitosti pro dosažitelnost implikují vztahy mezi složitostními třídami.
NSPACE(f) ⊆ DTIME(exp(O(f))) pro všechny f ≥ log n
Dosažitelnost je v DSPACE(log2 n).
Skládání funkcí vyčíslitelných v omezeném prostoru.
Savitchova věta: NSPACE(f) ⊆ DSPACE(f2).
PSPACE = NPSPACE
Immermannova-Szelepcényiho věta: NSPACE(s) = co-NSPACE(s) pro s ≥ log n
Polynomiální prostor
Problém kvantifikovaných booleovských formulí (QBF alias QSAT)
QBF je PSPACE-úplný
Strategie pro hry dvou hráčů s úplnou informací jsou v PSPACE.
Alternující Turingův stroj
Třídy ATIME(f) and AP
AP = PSPACE
Polynomiální hierarchie
Problémy Σk-SAT a Πk-SAT
Polynomiální hierarchie: třídy ΣkP a ΠkP, třída PH
Inkluze mezi třídami uvnitř PH
Ekvivalentní definice pomocí orákul
Kolaps PH
Uvnitř P
Log-space redukce
Třídy L a NL
Vyhodnocení obvodu je P-úplné.
Dosažitelnost je NL-úplná.
2-SAT je NL-úplný.
Věty o hierarchii
Věta o prostorové hierarchii
Věta o časové hierarchii
Obvodová složitost
Velikost obvodu, třídy SIZE(f)
Každá booleovská funkce s n vstupy se dá spočítat obvodem velikosti O(2n*n).
Existují funkce, která potřebují obvody velikosti aspoň 2n/10n.
Výpočet s nápovědou, třídy DTIME(f)/g a P/poly
Pro všechna k>0 existuje jazyk v EXP SIZE(nk + k).
EEXP není podmnožinou P/poly.
Pokud NP ⊆ P/poly, pak PH = Σ2P (bez důkazu).
Pravděpodobnostní algoritmy
Pravděpodobnostní TM
Třídy BPP, RP, co-RP, ZPP
Amplifikace pravděpodobnosti úspěchu
Ekvivalentní definice pravděpodobnostních tříd pomocí certifikátů
ZPP = RP ∩ co-NP
P ⊆ ZPP ⊆ (co-)RP ⊆ BPP, RP ⊆ NP, BPP ⊆ PSPACE
BPP ⊆ P/poly
Regulární jazyky
Deterministický konečný automat (DFA)
Výpočet, přijímání, rozšířená přechodová funkce
Regulární jazyky
{ 0n1n } není regulární.
Iterační (pumping) lemma pro regulární jazyky
Součinový automat
Průnik regulárních jazyků je regulární.
Nedeterministický konečný automat (NFA)
Jazyky přijímané NFA jsou regulární.
NFA s ε-přechody
Každý ε-NFA lze redukovat na ekvivanentní NFA.
Operace s jazyky
Regulární jazyky jsou uzavřené na ∩, ∪, doplněk, zřetězení, iteraci, otočení.
Kleeneova věta
Obousměrný DFA (jako restrikce TM)
DSPACE(1) je třída všech regulárních jazyků
Jemnozrnná složitost
Jemnozrnné redukce
Problém ortogonálních vektorů a hypotéza OVH
(Silná) hypotéza o exponenciálním čase aneb (S)ETH
OVH implikuje dolní odhad na přijímání pomocí NFA.
ETH implikuje dolní odhad na dominující množinu.
SETH implikuje OVH.
OVH implikuje dolní odhad na nejdelší společnou podposloupnost (bez důkazu).