2. Resumo da aula
- aula iniciada às 8:05 hs
- aluno Nielsen é chamado para discutir a definição abstrata da estrutura de dados
- aluno Alexandre é chamado para discutir a aplicação "componentes conexos de grafo não-orientado"
- aluno Fábio é chamado para discutir a implementação de florestas de conjuntos disjuntos
- aluno Augusto é chamado para discutir a primeira heurística utilizada em conjuntos disjuntos para melhorar o tempo de execução: união por posto (ranking)
- aluno José Augusto é chamado para complementar a explicação sobre as heurísticas com a explicação sobre a compressão de caminhos
- aluno Patrick é chamado para explicar as operações em florestas de conjuntos disjuntos com as heurísticas
- aluna Camila é chamada para discutir a complexidade das operações e a função alpha
- a aula é encerrada com uma breve discussão sobre os lemas 21.10, 21.11 e 21.12 do capítulo 21 de [1], e com as erratas do mesmo capítulo, o qual foi o estudo da aula.
- aula encerrada às 9:25 hs
3. Explicações detalhadas
3.1. Definição abstrata da estrutura de dados
Uma estrutura de dados de conjuntos disjuntos mantém uma coleção S1, S2, ..., Sk de conjuntos disjuntos dinâmicos, onde cada conjunto é identificado por um representante (algum elemento do conjunto). Portanto, os n elementos estarão distribuídos entre esses conjuntos, onde cada elemento pertence a somente um único conjunto, o que dá a característica de serem disjuntos. Inicialmente, cada elemento está em um conjunto, e vão ocorrendo uniões entre os conjuntos, sendo que não existem separações. Operações suportadas:
- MAKE-SET(x): cria um novo conjunto com um elemento, x, que é seu representante
- UNION(x,y): une dois conjuntos cujos representantes são x e y. Os dois conjuntos são distruídos e o representante do novo conjunto pode ser x, y ou qualquer outro elemento pertencente a ele.
- FIND-SET(x): retorna um ponteiro para o representante do (único) conjunto que contém o elemento x.
3.2. Aplicação: componentes conexos de grafos
Uma das muitas aplicações de estruturas de dados em conjuntos disjuntos surge na determinação dos componentes conexos de um grafo não-orientado (determinar se dois nós estão em um mesmo componente conexo). Para tal são utilizados:
- CONECTED-COMPONENTS(G): utiliza as 3 operações de conjuntos disjuntos para formar os componentes conexos do grafo G. Primeiro, o procedimento chama MAKE-SET para cada um dos vértices do grafo. Após isso, para cada aresta do grafo, ele une os conjuntos em que esses dois vértices estão, caso já não estejam unidos. Isto e feito chamando-se FIND-SET e comparando os conjuntos: se eles forem diferentes, UNION e chamado para uni-los.
- SAME-COMPONENT(u,v): uma vez que CONECTED-COMPONENT tenha sido chamado para criar os conjuntos disjuntos de vértices conectados, SAME-COMPONENT responde a consultas para saber se dois vértices, u e v, estão no mesmo componente conectado. Para isso, o procedimento chama FIND-SET para os dois vértices e compara seu retorno, retornando verdadeiro ou falso caso eles estejam ou não no mesmo conjunto.
É importante ressaltar que essa abordagem não suporta a operação de listar os nós de um componente, somente oferece a possibilidade de saber se um par de vértices estão num mesmo componente (se há um caminho que os conecta). Essa implementação é boa quando as arestas do grafo são dinâmicas (estão sempre sendo criadas novas arestas) e, portanto, precisa-se manter os componentes conexos à medida que cada aresta é adicionada.
Nesta seção da aula, foi levantada a dúvida de como FIND-SET poderia ser quase O(1) já que ele funciona sobre um conjunto de elementos. Na verdade, esta operação considera como entrada um ponteiro para o objeto ou seja, não é necessário fazer uma busca por ele.
3.3. Florestas de conjuntos disjuntos
Em uma implementação de conjuntos disjuntos representam-se conjuntos por árvores enraizadas, com cada nó contendo um elemento, e cada árvore representando um conjunto. Em cada árvore, cada nó aponta para seu pai - somente um ponteiro - e a raiz aponta para si mesma.
A operação MAKE-SET simplesmente cria uma árvore com apenas um nó. A operação FIND-SET segue os ponteiros de pais até encontrar a raiz (os nós visitados nesse caminho constituem o caminho de localização). E a operação UNION faz a raiz de uma árvore apontar para a raiz da outra.
Essa abordagem é bastante utilizada por dois motivos:
1 - simplicidade da estrutura e suas operações e
2 - simplicidade para aplicar as 2 heurísticas que melhoram o tempo de execução, tornando essa estrutura fácil de implementar, simples e eficiente.
3.4. Heurísticas para melhorar o tempo de execução
A implementação de conjuntos disjuntos com árvores enraizadas não é melhor, até agora, que a implementação por listas ligadas (não discutida na aula). Porém, é possível conseguir um tempo quase linear no número total de operações MAKE-SET, UNION e FIND-SET acrescentando duas heurísticas.
3.4.1. União por posto
A primeira heurística, união por posto (ranking), ou por ordenação, faz a raiz da árvore com "posto" menor apontar para a raiz com mais nós na operação UNION. Desta forma evita criar uma árvore muito profunda (com poucos nós em cada nível e muitos níveis). Para cada nó é mantido um "posto" que é um limite superior sobre a altura do nó. Na união por posto, a raiz com menor posto é levada a apontar para a raiz com maior posto.
3.4.2. Compressão de caminho
A segunda heurística, compressão de caminho, também é bastante simples e muito eficiente. Seu princípio básico é de, durante as operações FIND-SET, fazer cada nó no caminho de localização apontar diretamente para a raiz. Desta forma, na próxima chamade de FIND-SET deste elemento, o caminho estará "otimizado" e o procedimento levará somente O( 1 ). A compressão de caminho não altera quaisquer postos.
Durante esta seção foi levantada a dúvida sobre o significado do termo "heurística". O professor Meidanis explicou que heurística é uma abordagem, ou técnica, utilizada para melhorar algoritmos (tomando-se por base o escopo da disciplina) e/ou suas estruturas utilizadas mas que não se consegue provar alguma garantia sobre ela. Ex.: heurísticas são muito utilizadas em problemas NP-completos.
3.4.3. Operações para florestas de conjuntos disjuntos utilizando as duas heurísticas
Para implementar as operações em florestas de conjuntos disjuntos com heurística de união por posto, deve-se controlar o posto - posto[x] (no livro está como ordem[x]), que, para cada nó, corresponde a um limite superior para o número de arestas no caminho mais longo entre x e uma folha descendente. O posto existe para todos os nos mas é usado somente enquanto o nó é raiz. Quando ele deixa de ser raiz, seu posto não é mais atualizado nem utilizado.
MAKE-SET(x): o posto inicial do único nó na árvore correspondente é igual a zero.
UNION(x,y): se as raízes têm postos desiguais, a raiz de posto mais alto torna-se o pai da raiz de posto mais baixo, e os postos não se alteram; se as raízes têm postos iguais, escolhe-se arbitrariamente uma das raízes como pai e incrementa-se seu posto de uma unidade.
FIND-SET(x): recursivamente, efetua duas passagens - uma passagem para cima no caminho de localização a fim de encontrar a raiz, e depois faz uma segunda passagem de volta no caminho de localização, com o objetivo de atualizar cada nó, de modo que ele aponte diretamente para a raiz.
3.5. Complexidade e função alpha
O tempo de execução da estrutura de dados de conjuntos disjuntos é analisado em termos de dois parâmetros:
- n: o número de operações MAKE-SET, ou seja, o número total de elementos
- m: o número total de operações MAKE-SET, UNION e FIND-SET, onde m >= n, pois as operações MAKE-SET já estão incluídas no número total de operações m, e existem no máximo n - 1 operações UNION.
Embora as duas heurísticas possam ser analisadas separadamente, normalmente elas são utilizadas juntas pois dessa forma a melhora no tempo de execução é ainda maior.
Sozinha, a união por posto produz tempo de execução de O( m lg n ).
Já a heurística de compressão de caminhos, sozinha, fornece o tempo no pior caso de q ( n + f * ( 1 + log2 + f/n n ) ), onde f é o número de operações FIND-SET.
Usadas juntas, as duas heurísticas produzem um tempo de execução no pior caso de O( m a ( n ) ), onde a ( n ) é uma função muito lentamente crescente. Em qualquer aplicação concebível de uma estrutura de dados de conjuntos disjuntos, a ( n ) <= 4 e, desse modo, pode-se considerar o tempo de execução linear em m para todas as situações práticas.
A prova desse tempo exige a análise de diversos teoremas, dentre estes apenas o 20.10, 20.11, 20,12 foram brevemente discutidos na aula. Porém, a cobertura da matéria nao entra neste nível de detalhamento.
3.6. Aplicações
Alguns exemplos mais comuns foram citados na aula pelo professor Meidanis (p.e., Computação Distribuída) sendo que a maioria das aplicações caem no problema de determinar os componentes conexos de um grafo não-orientado. Este exemplo é o mais genérico para a aplicação deste tipo de estrutura de dados.
4. Referencias Bibliograficas
1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Cliford Stein, Algoritmos, Teoria e Pratica, traducao da segunda edicao americana, editora Campus, 2002.