078-2005

MO640 - Questão para a prova oral
Número: 078

Enunciado: Sobre permutações fáceis em relação à distância de transposição, é incorreto afirmar que:

a)      Para toda permutação fácil temos que a distância de transposição de prefixo é igual à distância de transposição geral.

b)      Uma permutação π é fácil se, e somente se, já está ordenada ou existe uma transposição de prefixo τ tal que b_p(πτ) = b_p(π) – 2  e  πτ é fácil; onde b_p é o número de pontos de quebra de prefixo.

c)      Toda permutação fácil deve ter um número ímpar de pontos de quebra de prefixo.

d)      É possível determinar se uma permutação é fácil em tempo polinomial. Porém, ordenar otimamente uma permutação fácil por transposições de prefixo é um problema de complexidade de tempo desconhecida.

e)      nda

Autor(a): Renato Hirata