[Záp] 4.2.2010

1. Popsat TS pro jazyk $1^k01^{k^2}$.

2. Ukázat, že div je PRF. +, sign, - a * lze použít bez odvozování.

3. Ukázat, že existuje n, pro které W_n = {0,..,n}.

4. Za pomoci nějakého problému z přednášky ukázat, že klika je NP úplný problém.

Kučera říkal, že stejné zadání bylo i včera.

Síce mám zápočet úspěšně za sebou, ale mohl by někdo ukázat jak na 3) ?

Ostatní jsou IMHO lehké, můžu pomoct na oplátku s tím...

Betlista wrote:Síce mám zápočet úspěšně za sebou, ale mohl by někdo ukázat jak na 3) ?

No, to bych taky rad vedel. V poznamkach z webu se pise tohle:

Něco na s-m-n větu a větu o rekurzi, například:
(a) Dokažte, že existuje prostá PRF f, pro kterou platí, že $W_{f(x)}=\{0, . . . , x\}$.
(b) Na základě toho ukažte, že existuje n, pro nějž $W_n=\{0, . . . , n\}$.

Prisel jsem na to, ze (b) se da dostat z (a) snadno pomoci vety o rekurzi. Horsi je to s (a). Nejaky napady, co s tim?

BTW kolik prikladu je treba spocitat pro ziskani zapoctu?

Ted jsem zjistil, ze (a) i (b) se resi v poznamkach z cvik, ktery jsou k stahnuti tady na foru - http://forum.matfyz.info/download/file.php?id=546. Konkretne v souboru IMG_0005.pdf. Akorat to je vzhuru nohama, takze chvili stravite hledanim v menu :)

jirka_v wrote:BTW kolik prikladu je treba spocitat pro ziskani zapoctu?

3 ze 4

caf ... neviete nahodou niekto ako na ten DIV alebo pripadne MOD ??

Na začátku ledna jsem si před zápočtovkou narychlo napsal takový emulátor primitivně rekurzivních funkcí a v něm si zkoušel udělat různé funkce. Je tam i DIV, MOD, LOG a PRIME. Není to ale vůbec dokumentované...

Attachments:

• recursive_functions.lua.txt