Submitted by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-03-10T11:46:41Z No. of bitstreams: 2 Dissertacao Andresson Firmino.pdf: 3482085 bytes, checksum: 4f063b2a655d0cba829cf4f976a64c37 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-10T11:46:41Z (GMT). No. of bitstreams: 2 Dissertacao Andresson Firmino.pdf: 3482085 bytes, checksum: 4f063b2a655d0cba829cf4f976a64c37 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2013-05-24 / A materialização de visões promove a redução do tempo de execução de consultas multidimensionais. No entanto, a materialização de uma visão possui um custo associado que quando somado ao custo de materialização de outras visões pode exceder certos limiares de custo de armazenamento de um dado ambiente. Surge então o Problema de Seleção de Visões (PSV) que consiste em selecionar as melhores visões dado um certo limiar de custo. Diversas soluções na literatura foram propostas para tentar resolver este problema. O foco das soluções propostas para o PSV são a construção de algoritmos de otimização para seleção de visões e a especificação de custos para as visões e critérios para seleção. Todavia, de acordo com o nosso conhecimento, nenhuma das propostas na literatura considera todo o ciclo de um ambiente real de análise multidimensional, que consiste na execução de consultas, seleção de visões e materialização das visões. Então, esse trabalho especifica um método de seleção e materialização de visões por meio de Assinaturas OLAP e algoritmos de otimização baseados na meta-heurística GRASP, Reactive GRASP e GRASP com Path-Relinking, visando maximizar o desempenho das consultas OLAP.

Made available in DSpace on 2014-06-12T15:51:11Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Este trabalho apresenta a ferramenta EvolUniT (Evolutionary Unit Testing), uma ferramenta para automatização de testes de unidade de código orientado a objetos (classes Java). A EvolUniT recebe como entrada uma classe Java a ser testada; gera uma classe de teste usando o framework JUnit; gera dados (parâmetros de construtores e métodos) inicialmente aleatórios para compor os casos de teste; e utiliza um Algoritmo Genético (AG) para evoluir os dados, de acordo com uma função de aptidão criada com base nas coberturas de código capturadas. A evolução dos dados se dá através de sucessivas execuções da classe sendo testada, até que um número máximo de gerações do AG seja atingido ou que uma cobertura máxima pré-definida seja atingida. A ferramenta foi implementada em Java, em forma de plug-in do Eclipse. A ferramenta proporciona uma semi-automação de testes de unidade, ao invés de automação completa, pois em alguns casos, o engenheiro de software ou de testes precisará complementar manualmente as classes de teste geradas. A vantagem desta semiautomação é que o conhecimento do desenvolvedor ou testador será acrescido aos testes gerados pela ferramenta, possibilitando assim melhores resultados. Foram realizados três estudos para avaliar a EvolUniT, e os resultados alcançados foram satisfatórios. A EvolUniT traz contribuições para duas áreas diferentes. Para a Engenharia de Software, com a semi-automação do processo de testes de unidade, reduz-se significativamente o tempo e o esforço por parte dos desenvolvedores, já que estes passam a usar seus conhecimentos para configurar a ferramenta, ao invés de escrever as classes de teste. Para a área de Computação Inteligente, a contribuição é na utilização de uma técnica de otimização evolutiva, os Algoritmos Genéticos, para resolver o problema da escolha de bons dados para testes estruturais, que nem sempre é bem resolvido por algoritmos convencionais ou técnicas aleatórias

Made available in DSpace on 2014-06-12T15:56:18Z (GMT). No. of bitstreams: 2 arquivo2839_1.pdf: 6993291 bytes, checksum: 09ffd9fa6a055cf66ddb65d681cdf1c2 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / No âmbito das redes de computadores destaca-se o problema encontrado na criação, ampliação ou manutenção das redes de longa distância (Wide Area Network - WAN), onde muitas vezes os especialistas designados a essas tarefas não conseguem levar em consideração a combinação de algumas métricas de qualidade de serviço (quality of service - QoS). Isto se deve a complexidade dessas combinações juntamente com um número elevado de equipamentos existentes em redes dessa magnitude, logo, muitas redes WAN não são conectadas de forma ótima. O presente trabalho tem como objetivo combinar métricas de QoS (atraso de um enlace, largura de banda, tamanho do caminho e probabilidade de falha) para que seja possível encontrar soluções ótimas, utilizando algoritmos evolucionários multiobjetivo (AEMO), mas especificamente o algoritmo evolucionário de força de Pareto (Strength Pareto Evolutionary Algorithm - SPEA). O SPEA determina o Pareto ótimo para atendimento de cada demanda na rede. Além disto, foi realizado um estudo sobre a sinergia dos operadores de cruzamento (de um ponto com conhecimento heurístico, de ciclo, de ordenamento, de aresta e parcialmente mapeado) para problemas de permutação, como é o caso da otimização das redes de longa distância

