Ata de Aula (18/10/2004)
Disciplina de Biologia
Computacional
Professor: Dr. João
Meidanis
Assunto: Algoritmo
quase-linear para construção de árvores PQR
Artigo texto: Building
PQR Trees in Almost-Linear Time, G. P. Telles, J. Meidanis. (Submited
for publication in August 2004).
Autor: Roberto Hiroshi Higa - RA: 876131
Esta ata cobre os seguintes tópicos:
- Complexidade do algoritmo quase-linear para construção de árvores
PQR
- Implementação do algoritmo
Os assuntos foram desenvolvidos por meio de uma dinâmica de
perguntas e respostas. Ao longo do processo, os tópicos da aula foram
desenvolvidos e as dúvidas sanadas.
Discussão:
-
Com
relação ao passo 1 (“colorir as folhas correspondentes a S”) do
algoritmo, descreva suscintamente o que ele faz e sua complexidade.
Este passo apenas
colore de preto os nós correspondentes aos elementos em S. Ele tem
complexidade linear no tamanho de S.
OBS: Na implementação, os nomes de
elementos serão trocados por números para facilitar a indexação.
-
Com
relação ao passo 2 (“Colorir a árvore e encontrar o LCA”) do
algoritmo, descreva suscintamente o que ele faz e sua complexidade.
A coloração da
árvore é realizada simultaneamente com o algoritmo para encontrar a LCA
descrito no artigo de Booth & Looker [1], visto em aula anterior.
A complexidade
do passo é linear em tamanho de prunned (artigo de Booth & Looker).
Prunned corresponde ao conjunto de nós coloridos (cinza + pretos) e seu
tamanho corresponde a m3 + tamanho de S (m3 é o número de passos no
passo 3 do algoritmo).
-
Com
relação ao passo 3 (“Reestruturar a árvore, eliminando nós cinza”),
descreva suscintamente o que ele faz e sua complexidade.
Basicamente, o
passo executa as operações descritas nas figuras 3 a 6.
O passo é
dominado pela operação de movimentação e, quanto à sua complexidade,
existe um limitante superior para o passo, dado pelo teorema 5.
Por que é a operação de movimentação que
domina o passo? Os outros passos em geral implicam em alguma
movimentação. Por exemplo, quando nós internos são criados, eles são
criados vazios. É preciso realizar operações de movimentação para
atribuir-lhe nós descendentes.
Mas o que significa “a operação de
movimentação domina” ? Quando os outros ocorrem, ele ocorre.
Então, juntando todas as operações
(movimentação, criação, reversão, merge), podemos dizer que eles são de
alguma forma proporcionais ao número de operações de movimentação?
Sim. Todos eles são da forma “uma constante vezes o número de
movimentações”. Basta avaliar o número de movimentações.
O número de movimentações no
passo 3 é limitado superiormente pelo tamanho de S? Não, m3 não
é limitado pelo tamanho de S.
-
Com
relação ao passo 4 (“Ajustar LCA”), descreva suscintamente o que ele
faz e sua complexidade.
Se o LCA é do tipo
P: se ele tem dois ou mais filhos pretos, e no mínimo um filho branco,
cria um novo filho do LCA do tipo P e move todos os filhos pretos para
esse novo nó.
Se o LCA é do
tipo Q: verifique se todos os filhos pretos são consecutivos. Se sim,
não faz nada, caso contrário, muda o tipo do LCA para R.
Se o LCA é do
tipo R: não faz nada.
A complexidade
do passo é O(tamanho de S).
-
Com
relação ao passo 5 (“descolorir a árvore”), descreva suscintamente o
que ele faz e sua complexidade.
Visita os nós
pretos (abaixo do LCA) descolorindo-os. Não faz nada com relação aos
nós brancos.
Como, no pior
caso (árvore binária), o número de nós é no máximo 2S, a complexidade
do passo é O(tamanho de S).
OBS: portanto, no total, a
complexidade do algoritmo é O(tamanho de prunned + tamanho de S).
-
Como
funciona a análise amortizada descrita no teorema 8?
Work(T,S) +
variação potencial (T,S) = O(tamanho de S)
E o que é a variação potencial? É a
diferença entre o potencial da árvore após a adição de S e antes
da adição de S.
-
O que
é o potencial da árvore?
É como se fosse uma
poupança. O algoritmo fica com uma espécie de crédito (obtidas de
operações não tão demandantes para inclusão de outros conjuntos S,
realizadas no passado) para utilizar em operações futuras mais
demandantes. Assim, na média, o algoritmo é O(tamanho de prunned +
tamanho de S).
-
E qual
a contribuição de cada nó da árvore para o potencial da árvore? Existe
um valor a mais no nó P quando comparado ao nó Q e R?
Cada nó do tipo P
contribui com o número de nós folhas descendentes enquanto nós do tipo
Q e R contribuem com 1 (vide página 13 do artigo). Note que a
contribuição do nó do tipo P, em geral, é muito maior que a dos nós do
tipo Q ou R.
OBS1: Mesmo que um conjunto pequeno
resulte em uma grande mudança na árvore, pode-se dispor do potencial e
manter a complexidade do algoritmo O(tamanho de prunned + tamanho de S).
OBS2: Se uma árvore apresenta muitos
nós do tipo P, com certeza, foi utilizada uma coleção grande de
subconjuntos de U para formar a árvore.
-
Sobre
implementação, com relação ao que foi discutido para árvores PQ, o que
muda na implementação da árvore PQR?
Utiliza-se as
estruturas de dados:
- Union
Find, permitindo a execução da operação “Merge to LCA” em O(1).
- Lista
simétrica (http://infosun.fmi.uni-passau.de/~raitner/)
para garantir a reversão da lista de filhos em O(1).
Referências:
[1] K. S. Booker
and G. S. Lueker. Testing for consecutive ones property, interval
graphs, and graph planarity using PQ-tree algorithms. Journal of
Computer and System Sciences, 13(3):335-379, 1976.