077-2005

MO640 - Questão para a prova oral
Número: 077
Enunciado:
Qual das alternativas é incorreta em relação a permutações fáceis?

1. Numa permutação fácil, existem no máximo duas transposições de prefixo que retiram dois pontos de quebra da permutação.
2. Todas as permutações intermediárias de uma ordenação ótima por transposições de prefixo de uma permutação fácil são fáceis.
3. É possível determinar se uma permutação é fácil em tempo polinomial.
4. Uma permutação é considerada fácil se, e somente se, dp=(bp-1)/2; onde dp é a distância e bp é o número de pontos de quebra.
5. NDA

Autor(a): Daniel Faria