FPF:UIDI011 Theory of Computability and Co - Course Information
UIDI011 Theory of Computability and Complexity
Faculty of Philosophy and Science in OpavaWinter 2007
- 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)
- 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. While programy, jejich výpočetní ekvivalence s Turingovým strojem. Primitivní rekurzívní funkce: charakterizace vyčíslitelných funkcí nezávislá na výpočetním modelu. 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. Příklady nerozhodnutelných problémů: problém dláždění, Postův korespondenční problém, desátý Hilbertův problém. Rozhodnutelné a nerozhodnutelné vlastnosti jazyků, Chomského hierarchie. Problémy a algoritmy. Turingův stroj, míry složitosti Turingova stroje, věta o urychlení, věta o kompresi. RAM a míry složitosti stroje. Ekvivalence Turingových strojů a RAM. Složitost jejich vzájemné simulace. Vícepáskové Turingovy stroje, redukce počtu pásek, nedeterministické TS a složitost vzájemné simulace. Třídy P a NP. NP úplné problémy. Paralelní výpočty a jejich složitost.
- Language of instruction
- Czech
- Further Comments
- The course can also be completed outside the examination period.
- Enrolment Statistics (Winter 2007, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2007/UIDI011