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) + suma i=0..n (i^2) ?

Omega je omezeni zespoda f(n) >= c * g(n), tzn hledame nejvetsi (a nejjednodussi) takovou fci, ktera splnuje tuto rovnost
f(n) = n^2.lg(n) + suma i=0..n (i^2)    // sumu si vzorcem na soucet prevedeme
f(n) = n^2.lg(n) + n*(1+n^2)/2          // coz da O(n^3), !!! maple říká (1/3)*n^3+(1/2)*n^2+(1/6)*n 
f(n) = n^2.lg(n) + n/2 + n^3/2          // n^3 > n^2.lg(n), takze nas zajima jen n^3
--> g(n) = O(n^3)

3/ T(n) = 6T(n/4) + n^2.lg(n), vyřešit (Master Theorem)

3. pripad n^2.lg(n) je Omega(n^(log4(6)))
6 *(n/4)^2*lg(n/4) <= c*n^2*lg(n)    // roznasobeni
6/16 * n^2*lg(n/4) <= c*n^2*lg(n)   // lg(n/4) si "zvetsim" na lg(n)
6/16 * n^2*lg(n) <= c*n^2*lg(n)     // pokratim (vydelim) n^2*lg(n)
6/16 <= c                           // c < 1, plati
--> T(n) = O(n^2*lg(n))

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/ Definovat paměťovou složitost TM.
3/ XXX
4/ XXX
5/ Vztah EXP vůči PSPACE, P, NP
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 ji rozhoduje, + definovat i tu redukci (a tady si dávejte sakra pozor, ať je ta definice dobře, jinak bude u ústní Demlová dost „naštvaná“ :)…..