[pt] MINIMIZAÇÃO SIMULTÂNEA DO PIOR CUSTO E DO CUSTO MÉDIO EM ÁRVORES DE DECISÃO

• Ano de defesa: 2017
• Autor(a) principal: ALINE MEDEIROS SAETTLER
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] ARVORE DE DECISAO; [pt] ALGORITMOS DE APROXIMACAO; [pt] ANALISE DE ALGORITMOS; [pt] OTIMIZACAO COMBINATORIA; [en] DECISION TREE; [en] APPROXIMATION ALGORITHMS; [en] COMBINATORIAL OPTIMIZATION
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=28810&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=28810&idi=2; http://doi.org/10.17771/PUCRio.acad.28810

[pt] O problema de minimizar o custo de avaliar uma função discreta lendo sequencialmente as suas variáveis é um problema que surge em diversas aplicações, entre elas sistemas de diagnóstico automático e aprendizado ativo. Neste problema, cada variável da função está associada a um custo, que se deve pagar para checar o seu valor. Além disso, pode existir uma distribuição de probabilidades associadas aos pontos onde a função está definida. A maioria dos trabalhos nesta área se concentra ou na minimização do custo máximo ou na minimização do custo esperado gasto para avaliar a função. Nesta dissertação, mostramos como obter uma Ômicron logaritmo de N aproximação em relação à minimização do pior custo (a melhor aproximação possível assumindo que P é diferente de NP). Nós também mostramos um procedimento polinomial para avaliar uma função otimizando simultaneamente o pior custo e o custo esperado.