Computabilidade

Código:

CC333

Sigla:

CC333

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

Ocorrência: 2011/2012 - 1S

Ativa?	Sim
Página Web:	www.dcc.fc.up.pt/~sbb/aulas/1011/computabilidade/index.html
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Geologia

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:AST	0	Plano de Estudos a partir de 2008	3	-	7,5	-
L:B	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:CC	30	Plano de estudos de 2008 até 2013/14	2	-	7,5	-
			3
L:F	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:G	0	P.E - estudantes com 1ª matricula anterior a 09/10	3	-	7,5	-
		P.E - estudantes com 1ª matricula em 09/10	3	-	7,5	-
L:M	1	Plano de estudos a partir de 2009	3	-	7,5	-
L:Q	0	Plano de estudos Oficial	3	-	7,5	-

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.

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;
- saibam classificar exemplos concretos de problemas e provar a sua
(in)decidibilidade dentro das diversas classes de computabilidade.

Programa

Linguagens, funções e problemas (semi-)decidíveis. Revisão de alguns
modelos de computação (DFA's, NFA's, CFL'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 e
lambda-calculus). Enumerabilidade efectiva das instâncias de um modelo
de computação. Linguagens recursivas e recursivamente
enumeráveis. Método da diagonalização e indecidibilidade do problema
da paragem. Redução "muitos para um" entre
linguagens. Indecidibilidade e incompletude de teorias da lógica de
primeira ordem. Outros problemas indecidíveis.

Bibliografia Complementar

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.
Foundations of Functional Programming, Lawrence C Paulson, www.cl.cam.ac.uk/~lp15/papers/Notes/Founds-FP.pdf
Computabilidade e Decidibilidade, Sabine Broda.
Introduction to the Theory of Computation, Michael Sipser.
Models of Computation - An Introduction to Computability Theory, Maribel Fernández.

Tipo de avaliação

Avaliação por exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	75,00
	Total:	-	0,00

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

Classificação final corresponde à classificação obtida
- como média aritmética dos dois testes a realizar durante o semestre;
- ou no exame final.

No caso do aluno ter aprovação por testes e mesmo assim optar por fazer exame final, ficará com a melhor das duas classificações.

Provas e trabalhos especiais

Haverá dois testes com a valorização de 20 valores cada a realizar nos dias 4/11/2011 e 12/12/2011 respetivamente.