[Zk] 16.2. 2012

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.
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

[Zk] 16.2. 2012

Příspěvek od Kubees »

1. konstrukce simple mnoziny
2. a) konstrukce fektivne neoddelitelne dvojice
2. b) sjednoceni ef. neod. dvojic je kreativni

U Simple mnoziny Kucera VZDY poklada otazku, jak funguje ten selektor, cili funkce, kterou v mnozine W_x hledate prvek y > 2x.

Spravna odpoved: "problem" je v tom, ze mam nekonecno mnozin W_x a potrebuju v konecnem case dojit na jakykoliv prvek jakekoliv z nich. Ta funkce ze selektoru to udela tak, ze vezme W_0 a podiva se na jeden prvek. Pak vezme W_0 a W_1 a u odbou se podiva na jeden prvek. Pak se zase vrati k W_0 a tentokrat se podiva na jeden prvek u W_0, W_1, W_2 atd. Cili vytvarime si takovy trojuhelnik prvku, ktere jsme jiz prosli.

W_0: x x x x x
W_1: x x x x
W_2: x x x
W_3: x x
W_4: x
W_5:
W_6:

U 2. otazky si clovek mohl vybrat a) nebo b)
Odpovědět

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