FI:IA046 Vyčíslitelnost - Informace o předmětu

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

• Aplikovaná informatika (program FI, N-AP)
• Bezpečnost informačních technologií (angl.) (program FI, N-IN)
• Bezpečnost informačních technologií (program FI, N-IN)
• Bioinformatika (program FI, N-AP)
• Diskrétní algoritmy a modely (program FI, N-TEI)
• Informační systémy (program FI, N-IN)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové systémy (program FI, N-IN)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Služby - výzkum, řízení a inovace (angl.) (program FI, N-AP)
• Služby - výzkum, řízení a inovace (program FI, N-AP)
• Sociální informatika (program FI, B-AP)
• Teoretická informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
• Zpracování obrazu (program FI, N-AP)

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.

• Statistika zápisu (jaro 2023, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2023/IA046