4 Programa
-
Apresentação Contextual e Histórica da Teoria da computação
- Modelos da computação: dos autómatos (de estados finitos, com
pilha) às máquinas de Turing.
- Modelos de computação alternativos: Funções recursivas de Kleene
e calculo lambda.
- Programação em modelos da computação.
- Tese de Church-Turing. Provas de equivalência de modelos.
- A não computabilidade e a indecidibilidade: Problemas
indecidíveis, técnica da diagonalização, técnica da redução.
- Complexidade. Introdução: problemas tratáveis e problemas
intratáveis. Critérios de catalogação (memória, tempo,
etc.). Caracterização das classes NP, P e NP-Completo. Problemas
NP-Completos: Exemplos. Técnica da redução polinomial para a
demonstração de NP-completude.
4.1 Competências da UC ou Resultados da Aprendizagem
O aluno deverá ser capaz de perceber e usar a capacidade de computação
das máquinas, assim como os seus limites teóricos.
Deverá ser capaz de formalizar adequadamente e avaliar se determinados
problemas tem solução computacional ou não.
Deverá perceber e saber usar modelos, técnicas e algoritmos de
computação simbólica introduzidos na resolução de problemas
informáticos do dia-a-dia.