Computabilidade e Complexidade
Objetivos
Pretende-se que os alunos se familiarizem com modelos de computação e com classes de complexidade computacional como P, NP, Pspace,... Neste âmbito pretende-se que os alunos desenvolvam competências que lhes permitam compreender não só os principais resultados envolvendo estas classes de complexidade, mas também vários problemas em aberto nesta área.
Caracterização geral
Código
8415
Créditos
6.0
Professor responsável
Isabel Maria Oitavem Fonseca da Rocha Kahle
Horas
Semanais - 4
Totais - 48
Idioma de ensino
Português
Pré-requisitos
---
Bibliografia
Referência principal Computability and Complexity Theory, Steven Homer and Alan L. Selman, Springer.
Outras referências:
- Structural Complexity, vol. I and II, Balcázar, Días and Gabarró, Springer.
- Mathematical Logic, Part II, Cori and Lascar, Oxford.
- Computability, Klaus Weihrauch, Springer.
- Handbook of Logic and Computer Science, Gabbay and Maibaum (ed.), Oxford University Press.
- A Programming approach to computability, Kfoury, Moll and Arbib, Springer.
- Computers and Intractability. A Guide to the Theory of NP-Completeness, Garey and Johnson, W.H.Freeman and Co., San Francisco.
Método de ensino
A disponibilizar brevemente
Método de avaliação
Para obter aprovação à UC é necessário assistir a pelo menos 2/3 das aulas dadas.
A avaliação é efectuada com base em um projeto por aluno (apresentação, discussão e relatório) e um teste. O projeto vale 16 valores da classificação final e o teste vale 4 valores.
Os alunos que obtiverem uma classificação final superior ou igual a 10 valores obtêm aprovação na UC com a correspondente classificação.
Os alunos que obtiverem uma classificação final superior a 17 valores podem ser chamados a prestar uma prova suplementar. Caso não o façam obtêm aprovação na UC com a classificação de 17 valores.
Conteúdo
A disponibilizar brevemente