Vyčíslitelnost - NLTM021
|
|
|
||
Poslední úprava: T_KNM (19.05.2008)
|
|
||
Poslední úprava: T_KNM (19.05.2008)
Studenti se seznámí s algoritmicky vyčíslitelnými a rekursivními funkcemi. |
|
||
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 |
|
||
Poslední úprava: T_KNM (19.05.2008)
Přednášky v posluchárně. |
|
||
Poslední úprava: T_KNM (19.05.2008)
Zkouška dle sylabu. |
|
||
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. |
|
||
Poslední úprava: T_KNM (19.05.2008)
Nejsou předpokládány žádné speciální znalosti. |