Ata de Resolução de Exercícios - Conjuntos Disjuntos - 09/05/2003

Disciplina: MO417 - Complexidade de Algoritmos I
Livro texto: Algoritmos : teoria e prática / Thomas H. Cormen... [et al.]; tradução da segunda edição [americana] - Rio de Janeiro : Campus, 2002
Redator: Alexandro Baldassin  022243

21.3-1
Faça o Exercício 21.2-2 usando uma floresta de conjuntos disjuntos com união por ordenação e compressão de caminho.
(21.2-2) Mostre a estrutura de dados resultante e as respostas retornadas pelas operações FIND-SET no programa a seguir.

1  for i <- 1 to 16
2     do MAKE-SET(xi)
3  for i <- 1 to 15 by 2
4     do UNION(xi, xi+1)
5  for i <- 1 to 13 by 4
6     do UNION(xi, xi+2)
7  UNION(x1, x5)
8  UNION(x11, x13)
9  UNION(x1, x10)
10 FIND-SET(x2)
11 FIND-SET(x9)


Ambos FIND-SETs das linhas 10 e 11 retornam x16. As estruturas são:

FIND-SET(x2)



FIND-SET(x9)

21.3-2
Escreva uma versão não recursiva de FIND-SET com compressão de caminho.
NR_FIND-SET(x)
    representante <- x

    ; primeiro achamos o representante do conjunto (primeira passada)
    enquanto (representante <> pai[representante]) faça    
       representante <- pai[representante]

    ; agora subimos novamente na árvore, associando os pais de x ao representante
    caminho <- x
    enquanto (caminho <> pai[caminho]) faça     
       temp <- pai[caminho]
       pai[caminho] <- representante
       caminho <- temp

    retorna representante

21.3-3
Forneça uma sequëncia de m operações MAKE-SET, UNION e FIND-SET, n das quais são operações MAKE-SET, que demore o tempo Ω(mlgn) quando usarmos somente a união por ordenação.

Sequëncia possível de operações, onde n é o número de elementos:

for i <- 1 to n do
   MAKE-SET(xi)
for dist <- 1 to piso(lgn) do
   for i <- 1 to ((n+1) - 2^dist) by 2^dist
      UNION(xi, xi+((2^dist)/2))
for j <- 1 to n do
   FIND-SET(x1)

As linhas 1 e 2 realizam n operações MAKE-SET. As linhas 3, 4 e 5 realizam sucessivas uniões em pares de nós: na primeira vez temos as uniões de pares consecutivos (x1,x2), (x3,x4),...,(xn-1,xn); depois temos (x1,x3), (x5,x7),...,(xn-3,xn-1); de forma que continuamos isso até termos somente um conjunto formado. Isso leva um total de n-1 operações de UNION e produz uma árvore de altura Ω(lgn). Por fim, as linhas 6 e 7 realizam n operações FIND-SET na folha mais profunda da árvore. Então, para m = n + n - 1 + n temos o tempo de Ω(n+mlgn) = Ω(mlgn).