No próximo dia 17 de Junho, pelas 14h00 na sala FC6 029 do DCC FCUP, Rogério Reis irá dar uma palestra intitulada "Obtenção de valores médios para objectos complicados de forma elegante".
A palestra é organizada pelo DCC-FCUP.
Title
Obtenção de valores médios para objectos complicados de forma elegante
Abstract
Para um grande conjunto de problemas é mais informativo ter uma estimativa em média do que a mesma estimativa para o pior caso. No entanto a forma usual para obter estimativas médias é através da recolha de dados obtidos por experimentação sendo o resultado sempre uma aproximação por muito significativa que a amostragem utilizada seja. No campo das linguagens formais, o tamanho do menor modelo que representa uma linguagem é uma boa medida da sua complexidade. No estudo do efeito das diversas operações sobre esta medida de complexidade assistiu-se a um crescente interesse nas últimas décadas, testemunho da importância que adquiriram as suas aplicações, da verificação formal de programas, passando pelo reconhecimento de padrões até ao processamento de voz. Mas para além do estudo desta complexidade, no pior caso, importa obter resultados em média, que não obstante serem muito mais difíceis, têm uma muito maior importância prática. Nesta introdução, para além da apresentação dos conceitos fundamentais envolvidos, será mostrado como as técnicas da Combinatória Analítica podem contribuir para resolver alguns problemas difíceis nesta área, sem qualquer recurso à experimentação.