Defesa de Mestrado de Klairton de Lima Brito

Título do Trabalho
Ordenação de Permutações com Sinais por Reversões e Transposições
Candidato(a)
Klairton de Lima Brito
Nível
Mestrado
Data
Add to Calender 2018-04-12 00:00:00 2018-04-12 00:00:00 Defesa de Mestrado de Klairton de Lima Brito Ordenação de Permutações com Sinais por Reversões e Transposições Auditório do IC 2 - Sala 85 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
13h30
Local
Auditório do IC 2 - Sala 85
Orientador(a)
Zanoni Dias
Banca Examinadora

Condição

Titulares  -  Professores Doutores

Unidade/Instituição

Orientador/Presidente

Zanoni Dias

IC/UNICAMP

Externo à Unidade

Maria Emilia Machado Telles Walter

ICE/UnB

Interno à Unidade

Guilherme Pimentel Telles

IC/UNICAMP

Condição

Suplentes  -  Professores Doutores

Unidade/Instituição

Interno à Unidade

Fábio Luiz Usberti

IC/UNICAMP

Externo à Unidade

Cleber Valgas Gomes Mira

DCC/UEMS

Resumo

Neste trabalho, apresentamos três heurísticas para melhorar os resultados de algoritmos para o Problema de Ordenação de Permutações com Sinais por Reversões e Transposições. Nossas heurísticas foram aplicadas tanto na versão clássica do problema quanto nas versões restrita a operações de prefixo e restrita a operações de prefixo ou sufixo. A nossa primeira heurística é chamada de Sliding Window, executa em tempo linear e fornece bons resultados. A nossa segunda heurística, Look Ahead, possui tempo de execução mais elevado dependendo do estimador de distância que é utilizado, mas seus resultados são mais expressivos. Nossa última heurística é chamada de Iterative Sliding Window e apresenta melhor custo-benefício entre o tempo de execução e a qualidade da solução em comparação com as duas primeiras heurísticas.

Mostramos que as heurísticas Look Ahead e Sliding Window podem ser combinadas visando fornecer resultados ainda melhores. Para verificar o comportamento de nossas heurísticas, implementamos diversos algoritmos da literatura e realizamos experimentos práticos onde observamos melhorias em relação aos algoritmos originais. Efetuamos ainda um comparativo de desempenho entre nossas próprias heurísticas.

Investigamos também o Problema de Ordenação de Permutações com Sinais por Reversões e Transposições Ponderadas, adotando os pesos 2 e 3 para os eventos de reversão e transposição, respectivamente. Conseguimos apresentar limitantes inferiores para o problema e quatro algoritmos de aproximação. Dois desses algoritmos adotam uma estratégia gulosa e apresentam fatores de aproximação 3 e 2, enquanto os outros dois utilizam a estrutura de grafo de ciclos para ordenar a permutação e apresentam fatores de aproximação
5/3 e 3/2. Realizamos experimentos práticos com diferentes grupos de permutações com características distintas.

Estendemos nossa investigação para considerar outras relações de peso entre os eventos de transposição e reversão. Mostramos também uma análise que considera essas relações distintas de peso e apresentamos o melhor fator de aproximação obtido para cada uma dessas relações.