Vyčíslitelnost I Kučera 3. 2. 2014

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Kreativní množiny.
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Vyčíslitelnost I Kučera 3. 2. 2014

Příspěvek od mathemage »

1) Existence efektivně neoddělitelných množin
2a) Efektivní generování rekurzivních množin
2b) Efektivní generování rekurzivně spočetných množin

Všechny důkazy viz Strojil. Dá se naučit za 3 dny za 1.
Carpe Diem!
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

Re: Vyčíslitelnost I Kučera 3. 2. 2014

Příspěvek od Jookyn »

Jinak Kucera je fakt hodnej, prijemna zkouska...

U 2) jsem mu napsal ty vety (vcetne variant s ORF a nekonecnymi mnozinami), ani jsem jeste nemel dopsany dukaz u 2b), ale kdyz videl, ze je tam myslenka, tak rikal, ze uz to dopisovat nemusim, ze to je dobre. U 1) jsem napsal definici efektivni neoddelitelnosti, zacal jsem dukaz existence neoddelitelnych mnozin, jen jsem se trochu zaseknul jak ma presne vypadat ta funkce, ale vedel jsem zhruba kostru (postavim tu fci, pustim ji na sebe a to bude divergovat). Ptal se mi jakou bych chtel znamku, ze to zatim vidi na 2, tak jsem hned vzal a sel...

Jinak moje pozorovani, ze v temer kazde pisemce je bud generovani R(S)M pomoci usekovych CRF, nebo konstrukce simple mnoziny se opet potvrdilo. A kdyz clovek tohle umi poradne (je to pomerne jednoduche) a zbytek umi alespon trochu, tak to podle me musi dat...
Odpovědět

Zpět na „TIN064 Vyčíslitelnost I“