Fórum studentů MFF UK

Dnes klasika
1) Věta o aritmetické hierarchii
2) Výběr:
a) Konstrukce 1-generické
b) v nekon. stromě je nekonečná větev (doplňte si na správné místa přívlastky o rekurzivitě, ty jsem zapoměl)

otazky jsou porad stejne

1) vlastnosti skoku
2a) konstrukce 1-genericke mnoziny
2b si nepamatuju

1) limitní vyčíslitelnost
2) buď a) konstrukce 1-generické
nebo b) věta o nízké bázi

1) Limitní vyčíslitelnost
2) výběr
a) konstrukce 1-generické
b) low basis theorem

U první otázky, první implikace - jak se tam definuje funkce f přes funkcionál Fí. Ptal se (všech), co bychom museli udělat kdyby nebyla totálni (nebo něco podobného). Což jsem nevěděl plus jsem nevěděl u druhé implikace jak to zakončit a známka 1-. Ještě zmínil, že zkouška je lehká (a taky u každého papíru který si bral k prozkoumání prohlásil "no tohle je lehké, tohle taky" :D)

Tak i v letním semestru 2014 probíhá zkouška pořád stejně, tj. přesně dle wiki.

1) vlastnosti skoku
2) konstrukce 1-generické množiny.

Tj. jedno základní a jedno rozšiřující téma. Předmět je minimálně na zápisky z přednášek hodně rozsáhlý, ale zkouší se tak třetina. V podstatě je to 6 velkých důkazů :D Vše důležité je tady v tomto [url=http://wiki.matfyz.cz/index.php?title=TIN065_Zhrnutie]shrnutí[/url], nicméně doporučuji zabrousit i do jednotlivých přednášek, protože spousta témat je tam hezky "lidsky" vysvětlena.

1) skok
2) výběr:
- konstrukce [latex]\emptyset<A<\emptyset'[/latex]
- konstrukce 1-generické [latex]A<\emptyset'[/latex]

Žádný výběr to vlastně není, je to totéž (přiznal to rovnou). Takže ponaučení: ne vždycky se dá tomuhle tématu vyhnout.

PS: Ještě postřeh pro ty, kdo hledají zdroje k učení: Na wiki [b]jsou[/b] jedny celkem obsáhlé zápisky, jen tady nefungují odkazy :) Já to zjistil až teď.

Dnes klasika: 1) skok 2) lim. vycislitelnost

[quote="adam"]1. Limitní vyčíslitelnost, 2. Příklady [latex]\Sigma_2[/latex], resp. [latex]\Pi_2[/latex]-úplných.[/quote]

Uplne stejne zadani :) Ani jsem tam nestihnul dopsat uplne vsechno, uz byl netrpelivy - jednicku bez asi jedne poloviny jednoho dukazu ohodnotil jako vybornou, ve dvojce jsem sotva napsal, jak ty mnoziny vypadaji, a uz po mne chtel jenom rict, ze potrebuju najit prostou ORF a ze ji najdu s-m-n vetou, that's all ;)

vcera (28.6) boli rovnake otazky

Zkouška 15. 6. vypadala takto: 1. Limitní vyčíslitelnost, 2. Příklady [latex]\Sigma_2[/latex], resp. [latex]\Pi_2[/latex]-úplných. Tzn. ve druhé otázce nebylo nic na výběr. Podle mě je to z těch otázek "na výběr", co se vyskytují, asi ta nejjednodušší, ale plyne z toho ponaučení, že by člověk neměl spoléhat na to, že si bude moci vybrat.

Na zkoušce jsme byli tři (nebudu jmenovat, ale styďte se;)!), a po zadání dva lidé odešli. :shock: Nevím, jak probíhaly jiné termíny, ale já být Kučera, tak začnu přemýšlet, jestli nejsem při zkoušení příliš měkký. Tak se trochu snažte, vy, co půjdete příště!

[quote="kaktus64"]Otázky 1.6.2010

1) Vlastnosti operácie skoku
2) na výber:
- konštrukcia množiny A, na ktorú je T prevediteľná prázdna množina, a zároveň je A T prevediteľná na skok prázdnej množiny. Obe prevoditeľnosti ostré.
- konštrukcia nekonečného rekurzívneho bin. stromu bez nekonečnej rekurzívnej vetvy[/quote]
Jen doplnim, ze k jednicce dal hint, ze je to konstrukce 1-genericke mnoziny

Otázky 1.6.2010

1) Vlastnosti operácie skoku
2) na výber:
- konštrukcia množiny A, na ktorú je T prevediteľná prázdna množina, a zároveň je A T prevediteľná na skok prázdnej množiny. Obe prevoditeľnosti ostré.
- konštrukcia nekonečného rekurzívneho bin. stromu bez nekonečnej rekurzívnej vetvy

Doplnil som [url=http://wiki.matfyz.cz/wiki/TIN065_Predn%C3%A1%C5%A1ka_00]poznámky z prednášok[/url] o [url=http://wiki.matfyz.cz/wiki/TIN065_Zhrnutie]zhrnutie pred skúškou[/url].
Ak by sa niekomu chcelo dopísať dvanástu prednášku, tak by to bolo vynikajúce. Bolo tam mierne doplnenie kolmogorovskej zložitosti (Martin Lof: Neexistuje A, že C(A redukované na n) > n-c) atiež prečo chceme bezprefixovosť a potom ešte existencia A a B, ktoré sú turingovsky neporovnateľné (prioritnou metódou).

Otazky z 9.6.2009
[list=1]
[*]Věta o aritmetické hierarchii[/*]
[*]Výběr z:
[list=a]
[*]existence 1-generické množiny[/*]
[*]nekonečný nerekurzivní strom má nekonečnou větev[/*]
[*]příklady Π[sub]2[/sub]-úplných a Σ[sub]2[/sub]-úplných množin[/*]
[/list]
[/*]
[/list]

1) Základní vlastnosti operace skoku
2) a) existuje 1-generická A <=[sub]T[/sub] emptyset' ; b) nekonečný nerekurzivní strom má nekonečnou větev

Ve dvojce jsme si mohli vybrat jednu z možností, protože se na začátku ptal, jestli jsme se učili i věci okolo 1-generičnosti (asi mu někdo tvrdil, že měl za to, že se to nebude zkoušet). O všeobecné úspěšnosti nemůžu spolehlivě poreferovat, protože tam byla asi půlka lidí na Vyčíslitelnost I (já měl za 2), ale všichni jsme byli odbaveni dost rychle.