Toto je starší verze dokumentu!

1)

Definice Theta(F(n))
Mějme f(n) = ln(n^(ln n)), g(n) = Suma_{k = 1..n} (1/k) -- určete (a vysvětlete), zda platí f(n) = O(g(n)) / g(n) = O(f(n)) / ...
Jednoduchý příklad na Master theorem (něco jako T(n) = 4*T(n/4)+n)

2)

Analýza McCarthyho algoritmu 91 -- http://en.wikipedia.org/wiki/McCarthy_91_function

3)

Definice TS (+ co znamená, že TS přijímá slovo/jazyk)
Udělat TS (a vysvětlit ho), který přijímá jazyk {a^n b^2n}

4)

Teoretické otázky: 
Definovat třídu NPC
Vyjmenovat dvě úlohy patřící do NPC, dvě úlohy patřící no NP
Třída EXP je třída všech jazyků přijímaných TS v exponenciálním čase (nebo něco v tom smyslu), určit vztah mezi EXP, NPSPACE, NP, co-NP