Programa

Teoria da Computabilidade, Complexidade e Informação

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

Programa

Teoria da computabilidade: computabilidade de funções e operadores, decidibilidade e semidecidibilidade de conjuntos, universalidade, m-redutibilidade, completude, não listabilidade efectiva, produtividade, imunidade, computabilidade relativa e graus, tese de Church-Turing e panorâmica dos modelos de computação. Complexidade computational: computação com recursos limitados no tempo e espaço; redução em tempo polinomial; classes de complexidade P, NP, PSPACE e EXPTIME; circuitos Booleanos e classe P/Poly; teorema de Cook-Levin; conjuntos NP-completos, PSPACE-completos e EXPTIME-completos; hierarquia polinomial; classes de complexidade probabilísticas e quânticas; relativização. Teoria da informação: axiomática de Kinchin, entropia de Shannon e suas propriedades fundamentais; divergência de Kullback-Leibler, informação mútua, desigualdade da informação e suas implicações; equipartição assimptótica; codificação de variáveis/fontes discretas, limites teóricos e códigos óptimos; entropia diferencial; canais discretos e Gaussianos; teoria da informação e estatística. Teoria algorítmica da informação: complexidade descritiva de funções e de sequências de símbolos, formulações alternativas, invariância, incompressibilidade, simetria da informação, teorema da codificação e relacionamento com a entropia de Shannon; complexidade descritiva com recursos limitados; aplicações em segurança de informação e em classificação automática.