A combinação de algoritmos tem despertado interesse para melhorar o desempenho de filtros adaptativos. Esse método consiste em combinar linearmente as saídas de dois filtros operando em paralelo com passos de adaptação diferentes para se obter um filtro com conver- gência rápida e um erro quadrático médio em excesso (EMSE - excess mean squared error) reduzido. Nesse contexto, foi proposta a combinação afim de dois algoritmos LMS (least-mean square), cujo parâmetro de mistura não fica restrito ao intervalo [0, 1] e por isso é considerada como uma generalização da combinação convexa. Neste trabalho, a combinação afim de dois algoritmos LMS é estendida para os algoritmos supervisionados NLMS (normalized LMS) e RLS (recursive least squares) e também para equalização autodidata, usando o CMA (constant modulus algorithm). Foi feita uma análise em regime da combinação afim desses algoritmos de forma unificada, considerando entrada branca ou colorida e ambientes estacionários ou não- estacionários. Através dessa análise, verificou-se que a combinação afim de dois algoritmos da mesma família pode apresentar uma redução de EMSE de até 3 dB em relação ao EMSE de seus filtros componentes e conseqüentemente ao EMSE da combinação convexa. Para garantir que a estimativa combinada seja pelo menos tão boa quanto a do melhor filtro componente, foram propostos e analisados três novos algoritmos para adaptação do parâmetro de mistura. Utilizando resultados da análise desses algoritmos em conjunto com os resultados da análise de transitório de filtros adaptativos, analisou-se o comportamento transitório da combinação afim. Através de simulações, observou-se uma boa concordância entre os resultados analíticos e os de simulação. No caso de equalização autodidata, também foi proposta uma combinação de dois equalizadores CMA com inicializações diferentes. Verificou-se através de simulações que em alguns casos a combinação afim é capaz de evitar a convergência para mínimos locais da função custo do módulo constante. / In order to improve the performance of adaptive filters, the combination of algorithms is receiving much attention in the literature. This method combines linearly the outputs of two filters operating in parallel with different step-sizes to obtain an adaptive filter with fast convergence and reduced excess mean squared error (EMSE). In this context, it was proposed an affine combination of two least-mean square (LMS) filters, whose mixing parameter is not restricted to the interval [0, 1]. Hence, the affine combination is a generalization of the convex combination. In this work, the affine combination of two LMS algorithms is extended to the supervised algorithms NLMS (normalized LMS) and RLS (recursive least squares), and also to blind equalization, using the constant modulus algorithm (CMA). A steady-state analysis of the affine combination of the considered algorithms is presented in a unified manner, assuming white or colored inputs, and stationary or nonstationary environments. Through the analysis, it was observed that the affine combination of two algorithms of the same family can provide a 3 dB EMSE gain in relation to its best component filter and consequently in relation to the convex combination. To ensure that the combined estimate is at least as good as the best of the component filters, three new algorithms to adapt the mixing parameter were proposed and analyzed. Using the analysis results of these algorithms in conjunction with the results of the transient analysis of adaptive filters, the transient behavior of the affine combination was analyzed. Through simulations, a good agreement between analytical and experimental results was always observed. In the blind equalization case, a combination of two CMA equalizers with different initializations was also proposed. The simulation results suggest that the affine combination can avoid local minima of the constant modulus cost function.

