====== 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.
{{:courses:a4m01tal:tm.jpg|}}
  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ý.

 --- //[[zacham3@fel.cvut.cz|Martin Zachar]] 2010/06/07 13:41//


~~DISCUSSION~~