Defesa de Dissertação de Mestrado: André Willik Valenti
Document Actions
Defesa de Dissertação de Mestrado: Thiago de Paulo Faleiros
Algoritmos para o Problema de Particionamento.
| What | Defesa de Mestrado |
|---|---|
| When |
16/12/2010 from 14:00 to 16:00 |
| Where | Sala 362 - IC 3,5 |
| Add event to calendar |
vCal
iCal
|
Investigamos Problemas de Particionamento de objetos que têm relações de similaridade entre si. Esses problemas podem ser representados por grafos, em que objetos são vértices e a similaridade entre dois objetos é representada por um valor associado à aresta que liga os objetos. O objetivo do problema é particionar os objetos de tal forma que objetos similares pertençam a um mesmo subconjunto de objetos. Problemas de particionamento possuem aplicações em diversas áreas, como mineração de dados, recuperação de informação, biologia computacional, entre outros. No caso geral, particionamento é um problema NP-Difícil e, por esse motivo, nosso interesse é investigar algoritmos eficientes (com complexidade de tempo polinomial), que utilizam técnicas como Heurísticas, Metaheurísticas e Algoritmos de Aproximação. Além disso, implementamos os algoritmos mais promissores e fazemos uma comparação de seus resultados utilizando instâncias geradas computacionalmente. Por fim, propomos um algoritmo que utiliza a metaheurística GRASP para o problema considerado e mostramos que, para as instâncias de testes geradas, nosso algoritmo obtém melhores resultados.
Concurso Público para Professor Doutor - MS-3
