============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Construção de árvores de decisão otimizadas 
	     para o problema de avaliação de funções discretas
            
Palestrante: Eduardo Sany Laber
             Departamento de Informática - PUC-Rio 

Hora e Data: 14h, sexta-feira, 14 de fevereiro de 2014

Local:       Sala Multi-usos do Numec

Resumo:

Tanto em aplicações que  envolvem a construção automática de
diagnósticos quanto  em aplicações que  envolvem aprendizado
ativo,  um problema  central  consiste na  avaliação de  uma
função  discreta  através  da  leitura  adaptativa  de  suas
variáveis. Em geral para ler uma variável é necessário pagar
um custo (e.g.  computational ou financeiro). Nessa palestra
discutimos um algoritmo  para avaliação de funções discretas
que  busca minimizar  simultaneamente o  custo esperado  e o
custo de  pior caso gasto  com a leitura das  variáveis.  No
caso  do  custo  esperado  assumimos  a  existência  de  uma
distribuição  de  probabilidade sobre  os  pontos  em que  a
função   está  definida.    Nosso  algoritmo   constrói  uma
estratégia  de  avaliação  (árvore  de  decisão)  que  obtém
simultaneamente   aproximação  logaritmica   tanto   para  a
minimização do custo de pior caso quanto para minimização do
custo esperado. Este  resultado, além de melhorar resultados
anteriores, é o melhor  possível assumindo que P é diferente
de NP.  Se o  tempo permitir vamos discutir também trade-off
existentes entre  a minimização do custo esperado  e o custo
de pior caso.