082-2005

MO640 - Questão para a prova oral
Número: 082
Enunciado:
Assinale a alternativa INCORRETA a respeito de transposições de prefixo

1. O número máximo de breakpoints que uma transposição de prefixo pode eliminar é igual ao de uma transposição qualquer
2. Para qualquer transposição t (que não seja de prefixo) e permutação p, é possível obtermos duas transformações de prefixo t1 e t2 tais que tp = t1t2p
3. Para uma permutação diferente da identidade, sempre é possível encontrarmos uma transposição de prefixo que reduza seu número de breakpoints em pelo menos um
4. Em uma permutação fácil, a ordenação pode ser feita utilizando apenas transposições de prefixo que removam dois breakpoints cada
5. NDA

Autor(a): Leonardo Elias Mariote