083-2005

MO640 - Questão para a prova oral
Número: 083
Enunciado:
Sobre permutações fáceis, no contexto de ordenação por transposição de prefixos, NÃO podemos afirmar que:

1. Uma permutação fácil deve ter um número ímpar de pontos de quebra.
2. O número de permutações fáceis cai drasticamente em proporção às não-fáceis com o aumento do comprimento da permutação.
3. Sempre passaremos por uma permutação fácil para ordenar uma permutação.
4. Para verificar que uma permutação é fácil, basta encontrar uma transposição que reduza em dois o número de pontos de quebra e verificar se a permutação resultante também possui uma transposição com tal propriedade.
5. NDA.

Autor: Tony Minoru Tamura Lopes