Média para a distância de reversão
Próximo seminário (dia 07/05)
Auditório do IME: 10:00 às 11:30
Professora: Thaynara Arielly de Lima
Título: Média para a distância de reversão (parte 2)
Resumo: É bem conhecido que permutações com sinal podem ser ordenadas por meio de reversões em tempo polinomial, enquanto que ordenar permutações sem sinal é um problema NP-difícil.
Apesar de ordenar permutações com sinal ser um problema “fácil” do ponto de vista computacional, o estudo da média da distância de reversão é justificado, pois provê interessantes questões combinatórias. Além disso, em aplicações relacionadas com a análise de similaridade entre genomas, soluções exatas para o problema de ordenar permutações com sinal por reversões têm sido utilizadas para conceber algoritmos aproximados para sua versão sem sinal.
Nesta palestra analisa-se o número médio de reversões necessárias para se ordernar permutações com sinal, explorando propriedades combinatórias de estruturas relacionadas a tais permutações, tais como grafo de pontos de quebra, e se fornece uma fórmula de recorrência para esta média.