# Zkouska 15.2.2010

<{ForumPost(poster="cyrilh", timestamp=2010-02-15 14:36:23)}>
Posilam dnesni pisemku.  
  
Reseni:  
1) L neni rekurzivni z Riceovy vety (mnozina fci, ktere pracuji v linearnim case |x| nezavisi primo na e a neni trivialni)  
  
2) tam to chce dokazovat, ze L' je R.S. (L' je doplnek L). Protoze staci ukazat, ze existuje x, pro ktery Me(x) neskonci v linearnim case. Je chyba zkouset dokazovat, ze L je r.s., protoze tam nemame jak zarucit, ze to bude fungovat pro vsechny vstupy. Takze navod: L' je r.s, takze ex. M tak, ze L=L(M). M spusti Me na x a zkousi, jestli se zastavi do x kroku. Kdyz mu to trva dele, tak ho prijmu. To, ze kdyz je L' r.s, tak L r.s. byt nemuze plyne z toho, ze L neni rekurzivni.  
  
3) To se da ukazat vice zpusoby, jednoduchy zpusob je volat funkci Me(x) x-krat. Takze mame fci f(x), ktera x-krat zavola fci Me (=Fi_e(x)). Je jasne, ze kdyz je x z L --> f(x) je z Q (protoze x-krat volam fci, ktera je linerani O(x)).  
  
4) To je de facto VP, staci S=V, C=E, S'=VP  
  
5) idea: setridim prvky C od nejvetsiho (asi to ale ani neni treba). Prochazim mnoziny z takove posluopnosti: pokud je prochazena mnozina disjunktni s S', tak ji do S' pridam. Na zacatku jsem do S' pridal nejvetsi mnozinu z C, z toho se da odvodit ten aprox. pomer.  
  
Na ustnim daval:  
- HK, VP, UTS, Savicovu vetu  
  
Dr. Kucera byl pri zkouseni prijemny, kdyz jste tomu rozumeli a chapali princip, tak se zbytecne ve formalitach nestoural, jen obcas otestoval jestli to chapete a nemate to jen naucene nazpamet.

*Attachments:*

- *[verzeH.jpg](/Forum%20archiv/Attachments/5018_0e2777827f9cc26b5e6c8c815bbe5913)*

<{/ForumPost}>

<{ForumPost(poster="Jochanan", timestamp=2010-02-16 11:57:47)}>
jen pro super úplnost na tu 1) Riceova věta použít nešla, protože v tý množině nešlo o třídy funkcí. Nicméně to byl omyl v zadání -> sám si toho všiml až odpoledne a odpověd s RV uznával. Nicméně ten důkaz u RV, kde se na tuto množinu převedlo K je (podle mě) již stoprocentně správně.
<{/ForumPost}>

<{ForumPost(poster="QZuzka", timestamp=2011-01-13 18:05:29)}>
Jak dlouho to celkově trvá?  
  
Psaní zkoušky, případná pauza, podle čeho bere pořadí na ústní a jak dlouho tam nechává lidi?
<{/ForumPost}>