IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2022
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
Út 15. 2. až Út 10. 5. Út 10:00–11:50 B411
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
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 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021.

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.

IA046 Computability

Fakulta informatiky
jaro 2018
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
Předpoklady
SOUHLAS
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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.
Vyučovací jazyk
Angličtina
Informace učitele
http://www.fi.muni.cz/usr/brim/IA046
Další komentáře
Výuka probíhá každý týden.
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 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2016
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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Čt 16:00–17:50 B410
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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
http://www.fi.muni.cz/usr/brim/IA046
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
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 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2014
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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Čt 14:00–15:50 B410
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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á 18 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
http://www.fi.muni.cz/usr/brim/IA046
Další komentáře
Předmět je vyučován jednou za dva roky.
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 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2012
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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Čt 12:00–13:50 D3
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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.
Cílem předmětu je: seznámit se základními výsledky o vyčíslitelnosti nad nespočetnými množinami; získat další poznatky o klasifikaci problémů, zejména aritmetické hierarchii; seznámit se s relativizovanou teorií 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
http://www.fi.muni.cz/usr/brim/IA046
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2010
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 B411
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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á 18 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.
Cílem předmětu je: seznámit se základními výsledky o vyčíslitelnosti nad nespočetnými množinami; získat další poznatky o klasifikaci problémů, zejména aritmetické hierarchii; seznámit se s relativizovanou teorií 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
http://www.fi.muni.cz/usr/brim/IA046
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2008
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 B411
Předpoklady
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á 18 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 jednou za dva roky.
Předmět je zařazen také v obdobích podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

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.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2005
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 určen pouze studentům mateřských oborů.
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 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2004
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 B411
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 určen pouze studentům mateřských oborů.
Mateřské obory/plány
předmět má 6 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 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
podzim 2002
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 12:00–13:50 B411
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 určen pouze studentům mateřských oborů.
Mateřské obory/plány
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í.
  • 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 každoročně.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2023

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

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
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á 20 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
Další komentáře
Studijní materiály
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 podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Computability

Fakulta informatiky
jaro 2019

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

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
Předpoklady
SOUHLAS
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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.
Vyučovací jazyk
Angličtina
Informace učitele
http://www.fi.muni.cz/usr/brim/IA046
Další komentáře
Předmět již není vypisován.
Výuka probíhá každý týden.
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 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2017

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

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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
http://www.fi.muni.cz/usr/brim/IA046
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 podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2015

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

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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á 18 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
http://www.fi.muni.cz/usr/brim/IA046
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 podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2013

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

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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á 18 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.
Cílem předmětu je: seznámit se základními výsledky o vyčíslitelnosti nad nespočetnými množinami; získat další poznatky o klasifikaci problémů, zejména aritmetické hierarchii; seznámit se s relativizovanou teorií 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
http://www.fi.muni.cz/usr/brim/IA046
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 podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2011

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

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.
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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á 18 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.
Cílem předmětu je: seznámit se základními výsledky o vyčíslitelnosti nad nespočetnými množinami; získat další poznatky o klasifikaci problémů, zejména aritmetické hierarchii; seznámit se s relativizovanou teorií 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
http://www.fi.muni.cz/usr/brim/IA046
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 podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2009

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

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.
Předpoklady
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
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á 18 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.
Cílem předmětu je: seznámite se základními výsledky o vyčíslitelnosti nad nespočetnými množinami; získat další poznatky o klasifikaci problémů, zejména aritmetické hierarchii; seznámit se s relativizovanou teorií 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
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
http://www.fi.muni.cz/usr/brim/IA046
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 podzim 2002, jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014, jaro 2016, jaro 2018, jaro 2021, jaro 2022.

IA046 Vyčíslitelnost

Fakulta informatiky
jaro 2007

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

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.
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á 6 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 jednou za dva roky.
Výuka probíhá každý týden.
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 2021, jaro 2022.