Critérios de listabilidade (conc)

30 setembro 2008, 15:30 • Amilcar Sernadas

Conclusão da demonstração do teorema dos critérios de listabilidade. Teorema da projecção. Teorema do grafo. Noção de problema de decisão. Decidibilidade de problemas. Redutibilidade.

Crtérios de listabilidade

24 setembro 2008, 14:30 • Amilcar Sernadas

AULA EXCEPCIONALMENTE LECCIONADA DAS 11H00 ÀS 12H30 NA SALA V1.26 POR SOLICITAÇÃO UNÂNIME DOS ALUNOS.

Início da demonstração do teorema.

Noções básicas

24 setembro 2008, 09:30 • Jaime Ramos

Exercícios sobre funções; funções computáveis e conjuntos decidíveis.

Decidibilidade e listabilidade de conjuntos

23 setembro 2008, 15:30 • Amilcar Sernadas

Conjuntos W-decidíveis. Conjuntos decidíveis. Decidibilidade da imagem inversa de conjunto decidível por função computável com domínio decidível. Conjuntos W-listáveis. Conjuntos listáveis. Listabilidade de conjunto decidível. Teorema de Post. Listabilidade da imagem de conjunto listável por função computável.

Noções básicas

17 setembro 2008, 14:30 • Amilcar Sernadas

NOTA: Aula leccionadade acordo com o horário antigo na quinta-feira 18 de Setembro 11h00-12h30m na Sala V1.07.

Alfabeto e universo de computação. Conjuntos de tipo n. Enumeração canónica de universo e sua inversa. Ordenação total induzida em universo. Noção de área de computação. Conjuntos de tipo n:W. Funções computáveis. Cardinalidade do conjunto das funções computáveis. Notação relativa a projecções. Minimização.