Made available in DSpace on 2014-06-12T16:01:23Z (GMT). No. of bitstreams: 2 arquivo8461_1.pdf: 682988 bytes, checksum: d7fff8575726440e9671293cfc34d7f6 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Este trabalho investiga o impacto do uso de comitês de agrupamentos para a análise de dados de expressão gênica. Mais especificamente, é realizada uma comparação dos desempenhos obtidos com algoritmos de combinação (comitês) com aqueles dos algoritmos de agrupamento individuais (algoritmos base). Para isso, são utilizados três métodos de comitês de agrupamento mais estabelecidos na literatura: matriz de co-associação, re-rotulagem e votação e comitês baseados em particionamento de grafos. As técnicas de agrupamento individuais escolhidas para realizar a comparação são: k-médias, mistura finita de gaussianas e o algoritmo hierárquico. Além de representarem diferentes paradigmas de agrupamento, estes algoritmos estão sendo muito utilizados no contexto de expressão gênica. Os resultados obtidos indicam que os algoritmos de comitê conseguem recuperar melhor a estrutura real dos dados, quando comparados aos algoritmos individuais. Outro aspecto observado na análise desenvolvida é que os comitês homogêneos conseguem, em geral, um melhor desempenho do que os comitês heterogêneos. De forma geral, os resultados dos experimentos indicam que, tanto os algoritmos individuais, quanto as técnicas de comitê apresentaram pequenas diferenças entre o número de grupos gerados, para os melhores desempenhos, e o número real de classes existentes nos dados

