059-2006

MO640 - Questão para a prova oral
Número: 059
Enunciado:
Qual das seguintes afirmações a respeito de transposição de prefixo, tratadas pelo artigo de Dias e Meidanis, está correta?

1. Para qualquer permutação, temos que a distância de transposição é maior ou igual à distância de transposição de prefixo;
2. O diâmetro de transposição de prefixo, D(n), sendo n o tamanho da permutação, é tal que:
   n/2 <= D(n) <= 3n/4;
3. Sendo π uma permutação, para qualquer transposição p(x,y,z) com x ≠ 1, existem transposição de prefixo p1 e p2 tais que p2p1π = pπ
4. As únicas permutações que não possuem breakpoints são as permutações identidades, para todos os tamanhos de permutação;
5. NDA

Autor(a): Bruno Dilly