#
FPF:UIMOIBP017 Computability and Complexity - Course Information

## UIMOIBP017 Computability and Complexity

**Faculty of Philosophy and Science in Opava**

Winter 2021

**Extent and Intensity**- 2/2/0. 6 credit(s). Type of Completion: zk (examination).
**Teacher(s)**- doc. Ing. Petr Sosík, Dr. (lecturer)

Mgr. Tomáš Filip (seminar tutor)

Mgr. Ondřej Mazurek (seminar tutor)

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 9:45–11:19 232
- Timetable of Seminar Groups:

*T. Filip, P. Sosík* **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**- 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

*required 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

*recommended literature***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**- Study Materials

- Enrolment Statistics (recent)

- Permalink: https://is.slu.cz/course/fpf/winter2021/UIMOIBP017