O planejamento probabilístico de mapa de rotas tem se mostrado uma poderosa ferramenta para o planejamento de caminhos para robôs móveis, devido a sua eficiência computacional, simplicidade de implementação e escalabilidade em diferentes problemas. Este método de planejamento possui duas fases. Na fase de construção, um mapa de rotas é gerado de forma iterativa e incremental, e armazenado na forma de um grafo G, cujos vértices são configurações livres, amostradas no espaço de configurações do robô e cujas arestas correspondem a caminhos livres de colisão entre tais configurações. Na fase de questionamento, dadas quaisquer configurações de origem e destino, \'alfa\' e \'beta\' respectivamente, o planejador conecta \'alfa\' e \'beta\' à G inserindo arestas que correspondem a caminhos livres de colisão, para então procurar por um caminho entre \'alfa\' e \'beta\' em G. Neste trabalho o foco reside principalmente na fase de construção do mapa de rotas. O objetivo aqui consiste em efetuar uma análise comparativa de diversas combinações de diferentes técnicas de amostragem das configurações livres e de diferentes técnicas de seleção de vértices em G, todas implementadas em um único sistema e aplicadas aos mesmos cenários. Os resultados propiciam um valioso auxílio aos usuários do planejamento probabilístico de mapas de rotas na decisão da melhor combinação para suas aplicações. / The probabilistic roadmap planning has emerged as a powerful framework for path planning of mobile robots due to its computational efficiency, implementation simplicity, and scalability in different problems. This planning method proceeds in two phases. In the construction phase a roadmap is incrementally constructed and stored as a graph G whose nodes are free configurations sampled on the robot\'s configuration space and whose edges correspond to collision-free paths between these configurations. In the query phase, given any start and goal configurations, \'alfa\' and \'beta\' respectively, the planner first connects \'alfa\' and \'beta\' to G by adding edges that correspond to collision-free paths, and then searches for a path in G between \'alfa\' and \'beta\'. In this work, we address mainly the roadmap construction phase. The goal here is to provide a comparative analysis of a number of combinations of different techniques for sampling free configurations and different node adding techniques, all implemented in a single system and applied to the same test workspace. Results help probabilistic roadmap planning users to choose the best combination for their applications.

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-09-05T13:28:55Z No. of bitstreams: 1 Cristiane Sousa.pdf: 1146877 bytes, checksum: 1ad12b0de7d3ec703fd7018518eaf404 (MD5) / Made available in DSpace on 2017-09-05T13:28:55Z (GMT). No. of bitstreams: 1 Cristiane Sousa.pdf: 1146877 bytes, checksum: 1ad12b0de7d3ec703fd7018518eaf404 (MD5) Previous issue date: 2009-02-13 / CAPES / Many of the adaptive filters are based on the Mean Squared Error (Mean Square Error - MSE). The development of these filters guarantees us to recover only second-order information of the signals to be filtered, ie not can fully recover information from Gaussian signals. However, the natural or artificial signals are not necessarily Gaussian. In this way, the use of high order statistics as a way of extracting more information of signals, has been shown to be of great value in adaptive systems [7] [8] [9]. In this work, we present the development of an adaptive algorithm based on nonlinear functions inspired by the deduction of the Recursive Lest algorithm Square (RLS) [1]. Such development is based on the use of high order to obtain more information on the signals involved in the process, with the goal of improving the performance of an adaptive filter. We will call this new nonlinear recursive algorithm - RNL. We deduce equations, based on a nonlinear function, to obtain convergence criteria. We also study covariance of the steady-state weight vector and we determine equations that calculate the mismatch and the learning time of the adaptive process of the RNL algorithm. We present the non - linear recursive algorithm, which uses the function "n = MP j = 1 nP i = 1nnnii [ei] 2jo, where M and n are positive integers. Were made simulations with this algorithm to validate the presented theory and study the convergence behavior of the RNL algorithm. The result showed that the RNL algorithm has a rapid convergence for the same mismatch when compared with the RLS algorithm. / Muitos dos flltros adaptativos s~ao baseados no método do Erro quadrático médio (Mean Square Error - MSE). O desenvolvimento desses flltros nos garante recuperar apenas informações de segunda ordem dos sinais a serem flltrados, ou seja, não consegue recuperar totalmente informações de sinais Gaussianos. No entanto, os sinais naturais ou artiflciais não são necessariamente gaussianos. Desta forma, a utilização de estatística de alta ordem, como uma forma de extrair mais informações dos sinais, tem se demonstrado de grande valia em sistemas adaptativos [7][8][9]. Neste trabalho, nós apresentamos o desenvolvimento de um algoritmo adaptativo baseado em funções não lineares inspirado na dedução do algoritmo Recursive Lest Square (RLS) [1]. Tal desenvolvimento baseia-se na utilização de estatísticas de alta ordem para a obtenção de mais informações dos sinais envolvidos no processo, com o objetivo de melhorar a performance de um flltro adaptativo. Chamaremos esse novo algoritmo de Recursivo não Linear - RNL. Deduzimos equações, baseadas em uma função não linear, para a obtenção de critérios que garantam a convergência. Também fazemos um estudo da covariância do vetor peso em regime estacionário e determinamos equações que calculem o desajuste e o tempo de aprendizagem do processo adaptativo do algoritmo RNL. Apresentamos o algoritmo n~ao linear recursivo, que utiliza como critério a função "n = MP j=1 nP i =1n‚n¡i [ei]2jo, sendo M e n inteiros positivos. Foram feitas simulações com este algoritmo para validar a teoria apresentada e estudamos o comportamento da convergência do algoritmo RNL. O resultado mostrou que o algoritmo RNL possui uma rápida convergência para o mesmo desajuste quando comparado com o algoritmo RLS.

