Número: 032
Enunciado:
Considere as seguintes afirmativas:
I - Árvores PQ são estruturas de dados compactas utilizadas para representar permutações entre elementos de um conjunto U sujeitas a diversas restrições especificadas por subconjuntos de U. Cada subconjunto especificado restringe as permutações àquelas em que os elementos do subconjunto aparecem de forma consecutiva.
II - Uma árvore PQ admite apenas dois tipos de transformações de equivalência: permutar arbitrariamente os filhos de um nó P e inverter a ordem dos filhos de um nó Q.
III - O algoritmo de redução que constrói uma árvore PQ, dados o conjunto universo U e um conjunto de subconjuntos de U, é um processo iterativo que começa com uma árvore PQ nula.
IV - Numa árvore PQ, os elementos do conjunto universo U estão sempre nas folhas.
Escolha a opção correta.
- Todas estão corretas.
- Apenas II e III estão corretas.
- Apenas I e II estão corretas.
- Apenas I, II e IV estão corretas.
- NDA
As páginas citadas ao longo da resolução fazem referência ao artigo
ResponderExcluirBooth, K.S. & Lueker, G.S., Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity usingPQ-Tree Algorithms. J. Comput. Systems Sci., 1976, Vol. 13(3), pp. 335-379
I - Árvores PQ são estruturas de dados compactas utilizadas para representar permutações entre elementos de um conjunto U sujeitas a diversas restrições especificadas por subconjuntos de U. Cada subconjunto especificado restringe as permutações àquelas em que os elementos do subconjunto aparecem de forma consecutiva.
VERDADEIRA. O conjunto U é chamado de Conjunto Universal (p. 338). Todo elemento de U aparece precisamente, e uma única vez, como uma folha da árvore PQ (p. 339). Porém, a maneira como eles aparecem deve respeitar o subconjunto S, que define as restrições de um dado problema (p. 335). Nesse contexto, uma árvore PQ representa a classe de todas as permutações possíveis (p. 336). Em outras palavras, todas as soluções possíveis, por isso ela é importante. Mesmo assim, necessita de uma quantidade modesta de armazenamento (p. 337), justificando o adjetivo “compacta”.
II - Uma árvore PQ admite apenas dois tipos de transformações de equivalência: permutar arbitrariamente os filhos de um nó P e inverter a ordem dos filhos de um nó Q.
VERDADEIRA. Essas transformações definem o conceito de Equivalência (p. 340). Duas árvores PQ são equivalentes se, e somente se, uma pode ser transformada na outra aplicando zero ou mais transformações de equivalência, descritas corretamente nesse item II. É nesse conceito que reside a propriedade de uma árvore PQ representar todas as permutações possíveis. Por exemplo, se uma árvore T representa uma solução, e se aplicarmos algumas transformações de equivalência, levando-nos à árvore T’, essa T’ também é uma solução. Ou seja, se T respeita S, T’ também o faz.
III - O algoritmo de redução que constrói uma árvore PQ, dados o conjunto universo U e um conjunto de subconjuntos de U, é um processo iterativo que começa com uma árvore PQ nula.
FALSA. Redução é uma operação sobre as árvores PQ (p. 342). A única, aliás. Ela parte da árvore original e, a cada iteração, gera uma nova árvore PQ. Ao final do processo as folhas se organizam de maneira consecutiva e ainda respeitando as restrições definidas no subconjunto S. Por isso esse algoritmo é aplicado ao problema das matrizes com a propriedade dos uns consecutivos (C1P). Por outro lado, e ao contrário do que afirma a III, se durante o procedimento obtém-se a árvore nula, isso indica que a árvore original não pode ser reduzida.
IV - Numa árvore PQ, os elementos do conjunto universo U estão sempre nas folhas.
VERDADEIRA. Essa afirmação faz parte da definição das árvores PQ (p. 338). Ler as folhas da esquerda para a direita leva à fronteira da árvore, que nada mais é do que uma permutação do conjunto U (p. 340).
Finalmente, como apenas I, II e IV estão certas, a opção correta é a 4.
Caro Adriano,
ResponderExcluirAchei suas respostas um pouco longas demais, abordando às vezes assuntos alheios ao que cada item precisa, e deixando de abordar o que precisa. Eu prefiro que vá direto ao ponto.
Fiquei com a impressão que eles são cópias fiéis do paper em vários lugares. Eu prefiro que vocês redijam os comentarios com suas prórpias palavras.
Noto ainda que você usa S para indicar todas as restrições. Neste caso, convencionamos chamar S de coleção ao invés de conjunto.
Gostei de você explicar o "compacta" na I, uma pergunta que surgiu em aula. Porém, fora isto, seus comentários em geral floreiam muito e às vezes não tocam no que interessa. Na III, por exemplo, você devia ter dito que parte-se da árvore universal.