FPF:UIDI011 Theory of Computability and Co - Course Information
UIDI011 Theory of Computability and Complexity
Faculty of Philosophy and Science in OpavaWinter 2012
- Extent and Intensity
- 0/0. 0 credit(s). Type of Completion: dzk.
- Guaranteed by
- doc. Ing. Petr Sosík, Dr.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Autonomous Systems (programme FPF, P1801 Inf)
- Course objectives (in Czech)
- 1. Abstraktní počítač a Entscheidungsproblem, modely abstraktního počítače, Turingova - Churchova teze. Turingův stroj (TS), vyčíslení funkcí pomocí TS, rekurzívní a částečně rekurzívní funkce. 2. While programy, jejich výpočetní ekvivalence s Turingovým strojem. 3. Primitivní rekurzívní funkce: charakterizace vyčíslitelných funkcí nezávislá na výpočetním modelu. 4. Rekurzívní a rekurzívně spočetné množiny, Riceova věta. Rozhodnutelné a nerozhodnutelné problémy, problém zastavení. Metoda diagonalizace a metoda redukce. 5. Příklady nerozhodnutelných problémů: problém dláždění, Postův korespondenční problém, desátý Hilbertův problém. 6. Rozhodnutelné a nerozhodnutelné vlastnosti jazyků, Chomského hierarchie. 7. Problémy a algoritmy. 8. Turingův stroj, míry složitosti Turingova stroje, věta o urychlení, věta o kompresi. 9. RAM a míry složitosti stroje. Ekvivalence Turingových strojů a RAM. Složitost jejich vzájemné simulace. 10. Vícepáskové Turingovy stroje, redukce počtu pásek, nedeterministické TS a složitost vzájemné simulace. 11. Třídy P a NP. NP úplné problémy. 12. Paralelní výpočty a jejich složitost. Odborná literatura: 1. Gruska, J.: Foundations of Computing. London: International Thomson Computer Press, 1997. 2. Hopcroft, J. E. - Ullman, J. D.: Formálne jazyky a automaty. Bratislava: Alfa, 1978. 3. Kozen, D. C.: Automata and Computability. New York: Springer-Verlag, 1997. 4. Černá, I.: Úvod do teórie zložitosti. Brno: FI MU, 1993. 5. Wiedermann, J.: Zložitosť: Strojovo orientovaná teória výpočtovej zložitosti sekvenčných a paralelných výpočtov. Zborník SOFSEM´86 Liptovský Ján, 1986, 367-396.
- Language of instruction
- Czech
- Further Comments
- The course can also be completed outside the examination period.
- Enrolment Statistics (Winter 2012, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2012/UIDI011