A combinação de algoritmos tem despertado interesse para melhorar o desempenho de filtros adaptativos. Esse método consiste em combinar linearmente as saídas de dois filtros operando em paralelo com passos de adaptação diferentes para se obter um filtro com conver- gência rápida e um erro quadrático médio em excesso (EMSE - excess mean squared error) reduzido. Nesse contexto, foi proposta a combinação afim de dois algoritmos LMS (least-mean square), cujo parâmetro de mistura não fica restrito ao intervalo [0, 1] e por isso é considerada como uma generalização da combinação convexa. Neste trabalho, a combinação afim de dois algoritmos LMS é estendida para os algoritmos supervisionados NLMS (normalized LMS) e RLS (recursive least squares) e também para equalização autodidata, usando o CMA (constant modulus algorithm). Foi feita uma análise em regime da combinação afim desses algoritmos de forma unificada, considerando entrada branca ou colorida e ambientes estacionários ou não- estacionários. Através dessa análise, verificou-se que a combinação afim de dois algoritmos da mesma família pode apresentar uma redução de EMSE de até 3 dB em relação ao EMSE de seus filtros componentes e conseqüentemente ao EMSE da combinação convexa. Para garantir que a estimativa combinada seja pelo menos tão boa quanto a do melhor filtro componente, foram propostos e analisados três novos algoritmos para adaptação do parâmetro de mistura. Utilizando resultados da análise desses algoritmos em conjunto com os resultados da análise de transitório de filtros adaptativos, analisou-se o comportamento transitório da combinação afim. Através de simulações, observou-se uma boa concordância entre os resultados analíticos e os de simulação. No caso de equalização autodidata, também foi proposta uma combinação de dois equalizadores CMA com inicializações diferentes. Verificou-se através de simulações que em alguns casos a combinação afim é capaz de evitar a convergência para mínimos locais da função custo do módulo constante. / In order to improve the performance of adaptive filters, the combination of algorithms is receiving much attention in the literature. This method combines linearly the outputs of two filters operating in parallel with different step-sizes to obtain an adaptive filter with fast convergence and reduced excess mean squared error (EMSE). In this context, it was proposed an affine combination of two least-mean square (LMS) filters, whose mixing parameter is not restricted to the interval [0, 1]. Hence, the affine combination is a generalization of the convex combination. In this work, the affine combination of two LMS algorithms is extended to the supervised algorithms NLMS (normalized LMS) and RLS (recursive least squares), and also to blind equalization, using the constant modulus algorithm (CMA). A steady-state analysis of the affine combination of the considered algorithms is presented in a unified manner, assuming white or colored inputs, and stationary or nonstationary environments. Through the analysis, it was observed that the affine combination of two algorithms of the same family can provide a 3 dB EMSE gain in relation to its best component filter and consequently in relation to the convex combination. To ensure that the combined estimate is at least as good as the best of the component filters, three new algorithms to adapt the mixing parameter were proposed and analyzed. Using the analysis results of these algorithms in conjunction with the results of the transient analysis of adaptive filters, the transient behavior of the affine combination was analyzed. Through simulations, a good agreement between analytical and experimental results was always observed. In the blind equalization case, a combination of two CMA equalizers with different initializations was also proposed. The simulation results suggest that the affine combination can avoid local minima of the constant modulus cost function.

