UIBUC15 Computability and Complexity Theory

Faculty of Philosophy and Science in Opava
Winter 2010
Extent and Intensity
2/2/0. 5 credit(s). Type of Completion: zk (examination).
Teacher(s)
RNDr. Miroslav Langer, Ph.D. (seminar tutor)
Guaranteed by
doc. Ing. Petr Sosík, Dr.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Prerequisites (in Czech)
UIAI019 Základy teoretické informatiky II || UIAI219 Základy teoretické informatiky II || UIBUC09 Theory of Languages and Automa || UINK106 Theory of Languages and Automa || UIN1006 Theory of Languages and Automa
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
Course objectives (in Czech)
Jsou předvedeny základní abstraktní modely výpočtu - Turingův stroj a stroj RAM. Na jejich bázi je vybudován koncept strojové vyčíslitelnosti, ukázána existence nevyčíslitelných problémů a jejich typické příklady. Dále je zavedena asymptotická výpočetní složitost algoritmů, umožňující porovnávat spotřebu paměti a strojového času bez vazby na konkrétní počítač. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášky.
Language of instruction
Czech
Further Comments
The course can also be completed outside the examination period.
The course is also listed under the following terms Winter 2011, Winter 2012, Winter 2013, Winter 2014, Winter 2015, Winter 2016, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021.
  • Enrolment Statistics (Winter 2010, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2010/UIBUC15