Disciplina Curricular

Complexidade de Kolmogorov CK

Diploma de Estudos Avançados em Matemática - DEAMat2006

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

Disciplinas Execução

2016/2017 - 1ºSemestre

2015/2016 - 1º Semestre

2014/2015 - 1º Semestre

2013/2014 - 1 Semestre