1 |
Experimentos computacionais com implementações de conjunto por endereçamento direto e o problema de conjunto independente máximo / Computational experiments with set implementations by direct addressing and the maximum independent set problemSantos, Marcio Costa January 2013 (has links)
SANTOS, Marcio Costa. Experimentos computacionais com implementações de conjunto por endereçamento direto e o problema de conjunto independente máximo. 2013. 78 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T19:04:45Z
No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-20T11:59:49Z (GMT) No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Made available in DSpace on 2016-07-20T11:59:49Z (GMT). No. of bitstreams: 1
2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5)
Previous issue date: 2013 / The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs. / A utilização de vetores de bits é prática corrente na representação de conjuntos por endereçamento direto com o intuito de reduzir o espaço de memória necessário e melhorar o desempenho de aplicações com uso de técnicas de paralelismo em bits. Nesta dissertação, examinamos implementações para representação de conjuntos por endereçamento direto. A estrutura básica nessas implementações é o vetor de bits. No entanto, além dessa estrutura básica, implementamos também duas variações. A primeira delas consiste em uma estratificação de vetores de bits, enquanto a segunda emprega uma tabela de dispersão. As operações associadas às estruturas implementadas são a inclusão ou remoção de um elemento do conjunto e a união ou interseção de dois conjuntos. Especial atenção é dada ao uso de paralelismo em bits nessas operações. As implementações das diferentes estruturas nesta dissertação utilizam uma interface e uma implementação abstrata comuns, nas quais as operações são especificadas e o paralelismo em bits é explorado. A diferença entre as implementações está apenas na estrutura utilizada. Uma comparação experimental é realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente máximo. Duas abordagens são utilizadas na implementação de algoritmos enumerativos para o problema de conjunto independente máximo, ambas explorando o potencial de paralelismo em bits na representação do grafo e na operação sobre subconjuntos de vértices. A primeira delas é um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o método das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiência quando empregado no cálculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais são apresentados como forma de comparação entre os dois algoritmos e como forma de avaliação das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no método das bonecas russas é mais eficiente quanto ao tempo de execução e quanto ao consumo de memória. Além disso, os resultados experimentais mostram também que o uso de estratificação e tabelas de dispersão permitem ainda maior eficiência no caso de grafos com muito vértices e poucas arestas.
|
2 |
Experimentos Computacionais com ImplementaÃÃes de Conjunto por EndereÃamento Direto e o Problema de Conjunto Independente MÃximo / Computational Experiments with Set Implementations by Direct Addressing and the Maximum Independent Set ProblemMarcio Costa Santos 13 September 2013 (has links)
CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A utilizaÃÃo de vetores de bits à prÃtica corrente na representaÃÃo
de conjuntos por endereÃamento direto com o intuito de reduzir o espaÃo de memÃria necessÃrio e melhorar o desempenho de aplicaÃÃes com uso de tÃcnicas de paralelismo em bits.
Nesta dissertaÃÃo, examinamos implementaÃÃes para
representaÃÃo de conjuntos por endereÃamento direto.
A estrutura bÃsica nessas implementaÃÃes à o vetor de bits.
No entanto, alÃm dessa estrutura bÃsica, implementamos tambÃm duas
variaÃÃes. A primeira delas consiste em uma estratificaÃÃo de
vetores de bits, enquanto a segunda emprega uma tabela de
dispersÃo.
As operaÃÃes associadas Ãs estruturas implementadas sÃo a
inclusÃo ou remoÃÃo de um elemento do conjunto e a uniÃo ou
interseÃÃo de dois conjuntos. Especial atenÃÃo à dada ao uso
de paralelismo em bits nessas operaÃÃes. As implementaÃÃes das
diferentes estruturas nesta dissertaÃÃo utilizam uma interface e uma
implementaÃÃo abstrata comuns, nas quais as operaÃÃes sÃo
especificadas e o paralelismo em bits à explorado. A diferenÃa entre
as implementaÃÃes està apenas na estrutura utilizada. Uma comparaÃÃo
experimental à realizada entre as diferentes estruturas utilizando
algoritmos enumerativos para
o problema de conjunto independente mÃximo.
Duas abordagens sÃo utilizadas na implementaÃÃo de algoritmos
enumerativos para o problema de conjunto independente mÃximo,
ambas explorando o potencial de paralelismo em bits na
representaÃÃo do grafo e na operaÃÃo sobre subconjuntos de vÃrtices.
A primeira delas à um algoritmo do tipo {em branch-and-boound}
proposto na literatura e a segunda emprega o mÃtodo das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiÃncia quando empregado no cÃlculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais sÃo apresentados como forma de comparaÃÃo entre os dois algoritmos e como forma de avaliaÃÃo das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no mÃtodo das bonecas russas à mais eficiente quanto ao tempo de execuÃÃo e quanto ao consumo
de memÃria. AlÃm disso, os resultados experimentais mostram tambÃm que o uso de estratificaÃÃo e tabelas de dispersÃo permitem ainda maior eficiÃncia no caso de grafos com muito vÃrtices e poucas arestas. / The use of bit vectors is a usual practice for represent sets by
direct addressing with the aim of reduce memory consumed and improve
efficiency of applications with the use of bit parallel techniques.
In this text, we study implementations for represent sets by
direct addressed. The basic structure in this implementations is
the bit vector. Besides that basic implementation, we implement two
variations also. The first one is a stratification of the bit vector, while
the second uses a hash table.
The operations linked to the implemented structure are include and
remove an element and the union and intersection of two sets. Especial
attention is given to the use of bit parallel in this condition. The
implementation of the different structures in this work use an
base interface and a base abstract class, where the operations
are defined and the bit parallel is used. An experimental comparative
between this structures is carry out using enumerative algorithms for
the maximum stable set problem.
Two approaches are used in the implementation of the enumerative
algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations
with subsets of vertices. The first one is a known branch-and-bound algorithm
and the second uses the Russian dolls method. In both cases, the use of
bit parallel improve efficiency when the lower bounds are calculated
based in a clique cover of the vertices. The results of computational experiments are presented as
comparison between the two algorithms and as an assessment of the structures
implemented. These results show that the algorithm based on the method
Russian Dolls is more efficient regarding runtime and the memory consumed.
Furthermore, the experimental results also show that the use
stratification and hash tables also allow
more efficiency in the case of sparse graphs.
|
Page generated in 0.147 seconds