Português English

Lista de Disciplinas | CMP615

Exame de Qualificação em Abrangência: Theory of Computation

Professor: André Grahl Pereira
Prerequisites: –
Hours: 15 hs
Credits: 1
Semesters: First and second semesters
Undergraduate Enrollment: Not allowed
Page Link: –


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


Ensure that the students have sufficient basic knowledge of theory of computation for successful Ph.D. studies.


There are two meetings between professor and students:
i) in the first meeting the procedures for qualification are exposed;
ii) in the second meeting the students have the qualification test.

The information about in which week the qualification test is applied can be found in the link “Calendário”, available under the “Institucional” link of the PPGC webpage (http://ppgc.inf.ufrgs.br/). The exact day is informed by the professor in the first meeting.


For approval, students should obtain a score >= 6,0.


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