Banca de DEFESA: PATRÍCIA MEDYNA LAURITZEN DE LUCENA DRUMOND

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: PATRÍCIA MEDYNA LAURITZEN DE LUCENA DRUMOND
DATA: 05/03/2012
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: 100
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de 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
Externo ao Programa - 348094 - ILONEIDE CARLOS DE OLIVEIRA RAMOS
Externo à Instituição - JOÂO XAVIER DA CRUZ NETO - UFPI
Notícia cadastrada em: 27/01/2012 10:54
SIGAA | Superintendência de Tecnologia da Informação - (84) 3342 2210 | Copyright © 2006-2024 - UFRN - sigaa04-producao.info.ufrn.br.sigaa04-producao