Made available in DSpace on 2018-08-01T22:57:26Z (GMT). No. of bitstreams: 1 tese_10029_Dissertação Final Tiago de Souza Marçal.pdf: 1829947 bytes, checksum: 97df059fea5ce8331745b5840ac8d15c (MD5) Previous issue date: 2016-06-30 / O milho (Zea mays L.) é uma espécie da família Poaceae, diplóide e alógama. Para esta cultura verifica-se o aumento do vigor com o acúmulo de loci heterozigotos, justificando assim a produção dos híbridos. Com o advento das drásticas previsões de mudanças climáticas e aumento populacional para os próximos anos é necessária à adoção, desenvolvimento e aprimoração de métodos que permitam maior eficiência na seleção e alcance de maior progresso genético em programas de melhoramento de culturas de importância agrícola poderão auxiliar na mitigação dos desafios para sustentar a segurança alimentar ainda neste século. Diante do exposto, este trabalho teve por objetivo implementar os algoritmos de primeira e segunda derivadas para o método REML (máxima verossimilhança restrita) em R, generalizáveis para diferentes modelos lineares mistos e capazes de incorporar matrizes de parentesco. Além de avaliar o impacto de simplificações matemáticas, matrizes esparsas, e diferentes taxas de erro de convergência na eficiência computacional destes algoritmos, visando a minimização do custo computacional para viabilizar o REML, em estudos com grande número de híbridos de milho e modelos complexos, em computadores de configuração simples. Os dados experimentais utilizados neste trabalho foram obtidos na safra 2013/14 em ensaio conduzido no delineamento de blocos aumentados com cinco testemunhas e 3352 híbridos simples de milho na Embrapa (Empresa Brasileira de Pesquisa Agropecuária) Milho e Sorgo situada em Sete Lagoas - MG. A variável analisada foi o rendimento de grãos, sendo esta submetida a análise através de modelos mistos com e sem a incorporação do pedigree utilizando-se diferentes algoritmos REML, em R, e a resposta computacional foi avaliada quanto aos critérios de convergência, taxas de erro de convergência, matrizes esparsas, computadores com diferentes capacidades de processamento, diferentes estimativas iniciais dos componentes de variância e número crescente de passos EM (Expectation Maximization) nos algoritmos combinados. Os algoritmos propostos foram equivalentes aos softwares testados (ASReml, Selegen e lme4) quanto as estimativas dos componentes de variância, indicando a coerência dos mesmos. Além disso, o uso de matrizes esparsas em associação com as otimizações propostas diminuíram o custo computacional dos algoritmos utilizando os coeficientes de determinação como critério de convergência e taxa de erro de convergência igual a 10-5. A combinação híbrida do algoritmo EM, em dez passos, com o NR (Newton Raphson) reduziu o custo computacional e aumentou o percentual de convergência médio. Ainda observou-se que pesos uniformes para as estimativas iniciais dos componentes de variância devem ser evitados.

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-16T09:31:55Z (GMT). No. of bitstreams: 1 Oliveira_IgorCarboni_M.pdf: 1109272 bytes, checksum: 3ab44664e4e0b862409cc8038c431a06 (MD5) Previous issue date: 2010 / Resumo: A teoria de complexidade computacional procura estabelecer limites para a eficiência dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema P vs NP é uma questão central em complexidade computacional. Informalmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por soluções é essencialmente a melhor alternativa algorítmica possível. Esta dissertação oferece tanto uma introdução clássica ao tema, quanto uma exposição a diversos teoremas mais avançados, resultados recentes e problemas em aberto. Em particular, o método da diagonalização é discutido em profundidade. Os principais resultados obtidos por diagonalização são os teoremas de hierarquia de tempo e de espaço (Hartmanis e Stearns [54, 104]). Apresentamos uma generalização desses resultados, obtendo como corolários os teoremas clássicos provados por Hartmanis e Stearns. Essa é a primeira vez que uma prova unificada desses resultados aparece na literatura / Abstract: Computational complexity theory is the field of theoretical computer science that aims to establish limits on the efficiency of algorithms. The main open question in computational complexity is the P vs NP problem. Intuitively, it states that, for several important computational problems, there is no algorithm that performs better than a trivial exhaustive search. We present here an introduction to the subject, followed by more recent and advanced results. In particular, the diagonalization method is discussed in detail. Although it is a classical technique in computational complexity, it is the only method that was able to separate strong complexity classes so far. Some of the most important results in computational complexity theory have been proven by diagonalization. In particular, Hartmanis and Stearns [54, 104] proved that, given more resources, one can solve more computational problems. These results are known as hierarchy theorems. We present a generalization of the deterministic hierarchy theorems, recovering the classical results proved by Hartmanis and Stearns as corollaries. This is the first time that such unified treatment is presented in the literature / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientadores: Eduardo Candido Xavier, Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T03:33:12Z (GMT). No. of bitstreams: 1 Silveira_JeffersonLuizMoisesda_M.pdf: 1516196 bytes, checksum: b3f9127c1017ef29bf9c429bb93e1a0c (MD5) Previous issue date: 2011 / Resumo: Neste trabalho estudamos problemas de empacotamento com restrições de descarregamento considerados NP-difíceis. Estes problemas possuem aplicações nas áreas de logística e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes (complexidade de tempo polinomial) e que geram soluções com garantia de qualidade. Estudamos técnicas para o desenvolvimento de algoritmos aproximados e também alguns algoritmos para problemas de empacotamento online que podem ser utilizados na resolução do problema estudado. Propomos também algumas heurísticas para o problema e, além disto, provamos que duas destas heurísticas possuem garantias de aproximação com fatores constantes. Realizamos testes computacionais com estes algoritmos propostos. Dentre estes, a heurística GRASP foi a que obteve melhores resultados para as instâncias de teste consideradas / Abstract: In this work we study some NP-hard packing problems with unloading constraints. These problems have applications in logistics and routing problems. Assuming P ? NP, there are no efficient algorithms to solve these problems. On way to deal with these problems is using approximation algorithms, that are efficient algorithms (polynomial time complexity) that produce solutions with quality guarantee. We study techniques used in the development of approximation algorithms and some algorithms for online packing problems which can be used to solve the considered problem. We propose some heuristics for the problem and prove that two of them have constant approximation guarantees. We also perform computational tests with the proposed algorithms. Among them, the GRASP heuristic achieved the best results on the considered instances / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Carlile Campos Lavor / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T10:25:36Z (GMT). No. of bitstreams: 1 Fidalgo_FelipeDelfiniCaetano_M.pdf: 1387888 bytes, checksum: 10eea772ac455d900f31182f86cad9d0 (MD5) Previous issue date: 2011 / Resumo: Neste trabalho, analisamos dois algoritmos da literatura para o "Molecular Distance Geometry Problem" (MDGP) e propomos um novo algoritmo que mantém a qualidade das soluções obtidas pelos dois anteriores e apresenta ganhos em termos de eficiência computacional. O MDGP consiste em determinar as posições dos átomos de uma molécula, no espaço tridimensional, a partir de um conjunto de distâncias entre eles. Quando todas as distâncias são conhecidas, o problema pode ser resolvido em tempo polinomial. Caso contrário, é um problema NP-difícil / Abstract: In this work, we analyse two algorithms from the bibliography to solve the so-called "Molecular Distance Geometry Problem" (MDGP). Then, we propose a new algorithm that keeps the quality on the solutions obtained by both the previous ones and shows gains regarding computacional efficiency. The MDGP consists on the determination of positions of atoms in a molecule, on the tridimensional space, from a set containing distances among them. When all the distances are known, the problem might be solved in polynomial time. Otherwise, it is an NP-hard problem / Mestrado / Matemática da Computação / Mestre em Matemática Aplicada

