MO640 – Resolução dos
Exercícios - Sobre a aula de 2006-06-19
1.
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? Se adicionarmos o conjunto a1an a esta árvore,
qual será o tamanho de PRUNED? Qual será a árvore resultante e qual sua norma?
Árvore PQ correspondente:
Norma da árvore:
Norma = num de nós Q + num de nós cujo
pai eh nó P
num de nós Q = 0
num de nós cujo pai eh nó P = numero de
folhas + nós internos = (n) + (n-2)
Logo… Norma = 2n – 2
Ao adicionar a1an qual será o tamanho de PRUNED? (n+1)
Qual a árvore resultante e qual a sua norma?
Norma
= 0+1 = 1