I046 Vyčíslitelnost II

Fakulta informatiky
jaro 2000
Rozsah
2/0. 2 kr. (plus ukončení). 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
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
Předpoklady
I997 Státní zkouška || ( I007 Vyčíslitelnost && M006 Teorie množin && P998 Souborná zkouška )
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
  • Věta o rekurzi. Zobecněná Riceova věta, injektivní smn-věta, Rogersova věta o isomorfismu, aplikace věty o rekurzi.
  • Aplikace v logice. 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, aplikace v logice.
  • 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
Informace učitele
http://www.fi.muni.cz/usr/brim/I046
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1998, jaro 1999.

I046 Vyčíslitelnost II

Fakulta informatiky
jaro 1999
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 && I011 Sémantiky progr. jazyků && M006 Teorie množin II
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ů.
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1998, jaro 2000.

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.

I046 Vyčíslitelnost II

Fakulta informatiky
jaro 2002

Předmět se v období jaro 2002 nevypisuje.

Rozsah
2/0. 2 kr. (plus ukončení). 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
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
Předpoklady
I997 Státní zkouška || ( I007 Vyčíslitelnost && M006 Teorie množin && P998 Souborná zkouška )
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
  • Věta o rekurzi. Zobecněná Riceova věta, injektivní smn-věta, Rogersova věta o isomorfismu, aplikace věty o rekurzi.
  • Aplikace v logice. 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, aplikace v logice.
  • 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
Informace učitele
http://www.fi.muni.cz/usr/brim/I046
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2000.

I046 Vyčíslitelnost II

Fakulta informatiky
jaro 2001

Předmět se v období jaro 2001 nevypisuje.

Rozsah
2/0. 2 kr. (plus ukončení). 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
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
Předpoklady
I997 Státní zkouška || ( I007 Vyčíslitelnost && M006 Teorie množin && P998 Souborná zkouška )
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
  • Věta o rekurzi. Zobecněná Riceova věta, injektivní smn-věta, Rogersova věta o isomorfismu, aplikace věty o rekurzi.
  • Aplikace v logice. 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, aplikace v logice.
  • 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
Informace učitele
http://www.fi.muni.cz/usr/brim/I046
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2000.