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: –

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.