Algoritmos e Estruturas de Dados/Estruturas para classes de equivalência: mudanças entre as edições
imported>LeonardoG (cat) |
imported>LeonardoG Sem resumo de edição |
||
Linha 36: | Linha 36: | ||
Existe basicamente duas estruturas de dados para implementar o tipo abstrato ''União-Busca'': a baseada em listas, e a baseada em árvores. A [[CC:ED:uniao_busca_linear|estrutura de dados linear]], baseada em listas encadeadas, é mais apropriada para aplicações onde o número de operações de união é pequeno com relação ao número de aplicações de busca. Em contrapartida, a [[CC:ED:uniao_busca_ramificada|estrutura de dados ramificada]], baseada em árvores, é mais eficiente quando o número de união é proporcionalmente mais elevado que o número de buscas. | Existe basicamente duas estruturas de dados para implementar o tipo abstrato ''União-Busca'': a baseada em listas, e a baseada em árvores. A [[CC:ED:uniao_busca_linear|estrutura de dados linear]], baseada em listas encadeadas, é mais apropriada para aplicações onde o número de operações de união é pequeno com relação ao número de aplicações de busca. Em contrapartida, a [[CC:ED:uniao_busca_ramificada|estrutura de dados ramificada]], baseada em árvores, é mais eficiente quando o número de união é proporcionalmente mais elevado que o número de buscas. | ||
[[Categoria: | [[Categoria: Estrutura de dados]] |
Edição das 12h07min de 4 de fevereiro de 2006
Estruturas para classes de equivalência
Introdução
Definições
Uma relação binária sobre um domínio é uma relação de equivalência se satisfaz as seguintes propriedades
- ( é simétrica);
- ( é reflexiva);
- ( é transitiva).
Seja um elemento do domínio, a classe de equivalência de é o conjunto dos elementos relacionados com .
Objetivos
O objetivo é definir um tipo abstrato de dados que permita representar e manipular eficientemente classes de equivalência que evoluem dinamicamente, podendo tanto ser criada novas classes, quanto juntadas classes existentes. Também queremos ter uma operação que permite determinar a classe de equivalência de um elemento.
Para tanto, consideramos que o cliente do tipo abstrato de dados manipula valores de um determinado domínio que nomeamos domain.
O tipo abstrato de dados possuirá três operações: criação de uma nova classe, busca da classe de um valor, e união de duas classes.
- criação de uma nova classe de equivalência
- dado um elemento d de domain, cria uma nova classe comportando apenas como elemento d e retorna o handler associado a d. O cliente apenas poderá acessar a classe de d através desse handler. Portanto, é da responsabilidade do cliente manter uma associação entre valores e handlers dos valores.
- busca da classe de equivalência
- dado o handler de um elemento d de domain, retorna a classe de d.
- união de duas classes de equivalência
- dado os handlers de dois elementos d1 e d2 de domain, realiza a união das duas classes de equivalência de d1 e d2.
Apresentação das soluções
Os algoritmos e estruturas de dados que provêm implementação eficientes desse tipo abstrato de dados são conhecidos como algoritmos Union-Find (União-Busca), pelo tipo de operações que são providas. Outros nomes encontrados são disjoint sets (conjuntos disjuntos) e dynamic equivalence relations (relações de equivalência dinâmicas).
Existe basicamente duas estruturas de dados para implementar o tipo abstrato União-Busca: a baseada em listas, e a baseada em árvores. A estrutura de dados linear, baseada em listas encadeadas, é mais apropriada para aplicações onde o número de operações de união é pequeno com relação ao número de aplicações de busca. Em contrapartida, a estrutura de dados ramificada, baseada em árvores, é mais eficiente quando o número de união é proporcionalmente mais elevado que o número de buscas.