IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2021
Rozsah
2/0/0. 2 kr. (plus ukončení). 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
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
St 14:00–15:50 Virtuální místnost
Předpoklady
Jsou předpokládány znalosti odpovídající předmětu IB107 Vyčíslitelnost a složitost
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á 19 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.
Po skončení kurzu student porozumí základním výsledkům o vyčíslitelnosti nad nespočetnými množinami; bude schopen zhodnotit další poznatky o klasifikaci problémů, zejména aritmetické hierarchii a relativizované teorii vyčíslitelnosti.
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
Výukové metody
přednáška, domácí úkoly
Metody hodnocení
Zkouška je písemná. Při 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
https://www.fi.muni.cz/usr/brim/home/#teaching
Předmět je zařazen také v obdobích podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2022.