M8890 Vyčíslitelnost

Přírodovědecká fakulta
jaro 2000
Rozsah
2/1/0. 5 kr. Ukončení: zk.
Vyučující
prof. RNDr. Luboš Brim, CSc. (přednášející)
Garance
prof. RNDr. Luboš Brim, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
Mateřské obory/plány
  • Matematika (program PřF, M-MA, směr Diskrétní matematika)
  • Matematika (program PřF, N-MA, směr Diskrétní matematika)
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 rekurzivně 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í.
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2001.