(DCC, UP)
Complexidade de Komolgorov: quando a teoria se encontra com a prática
Data: 24 de Março de 2006
Local: Sala 5.5.
Hora: 14:30
Resumo
Nesta palestra apresentaremos dois trabalhos recentes na área de
Complexidade de Kolmogorov, uma medida teórica, rigorosa, da
quantidade de informação em objectos individuais:
- Sob uma assunção de dificuldade computacional standard
caracterizamos de forma exacta o tempo de execução (no
pior caso) de linguagens que pertencem a classe Aver_P (tempo
polinomial em média) para todas as distribuições
"sampleable".
- A monitorização do batimento cardíaco fetal (FHT), antes do parto, é uma prática médica de muita importância na detecção de fetos em perigo. Vamos mostrar como podemos agrupar traçados de FHT, usando Complexidade de Kolmogorov, para identificar traçados anormais.
Este seminário é organizado com apoio do CMUC.
Reinhard Kahle, 20.03.06