Vyčíslitelnost - NLTM021

• Anglický název: Computability
• Zajišťuje: Katedra numerické matematiky (32-KNM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2011 do 2016
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• 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
• Je záměnnost pro: NLTM020

Anotace

čeština

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.

angličtina

Poslední úprava: T_KNM (19.05.2008)

Enumerable functions, possible definitions, properties. Recursive and recursively enumerable sets and semirecursive predicates. Time and space complexity.

Cíl předmětu

čeština

Poslední úprava: T_KNM (19.05.2008)

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

angličtina

Poslední úprava: T_KNM (19.05.2008)

The course gives students a knowledge of enumerable and recursive functions.

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

čeština

Poslední úprava: T_KNM (19.05.2008)

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

angličtina

Poslední úprava: T_KNM (19.05.2008)

Lectures in a lecture hall.

Požadavky ke zkoušce

čeština

Poslední úprava: T_KNM (19.05.2008)

Zkouška dle sylabu.

angličtina

Poslední úprava: T_KNM (19.05.2008)

Examination according to the syllabus.

Sylabus

čeština

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.

angličtina

Poslední úprava: T_KNM (19.05.2008)

Enumerable functions, their properties, equivalence of their various mathematical definitions. Recursive and recursively enumerable sets and predicates.

Turing Machines' ability to compute all recursive functions. Recursive functions, primitive recursive functions, predicates and sets. Emulation of Turing Machine by primitive recursive functions and predicates. Kleene's theorems. Semirecursive predicates. Predicates that are not recursive. Predicates that are not semirecursive. Creative and simple functions.

Vstupní požadavky

čeština

Poslední úprava: T_KNM (19.05.2008)

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

angličtina

Poslední úprava: T_KNM (19.05.2008)

There are no special entry requirements.

Požadavky k zápisu

Poslední úprava: RNDr. Vojtěch Jákl (24.02.2016)

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