[Záp] 4.2.2010

[MarPol]

1) Popsat TS pro jazyk .
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.

[Betlista]

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...

[jirka_v]

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 .
(b) Na základě toho ukažte, že existuje n, pro nějž .

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?

[jirka_v]

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

[Betlista]

BTW kolik prikladu je treba spocitat pro ziskani zapoctu?

3 ze 4

[frantik]

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

[Xerxes]

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é...