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
Anotace
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.
Klíčová témata
  • 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.
Studijní zdroje a literatura
  • Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987, 482 s. ISBN 0262680521. info
Přístupy, postupy a metody používané ve výuce
přednáška, domácí úkoly
Způsob ověření výstupů z učení a požadavky na ukončení
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.
Odkaz a informace vyučujících
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.