O que é um algoritmo operando sobre números reais? Quais subconjuntos dos números reais podem ser decididos por algoritmo? Quais problemas numéricos são tratáveis?
Abordaremos neste curso a teoria de computabilidade sobre um anel, desenvolvida por Blum, Shub e Smale. No caso particular do anel finito \(\mathbb F_2\), recupera-se o modelo de Turing. Outros casos de interesse são o anel dos números inteiros, o dos números reais, o dos números complexo.
Também veremos como aplicar essas idéias no âmbito de problemas numéricos, como a solução de sistemas densos de polinômios.
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.
- Professor: GREGORIO MALAJOVICH MUNOZ - Docente