FPF:UIMOIBP017 Computability and Complexity - Course Information
UIMOIBP017 Computability and Complexity
Faculty of Philosophy and Science in OpavaWinter 2024
- Extent and Intensity
- 2/2/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- doc. Ing. Petr Sosík, Dr. (lecturer)
Mgr. Daniel Valenta, Ph.D. (lecturer)
Mgr. Jan Schreier (seminar tutor)
doc. Ing. Petr Sosík, Dr. (seminar tutor)
Mgr. Daniel Valenta, Ph.D. (seminar tutor) - Guaranteed by
- doc. Ing. Petr Sosík, Dr.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - Timetable
- Wed 14:45–16:20 B3a
- Timetable of Seminar Groups:
- Prerequisites
- Theory of Languages and Automata I
- 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
- Information and communication technologies (programme FPF, MOI)
- 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
- Enrolment Statistics (Winter 2024, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2024/UIMOIBP017