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.

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

Příspěvekod mathemage » 3. 2. 2014 10:03

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!
mathemage
Matfyz(ák|ačka) level III
 
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Login do SIS: had

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

Příspěvekod Jookyn » 3. 2. 2014 11:30

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...
Jookyn
Matfyz(ák|ačka) level III
 
Příspěvky: 115
Registrován: 13. 9. 2008 20:42
Typ studia: Informatika Mgr.
Login do SIS: 80320124


Zpět na TIN064 Vyčíslitelnost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 2 návštevníků

cron