Orientador: Jose C. Geromel / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-21T04:03:45Z (GMT). No. of bitstreams: 1 Oliveira_MauricioCarvalhode_M.pdf: 6359919 bytes, checksum: 960400e58c19c10ffb1d99e0fee0a904 (MD5) Previous issue date: 1996 / Resumo: Esta dissertação é dedicada ao estudo dos mecanismos dos algoritmos de pontos interiores aplicados à resolução de problemas lineares sujeitos a restrições dadas na forma de desigualdades matriciais lineares. Abordam-se tanto aspectos teóricos quanto práticos. De aspecto teórico, encontram-se presentes análises de convergência e complexidade para diversos algoritmos seguidores de trajetória, primais-duais e projetivos, aliados às análises de alguns procedimentos críticos, como a resolução dos problemas de mínimos quadrados e a determinação do passo ótimo, aspectos eminentemente práticos. A título de ilustração, apresenta-se uma série de exemplos de problemas comumente encontrados em programação matemática e, em especial, problemas da área de controle ótimo formulados como LMI / Abstract: The subject of this thesis is the study of the interior point machinery applied to linear problems constrained by linear matrix inequa.lities (LMI). Both theoretical and practical issues are addressed. Of theoretical fiavor, convergence and complexity of several path following, primal-dual and projective algorithms are analyzed; the analysis of some critical procedures, as solving mean-square problems and calculating the optimal step length, stand for the practica.l issues. For the sake of illustration, many mathematical programs and problems from optimal control theory are formulated as LMI / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Orientador: João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da ComputaçãO / Made available in DSpace on 2018-07-21T05:57:00Z (GMT). No. of bitstreams: 1 Cruz_CarlosFernandoBella_M.pdf: 2090300 bytes, checksum: c7ddb8099b731928143e26f66c270afc (MD5) Previous issue date: 1996 / Resumo: Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com partilhada. A implementação consiste em permitir que cada processador procure caminhos aumentantes no grafo de forma assíncrona e independente dos demais. Embora a busca ocorra de forma paralela, o aumento do emparelhamento é feito por somente 1 processador por vez, o que garante a corretude do algoritmo sem incorrrer em atraso significativo no tempo de execução. O desenvolvimento da implementação teve como antecedente uma experiência negativa de paralelização baseada no algoritmo de Micali e Vazirani. / Abstract: In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows each processor to find augmenting paths assinchronously and independently of each other. Each matching augmentation is done by only one processor, and this makes the algorithm correct without causing significant delay in the execution time, in practice. The development of this implementation was made after a nega tive experience of paralelization based on the sequential algorithm of Micali and Vazirani. / Mestrado / Mestre em Ciência da Computação