Enunciado distribuido na sala.
Ordenação usando o algoritmo de Christie (os blocos a trocar estão indicados pelas cores rosa e azul):
| 7 | 4 | 1 | 2 | 5 | 3 | 8 | 6 |
| 1 | 2 | 5 | 3 | 4 | 7 | 8 | 6 |
| 1 | 2 | 3 | 4 | 7 | 8 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Praticamente todos acertaram esta questão. Alguns alunos erraram a distância, ficando com 0,5 apenas. Outros argumentaram erradamente, caso em que perderam 0,2.
Pares corretos:
12(-), 23(+), 34(+), 45(-), 56(+), 67(-), 24(-), 25(+), 26(+), 27(-), 35(+).
Várias pessoas colocaram o par 17, mas está incorreto, pois não dá similaridade prefixo-sufixo, apenas local. O mesmo ocorre com outros pares.
Para cada par a mais ou a menos, perdeu-se 0,2; se foi dado o par correto, mas orientação errada, perdeu 0,1.
Poucos acertaram esta questão. Basicamente, era para calcular σπ-1, τσ-1 e πτ-1 e ver quem tinha mais ciclos. O pessoal se confundiu muito para chegar aos genomas. Alguns tentaram usando π1, σ1, etc. mas está errado. Dei 1,0 ponto para quem conseguiu pelo menos escrever os três genomas.
A solução correta:
π = (-a c d -b e) (-e b -d -c a)
σ = (-c -d e b -a) (a -b -e d c)
τ = (b c d -a e) (-e a -d -c -b)
σπ-1 = (a -d -a b d) (-b c -c e -e)
πτ-1 = (b -a -b a) (-d -e e c) (-c) (d)
τσ-1 = (a d) (-a c) (b) (-b -d) (-c e) (-e)
Esta era a questão mais trabalhosa, por isso valia mais. A maioria acertou. Houve casos em que tudo estava certinho, exceto a distância no final; para estes tirei 0,5. Houve gente que parou no meio: faltou fôlego (ou tempo); para estes dei nota proporcional ao quanto avançaram. Quem só fez o diagrama ganhou 0,5.
A solução dá 9 passos. Um dos possíveis caminhos segue abaixo (trecho a reverter em cor rosa):
| -3 | 5 | 2 | -6 | -4 | -1 | 7 | 9 | 8 |
| 1 | 4 | 6 | -2 | -5 | 3 | 7 | 9 | 8 |
| 1 | 2 | -6 | -4 | -5 | 3 | 7 | 9 | 8 |
| 1 | 2 | -6 | -4 | -3 | 5 | 7 | 9 | 8 |
| 1 | 2 | -6 | 3 | 4 | 5 | 7 | 9 | 8 |
| 1 | 2 | -6 | -5 | -4 | -3 | 7 | 9 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | -9 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | -8 | 9 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Seguimos o algoritmo sugerido por Anne Bergeron atá o ponto em que fica uma permutação sem pares orientados. Então cortamos um obstáculo, e continuamos con o algoritmo básico de Bergeron até o final.
© 2007 João Meidanis