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: 2016/2017 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~rvr/aulas/AC1617/CeC/
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	47	Plano de estudos a partir de 2014	3	-	6	56	162
L:M	0	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	11	Plano Oficial desde ano letivo 2014	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 intrepertar 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 registo. Tese de Church-Turing. Hierarquia
de Chomsky. Estudo de outros modelos de computação Turing-completos e
sua equivalência (máquinas de Turing, funções recursivas). Enumerabilidade efetiva das instâncias de um modelo
de computação. 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 NP; teorema de Cook e outros problemas NP-completos.

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	70,00
Teste	30,00
Total:	100,00

Obtenção de frequência

Presença a 2/3 das aulas práticas

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

Classificação final corresponde à classificação obtida
- como média aritmética dos dois testes, o primeiro a realizar durante o semestre e o segundo na data do exame da época normal (cada um com nota mínima de 7 valores). Os dois testes incidem respectivamente sobre a matéria lecdionada durante a primeira e a segunda parte do semestre.
- o exame da época de recurso não contabiliza a nota obtida no primeiro teste e aborda toda a matéria leccionada durante o semestre.