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.