Předmět Vyčíslitelnost a složitost 2 (KIP / XVYS2)
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 KIP / XVYS2 - Vyčíslitelnost a složitost 2, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
Materiál | Typ | Datum | Počet stažení |
---|
Další informace
Obsah
1. Parciální funkce2. Počáteční funkce3. Primitivně rekurzívní funkce4. Rozsah primitivně rekurzívních funkcí5. Příklady primitivně rekurzívních funkcí6. Parciálně rekurzívní funkce, definice7. Funkce vyčíslitelné Turingovými stroji8. Parciální rekurzívní povaha Turingových strojů9. Vyjadřovací síla programovacích jazyků10. Skeletový programovací jazyk11. Parciálně rekurzívní funkce ve skeletovém jazyku12. Funkce programovatelné ve skeletovém jazyku
Získané způsobilosti
- znalost hlubších vztahů teorie vyčíslitelnosti a složitosti- dobrá znalost vlastností formalizací pojmu algoritmu (Turingův stroj, rekurzivní funkce, PL-programy) a jejich ekvivalence- schopnost konstrukce Turingových strojů,rekurzivních funkcí, PL-programů včetně výpočtů složitosti, - složitější NP úplné problémy a jejich převeditelnost
Literatura
http://www.cs.vsb.cz/jancar/Pavliska V. Vyčíslitelnost a složitost II., OU Ostrava, 2003. CHYTIL, Milan. Automaty a gramatiky. Praha, SNTL, 1984. U. Manber. Introduction to Algorithms, Addison-Wesley. A. Aho, J. Hopcroft, J. Ullman. The design and analysis of computer algorithms, Addison-Wesley, London 1974. Habiballa H. Vyčíslitelnost a složitost. MFI Prometheus Praha, 2005.
Požadavky
Vypracování jednoho korespondenčního úkolu, ústní zkouška skládající se zedvou teoretických otázek vycházejících ze studijní opory k danému předmětu. hodnocení dle platných předpisů na základě bodů (škála 0-100 b.)
Garant
doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.prof. Irina Perfiljeva, CSc.
Vyučující
doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.prof. Irina Perfiljeva, CSc.doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.prof. Irina Perfiljeva, CSc.