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í
prof. RNDr. Luboš Brim, CSc. (přednášející)
prof. RNDr. Jan Strejček, Ph.D. (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
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ě.
Předmět je zařazen také v obdobích léto 1996, léto 1997, léto 1998, jaro 1999, jaro 2000, jaro 2001, jaro 2003.