FI:I007 Vyčíslitelnost - Informace o předmětu

I007 Vyčíslitelnost

Fakulta informatiky
jaro 2002

Rozsah

2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

Garance

Rozvrh

St 16:00–16:50 B411, Čt 9:00–10:50 D2, Čt 15:00–15:50 B204, Čt 16:00–16:50 B204, Čt 17:00–17:50 B204

Předpoklady

I005 FJA I && (! I507 Vyčíslitelnost )&&(!NOW( I507 Vyčíslitelnost ))

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

Osnova

Algoritmus, Churchova téze.
WHILE-programy jako model algoritmu, vyčíslitelné funkce, funkce nad slovy.
Standardní numerace, věta o numeraci, věta o parametrizaci, přípustná numerace, Kleeneho věta o normální formě.
Rekurzívní a rekurzívně spočetné množiny, uzávěrové vlastnosti, numerace rekurzívně spočetných množin.
Metoda redukce a metoda diagonalizace. Problémy zastavení, verifikace, ekvivalence. Některé "přirozené" nerozhodnutelné problémy.
Riceovy věty.
Kreativní a produktivní množiny, m-ú\-pl\-né množiny a 1-úplné množiny, efektivně neoddělitelné množiny, jednoduché a imunní množiny.
Věta o rekurzi, aplikace v logice.
Primitivně rekurzívní, totálně rekurzívní a částečně rekurzívní funkce a predikáty, ekvivalence s třídou vyčíslitelných funkcí.

Literatura

KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987, 482 s. ISBN 0262680521. info
KFOURY, A. J., Robert N. MOLL a Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info

Navazující předměty

Informace učitele

http://www.fi.muni.cz/usr/brim/I007

Další komentáře

Předmět je vyučován každoročně.