Informace o předmětu

IA046 Vyčíslitelnost

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ě.

IA046 Vyčíslitelnost

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

IA046 Computability

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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ě.

IA046 Vyčíslitelnost

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ě.

IA046 Vyčíslitelnost

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ě.

IA046 Vyčíslitelnost

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

• Aplikovaná informatika (program FI, N-AP)
• Informatika (program FI, M-IN)
• Informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)

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ě.

IA046 Vyčíslitelnost

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.

IA046 Computability

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

IA046 Vyčíslitelnost

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.

• Statistika zápisu (nejnovější)