Lista de Disciplinas | CMP613

Theory of Computation

Professor: André Grahl Pereira
Prerequisites: –
Hours: 30 hs
Credits: 2
Semesters: First and second semesters
Undergraduate Enrollment: –
Page Link: –

SUMMARY

Models of computation. Limits of formal systems. Complexity theory.

OBJECTIVES

This course will introduce the main models of computation, justifying each model and comparing them. We will also study classes of problems that can or can not be solved by computers (limits of computation) as well as how to classify the computable problems according to how efficiently they can be solved (complexity theory). After successful completion of the course, the students are expected to: (i) understand what a model of computation is and understand the main models (ii) be able to analyze whether a problem may have an algorithmic solution or not (iii) know the main complexity classes.

PROGRAM

1. Turing Machines and the Church-Turing Thesis (chapter 3)
2. Decidability and Undecidability (chapters 4 and 5)
3. Reducibility (chapter 5)
4. Time Complexity and Space Complexity (chapters 7 and 8)
5. Intractability (chapter 9)

EVALUATION

Students will be evaluated during the course through exams or exercise lists, as informed by the instructor at the beginning of the course. At the end of the semester, there will be an exam that can substitute the final score obtained. The possible grades are A (score >= 9.0), B (score >= 7.5 and < 9.0), C (score >= 6.0 and < 7.5), D (failed, score< 6.0) or FF (failed, the student attended less than 75% of the classes).

BIBLIOGRAPHY

Michael Sipser. Introduction to the Theory of Computation, Cengage Learning, 2013.