Computabilidade e Complexidade

Objectivos

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 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

Cursos

Cursos onde a unidade curricular é leccionada: