navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2014-06-12 [2014/06/12 20:44] koprija6 |
courses:a4m01tal:zkouska-2014-06-12 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 3: | Řádek 3: | ||
| ==== Složitosti ==== | ==== Složitosti ==== | ||
| 1/ f(n) je Ω(g(n)), f(n) je o(g(n)) vysvětlit co to znamená + jejich vztahy\\ | 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) ? \\ | + | 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) ? \\ |
| + | <code> | ||
| + | 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) | ||
| + | </code> | ||
| 3/ T(n) = 6T(n/4) + n^2.lg(n), vyřešit (Master Theorem) \\ | 3/ T(n) = 6T(n/4) + n^2.lg(n), vyřešit (Master Theorem) \\ | ||
| + | <code> | ||
| + | 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)) | ||
| + | </code> | ||
| + | |||
| ==== Turingovy stroje ==== | ==== Turingovy stroje ==== | ||
| Řádek 16: | Řádek 31: | ||
| 1/ PSPACE, NPSPACE, vztah mezi nimi \\ | 1/ PSPACE, NPSPACE, vztah mezi nimi \\ | ||
| 2/ Je definována paměťová složitost TM, pokud o nem vime, ze rozhoduje jazyk L? \\ | 2/ Je definována paměťová složitost TM, pokud o nem vime, ze rozhoduje jazyk L? \\ | ||
| - | 2/ XXX \\ | + | 2/ Definovat paměťovou složitost TM. \\ |
| 3/ XXX \\ | 3/ XXX \\ | ||
| 4/ XXX \\ | 4/ XXX \\ | ||
| - | 5/ XXX \\ | + | 5/ Vztah EXP vůči PSPACE, P, NP\\ |
| 6/ definovat RP + vztah s 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 neco, ..... | + | 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á" :)..... |
| - | + | ||
| - | + | ||
| - | ~~DISCUSSION~~ | + | |
| - | + | ||
| + | ~~DISCUSSION|Custom Title String~~ | ||
