PPgSC/UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO ADMINISTRAÇÃO DO CCET Téléphone/Extension: (84)3342-2225/115 https://posgraduacao.ufrn.br/ppgsc

Banca de QUALIFICAÇÃO: PATRÍCIA MEDYNA LAURITZEN DE LUCENA DRUMOND

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE: PATRÍCIA MEDYNA LAURITZEN DE LUCENA DRUMOND
DATA: 26/08/2011
HORA: 09:00
LOCAL: sala de reuniões DIMAp
TÍTULO:

Uma Análise Experimental de Algoritmos Exatos Aplicados ao Problema da Árvore Geradora Multiobjetivo


PALAVRAS-CHAVES:

Árvore geradora multiobjetivo, algoritmo exato, análise experimental


PÁGINAS: 40
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
RESUMO:

O Problema da Árvore Geradora Multiobjetivo (AGMO) é uma extensão natural do problema do Problema da Árvore Geradora Mínima com único objetivo. O problema é NP‑árduo e possui aplicação em diversas áreas, por exemplo, no projeto de redes de comunicação. O trabalho apresenta uma análise experimental das diferentes estratégias de algoritmos exatos encontrados na literatura para resolver o problema. As abordagens consideradas para a análise experimental compreendem dois algoritmos utilizando o método duas fases, que diferem apenas na fase 2, um método Branch-and-Bound e duas abordagens baseada em preferências, utilizando os algoritmos de Prim e Kruskal e as integrais de Choquet. Os experimentos computacionais abrangem a comparação do desempenho dos algoritmos levando-se em consideração o tempo de execução, sua eficiência em função do número de objetivos e a quantidade de soluções encontradas em determinado tempo. Para verificar as diferentes abordagens foi investigado o desempenho dos algoritmos em três tipos de instâncias propostas na literatura.


MEMBROS DA BANCA:
Presidente - 1201268 - ELIZABETH FERREIRA GOUVEA
Interno - 1171465 - MARCELO FERREIRA SIQUEIRA
Interno - 1149561 - MARCO CESAR GOLDBARG
Notícia cadastrada em: 13/07/2011 14:44
SIGAA | Superintendência de Tecnologia da Informação - (84) 3342 2210 | Copyright © 2006-2024 - UFRN - sigaa03-producao.info.ufrn.br.sigaa03-producao