080-2005

MO640 - Questão para a prova oral
Número: 080
Enunciado:
Considere:
d(π) a distância de transposição de prefixo
b(π) o número de breakpoints
De acordo com o paper Sorting by Prefix Transpositions (DM 2002b), sobre transposição de prefixo, é incorreto afirmar:

1. Dada uma permutação π (diferente da identidade), sempre é possível obter uma transposição de prefixo que elimina um ou dois breakpoints.
2. Sempre eliminamos 2 breakpoints na última transposição de prefixo efetuada (antes de obter a identidade).
3. Temos que d(π) >= teto( (b(π) - 1) / 2 )
4. Temos que d(π) <= b(π) - 2
5. NDA

Autora: Roseane Midori Miya