Vyčíslitelnost II

Ahoj, právě jsem zjistil, že mi chybí poznámky k druhé přednášce z Vyčíslitelnosti II, začíná to relativní vyčíslitelností. Mohl by je prosím někdo dát do studnice? Pokud je to ve Strojilovejch skriptech, tak mi stačí když sem někdo napíše co se tam dělalo a kde to v nich je. Předem moc díky.

Nabízím vlastní (skoro úplný) výpis učiva z Vyčíslitelnosti II na tři A4ky (.odt k úpravě), vhodný na opakování nebo "rychloučení" v tramvaji nebo před zkouškou. :P Dělal jsem je podle vlastního sešitu a konce Strojilových skript, dvě vynechané hodiny jsem doplnil z kompletního naskenovaného sešitu někoho jiného, který se s tím mým shodoval snad z 95%. Enjoy & feel free to edit. :wink:

Ja som nevynechal ani jednu prednasku, o to viac som prekvapeny z obsahu tvojich poznamok

1, imunna, hyperimunna, simple a hypersimple sa vobec neriesili
2, definicia turingovskej prevoditelnosti je zle: nie efektivne vycislitelna ale totalne vycislitelna, (lebo je to ORF prevod)
3, k crfal - tam hlavne daj ze je to rekurzivne spocetna mnozina trojic s funkcionalnou vlastnostou (nie syntax)
4, konigova lemma je lahke, tam je skor dolezite, to ze v rekurzivnom strome vies najst nekonecny string pomocou emptyset' (teda K)

inak poznamky by som riesil z tadeto : http://wiki.matfyz.cz/wiki/TIN065_Predn ... C5%A1ka_00

ako zaujimavy sposob zhrnutia, ale vyzera ze to napisal niekto, kto kracal daleko od vycislitelnosti.

ked kratke poznamky tak
1, def. CRF-AL, numeracia CRF, s-m-n veta
2, definicia skoku a veta o skoku
3, definicia limitnej vycislitelnosti a ekvivalencia so skokom
4, definicia aritmetickej hierarchii a vety o aritmetickej hierarchii
5, PI_2 uplna, SIGMA_2 uplna, SIGMA_3 uplna\
6, definicia 1 genericnosti a existencia takej mnoziny cez emptyset'
7, definicia rekurzivneho stromu a to ze vieme najst nekonecnu vetvu pomocou emptyset'

Jelikož jsem chyběl zrovna na první přednášce, bez ověření jsem předpokládal, že co je v naskenovaném sešitě před mými poznámkami z druhé přednášky, to tvoří první přednášku (jinak se totiž ten sešit až překvapivě shodoval). Tento fakt odpovídá na tvé body 1 a 2, které jsou v tom starém naskenovaném sešitě jako první přednáška. Ad 3: ČRFál je tam takto zapsán. Pokud jde o množství informací, které uvádět a které ne, to asi bude vždycky subjektivní. Ad 4: Občas jsem vynechal pasáže kvůli nedostatku času (zítra jdu na zkoušku :oops:).
Každopádně díky za poznámky a za odkaz. :wink:
Btw pochopil jsem správně, že ta jedenáctá přednáška se zkoušet nebude? Resp. není tu někdo, kdo už zkoušku z vyčíslitelnosti II absolvoval a podělil by se o zadané otázky?

1. Základní vlastnosti operace skoku

2. a) existuje 1-generická A <=_T 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.

Otazky z 9.6.2009

1. Věta o aritmetické hierarchii

2. Výběr z:

   1. existence 1-generické množiny

   2. nekonečný nerekurzivní strom má nekonečnou větev

   3. příklady Π₂-úplných a Σ₂-úplných množin{: style="list-style-type:lower-alpha"} {: style="list-style-type:decimal"}

Doplnil som poznámky z prednášok o zhrnutie pred skúškou.
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).

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

kaktus64 wrote: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

Jen doplnim, ze k jednicce dal hint, ze je to konstrukce 1-genericke mnoziny

Zkouška 15. 6. vypadala takto: 1. Limitní vyčíslitelnost, 2. Příklady $\Sigma_2$, resp. $\Pi_2$-ú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ě!

vcera (28.6) boli rovnake otazky

adam wrote:1. Limitní vyčíslitelnost, 2. Příklady $\Sigma_2$, resp. $\Pi_2$-úplných.

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 ;)

Dnes klasika: 1) skok 2) lim. vycislitelnost

1. skok

2. výběr:

• konstrukce $\emptyset<A<\emptyset'$

• konstrukce 1-generické $A<\emptyset'$

Žá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 jsou jedny celkem obsáhlé zápisky, jen tady nefungují odkazy :) Já to zjistil až teď.

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 shrnutí, nicméně doporučuji zabrousit i do jednotlivých přednášek, protože spousta témat je tam hezky "lidsky" vysvětlena.

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)

1. limitní vyčíslitelnost

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

otazky jsou porad stejne

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

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)