Computabilidade e Complexidade
Código
8415
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Reinhard Kahle
Horas semanais
4
Total de horas
56
Língua de ensino
Português
Conteúdo
1. Introdução a computabilidade
2. Indicibilidade
3. Introdução a teoria de complexidade
4. Resultados básicos da teoria de complexidade
5. Não-determinismo e completude NP
6. Complexidade relativa
Bibliografia
- Computability and Complexity Theory, Steven Homer e Alan L. Selman, Springer.
- Structural Complexity, vol. I and II, Balcázar, Días e Gabarró, Springer.
- Mathematical Logic, Part II, Cori e Lascar, Oxford.
- Computability, Klaus Weihrauch, Springer.
- Handbook of Logic and Computer Science, Gabbay e Maibaum (co.), Oxford University Press.
- A Programming approach to computability, Kfoury, Moll e Arbib, Springer.
- Computers and Intractability. A Guide to the Theory of NP-Completeness, Garey e Johnson, W.H.Freeman and Co., San Francisco.
Método de ensino
Métodos habituais de ensino universitário da Matemática.