Termín 7.6.2010

Co si pamatuji, kdo si pamatuje víc, ať doplní nebo mě opraví: Hlídala nějaká jiná ženská (ne Demlová), seděla a dalo se zřejmě i dost opisovat (co jsem sledoval lidi přede mnou). Na vypracování 2 hodiny.

1)

 a) Co platí pro f(n) = Theta(g(n))?

 b) Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = theta(g(n))

 c) Prozkoumej T(n) = 2 T(n/2) + 1. Příklad na Master Theorem.

2) Je dán algoritmus

Give(m,n,s)

s = 0; i = 1;

while i ⇐ n

j = 1;

while j ⇐ m

s = s + j*n;

j = j + 1;

end;

i = i + 1;

end;

Output s

a) časová složitost

b) najdi obecný zápis funkce s

c) dokaž správnost b)

3)

a) Co je to Turingův stroj a co to znamená, když přijímá jazyk L?

b) Rozdíl mezi tím, když TM nějaký jazyk přijímá a když jej rozhoduje.

c) Je dán jazyk L, jehož slova mají tvar: {0|1}* - libovolná posloupnost 0 a 1, kde ale musí být víc jedniček.

   Napiš TM, který rozhoduje tento jazyk. Stačí slovní popis nebo klidně i přechody.

d) Napiš jeden netriviální stav z c) jako přechodovou funkci.

4)

a) Co je to třída NP a napiš jeden rozhodovací problém, který do ní nepatří.

b) Patří randomizovaný quick sort do RP nebo ZPP? Co je to RP a ZPP?

c) Popiš postup pro důkaz toho, že je něco NP úplné. Popiš redukci atd. Můžeš buďto všeobecně a nebo na příkladu nějakého převodu.

d) Co jsou to rekurzivní a rekurzivně spočetné jazyky.

e) Příklad rekurzivního jazyku, který není rekurzivně spočetný.

— Martin Zachar 2010/06/07 13:41