Disciplina Curricular

Computabilidade e Complexidade da Aprendizagem CCA

Diploma de Estudos Avançados em Matemática - DEAMat2006

Contextos

Grupo: DEAMat2006 > 3º Ciclo > Lógica e Computação

Período:

Peso

7.5 (para cálculo da média)

Objectivos

Identificação de linguagens e funções, tais como leis científicas ou teorias científicas descritas através de conjuntos de números ou de funções. Introdução à atitude científica, tendo como foco (a) leis que podem ser aprendidas por cientistas computáveis ou não computáveis, (b) complexidade da descoberta científica, (c) unificação de teorias científicas e (d) inferência científica e validade de inferências indutivas.

Programa

Conceito de cientista segundo Gold. Identificação de linguagens e funções. Cientistas computáveis e não computáveis. Cientistas de memória limitada. Identificação por cientistas computáveis. Estratégias de identificação de linguagens e funções. Cientistas popperianos. Classes: Ex, Ex*, Bc, Bc*, TxtEx, TxtEx*, TxtFex and TxtFex*. Teoremas de Blum e Blum, de Case e Smith, de Adleman, e de Harrington. Identificação de linguagens e funções por equipas de cientistas determinísticos e probabilísticos. Identificação por cientistas que consultam oráculos. Teoremas de Adleman e Blum, de Jockusch, de Fortnow et al. Complexidade da identificação.