MO640/MC931 - Biologia computacional

Ata de aula - 13 / Out / 2004

Autor: Fernando César David Rama - ra008690

Aula baseada no artigo Meidanis e Telles 2004 - TELLES, G. P.; MEIDANIS, J. Building PQR Trees in Almost-Linear Time. Submetido a publição, 2004.

1. Na seção 1 - introduction -, é descrito o problema que motiva o artigo.
   
   1. O que é union find?
      É uma estrutura onde o utilizador tenta fazer operações sobre conjuntos (união e busca¹) em O(α)≈O(1) amortizados.
      Utilização: divisão dos nós em conjuntos disjuntos e determinação do líder².
   Pesquisando para re-escrever.

2. À página 6 do artigo, fala-se sobre coloração dos nós da árvore.
   
   1. Como obtém-se coloração com LCA?
      Primeiro passo: determinação de quantos filhos pertinentes.
      Segundo passo: determinação do LCA.
      Coloração:
      • preto: folhas. Quando todos os filhos forem pertinentes e pretos, então o pai é preto.
      • cinza: quando tiver uma folha descendente branca e uma preta.
      • branco: nós não visitados e LCA.

3. Dada uma árvore T e um set S, quais nós T ganha e quais perde em sua atualização em função de S?
   • Ganha: nós P na primeira operação.
   • Perde: nós cinzas, porque estes não são ortogonais a S.

4. No artigo em questão, fala-se em potencial da árvore. Este é definido como segue.
   pot(T) = ∑_{v nó P de T}|v| + ∑_{v nó Q/R de T}1

5. Fala-se também em reversão condicional.
   Ela pode acontecer em dois lugares:
   1. preparando LCA: o LCA é revertido quando a cor de seu filho mais à esquerda é menos que a cor de seu filho mais à direita.
   2. preparando os filhos: um nó cinza v é revertido quando a cor do vizinho à esquerda de v é menos que a cor do vizinho à direita. Se v tiver apenas um vizinho, deve-se aplicar o mesmo critério, assumindo-se que a cor do vizinho faltante é 1/2.

6. O padrão que o algoritmo mostrado no artigo usa para a atualizaçÃo da árvore em função da coloração é percorrer os filhos do nó em questão da esquerda para direita, tratando os mais escuros primeiro. Quando não for possível seguir isto, usa a reversão condicional, discutida à seção 5 desta ata.

1. A busca citada é por qual conjunto ao qual pertence o elemento sendo analizado.
2. Líder, em union find, é o filho que aponta para o pai e para o qual apontam seus irmãos.