Carga Horária: 60h/aula (4 créditos)

EMENTA:

I. Introdução à teoria da complexidade sobre um anel: problemas de decisão, NP-completude, máquinas sobre os inteiros, formulação algébrica do problema P versus NP.

II. Geometria de Algoritmos Numéricos: iteração de Newton, complexidade do Teorema Fundamental da Álgebra, complexidade do Teorema de Bézout, números de condicionamento para problemas lineares, não lineares, e complexidade do condicionamento.

Bibliografia:

Lenore Blum, Felipe Cucker, Mike Shub, Steve Smale, Complexity and Real Computation. Springer-Verlag, New York, 1998.