M8890 Vyčíslitelnost

Přírodovědecká fakulta
jaro 2001
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)
Cíle předmětu
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 2000.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/sci/jaro2001/M8890