Vyčíslitelnost II
- 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
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.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 22
- Registrován: 28. 10. 2007 23:37
- Typ studia: Informatika Mgr.
- Login do SIS: brust5am
- Bydliště: Petřvald u N.J. / kolej 17.listopadu
- Kontaktovat uživatele:
Re: Vyčíslitelnost II
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. 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.
-
- 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
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'
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'
-
- Matfyz(ák|ačka) level I
- Příspěvky: 22
- Registrován: 28. 10. 2007 23:37
- Typ studia: Informatika Mgr.
- Login do SIS: brust5am
- Bydliště: Petřvald u N.J. / kolej 17.listopadu
- Kontaktovat uživatele:
Re: Vyčíslitelnost II
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 ).
Každopádně díky za poznámky a za odkaz.
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?
Každopádně díky za poznámky a za odkaz.
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?
-
- Matfyz(ák|ačka) level I
- Příspěvky: 22
- Registrován: 28. 10. 2007 23:37
- Typ studia: Informatika Mgr.
- Login do SIS: brust5am
- Bydliště: Petřvald u N.J. / kolej 17.listopadu
- Kontaktovat uživatele:
[Zk] 2.6.2009
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.
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.
- 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
Otazky z 9.6.2009
- Věta o aritmetické hierarchii
- Výběr z:
- existence 1-generické množiny
- nekonečný nerekurzivní strom má nekonečnou větev
- příklady Π2-úplných a Σ2-úplných množin
- 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
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).
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).
-
- 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
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
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
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 162
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
Re: Vyčíslitelnost II
Jen doplnim, ze k jednicce dal hint, ze je to konstrukce 1-genericke mnozinykaktus64 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
"Go for the eyes Boo, go for the eyes! Yeahh!!"
- 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
Zkouška 15. 6. vypadala takto: 1. Limitní vyčíslitelnost, 2. Příklady , resp. -ú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. 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ě!
Na zkoušce jsme byli tři (nebudu jmenovat, ale styďte se;)!), a po zadání dva lidé odešli. 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ě!
-
- 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
vcera (28.6) boli rovnake otazky
-
- 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
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 alladam píše:1. Limitní vyčíslitelnost, 2. Příklady , resp. -úplných.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 49
- Registrován: 14. 1. 2011 15:10
- Typ studia: Informatika Ph.D.
- Login do SIS: 35685873
Re: Vyčíslitelnost II
1) skok
2) výběr:
- konstrukce
- konstrukce 1-generické
Žá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ď.
2) výběr:
- konstrukce
- konstrukce 1-generické
Žá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ď.
-
- 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
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ů 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) 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ů 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.