TAL zkouška 12.6.2014

1/ f(n) je Ω(g(n)), f(n) je o(g(n)) vysvětlit co to znamená + jejich vztahy
2/ Najděte nejjednodušší funkci g(n) co největšího asymptotického růstu a takovou, že f(n) je Ω(g(n)), f(n) = n^2.lg(n) + sum(k^2) ?
3/ T(n) = 6T(n/4) + n^2.lg(n), vyřešit (Master Theorem)

1/ Definice nedeterministického TS - z čeho se skládá a popsat co části dělají, ..
2/ Navrhnout nedeterministický TS, který přijímá jazyk L = {w|w = w0w, w je {0,1}*}. Provést výpočet nad slovem w = 10010

1/ PSPACE, NPSPACE, vztah mezi nimi
2/ Je definována paměťová složitost TM, pokud o nem vime, ze rozhoduje jazyk L?
2/ XXX
3/ XXX
4/ XXX
5/ XXX
6/ definovat RP + vztah s NP?
7/ U <| V, co muzeme rici o U pokud vime ze V je uloha, pro kterou ex. TM, ktery neco, …..