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: 2021/2022 - 2S

Ativa?	Sim
Página Web:	http://https://moodle.up.pt/enrol/index.php?id=3670
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	77	Plano estudos a partir do ano letivo 2021/22	3	-	6	56	162
L:F	0	Plano de Estudos Oficial	2	-	6	56	162
			3
L:G	0	Plano estudos a partir do ano letivo 2017/18	2	-	6	56	162
			3
L:IACD	0	Plano Oficial a partir do ano letivo 2021/22	3	-	6	56	162
L:M	3	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

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 sem exame final

Componentes de Avaliação

Designação	Peso (%)
Teste	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 critérios de frequência.

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

Primeiro teste (50% de peso na nota final).
Segunto teste (50% de peso na nota final). 
Sendo PT a classificação obtida  no teste intercalar e ST a
classificação obtida no exame final, então a nota final é dada por:
F = PT*(0.5) + ST*(0.5) 
PT,ST >= 6 e F >= 9.5
Não obterão aprovação na avaliação distribuída, os alunos que não obtiverem um mínimo de 6 valores (em 20), em ambos os testes e um mínimo de 9.5 valores de nota final.
Para os alunos que não obtiverem aprovação, haverá um exame de recurso, cotado para 20 valores.

Adicionalmente poderão ser propostos projectos laboratoriais, sendo o peso desses projectos na classificação final a determinar pelo docente responsável.