MO640 – Biologia Computacional
Ata de Exercícios (20/10/2004)
Autor: Cleber Valgas Gomes Mira - RA980866.

Os exercícios desta aula correspondem ao artigo:
Meidanis e Telles 2004 - TELLES, G. P.; MEIDANIS, J. Building PQR Trees in Almost-Linear Time. Submetido a publicação, 2004.


1-  Dada uma árvore PQR T, defina uma árvore T^⊥ tal que Compl(T)^⊥ = Compl(T^⊥).
R- Dada uma árvore PQR T, a árvore T^⊥ tal que Compl(T)^⊥ = Compl(T^⊥) é definida como a árvore que possui os mesmos nós que a árvore T, porém com os tipos dos nós modificados segundo a seguinte regra: nós P com mais de 2 filhos são transformados em R, nós Q e R são transformados em nós P.

Obs.: Os nós de T são representados pelo conjunto (Ĉ inter (C)^⊥ ), enquanto os da árvore T^⊥ são representados pelo conjunto
  ( (C)^⊥ inter (C^⊥ )^⊥ ). Os nós das árvores T e T^⊥  são os mesmos, exceto por mudanças de tipo, devido aos dois conjuntos anteriores serem iguias.

Notação:       Ĉ  - "C barra"
                     C^⊥ -  "C ortogonal"
                    inter - interseção de conjuntos

2-  Determine uma coleção de tamanho mínimo que adicionada à árvore PQR da Figura 2 do artigo de Meidanis, Porto e Telles, 1998, produza uma árvore com apenas um nó interno do tipo R. O tamanho de uma coleção é dado pela soma dos tamanhos dos conjuntos que a compõe.
R- { ae , ca }