Disciplina Curricular

Teoria da Computabilidade, Complexidade e Informação TCCI

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

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%).

Disciplinas Execução

2017/2018 - 1ºSemestre

2016/2017 - 1ºSemestre

2015/2016 - 1º Semestre

2014/2015 - 1º Semestre