Disciplina Curricular

Computabilidade e Complexidade da Aprendizagem CCA

Diploma de Estudos Avançados em Segurança de Informação - DEASegInf2007

Contextos

Grupo: DEASegInf2007 > 3º Ciclo > Matemática > 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.

Metodologia de avaliação

Exercícios (50%) e apresentação de tópico de investigação (50%).

Disciplinas Execução

2016/2017 - 1ºSemestre

2015/2016 - 1º Semestre

2014/2015 - 1º Semestre

2013/2014 - 1 Semestre