Předmět Vyčíslitelnost (NLTM021)
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 NLTM021 - Vyčíslitelnost, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
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
Studenti se seznámí s algoritmicky vyčíslitelnými a rekursivními funkcemi.
Sylabus
Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Rekursivní a rekursivně spočetné množiny a predikáty. Časová a prostorová složitost algoritmů a problémů, NP-úplnost. Turingův stroj. Rekursivní funkce. Primitivně rekursivní funkce. Kleeneho věta o normální formě. Semirekursivní predikáty. Kleeneho enumerační věta.
Literatura
Davis M.: Computability and unsolvability. Mc Graw Hill, N.Y., 1958Rogers H. jr.: Theory of recursive functions and effective computability. Mc Graw Hill, N.Y., 1967
Požadavky
Zkouška dle sylabu.
Garant
RNDr. Vojtěch Jákl