MO640 - Biologia Computacional

Prova Individual - 30/05/2005

Questão 1 (Valor 3,0) Considerando o problema da distância de reversão com sinais, classifique as afirmações abaixo como verdadeiras ou falsas:

1. uma componente boa pode ser um super-obstáculo

2. uma componente pode ser ao mesmo tempo um super-obstáculo e um obstáculo simples

3. uma componente ruim pode ser um não-obstáculo, um obstáculo simples ou um superobstáculo

4. não é possível ter uma permutação onde haja exatamente duas componentes ruins, e tal que ambas sejam super-obstáculos

Questão 2 (Valor 2,0) Considerando o problema de distância de transposição de prefixos, sem sinais, exiba uma permutação fácil, diferente da identidade, que se inicie com “1”, ou então dê um argumento explicando porque tal permutação não existe.

Questão 3 (Valor 3,0) Encontre uma seqüência ótima de reversões com sinal que ordene a permutação abaixo. Justifique porque você acredita que sua seqüência seja ótima.

[−2, 1, −3, 4, −8, 6, 7, −5].

Questão 4 (Valor 2,0) Encontre a seqüência de transposições sem sinal mais curta que você conseguir que ordene a permutação abaixo.

[3, 2, 1, 6, 5, 4].