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

I007 Vyčíslitelnost

Rozsah

0/0. 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

• Informatika (program FI, B-IN)
• Informatika (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Výpočetní technika (program FI, B-IN)

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í.

• Statistika zápisu (léto 1996, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/leto1996/I007