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