I007 Vyčíslitelnost

Fakulta informatiky
léto 1998
Rozsah
2/1. 3 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Luboš Brim, CSc. (přednášející)
Garance
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
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 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í.
Předmět je zařazen také v obdobích léto 1996, léto 1997, jaro 1999, jaro 2000, jaro 2001, jaro 2002, jaro 2003.