Ata da solução dos exercícios sobre a aula de 2007-06-11
1. Ache a árvore PQ correspondente ao seguinte problema: U=abcde, S={abc, be, cd}.
Mostre as árvores intermediárias obtidas adicionando um conjunto de cada vez.
Resposta: A árvore PQ correspondente pode ser vista na figura abaixo. As linhas pontilhadas indicam que a aplicação do template dá continuidade na linha abaixo,
os asteriscos acima de uma seta horizontal indicam árvores intermediárias à adição de um conjunto; o conjunto correspondente à adição corrente se encontra
sob a seta horizontal anterior à primeira árvore necessária para a adição do mesmo.
2. Considere o conjunto universo U = {a1, a2, a3, ..., an} e a coleção S = {a1a2,
a1a2a3, a1a2a3a4, ..., a1a2...an-2an-1}. Qual será a árvore PQ correspondente a este problema? Qual será a norma desta árvore?
Ao adicionarmos o conjunto a1an a esta árvore, qual será o tamanho de PRUNED?
Qual será a árvore resultante e qual sua norma?
Resposta: A árvore PQ correspondente ao conjunto universo U = {a1, a2, a3, ..., an}
e à coleção S = {a1a2, a1a2a3, a1a2a3a4, ..., a1a2...an-2an-1} pode ser vista na figura abaixo na qual a linha pontilhada indica a existência de outros níveis intermediários:
A norma da árvore PQ acima pode ser calculada pela soma do número de nós do tipo Q
com o número de nós filhos de nós P. Portanto a norma é igual a 2n - 2.
Adicionando o conjunto a1an teremos a norma de PRUNED igual a n - 1.
A árvore PQ correspondente à adição do conjunto a1an pode ser vista na figura abaixo:
A norma da árvore PQ acima é igual a 1.
3. O algoritmo BUBBLE dado no artigo de Booth e Lueker só funciona quanto o conjunto S pode ser adicionado à árvore T gerando uma nova árvore não nula.
Contudo, em classe foi visto um algoritmo que encontra a raiz da subárvore pertinente em qualquer caso. Escreva este algoritmo em pseudo-código.
Resposta: O pseudo-código é formado por dois passos e pode ser visto na figura abaixo:
