[Zk] 22. 1. 2010

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.
Martin Černý

[Zk] 22. 1. 2010

Příspěvek od Martin Černý »

Klasický systém - všichni dostali dvě stejné otázky, prof. Kučera to pak průběžně obcházel:

1) Dokažte, že každá produktivní množina má produktivní ORF
2) Dokažte existenci simple množiny

Obojí jsem naštěstí věděl, tak jsem to napsal. Prof. Kučera to projel pohledem, usoudil, že to mám správně, vůbec se v tom nehrabal, jen se mě ke 2) ještě zeptal, jak funguje selektor, tak jsem řekl, že minimalizuje obecný PRF predikat T z Kleeneho věty. S tím byl spokojen a dostal jsem za jedna.
Odcházel jsem první, takže úspěšnost si netroufám odhadnout...
Odpovědět

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