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 [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í
• 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

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.

Poslední úprava: T_KNM (19.05.2008)

angličtina

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

Poslední úprava: T_KNM (19.05.2008)

Cíl předmětu

čeština

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

Poslední úprava: T_KNM (19.05.2008)

angličtina

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

Poslední úprava: T_KNM (19.05.2008)

Literatura

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

Poslední úprava: T_KNM (19.05.2008)

Metody výuky

čeština

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

Poslední úprava: T_KNM (19.05.2008)

angličtina

Lectures in a lecture hall.

Poslední úprava: T_KNM (19.05.2008)

Požadavky ke zkoušce

čeština

Zkouška dle sylabu.

Poslední úprava: T_KNM (19.05.2008)

angličtina

Examination according to the syllabus.

Poslední úprava: T_KNM (19.05.2008)

Sylabus

čeština

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.

Poslední úprava: T_KNM (19.05.2008)

angličtina

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.

Poslední úprava: T_KNM (19.05.2008)

Vstupní požadavky

čeština

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

Poslední úprava: T_KNM (19.05.2008)

angličtina

There are no special entry requirements.

Poslední úprava: T_KNM (19.05.2008)

Požadavky k zápisu

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

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