Vyčíslitelnost II

Uživatelský avatar
langosh
Matfyz(ák|ačka) level II
Příspěvky: 96
Registrován: 28. 1. 2006 13:20
Typ studia: Informatika Mgr.
Bydliště: Bohnice
Kontaktovat uživatele:

Vyčíslitelnost II

Příspěvek od langosh »

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.
Ceberus
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 28. 10. 2007 23:37
Typ studia: Informatika Mgr.
Bydliště: Petřvald u N.J. / kolej 17.listopadu
Kontaktovat uživatele:

Re: Vyčíslitelnost II

Příspěvek od Ceberus »

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:
mito
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 1. 4. 2008 11:16
Typ studia: Informatika Mgr.

Re: Vyčíslitelnost II

Příspěvek od mito »

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'
Ceberus
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 28. 10. 2007 23:37
Typ studia: Informatika Mgr.
Bydliště: Petřvald u N.J. / kolej 17.listopadu
Kontaktovat uživatele:

Re: Vyčíslitelnost II

Příspěvek od Ceberus »

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?
Ceberus
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 28. 10. 2007 23:37
Typ studia: Informatika Mgr.
Bydliště: Petřvald u N.J. / kolej 17.listopadu
Kontaktovat uživatele:

[Zk] 2.6.2009

Příspěvek od Ceberus »

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.
Uživatelský avatar
snail
Matfyz(ák|ačka) level III
Příspěvky: 144
Registrován: 23. 5. 2005 22:31
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Vyčíslitelnost II

Příspěvek od snail »

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 Π2-úplných a Σ2-úplných množin
Uživatelský avatar
Stevko
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 31. 1. 2007 21:52
Typ studia: Informatika Mgr.
Bydliště: kolej

Re: Vyčíslitelnost II

Příspěvek od Stevko »

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).
kaktus64
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 3. 6. 2008 10:42
Typ studia: Informatika Mgr.

Re: Vyčíslitelnost II

Příspěvek od 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
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: Vyčíslitelnost II

Příspěvek od Myshaak »

kaktus64 píše: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
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Vyčíslitelnost II

Příspěvek od adam »

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ě!
dmt
Matfyz(ák|ačka) level I
Příspěvky: 29
Registrován: 7. 5. 2006 21:52
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Vyčíslitelnost II

Příspěvek od dmt »

vcera (28.6) boli rovnake otazky
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Vyčíslitelnost II

Příspěvek od peci1 »

adam píše: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 ;)
iiimi

Re: Vyčíslitelnost II

Příspěvek od iiimi »

Dnes klasika: 1) skok 2) lim. vycislitelnost
vojta_vorel
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 14. 1. 2011 15:10
Typ studia: Informatika Ph.D.

Re: Vyčíslitelnost II

Příspěvek od vojta_vorel »

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ď.
tobik
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 27. 5. 2011 18:10
Typ studia: Informatika Bc.

Re: Vyčíslitelnost II

Příspěvek od tobik »

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

Zpět na „I1 Ostatní Teoretická informatika“