063-2005

MO640 - Questão para a prova oral
Número: 063

Enunciado:

De acordo com o artigo de Kaplan et al. 1997, intitulado: “Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals”, é INCORRETO afirmar que:

1. É apresentado um algoritmo de complexidade de tempo O(n^2) (onde n é o número de elementos da permutação) que encontra o número mínimo de reversões necessárias para se ordenar uma permutação com sinais.
2. Um ciclo do grafo de pontos de quebra (B(π)) é orientado caso possua ao menos uma aresta cinza orientada.
3. O grafo de sobreposição (Overlap Graph – OV) de uma permutação π possui como vértices as arestas cinzas do grafo de pontos de quebra B(π).
4. Fortaleza é definida como uma permutação com um número ímpar de obstáculos, sendo que ao menos um deles é super-obstáculo.
5. NDA  

Autor(a): Renato Hirata