UIINK25 Computability and Complexity

Faculty of Philosophy and Science in Opava
Winter 2023
Extent and Intensity
12/0/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. Ing. Petr Sosík, Dr. (lecturer)
Guaranteed by
doc. Ing. Petr Sosík, Dr.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Prerequisites
Theory of Languages and Automata I
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives
The course deals with machine computability and problem difficulty. The first part of the course - the theory of computability - examines which problems cannot be solved on computers. The second part of the subject - the theory of complexity - focus on problems that can be solved on computers. We will examine how much time and memory is needed to solve them, and we will divide the problems into different classes accordingly.
Learning outcomes
Students will be able to:
- describe the class of problems that can be solved on computer
- analyze a situation where the problem is not solved on computer
- compare various problems in terms of the complexity of their solutions
Syllabus
  • 1. Turing machine - the model of mechanical computation
  • 2. Recursive and recursively enumerable sets, method of diagonalization
  • 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. The 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
  • SOSÍK, P. Teorie vyčíslitelnosti. Online studijní text. Opava: FPF SU, 2017
  • SIPSER, Michael. Introduction to the theory of computation. 3rd ed. Boston, MA: Course Technology CengageLearning, 2012. ISBN 978-1-133-18779-0. 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
Lecturing
Interactive lecture
Assessment methods
Credit:
- elaboration of Turing machine according to individual specification
- partial credit tests at seminars
Test:
- written exam, semestral work, individual project
Language of instruction
Czech
Further comments (probably available only in Czech)
Study Materials
The course can also be completed outside the examination period.
Information on the extent and intensity of the course: Přednáška 12 HOD/SEM.
The course is also listed under the following terms Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2024.
  • Enrolment Statistics (Winter 2023, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2023/UIINK25