1. Cast
1.1 Konstrukce konecnych automatu, regularnich vyrazu, bezkontextove gramatiky, zasobnikovych automatu...
ukazka-sjednoceni dvou automatu a napsat ho regularni gramatikou
2 termin-konstrukce DKA jeho minimalizace
2012-konstrukce BG
2009-konstrukce BG

1.2 Nejaky alg. postup na KA,RV,BG,ZA
redukce BG
2009-minimalizace automatu a vypsani v normovanem tvaru
FB-minimalizace automatu

1.3 Jazykove operace a pojmy z KA,RV,BG,ZA a uzaverove vlastnosti REG, CFL
ukazka-vytvoreni BG ktera je iterace jine BG(G'->G'G|e, kde G' je nova BG a G je startovni neterminal puvodni BG)
2 termin-algoritmus pro prevod BG na NZA(lze), algoritmus pro prevod NZA na DZA(nelze)
2012-co to znamena ze je REG ozavrena vuci zretezeni
2009-co to znamena ze je REG ozavrena vuci iteraci

1.4 Zarazeni jazyku do trid
default

1.5 Dukaz tvrzeni
ukazka-dukaz ze kazdy jazyk generovany bezkontextovou gramatikou je prijmany zasobnikovym automatem
2 termin-dukaz ze jazyk neni regularni


2. Cast
2.1 RAM, TS
RAM kod

2.2 Preveditelnost mezi dvemy problemy
ukazka- Eq-NFA na QBF
2 termin- IS na SAT
2012- 3-SAT na IS
2009- 3-SAT na IS
FB- IS na 3-GC

2.3 Rozhodnutelne, nerozhodnutelne, castecne rozhodnutelne problemy a Riceova veta
default

2.4 Razeni problemu do trid slozitosti a asymptoticke slozitosti algoritmu
ukazka-
2 termin-co to je PSPACE-tezky problem a jeho vztah k PSPACE-uplne tride
2009-co to je PSPACE-tezky problem a jeho vztah k PSPACE-uplne tride
2012-co je to nerozhodnutelny problem a priklad

2.5 Aproximacni a pravdepodobnostni algoritmy
foku dat