063-2006

MO640 - Questão para a prova oral
Número: 063
Enunciado:  Em relação ao artigo de Bafna e Pevzner sobre transposições (1998) podemos afirmar que:
I - O melhor limite inferior encontrado para a distância de transposição foi de (n +1 -c_odd(π)) / 2.
II - O melhor limite superior encontrado para a distância de transposição foi de n + 1 - c(π).
III - O melhor algoritmo de aproximação tem a taxa de 1.5.

Quais destas estão corretas?

1. I, III apenas.
2. II, III apenas.
3. II apenas.
4. III apenas.
5. NDA

Autor(a): Marcus Vinícius Benedito