Předmět Vyčíslitelnost (IA046)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IA046 - Vyčíslitelnost, Fakulta informatiky, Masarykova univerzita (MU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
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í kurzustudent 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 aprediká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
ROGERS, Hartley. Theory of Recursive Functions and Effective Computability. Cambridge: Massachusetts Institute of Technology, 1987. 482 s. ISBN 0-262-68052-1. info
Požadavky
Jsou předpokládány znalosti odpovídající předmětům IB107 Vyčíslitelnost a složitost,M4155
Garant
prof. RNDr. Mojmír Křetínský, CSc.
Vyučující
prof. RNDr. Luboš Brim, CSc.