Lista de Disciplinas | CMP600

Exame de Qualificação em Abrangência

Responsáveis: Profs. André Grahl Pereira e Santiago Valdes Ravelo

Pré-Requisitos: –
Carga Horária: 30 hs
Créditos: 2
Semestres Oferecidos: Primeiro e segundo semestres
Matrícula de Graduandos: Não permitida
Página da Disciplina: –

SUMMARY

Theory of Computation: Models of computation. Limits of formal systems. Complexity theory. Algorithms: Analysis of algorithms. Main techniques for designing algorithms.

OBJECTIVES

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

PROGRAM

There are three meetings between professors and students:
a) in the first meeting the procedures for qualification are exposed;
b) in the second meeting the students have the first qualification test.
c) Finally, in one of the last weeks of the semester, a second qualification test is applied
The information about in which weeks the qualification tests are 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 days are informed by the professors in the first meeting.

EVALUATION

For approval, students should obtain a score >= 7,0 in at least one of the two test applications of the semester

BIBLIOGRAPHY

1. Michael Sipser. Introduction to the Theory of Computation, Cengage Learning, 2013
2. J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.