MO640 - Questão para a prova oral

Número: 039

Enunciado: Qual das alternativas está errada?

1. Para toda permutação fácil π, temos d_p(π) = d(π), onde d_p é a distância de transposição de prefixo e d é a distância de transposição;
2. É possível ordenar otimamente por tranposição de prefixo uma permutação fácil em tempo polinomial;
3. Toda permutação fácil tem um número ímpar de pontos de quebra de prefíxo;
4. Para toda permutação fácil π, temos π(1) ≠ 1;
5. NDA

Autor(a): Moacy Barros Correia da Silva