Número: 045
Enunciado: Num problema de ordenação por reversões, resultou o seguinte diagrama de ciclos. Sobre este diagrama, podemos afirmar que:
- Ele possui três componentes, sendo que todas elas são componentes ruins e super-obstáculos que formam uma fortaleza.
- Ele possui três componentes, sendo que uma delas é boa e as outras duas são ruins.
- Ele possui três componentes, sendo que duas delas são componentes boas e a outra é uma componente ruim e também um obstáculo simples.
- Ele possui três componentes, sendo que duas delas são componentes boas e a outra é uma componente ruim que não é obstáculo.
- NDA
Este comentário foi removido pelo autor.
ResponderExcluirResposta: c
ResponderExcluir----------
O 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.c) 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.d) 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 BOM
Componente que possui pelo menos um ciclo bom.
iv.c) COMPONENTE RUIM
Componente composto totalmente por ciclos ruins.
iv.c.1) OBSTÁCULO
É um componente ruim que NÃO separa quaisquer dois outros componentes ruins.
iv.c.2) OBSTÁCULO SIMPLES E SUPEROBSTÁCULO
Um obstáculo A é chamado de Superobstáculo se ele protege um componente B que não é um obstáculo. Caso contrário, ele é chamado de Obstáculo Simples.
----------
Com as definições acima, podemos classificar todos os ciclos e componentes do diagrama.
O diagrama em questão é um Diagrama de Realidade e Desejo.
CICLOS: A, B, C, D, E e M (o ciclo da “Mãozinha”)
CICLOS BONS: C e M
CICLOS RUINS: A, B, D e E
COMPONENTES: AE, BCD e M
COMPONENTES BONS: BCD e M
COMPONENTES RUINS: AE
Passemos agora à avaliação das alternativas:
a) FALSA. Nem todos os componentes são ruins.
b) FALSA. Dois componentes bons e um ruim.
c) VERDADEIRA.
d) FALSA. Apenas o componente AE poderia separar outros componentes. Como ele é ruim, é um candidato a obstáculo. Ele separa os outros componentes (BCD e M). Entretanto, como esses outros componentes são bons, não há como AE separar componentes ruins. Portanto, AE é o único componente ruim e TAMBÉM É um obstáculo, invalidando essa alternativa.
Excelente. Detalhou bem. Apenas uma coisa: em (iv) GRAFO DE ENTRELAÇAMENTO, são arestas Desejo que se cruzam, e não realidade.
ResponderExcluirNota 9,5 (nove e meio).