PředmětyPředměty(verze: 850)
Předmět, akademický rok 2019/2020
   Přihlásit přes CAS
Vyčíslitelnost - NLTM021
Anglický název: Computability
Zajišťuje: Středisko informatické sítě a laboratoří (32-SISAL)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: http://www.win.ms.mff.cuni.cz
Garant: RNDr. Vojtěch Jákl
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: T_KNM (19.05.2008)
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.
Cíl předmětu -
Poslední úprava: T_KNM (19.05.2008)

Studenti se seznámí s algoritmicky vyčíslitelnými a rekursivními funkcemi.

Literatura
Poslední úprava: T_KNM (19.05.2008)

Davis M.: Computability and unsolvability. Mc Graw Hill, N.Y., 1958

Rogers H. jr.: Theory of recursive functions and effective computability. Mc Graw Hill, N.Y., 1967

Metody výuky -
Poslední úprava: T_KNM (19.05.2008)

Přednášky v posluchárně.

Požadavky ke zkoušce -
Poslední úprava: T_KNM (19.05.2008)

Zkouška dle sylabu.

Sylabus -
Poslední úprava: T_KNM (19.05.2008)

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.

Vstupní požadavky -
Poslední úprava: T_KNM (19.05.2008)

Nejsou předpokládány žádné speciální znalosti.

Požadavky k zápisu
Poslední úprava: RNDr. Vojtěch Jákl (24.02.2016)

tento předmět se již nevyučuje

 
Univerzita Karlova | Informační systém UK