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?
- Para qualquer permutação, temos que a distância de transposição é maior ou igual à distância de transposição de prefixo;
- 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;
- 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π
- As únicas permutações que não possuem breakpoints são as permutações identidades, para todos os tamanhos de permutação;
- NDA
Autor(a): Bruno Dilly