Computabilidade e Complexidade

Código:

CC3004

Sigla:

CC3004

Nível:

300

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2019/2020 - 2S

Ativa?	Sim
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Ciência de Computadores

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:B	0	Plano de Estudos Oficial	3	-	6	56	162
L:CC	64	Plano de estudos a partir de 2014	3	-	6	56	162
L:F	0	Plano de Estudos Oficial	2	-	6	56	162
			3
L:G	3	Plano estudos a partir do ano letivo 2017/18	2	-	6	56	162
			3
L:M	2	Plano de Estudos Oficial	2	-	6	56	162
			3
L:Q	0	Plano estudos a partir do ano letivo 2016/17	3	-	6	56	162
MI:ERS	8	Plano Oficial desde ano letivo 2014	2	-	6	56	162
			3

Língua de trabalho

Português

Objetivos

Estudo e comparação de vários modelos de computação
(Turing-completos), do seu poder computacional e das suas limitações. Estudo das diversas classes de complexidade computacional.

Ao completar este curso espera-se que os alunos
- conheçam os modelos de computação clássicos utilizados no estudo da
computabilidade de diversos problemas;
- saibam provar a equivalência de vários modelos Turing-completos;
- conheçam os resultados e métodos mais importantes no estudo da
computabilidade e complexidade;
- saibam classificar exemplos concretos de problemas e provar a sua
(in)decidibilidade dentro das diversas classes de computabilidade.
- saibam classificar elemplos concretos pelas sua complexidade temporal e interpretar essa classificação. 

Resultados de aprendizagem e competências

Os alunos são expostos a vários dos modelos de computação Turing-completos standard, como as máquinas de registo, máquinas de Turing e as funções recursivas. Para além da prova da equivalência dos diferentes modelos, estes são também utilizados para identificar diferentes problemas indecidíveis. São usadas diferentes técnicas, como o método da diagonalização e da redução entre linguagens. Para adquirirem experiência em identificar a complexidade computacional de problemas concretos, faz-se uma introdução às classes P e NP, completude NP e o teorema de Cook, voltando também à técnica da redução.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Conhecimentos de alguns modelos de computação como Autómatos finitos, Expressões regulares e Gramáticas independentes. Conhecimentos básicos de Lógica.

Programa

Noção de linguagem/problema (semi-)decidível. Revisão de alguns
modelos de computação (DFA's, NFA's, CFG's e PDA's) e do seu poder
computacional. Máquinas de Turing. Máquinas de registo. Funções Recursivas. Lambda Calculus. Tese de Church-Turing. Hierarquia
de Chomsky. Teorema da Recursão de Kleene. Método da diagonalização e indecidibilidade do problema
da paragem. Redução "muitos para um" entre linguagens. Introdução à teoria de complexidade: classes P e NP; completude em NP; teorema de Cook e outros problemas NP-completos. reduções polinomiais. Classes co-NP, etc.
A classe dos problemas PSPACE. 

Bibliografia Obrigatória

Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullmann.
Recursion theory, Phillips, in Handbook of logic in computer science (vol. 1), Oxford University Press.

Bibliografia Complementar

Introduction to the Theory of Computation, Michael Sipser.
Models of Computation - An Introduction to Computability Theory, Maribel Fernández.
Oded Goldreich; P, NP, and NP-Completeness - The Basics of Computational Complexity, Cambridge University Press, 2010

Métodos de ensino e atividades de aprendizagem

Aulas teóricas de exposição dos conteúdos programáticos.
Aulas práticas de resolução de exercícios propostos semanalmente.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	100,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	106,00
Frequência das aulas	56,00
Total:	162,00

Obtenção de frequência

Sem condições.

Fórmula de cálculo da classificação final

Valorização obtida em exame.