Disciplina Curricular
Teoria da Computabilidade, Complexidade e Informação TCCI
Diploma de Estudos Avançados em Segurança de Informação - DEASegInf2021
Contextos
Grupo: DEASegInf2021 > 3º Ciclo > Matemática > Lógica e Computação
Período:
Peso
7.5 (para cálculo da média)
Objectivos
Dominar os conceitos, técnicas, resultados fundamentais e aplicações significativas das teorias da computabilidade, da complexidade computational, da informação e da complexidade de Kolmogorov. Contactar com alguns tópicos na fronteira da investigação no domínio.
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.
Metodologia de avaliação
Exercícios (80%) e apresentação de tópico de investigação (20%).