O planejamento probabilístico de mapa de rotas tem se mostrado uma poderosa ferramenta para o planejamento de caminhos para robôs móveis, devido a sua eficiência computacional, simplicidade de implementação e escalabilidade em diferentes problemas. Este método de planejamento possui duas fases. Na fase de construção, um mapa de rotas é gerado de forma iterativa e incremental, e armazenado na forma de um grafo G, cujos vértices são configurações livres, amostradas no espaço de configurações do robô e cujas arestas correspondem a caminhos livres de colisão entre tais configurações. Na fase de questionamento, dadas quaisquer configurações de origem e destino, \'alfa\' e \'beta\' respectivamente, o planejador conecta \'alfa\' e \'beta\' à G inserindo arestas que correspondem a caminhos livres de colisão, para então procurar por um caminho entre \'alfa\' e \'beta\' em G. Neste trabalho o foco reside principalmente na fase de construção do mapa de rotas. O objetivo aqui consiste em efetuar uma análise comparativa de diversas combinações de diferentes técnicas de amostragem das configurações livres e de diferentes técnicas de seleção de vértices em G, todas implementadas em um único sistema e aplicadas aos mesmos cenários. Os resultados propiciam um valioso auxílio aos usuários do planejamento probabilístico de mapas de rotas na decisão da melhor combinação para suas aplicações. / The probabilistic roadmap planning has emerged as a powerful framework for path planning of mobile robots due to its computational efficiency, implementation simplicity, and scalability in different problems. This planning method proceeds in two phases. In the construction phase a roadmap is incrementally constructed and stored as a graph G whose nodes are free configurations sampled on the robot\'s configuration space and whose edges correspond to collision-free paths between these configurations. In the query phase, given any start and goal configurations, \'alfa\' and \'beta\' respectively, the planner first connects \'alfa\' and \'beta\' to G by adding edges that correspond to collision-free paths, and then searches for a path in G between \'alfa\' and \'beta\'. In this work, we address mainly the roadmap construction phase. The goal here is to provide a comparative analysis of a number of combinations of different techniques for sampling free configurations and different node adding techniques, all implemented in a single system and applied to the same test workspace. Results help probabilistic roadmap planning users to choose the best combination for their applications.

