MO640 - Questão para a prova oral

Número: 048

Enunciado:
Escolha a alternativa correta :

1. Toda permutação fácil pode ser ordenada por transposições de prefixo otimamente em tempo polinomial.
2. Decidir se uma permutação é fácil ou não é O(n!).
3. Toda permutação fácil deve ter um número par de pontos de quebra de prefixo.
4. O número de permutações fáceis de comprimento n é aproximadamente igual a n/3.
5. NDA

Autor(a): Luís Felipe Strano Moraes