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

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

• Aplikovaná informatika (program FI, N-AP)
• Bezpečnost informačních technologií (program FI, N-IN)
• Bioinformatika (program FI, N-AP)
• Informační systémy (program FI, N-IN)
• Informatika (program FI, M-IN)
• Informatika (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)
• Teoretická informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Učitelství výpočetní techniky pro střední školy (program FI, M-TV)
• 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.

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.

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