Professor: André Grahl Pereira
Prerequisites: –
Hours: 15 hs
Credits: 1
Semesters: First and second semesters
Undergraduate Enrollment: Not allowed
Page Link: –
SUMMARY
Models of computation. Limits of formal systems. Complexity theory.
OBJECTIVES
Ensure that the students have sufficient basic knowledge of theory of computation for successful Ph.D. studies.
PROGRAM
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.
EVALUATION
For approval, students should obtain a score >= 6,0.
BIBLIOGRAPHY
Michael Sipser. Introduction to the Theory of Computation, Cengage Learning, 2013.