od cyrilh » 15. 2. 2010 14:36
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.
- Přílohy
-
- pisemka verze H
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.