# [Záp] 4.2.2010

<{ForumPost(poster="MarPol", timestamp=2010-02-04 11:52:31)}>
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<sub>n</sub>  = {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.
<{/ForumPost}>

<{ForumPost(poster="Betlista", timestamp=2010-02-04 12:02:25)}>
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...
<{/ForumPost}>

<{ForumPost(poster="jirka_v", timestamp=2010-02-04 17:47:17)}>

 > 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?**
<{/ForumPost}>

<{ForumPost(poster="jirka_v", timestamp=2010-02-04 18:11:57)}>
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](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 :)
<{/ForumPost}>

<{ForumPost(poster="Betlista", timestamp=2010-02-05 19:18:02)}>

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

3 ze 4
<{/ForumPost}>

<{ForumPost(poster="frantik", timestamp=2010-02-07 00:14:57)}>
caf ... neviete nahodou niekto ako na ten DIV alebo pripadne MOD ??
<{/ForumPost}>

<{ForumPost(poster="Xerxes", timestamp=2010-02-07 16:50:57)}>
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](/Forum%20archiv/Attachments/3387_748d527c5c84131e054fceb1b676cde8)*

<{/ForumPost}>