Weby shortcut
mousehuman

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.