Ata de solução de exercícios - sobre a aula de 2007-04-18

1) Enunciado: Desenhe o diagrama de realidade e desejo relativo aos genomas (-2, +1, +3, -9, +5, +6, +8, -4, -7) e (+4, -1, +8, +3, +2, +5, -9, -7, +6). A seguir, diga quantos ciclos, componentes e obstáculos este problema tem. Entre os ciclos, quantos são bons e quantos ruins? E entre as componentes? Qual a distância de reversão entre estes dois genomas?

Solução: O aluno Douglas apresentou o diagrama de realidade e desejo (veja Figura 1)


Figura 1 – Diagrama de realidade e desejo para exercício 1



Ciclo1 = 0 2 -5 -9 7 -4 0 . É ciclo bom, pois, por exemplo, as arestas realidade (0 2) (-5 -9) divergem.

Ciclo 2 = 10 -7 -6 5 9 3 -2 -1 -8 6 10 . É ciclo bom, pois, por exemplo, as arestas realidade (10 -7) (-2 -1) divergem.

Ciclo 3 = 1 -3 8 4 1 . É ciclo ruim, pois todos as arestas realidade convergem.

Existe apenas uma componente pois todos os ciclos se entrelaçam. Esta componente é boa pois ela contém pelo menos um ciclo bom (no caso, ciclos 1 e 2).

Não há nenhum obstáculo, pois temos apenas uma componente e ela é boa. Obstáculos precisam ser componentes ruins que não separam quaisquer dois outros componentes ruins.

d = n + 1 – c – h = 9 + 1 -3 + 0 = 7

onde:

d = distância de reversão

n = número de genes

c = número de ciclos no diagrama de realidade e desejo

h = número de obstáculos no diagrama de realidade e desejo



2. Enunciado: Defina dois genomas tais que o diagrama de realidade e desejo entre eles contém 10 ciclos, sendo 5 bons e 5 ruins, 5 componentes, sendo 2 boas e 3 ruins, e 2 obstáculos. Este diagrama é uma fortaleza? Qual é a distância de reversão neste caso?

Solução: O aluno Lucas forneceu o diagrama de realidade e desejo (veja Figura 2 – os textos indicam os componentes):


Figura 2 – Diagrama de realidade e desejo para exercício 2



Onde:

alfa = 0 (-5, -1, 6, 4, 2, -7, -3, 8, 10, 9, 11, 18, 17, 12, 15, 14, 13, 16, 19, -20) -21

beta = 0 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20) -21

Verificação:

Componente C1 contém 4 ciclos, sendo todos eles ciclos bons.

Componente C2 contém 1 ciclo ruim (é interessante notar que se trata de um ciclo em que as três arestas realidade convergem).

Componente C3 contém 2 ciclos ruins.

Componente C4 contém 1 ciclo bom.

Componente C5 contém 2 ciclos ruins.

Logo, temos 10 ciclos conforme solicitado, sendo 5 bons e 5 ruins.

2 componentes boas: C1 e C4 (pois têm pelo menos um ciclo bom nelas).

3 componentes ruins: C2, C3 e C5 são componentes ruins pois contém apenas ciclos ruins nelas.

Temos 3 componentes ruins, dentre elas C3 separa C2 e C5 e por isso não pode ser um obstáculo.

Por sua vez, C2 e C5 não separam quaisquer outros dois componentes ruins. Logo, os dois são obstáculos.

A menor fortaleza têm 3 super-obstáculos, por isso como temos apenas 2 obstáculos, não é possível haver fortaleza no diagrama da Figura 2.

d = n + 1 – c – h = 20 + 1 – 10 + 2 = 13