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.

— Vlastni zkusenost: resej pi*oviny… Je videt, ze to je katedra matematiky, kazdy slovicko musi bejt presne to co chtej slyset.. Udelat to podle me problem neni, ale pro dobrou znamku musite vedet naprosty nesmysly (nebo je dovymyslite, nevim, de to, s ustni u me problem nebyl vedel jsem vsechno co chtela, ale vazne, nesmysly co nikdy nikdo nikde nepouzije, a to ani vzdalene). Ustni se zkousi i dalsi tejden treba, vubec nezvladaj (obecne organizace trochu rachta). Kdyz lidi zacli odevzdavat, radsi sem sel odevzdat taky aniz bych resil jeste 2 otazky kazdou za 6b jenom abych se moh zapsat na ustni druhej den a nemusel to resit jeste dodatecne dalsi tejden (rozepisoval sem jak blbec celej postup toho TM a tim zabil dost casu). Tak zalezi jestli vas jeste zajima znamka, nebo uz toho mate plny zuby a chcete to mit za sebou :)

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?

… radsi pridavam vyfocene kompletni zadani: