UIIABP0022 Computability and Complexity

Faculty of Philosophy and Science in Opava
Winter 2022
Extent and Intensity
2/2/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. Ing. Petr Sosík, Dr. (lecturer)
doc. Ing. Petr Sosík, Dr. (seminar tutor)
Guaranteed by
doc. Ing. Petr Sosík, Dr.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Timetable
Wed 10:35–12:10 B2
  • Timetable of Seminar Groups:
UIIABP0022/A: Wed 13:55–15:30 B3b, P. Sosík
Prerequisites
- elements of propositional logic - elements of graph theory - basics of procedural programming
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
Abstract machine models of computation - the Turing Machine and the RAM - are introduced. The concept of machine computability is built on their basis. The existence of non-computable problems is proven and their examples given. In the second part of the course, asymptotical time and space complexity of algorithms is introduced. This allows to describe the consumption of time and space of algorithms without fixing to any particular computing machine. Elementary complexity classes and their properties are studied, with special emphasis on the classes P and NP.
Learning outcomes
Students will be able to distinguish computer-computable and non-computable problems in practice. They will be able to determine at least basically the computational complexity of a given problem and adapt the way of its algorithmic solution.
Syllabus
  • 1. Turing machine - model of mechanical computer 2. Recursive and recursively enumerable sets, diagonalization method 3. Decidable and undecidable problems, reduction method 4. Rice's theorem 5. Introduction to computational complexity, asymptotics 6. Time and space complexity of algorithms 7. RAM machine: a realistic computer model 8. Computational complexity of common programs 9. Basic complexity classes 10. Relationships between complexity classes 11. NP-complete problems 12. Applications: Dynamic programming
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. 3rd ed. Boston, MA: Course Technology CengageLearning, 2012. ISBN 978-1-133-18779-0. info
  • Sosík, P. Teorie vyčíslitelnosti. Online studijní text. Opava: FPF SU, 1996. info
    recommended literature
  • HOPCROFT, JOHN E, Rajeev MOTWANI and JEFFREY D ULLMAN. Introduction to automata theory, languages, and computation. Harlow: Pearson Addison-Wesley, 2014. ISBN 978-1-292-03905-3. info
  • DU, Dingzhu and Ker-I KO. Theory of computational complexity. Second edition. Hoboken, New Jersey: Wiley, 2014. ISBN 978-1-118-30608-6. info
  • Černá, I. Úvod do teórie zložitosti. Brno: FI MU, 1993. info
Teaching methods
Lecture, tutorial
Assessment methods
Credit: • development of Turing machine according to individual assignment • partial credit tests at seminars Exam: • written exam, semestral work, individual project
Language of instruction
Czech
Further Comments
Study Materials
The course is also listed under the following terms Winter 2020, Winter 2021, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2022, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2022/UIIABP0022