Orientadores: Aurelio Ribeiro Leite de Oliveira, Fernando da Rocha Villas-Bôas, Clóvis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T03:16:18Z (GMT). No. of bitstreams: 1 Santos_LuizRafaeldos_D.pdf: 1892418 bytes, checksum: f636057b6014ba9f4fdbc0c69c99bdeb (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, propomos um método de pontos interiores do tipo preditor-corretor para programação linear em um contexto primal-dual, em que o próximo iterado será escolhido através de um subproblema de minimização de uma função de mérito polinomial a três variáveis: a primeira variável é o tamanho de passo, a segunda define a trajetória central e a última modela o peso que uma direção corretora deve ter. A minimização da função de mérito é feita sujeitando-a à restrições definidas por uma vizinhança da trajetória central que permite passos largos. Dessa maneira, combinamos diferentes direções, tais como preditora, corretora e de centralização com o objetivo de obter uma direção melhor. O método proposto generaliza grande parte dos métodos de pontos interiores preditores-corretores, a depender da escolha do valor das variáveis acima descritas. É feita, então uma análise de convergência do método proposto, considerando um ponto inicial que tem bom desempenho na prática, e que resulta em convergência linear dos iterados em complexidade polinomial. São feitos experimentos numéricos, utilizando o conjunto de testes Netlib, que mostram que essa abordagem é competitiva, quando comparada a implementações de pontos interiores bem estabelecidas como o PCx / Abstract: In this work we propose a predictor-corrector interior point method for linear programming in a primal-dual context, where the next iterate is chosen by the minimization of a polynomial merit function of three variables: the first one is the step length, the second one defines the central path and the last one models the weight that a corrector direction must have. The merit function minimization is performed by restricting it to constraints defined by a neighborhood of the central path that allows wide steps. In this framework, we combine different directions, such as the predictor, the corrector and the centering directions, with the aim of producing a better direction. The proposed method generalizes most of predictor-corrector interior point methods, depending on the choice of the variables described above. Convergence analysis of the method is carried out, considering an initial point that has a good practical performance, which results in Q-linear convergence of the iterates with polynomial complexity. Numerical experiments are made, using the Netlib test set, which show that this approach is competitive when compared to well established solvers, such as PCx / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-08-18T14:43:06Z No. of bitstreams: 1 Gilberto.pdf: 2769310 bytes, checksum: 210d2e0115f0c134b325cbf3a2354263 (MD5) / Made available in DSpace on 2017-08-18T14:43:06Z (GMT). No. of bitstreams: 1 Gilberto.pdf: 2769310 bytes, checksum: 210d2e0115f0c134b325cbf3a2354263 (MD5) Previous issue date: 2009-02-13 / CAPES / During the development of Grid middleware systems, researchers often employ simulation tools and techniques for validating new concepts and implementations. Simulation tools play a fundamental role on the development of Grid middleware systems since: (a) researchers often do not have access to huge Grid testbed environments, limiting the capacity for evaluating situations that demand high amount of resources; (b) it is difficult to explore in large scale application and resources scenarios involving several users in a repetitive and controlled way, due to the dynamic nature of Grid environments; (c) real Grid applications usually consume great amount of time, ranging from a few hours to even weeks. This work describes OGST, an object-oriented discrete event simulator whose main objective is to assist developers of opportunistic Grid middleware on validating new concepts and implementations. The preliminary motivation for OGST development was to provide a way for evaluating the behavior of scheduling algorithms commonly used on Grid environments under different execution environment conditions and the investigation of adaptive scheduling approaches. It was carefully designed to take into consideration the dynamics of opportunistic Grids, providing a set of features that hasten the development of simulations that takes into consideration the dynamism of the execution environment. The simulator was developed in the context of the InteGrade project, but was designed to allow the simulation of generic opportunistic Grids in order to be applied by other Grid middleware research projects. / Durante o desenvolvimento de sistemas de middleware de grade, pesquisadores freqüentemente empregam técnicas e ferramentas de simulação para valida- ção de novos conceitos e implementações. Ferramentas de simulação têm um papel fundamental no desenvolvimento de sistemas de middleware de grade uma vez que: (a) pesquisadores freqüentemente não têm acesso a grandes ambientes de grade para testes, limitando a capacidade para avaliar situações que demandam por uma grande quantidade de recursos; (b) é difícil explorar cenários com recursos e aplicações em larga escala envolvendo diversos usuários de forma repetitiva e controlada, devido à natureza dinâmica de ambientes de grade; (c) aplicações reais da grade geralmente consomem muito tempo, de poucas horas até mesmo a semanas. Este trabalho descreve o OGST, um simulador de eventos discretos orientado a objetos cujo principal objetivo é auxiliar desenvolvedores de sistemas de middleware de grade oportunista na validação de novos conceitos e implementações. A motivação preliminar para o desenvolvimento do OGST foi prover um caminho para avaliar o comportamento de algoritmos de escalonamento comumente usados em ambientes de grade sob diferentes condições do ambiente de execução e a investigação de abordagens de escalonamento adaptativo. Ele foi cuidadosamente projetado para levar em consideração a dinâmica de grades oportunistas, provendo um conjunto de funcionalidades que agilizam o desenvolvimento de simulações que consideram o dinamismo do ambiente de execução. O simulador foi desenvolvido no contexto do projeto InteGrade, mas foi projetado para permitir a simulação de grades oportunistas de uma maneira em geral com o propósito de ser aplicado a outros projetos de pesquisa envolvendo middleware de grades.

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-04-17T12:23:49Z No. of bitstreams: 1 Tiago Martins Ribeiro.pdf: 2146814 bytes, checksum: c04c7e63303157b4345d0985576e1620 (MD5) / Made available in DSpace on 2017-04-17T12:23:49Z (GMT). No. of bitstreams: 1 Tiago Martins Ribeiro.pdf: 2146814 bytes, checksum: c04c7e63303157b4345d0985576e1620 (MD5) Previous issue date: 2017-02-20 / CAPES / Complex optimization problems have been studied over the years by researchers seeking better solutions, these studies have encouraged the development of several algorithms of artificial intelligence, and a part of them are bio-inspired methods, based on the behavior of populations. These algorithms target to develop techniques based on nature in search of solutions to these problems. In this work, was introduced as a purpose, an algorithm based on the behavior of locust swarms, the Locust Swarm Optimizer (LSO). The behavior of the desert locust is introduced highlighting the formation of clouds of attacks caused by a synthesized neurotransmitter monoamine, present on the insect, known as serotonin. Observing this behavior, the LSO was developed. It was compared to other known artificial intelligence techniques through 23 benchmark functions and also tested on an power system economical dispatch problem. From the point of view of the results and the ease of implementation, it can be concluded that the LSO algorithm is very competitive as compared to existing methods / Problemas complexos de otimização vêm sendo estudados ao longo dos anos por pesquisadores que buscam melhores soluções, estes estudos incentivaram o desenvolvimento de vários algoritmos de inteligência artificial, sendo que uma parte deles são métodos bioinspirados, baseados no comportamento de populações. Estes algoritmos têm como objetivo desenvolver técnicas baseadas na natureza em busca de soluções para estes problemas. Neste trabalho um algoritmo baseado no comportamento de enxames de gafanhotos-do-deserto, o Locust Swarm Optimizer (LSO), foi introduzido como objetivo. O comportamento do gafanhoto-do-deserto é apresentado destacando a formação de nuvens de ataques causada por uma monoamina neurotransmissora sintetizada, presente no inseto, conhecido por serotonina. Observando este comportamento, foi desenvolvido o LSO. Ele foi comparado com outras conhecidas técnicas de inteligência artificial através de 23 funções benchmarks e também, testado em um problema de despacho econômico. Do ponto de vista dos resultados e da facilidade de implementação, pode-se concluir que o algoritmo LSO é bastante competitivo comparado aos métodos atuais existentes.

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-08-22T13:19:28Z No. of bitstreams: 1 Patricia Moraes Rêgo.pdf: 1511056 bytes, checksum: 21108136b08107eeb212f5d74ed79ef7 (MD5) / Made available in DSpace on 2017-08-22T13:19:28Z (GMT). No. of bitstreams: 1 Patricia Moraes Rêgo.pdf: 1511056 bytes, checksum: 21108136b08107eeb212f5d74ed79ef7 (MD5) Previous issue date: 2007-08-03 / FAPEMA / In this work are proposed models and a convergence analysis of a hierarchical genetic algorithm for the linear quadratic regulator design loop recovery through LQG/LTR controllers. Models are oriented to the weighting and covariance matrices searching of the performance indices of the LQR and LQG design, respectively, and to the selection of the matrices for the LQR design loop recovery gain. The convergence analysis aims at promoting the enhancement of the algorithm performance, as well as to generate satisfactory solutions and speed up the convergence time. The algorithm performance is evaluated with respect to the e ects of an elitist strategy embodied into the algorithm and to variations in the values of some given parameters of the algorithm. The proposed methodology is evaluated in a multi-variable dynamical system representing an aircraft. / Propõe-se neste trabalho os modelos e a análise de convergência de um algoritmo genético hierárquico para recuperação da malha de projeto do regulador linear quadrático por controladores LQG/LTR (Linear Quadratic Gaussian/Loop Transfer Recovery). Os modelos dedicam-se à busca das matrizes de ponderações e covariâncias dos índices de desempenho dos projetos de controladores LQR (Linear Quadratic Regulator) e LQG (Linear Quadratic Gaussian), respectivamente, e à seleção de matrizes de ajuste para o ganho de recuperação da malha do projeto LQR. O objetivo da análise de convergência é promover melhorias no desempenho do algoritmo no sentido de gerar soluções satisfatórias e acelerar o tempo de convergência. O desempenho do algoritmo é avaliado em relação aos efeitos de uma estratégia elitista incorporada ao algoritmo e à variações nos valores de determinados parâmetros do algoritmo. A metodologia proposta é avaliada em um sistema dinâmico multivariável que representa uma aeronave.

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.