Zkouska 15.2.2010

cyrilh
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 15. 2. 2010 14:08
Typ studia: Informatika Mgr.

Zkouska 15.2.2010

Příspěvek od cyrilh »

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
pisemka verze H
Naposledy upravil(a) cyrilh dne 16. 2. 2010 23:09, celkem upraveno 1 x.
Jochanan
Matfyz(ák|ačka) level II
Příspěvky: 85
Registrován: 12. 5. 2007 15:58
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zkouska 15.2.2010

Příspěvek od Jochanan »

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ě.
QZuzka
Matfyz(ák|ačka) level III
Příspěvky: 209
Registrován: 2. 12. 2007 19:51
Typ studia: Informatika Mgr.
Bydliště: Praha 4

Re: Zkouska 15.2.2010

Příspěvek od QZuzka »

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?
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“