TAL zkouška 5.6.2014

1h 45min času.

Hodně otázek jako z minulých let. Test není kompletní, na některé otázky jsem si nevzpomněl.

Ústní část: prý část lidí ten samý den, část lidí následující den.

1/ f(n) je Ω(g(n)), f(n) je Θ(g(n)) vysvětlit co to znamená
2/ f(n) > 3, g(n) > 3. Platí že když f(n) je Ω(g(n)), tak že ln(f(n)) je Ω(ln(g(n))) ?
3/ T(n) = 3T(n/4) + n, vyřešit (Master Theorem)

1/ Definice deterministického TS - z čeho se skládá a popsat co části dělají, udělat jeden krok podle přechodové funkce a popsat, co se při tom děje
2/ Navrhnout TS, který přijímá jazyk L = {w|w = u111u^R, u je {0,1}*}. Provést výpočet nad slovem w = 1011101

1/ NP, NPC, co-NP popsat
2/ PSPACE, NPSPACE, napsat jazyk NPSPACE
3/ Vztah P, NP, PSPACE, NPSPACE
4/ (To znění je trochu kostrbaté, ale lépe si to nepamatuju) Mějme jazyk, který leží v PSPACE. Jazyk je PSPACE-úplný, pokud každý jazyk z PSPACE se na něj polynomiálně redukuje. Předpokládejme, že existuje PSPACE-úplný jazyk, pro který by se našel nedeterministický Turingův stroj, který by ho rozhodl. Co lze dokázat?
5/ Rekurzivní, rekurzivně spočetné jazyky definice. (a k tomu myslím ještě bylo něco jako:) Jazyk Turingova stroje přijímá alespoň 1 slovo. Kam takový jazyk patří?
6/ Mějme prostý, orientovaný graf, ohodnocený. Něco jako „rozhodni, zda každá orientovaná cesta z vrcholu u do vrcholu v má délku > k“ a kam patří takový jazyk?

… vyfocene kompletni zadani: