IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2006
Rozsah
2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučující
prof. RNDr. Luboš Brim, CSc. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
Rozvrh
Čt 14:00–15:50 B410
Předpoklady
! I046 Vyčíslitelnost II
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,MA006 Teorie množin
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
předmět má 7 mateřských oborů, zobrazit
Cíle předmětu
Předmět je zaměřen na hlubší studium výsledků teorie vyčíslitelnosti s důrazem na osvojení si používaných důkazových metod a technik.
Osnova
  • 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í.
  • Aritmetické množiny a funkce, Goedelova-Rosserova věta o neúplnosti, druhá Goedelova věta o neúplnosti.
  • Relativizovaná teorie vyčíslitelnosti. Programy s orákulem.
  • Kleeneho hierarchie. T-redukce, aritmetická hierarchie, tt-redukovatelnost.
  • Postův problém.
  • Analytická hierarchie.
  • Vyčíslitelnost nespočetných množin. Úplné částečně uspořádané množiny, domény.
Literatura
  • Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987, 482 s. ISBN 0262680521. info
Metody hodnocení
Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.
Informace učitele
http://www.fi.muni.cz/usr/brim/IA046
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2002, jaro 2004, jaro 2005, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.