Lista de Disciplinas | CMP622

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

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.