Número: 081
Sobre o texto "Lecture 16: Genome rearrangements, sorting by reversals Saad Mneimneh" discutido em sala de aula, considere o diagrama de Realidade e Desejo abaixo, no qual os ciclos foram identificados com as letras A, B, C e D.
Assinale a alternativa correta:
|  |
Este comentário foi removido pelo autor.
ResponderExcluirResposta: d.
ResponderExcluirO diagrama apresentado é um DIAGRAMA DE REALIDADE E DESEJO.
Para responder a questão são necessárias as seguintes definições:
i) ARESTAS REALIDADE
Linhas que estão sobre a circunferência do círculo;
ii) ARESTAS DESEJO
Linhas que ligam as extremidades de duas arestas Realidade.
iii) CICLO
União entre arestas Realidade e arestas Desejo, formando um caminho fechado. O menor ciclo possível é formado por uma aresta Realidade e uma aresta Desejo.
iii.a) CICLO PRÓPRIO
Ciclo com duas ou mais arestas Realidade, ou seja, com quatro ou mais arestas.
iii.b) SENTIDO DAS ARESTAS
Suponha que um ciclo possua duas arestas Realidade e, consequentemente, duas arestas Desejo. Escolha uma das arestas Realidade e, arbitrariamente, defina um sentido no círculo (horário ou antihorário).
Imagine agora que uma partícula passe a “andar” sobre essa aresta Realidade no sentido definido. Ela chega à primeira aresta Desejo e, em seguida, atinge a outra aresta Realidade. Ao passar pela segunda aresta Desejo, o percurso está completo.
Note que, uma vez definido o sentido na primeira aresta Realidade, o sentido em todas as outras arestas (Desejo ou Realidade) fica obrigatoriamente estipulado.
Esse procedimento é válido para qualquer ciclo.
iii.b) CICLO BOM
Um Ciclo Bom é aquele que possui pelo menos duas arestas Realidade com sentidos opostos (uma no sentido horário e outra no sentido antihorário).
iii.c) CICLO RUIM
Ciclo Ruim é aquele em que todas as arestas Realidade possuem o mesmo sentido.
Observação: A classificação dos ciclos como bons ou ruins não é aplicável aos ciclos com apenas uma aresta Realidade.
iv) GRAFO DE ENTRELAÇAMENTO
Pode-se representar o Diagrama de Realidade e Desejo como um grafo. Os nós são os ciclos do diagrama. Uma aresta é criada entre dois nós (ciclos) sempre que uma aresta Realidade de um ciclo cruza (ou se entrelaça) com a aresta Realidade de outro ciclo. Os ciclos bons são representados por nós cinza, e os ruins como nós brancos.
iv.a) COMPONENTE DE UM GRAFO DE ENTRELAÇAMENTO
Obviamente nem todos os nós se entrelaçarão. Por exemplo, suponha um diagrama de Realidade e Desejo com cinco ciclos: A, B, C, D e E. Presumindo que A se entrelace com B, C se entrelace com D, e que E permaneça sozinho, dizemos então que o Grafo de Entrelaçamento possui três componentes, a saber: A-B, C-D e E.
iv.b) COMPONENTE RUIM
Componente composto totalmente por ciclos ruins.
iv.c) COMPONENTE BOM
Componente que possui pelo menos um ciclo bom.
------------------
Com as definições acima, podemos classificar todos os ciclos e componentes do diagrama.
Como já dito no enunciado da questão, há quatro ciclos no diagrama. Os ciclos bons são o B e o D. O único ciclo ruim é o A. O ciclo C não é próprio e, portanto, não pode ser classificado. Há três componentes: o A-B, o C e o D. Como B é bom, o componente A-B é bom, assim como o componente D.
Passemos agora à avaliação das alternativas:
a) FALSA. O diagrama de fato possui quatro ciclos, mas apenas três componentes.
b) FALSA. O ciclo D forma sozinho um componente, porém, como o ciclo D é bom, o componente D é bom.
c) FALSA. O ciclo A é ruim, e o ciclo C não pode ser classificado.
d) VERDADEIRA.
Excelente. Mesmo comentário anterior: em (iv), são as arestas Desejo que se cruzam, e não as Realidade.
ResponderExcluirNota 9,5 (nove e meio)