Disciplina Curricular

Complexidade Estrutural CEst

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

Peso

6.0 (para cálculo da média)

Programa

Complexidade de Kolmogorov: complexidade de Kolmogorov sem limite de recursos; complexidade de Kolmogorov com recursos limitados. Complexidade de prefixos. Teoria da informação algorítmica. Máquinas de Turing alternadas. Complexidade de circuitos uniformes: hierarquia NC; robustez. Isomorfismo e NP-completude: isomorfismos em tempo polinomial; cilindros polinomiais; conjuntos esparsos completos. Classes de complexidade não uniformes com conselhos em log, log*, poly e polylog: classes centrais P/poly, P/log* e BPP/log*. Algoritmos probabilísticos. Algoritmos estocásticos. Classes de complexidade. Computação com ruído. Hierarquia dos números reais de acordo com a sua incompressibilidade: hierarquia de Kolmogorov - de P(Q) a P/poly (R). A classe recursiva P. Computação experimental. Classes de complexidade que advêm da computação experimental em mecânica clássica e mecânica quântica. Aleatoriedade algorítmica. Classes de complexidade de problemas que se resolvem probabilística e estocasticamente recorrendo a sequências aleatórias.

Disciplinas Execução

2011/2012 - 1 Semestre

2010/2011 - 1 Semestre

2009/2010 - 1 Semestre

2007/2008 - 1 Semestre