I046 Vyčíslitelnost II

Fakulta informatiky
léto 1998
Rozsah
0/2. 2 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.
Předpoklady
I007 Vyčíslitelnost
Předpoklady: I007 Vyčíslitelnost,I011 Sémantiky programovacích jazyků, M006 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
Osnova
  • Seminář je zaměřen na podrobné studium okruhů vybraných z níže uvedeného seznamu. Předpokládá se aktívní účast studentů spočívající v nastudování a přednesení problematiky zadané po dohodě s vedoucím semináře. Po referátu bude následovat diskuse k přednesenému tématu.
  • Věta o rekurzi. Zobecněná Riceova věta, Rogersova věta o isomorfismu.
  • Aplikace v logice. Aritmetické množiny a funkce, Gödelova--Rosserova věta o neúplnosti.
  • Kleeneho hierarchie. T-redukce, aritmetická hierarchie.
  • Analytická hierarchie, aplikace v logice.
  • Vyčíslitelnost nespočetných množin. Úplné částečně uspořádané množiny, denotační sémantika programovacích jazyků.
Předmět je zařazen také v obdobích jaro 1999, jaro 2000.