Algoritmos e Estruturas de Dados/Estruturas para classes de equivalência: mudanças entre as edições
imported>David Deharbe |
imported>David Deharbe |
||
Linha 5: | Linha 5: | ||
==== Definições ==== | ==== Definições ==== | ||
Uma relação binária <math>\equiv</math> sobre um domínio <math>\mathcal{D}</math> é uma relação de | Uma relação binária <math>\equiv</math> sobre um domínio <math>\mathcal{D}</math> é uma '''relação de | ||
equivalência se satisfaz as seguintes propriedades | equivalência''' se satisfaz as seguintes propriedades | ||
# <math>\forall a, b \in \mathcal{D} \bullet a \equiv b \Leftrightarrow b \equiv a</math> (<math>\equiv</math> é simétrica); | # <math>\forall a, b \in \mathcal{D} \bullet a \equiv b \Leftrightarrow b \equiv a</math> (<math>\equiv</math> é simétrica); | ||
# <math>\forall a \in \mathcal{D} \bullet a \equiv a</math> (<math>\equiv</math> é reflexiva); | # <math>\forall a \in \mathcal{D} \bullet a \equiv a</math> (<math>\equiv</math> é reflexiva); | ||
# <math>\forall a, b, c \in \mathcal{D} \bullet a \equiv b \land b \equiv c \Rightarrow a \equiv c</math> | # <math>\forall a, b, c \in \mathcal{D} \bullet a \equiv b \land b \equiv c \Rightarrow a \equiv c</math> (<math>\equiv</math> é transitiva). | ||
Seja <math>a \in \mathcal{D}</math> um elemento do domínio, a classe de equivalência | Seja <math>a \in \mathcal{D}</math> um elemento do domínio, a '''classe de equivalência''' | ||
de <math>a</math> é o conjunto <math>{x \in \mathcal{D} \mid x \equiv a}</math> dos elementos | de <math>a</math> é o conjunto <math>\{x \in \mathcal{D} \mid x \equiv a\}</math> dos elementos | ||
relacionados com <math>a</math>. | relacionados com <math>a</math>. | ||
Edição das 17h22min de 4 de novembro de 2005
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.