Disciplina Curricular
Complexidade de Kolmogorov CK
Diploma de Estudos Avançados em Segurança de Informação - DEASegInf2007
Peso
7.5 (para cálculo da média)
Objectivos
Dominar os conceitos, técnicas, resultados fundamentais e aplicações significativas da teoria algorítmica da informação, incluindo complexidade de Kolmogorov de sequências e outras noções algorítmicas de aleatoriedade. Contactar com alguns tópicos na fronteira da inestigação no domínio.
Programa
Síntese dos conceitos, técnicas e resultados relevantes de computabilidade e complexidade computacional. Complexidade de Kolmogorov de funções computáveis. Formulações alternativas de complexidade de sequências: simples, livre de prefixos e sobre palavras. Resultados fundamentais: invariância, incompressibilidade, compressão de linguagens, minoração/majoração, simetria de informação e codificação. Ligações à teoria da informação. Comparação entre as formulações alternativas. Panorâmica das aplicações: análise de algoritmos, lógica e segurança de informação. Complexidade de Kolmogorov com erros. Complexidade de Kolmogorv com recurso limitado. Complexidade e aleatoriedade de sucessões.
Metodologia de avaliação
Exercícios (50%) e apresentação de tópico de investigação (50%).