Tesis: "Algoritmos"

1

Aguiar, Marilton Sanchotene de. "Análise formal da complexidade de algoritmos genéticos." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 1998. http://hdl.handle.net/10183/25941.

Texto completo

Resumen

O objetivo do trabalho é estudar a viabilidade de tratar problemas de otimização, considerados intratáveis, através de Algoritmos Genéticos, desenvolvendo critérios para a avaliação qualitativa de um Algoritmo Genético. Dentro deste tema, abordam-se estudos sobre complexidade, classes de problemas, análise e desenvolvimento de algoritmos e Algoritmos Genéticos, este ultimo sendo objeto central do estudo. Como produto do estudo deste tema, é proposto um método de desenvolvimento de Algoritmos Genéticos, utilizando todo o estudo formal de tipos de problemas, desenvolvimento de algoritmos aproximativos e análise da complexidade. O fato de um problema ser teoricamente resolvível por um computador não é suficiente para o problema ser na prática resolvível. Um problema é denominado tratável se no pior caso possui um algoritmo razoavelmente eficiente. E um algoritmo é dito razoavelmente eficiente quando existe um polinômio p tal que para qualquer entrada de tamanho n o algoritmo termina com no máximo p(n) passos [SZW 84]. Já que um polinômio pode ser de ordem bem alta, então um algoritmo de complexidade polinomial pode ser muito ineficiente. Genéticos é que se pode encontrar soluções aproximadas de problemas de grande complexidade computacional mediante um processo de evolução simulada[LAG 96]. Como produto do estudo deste tema, é proposto um método de desenvolvimento de Algoritmos Genéticos com a consciência de qualidade, utilizando todo o estudo formal de tipos de problemas, desenvolvimento de algoritmos aproximativos e análise da complexidade. Uma axiomatização tem o propósito de dar a semântica do algoritmo, ou seja, ela define, formalmente, o funcionamento do algoritmo, mais especificamente das funções e procedimentos do algoritmo. E isto, possibilita ao projetista de algoritmos uma maior segurança no desenvolvimento, porque para provar a correção de um Algoritmo Genético que satisfaça esse modelo só é necessário provar que os procedimentos satisfazem os axiomas. Para ter-se consciência da qualidade de um algoritmo aproximativo, dois fatores são relevantes: a exatidão e a complexidade. Este trabalho levanta os pontos importantes para o estudo da complexidade de um Algoritmo Genético. Infelizmente, são fatores conflitantes, pois quanto maior a exatidão, pior ( mais alta) é a complexidade, e vice-versa. Assim, um estudo da qualidade de um Algoritmo Genético, considerado um algoritmo aproximativo, só estaria completa com a consideração destes dois fatores. Mas, este trabalho proporciona um grande passo em direção do estudo da viabilidade do tratamento de problemas de otimização via Algoritmos Genéticos. The objective of the work is to study the viability of treating optimization problems, considered intractable, through Genetic Algorithms, developing approaches for the qualitative evaluation of a Genetic Algorithm. Inside this theme, approached areas: complexity, classes of problems, analysis and development of algorithms and Genetic Algorithms, this last one being central object of the study. As product of the study of this theme, a development method of Genetic Algorithms is proposed, using the whole formal study of types of problems, development of approximate algorithms and complexity analysis. The fact that a problem theoretically solvable isn’t enough to mean that it is solvable in pratice. A problem is denominated easy if in the worst case it possesses an algorithm reasonably efficient. And an algorithm is said reasonably efficient when a polynomial p exists such that for any entrance size n the algorithm terminates at maximum of p(n) steps [SZW 84]. Since a polynomial can be of very high order, then an algorithm of polynomial complexity can be very inefficient. The premise of the Genetic Algorithms is that one can find approximate solutions of problems of great computational complexity by means of a process of simulated evolution [LAG 96]. As product of the study of this theme, a method of development of Genetic Algorithms with the quality conscience is proposed, using the whole formal study of types of problems, development of approximate algorithms and complexity analysis. The axiom set has the purpose of giving the semantics of the algorithm, in other words, it defines formally the operation of the algorithm, more specifically of the functions and procedures of the algorithm. And this, facilitates the planner of algorithms a larger safety in the development, because in order to prove the correction of a Genetic Algorithm that satisfies that model it is only necessary to prove that the procedures satisfy the axioms. To have conscience of the quality of an approximate algorithm, two factors are important: the accuracy and the complexity. This work lifts the important points for the study of the complexity of a Genetic Algorithm. Unhappily, they are conflicting factors, because as larger the accuracy, worse (higher) it is the complexity, and vice-versa. Thus, a study of the quality of a Genetic Algorithm, considered an approximate algorithm, would be only complete with the consideration of these two factors. But, this work provides a great step in direction of the study of the viability of the treatment of optimization problems through Genetic Algorithms.

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

Candido, Renato. "Combinação afim de algoritmos adaptativos." Universidade de São Paulo, 2009. http://www.teses.usp.br/teses/disponiveis/3/3142/tde-29062009-113546/.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

Fidalgo, Felipe Delfini Caetano 1987. "Algoritmos para problemas de geometria molecular." [s.n.], 2011. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306803.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

Muñoz, Jugo Cynthia Mariela. "Algoritmos Greedy." Universidad Peruana de Ciencias Aplicadas - UPC, 2007. http://hdl.handle.net/10757/272784.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

Mole, Vilson Luiz Dalle. "Algoritmos genéticos." Florianópolis, SC, 2002. http://repositorio.ufsc.br/xmlui/handle/123456789/83304.

Texto completo

Resumen

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. Made available in DSpace on 2012-10-19T22:42:58Z (GMT). No. of bitstreams: 1 188790.pdf: 950320 bytes, checksum: 1bd92621c53fa691f3e779d757acccd2 (MD5) O trabalho desenvolvido consta da proposição, teste e análise de resultados, de uma estrutura de paralelização para algoritmos genéticos. A estrutura proposta está baseada em um conjunto de populações cooperantes que evoluem em paralelo, onde a troca de material genético, entre as populações, se processa através de indivíduos migrantes. A estrutura para implementação baseia-se na tecnologia de orientação a objetos, sendo que a mesma pressupõem a exploração do paralelismo de máquina através das redes de computador, bem como a exploração do paralelismo local - máquinas multiprocessadas - pela utilização de threads. O trabalho descreve os resultados obtidos com um protótipo construído para simular toda a estrutura proposta. Neste, o paralelismo de máquina foi simulado através de programação concorrente, com a utilização de threads. Os resultados obtidos demonstram a viabilidade da proposta e indicam a necessidade de novas pesquisas buscando testar a estrutura em modo real, sobre um ambiente distribuído.

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

Crocomo, Márcio Kassouf. "Algoritmo de otimização bayesiano com detecção de comunidades." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-23012013-160605/.

Texto completo

Resumen

ALGORITMOS de Estimação de Distribuição (EDAs) compõem uma frente de pesquisa em Computação Evolutiva que tem apresentado resultados promissores para lidar com problemas complexos de larga escala. Nesse contexto, destaca-se o Algoritmo de Otimização Bayesiano (BOA) que usa um modelo probabilístico multivariado (representado por uma rede Bayesiana) para gerar novas soluções a cada iteração. Baseado no BOA e na investigação de algoritmos de detecção de estrutura de comunidades (para melhorar os modelos multivariados construídos), propõe-se dois novos algoritmos denominados CD-BOA e StrOp. Mostra-se que ambos apresentam vantagens significativas em relação ao BOA. O CD-BOA mostra-se mais flexível que o BOA, ao apresentar uma maior robustez a variações dos valores de parâmetros de entrada, facilitando o tratamento de uma maior diversidade de problemas do mundo real. Diferentemente do CD-BOA e BOA, o StrOp mostra que a detecção de comunidades a partir de uma rede Bayesiana pode modelar mais adequadamente problemas decomponíveis, reestruturando-os em subproblemas mais simples, que podem ser resolvidos por uma busca gulosa, resultando em uma solução para o problema original que pode ser ótima no caso de problemas perfeitamente decomponíveis, ou uma aproximação, caso contrário. Também é proposta uma nova técnica de reamostragens para EDAs (denominada REDA). Essa técnica possibilita a obtenção de modelos probabilísticos mais representativos, aumentando significativamente o desempenho do CD-BOA e StrOp. De uma forma geral, é demonstrado que, para os casos testados, CD-BOA e StrOp necessitam de um menor tempo de execução do que o BOA. Tal comprovação é feita tanto experimentalmente quanto por análise das complexidades dos algoritmos. As características principais desses algoritmos são avaliadas para a resolução de diferentes problemas, mapeando assim suas contribuições para a área de Computação Evolutiva ESTIMATION of Distribution Algorithms represent a research area which is showing promising results, especially in dealing with complex large scale problems. In this context, the Bayesian Optimization Algorithm (BOA) uses a multivariate model (represented by a Bayesian network) to find new solutions at each iteration. Based on BOA and in the study of community detection algorithms (to improve the constructed multivariate models), two new algorithms are proposed, named CD-BOA and StrOp. This paper indicates that both algorithms have significant advantages when compared to BOA. The CD-BOA is shown to be more flexible, being more robust when using different input parameters, what makes it easier to deal with a greater diversity of real-world problems. Unlike CD-BOA and BOA, StrOp shows that the detection of communities on a Bayesian network more adequately models decomposable problems, resulting in simpler subproblems that can be solved by a greedy search, resulting in a solution to the original problem which may be optimal in the case of perfectly decomposable problems, or a fair approximation if not. Another proposal is a new resampling technique for EDAs (called REDA). This technique results in multivariate models that are more representative, significantly improving the performance of CD-BOA and StrOp. In general, it is shown that, for the scenarios tested, CD-BOA and StrOp require lower running time than BOA. This indication is done experimentally and by the analysis of the computational complexity of the algorithms. The main features of these algorithms are evaluated for solving various problems, thus identifying their contributions to the field of Evolutionary Computation

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

Naldi, Murilo Coelho. "Agrupamento híbrido de dados utilizando algoritmos genéticos." Universidade de São Paulo, 2006. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-07112006-080351/.

Texto completo

Resumen

Técnicas de Agrupamento vêm obtendo bons resultados quando utilizados em diversos problemas de análise de dados, como, por exemplo, a análise de dados de expressão gênica. Porém, uma mesma técnica de agrupamento utilizada em um mesmo conjunto de dados pode resultar em diferentes formas de agrupar esses dados, devido aos possíveis agrupamentos iniciais ou à utilização de diferentes valores para seus parâmetros livres. Assim, a obtenção de um bom agrupamento pode ser visto como um processo de otimização. Esse processo procura escolher bons agrupamentos iniciais e encontrar o melhor conjunto de valores para os parâmetros livres. Por serem métodos de busca global, Algoritmos Genéticos podem ser utilizados durante esse processo de otimização. O objetivo desse projeto de pesquisa é investigar a utilização de Técnicas de Agrupamento em conjunto com Algoritmos Genéticos para aprimorar a qualidade dos grupos encontrados por algoritmos de agrupamento, principalmente o k-médias. Esta investigação será realizada utilizando como aplicação a análise de dados de expressão gênica. Essa dissertação de mestrado apresenta uma revisão bibliográfica sobre os temas abordados no projeto, a descrição da metodologia utilizada, seu desenvolvimento e uma análise dos resultados obtidos. Clustering techniques have been obtaining good results when used in several data analysis problems, like, for example, gene expression data analysis. However, the same clustering technique used for the same data set can result in different ways of clustering the data, due to the possible initial clustering or the use of different values for the free parameters. Thus, the obtainment of a good clustering can be seen as an optimization process. This process tries to obtain good clustering by selecting the best values for the free parameters. For being global search methods, Genetic Algorithms have been successfully used during the optimization process. The goal of this research project is to investigate the use of clustering techniques together with Genetic Algorithms to improve the quality of the clusters found by clustering algorithms, mainly the k-means. This investigation was carried out using as application the analysis of gene expression data, a Bioinformatics problem. This dissertation presents a bibliographic review of the issues covered in the project, the description of the methodology followed, its development and an analysis of the results obtained.

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

Naves, Humberto Silva. "Algoritmos em combinatória." Instituto Tecnológico de Aeronáutica, 2009. http://www.bd.bibl.ita.br/tde_busca/arquivo.php?codArquivo=818.

Texto completo

Resumen

Esta tese de mestrado se propõe a resolver alguns problemas interessantes na área de Computação e Matemática, utilizando técnicas de Análise Combinatória, Teoria dos Grafos, Funções Geratrizes, Programação Dinâmica e Álgebra Linear. No decorrer da tese são abordados 3 problemas cujas soluções apresentam enfoque original, sob o ponto de vista da Teoria da Computação. O primeiro problema é o problema de Ulam (no capítulo referente a este problema, um novo algoritmo heurístico que interpreta o papel de um dos jogadores é apresentado). O segundo problema trata da contagem do número de matrizes de sinais alternantes e o último problema trata da contagem do número recobrimentos por dominós de uma dada figura plana (ou pareamentos perfeitos em grafos bipartidos).

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

Felipe, Denis. "Algoritmos cient?ficos." Universidade Federal do Rio Grande do Norte, 2014. http://repositorio.ufrn.br:8080/jspui/handle/123456789/18105.

Texto completo

Resumen

Made available in DSpace on 2014-12-17T15:48:10Z (GMT). No. of bitstreams: 1 DenisF_DISSERT.pdf: 776997 bytes, checksum: c0d801fdcf21ff4f335f115d3918ed93 (MD5) Previous issue date: 2014-02-14 The Scientific Algorithms are a new metaheuristics inspired in the scientific research process. The new method introduces the idea of theme to search the solution space of hard problems. The inspiration for this class of algorithms comes from the act of researching that comprises thinking, knowledge sharing and disclosing new ideas. The ideas of the new method are illustrated in the Traveling Salesman Problem. A computational experiment applies the proposed approach to a new variant of the Traveling Salesman Problem named Car Renter Salesman Problem. The results are compared to state-of-the-art algorithms for the latter problem Os algoritmos cient?ficos s?o uma nova metaheur?stica inspirada no processo da pesquisa cient?fica. O novo m?todo introduz a ideia de tema para buscar o espa?o de solu??es de problemas dif?ceis. A inspira??o para esta classe de algoritmos vem do ato de pesquisar, que compreende pensar, compartilhar conhecimento e descobrir novas ideias. As ideias do novo m?todo s?o ilustradas no Problema do Caixeiro Viajante. Um experimento computacional aplica a abordagem proposta a uma nova variante do Problema do Caixeiro Viajante intitulada Problema do Caixeiro Alugador. Os resultados s?o comparados aos algoritmos do estado da arte para o ?ltimo problema

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

Pessini, Evandro Carlos. "Algoritmos genéticos paralelos." Florianópolis, SC, 2003. http://repositorio.ufsc.br/xmlui/handle/123456789/85977.

Texto completo

Resumen

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. Made available in DSpace on 2012-10-21T01:58:16Z (GMT). No. of bitstreams: 1 238259.pdf: 345738 bytes, checksum: 8fd451584294d161e5c8caafa1ab78d8 (MD5) Os algoritmos genéticos têm deficiências conhecidas, principalmente no que diz respeito ao alto custo computacional e a baixa qualidade das soluções devido a convergência prematura. Um algoritmo genético clássico executado em um espaço de endereçamento simples tende a alcançar um ponto de equilíbrio onde os descendentes são muito semelhantes aos seus pais. Esta diversidade limitada induz o algoritmo genético a explorar somente uma região restrita do espaço de soluções, resultando em soluções subótimas. Uma tentativa de evitar este problema é criar um ambiente onde diversas populações independentes evoluem em paralelo e, periodicamente, efetuam a troca (migração) de indivíduos objetivando evitar a convergência prematura e manter a diversidade da população. Esta pesquisa apresenta a implementação de um algoritmo genético paralelo assíncrono de granularidade grossa (coarse grain) que usa a tecnologia JavaSpaces como mecanismo de distribuição das populações e dos indivíduos migrantes. A tecnologia JavaSpaces foi usada como repositório de objetos para a efetivação da comunicação entre as diversas máquinas do ambiente distribuído. Para avaliar a funcionalidade e o desempenho do algoritmo, aplicou-se o mesmo na obtenção de soluções para o Problema do Caixeiro Viajante (PCV) com o uso de soluções conhecidas disponíveis na Internet.

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

Silva, Isaac Dayan Bastos da. "An?lise e compara??o entre algoritmos de percola??o." Universidade Federal do Rio Grande do Norte, 2008. http://repositorio.ufrn.br:8080/jspui/handle/123456789/17000.

Texto completo

Resumen

Made available in DSpace on 2014-12-17T15:26:35Z (GMT). No. of bitstreams: 1 IsaacDBS.pdf: 539336 bytes, checksum: ac9f1f2543159f0c009f0242077b1d5c (MD5) Previous issue date: 2008-07-25 In this work, we study and compare two percolation algorithms, one of then elaborated by Elias, and the other one by Newman and Ziff, using theorical tools of algorithms complexity and another algorithm that makes an experimental comparation. This work is divided in three chapters. The ﬁrst one approaches some necessary deﬁnitions and theorems to a more formal mathematical study of percolation. The second presents technics that were used for the estimative calculation of the algorithms complexity, are they: worse case, better case e average case. We use the technique of the worse case to estimate the complexity of both algorithms and thus we can compare them. The last chapter shows several characteristics of each one of the algorithms and through the theoretical estimate of the complexity and the comparison between the execution time of the most important part of each one, we can compare these important algorithms that simulate the percolation. Nesta disserta??o estudamos e comparamos dois algoritmos de percola??o, um elaborado por Elias e o outro por Newman e Ziff, utilizando ferramentas te?ricas da complexidade de algoritmos e um algoritmo que efetuou uma compara??o experimental. Dividimos este trabalho em tr?s cap?tulos. O primeiro aborda algumas deﬁni??es e teoremas necess?rios a um estudo matem?tico mais formal da percola??o. O segundo apresenta t?cnicas utilizadas para o c?lculo estimativo de complexidade de algoritmos, sejam elas: pior caso, melhor caso e caso m?dio. Utilizamos a t?cnica do pior caso para estimar a complexidade de ambos algoritmos e assim podermos compar?-los. O ?ltimo cap?tulo mostra diversas caracter?sticas de cada um dos algoritmos e atrav?s da estima- tiva te?rica da complexidade e da compara??o entre os tempos de execu??o da parte mais importante de cada um, conseguimos comparar esses importantes algoritmos que simulam a percola??o

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

Xavier, Eduardo Candido 1979. "Algoritmos para problemas de empacotamento." [s.n.], 2006. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275871.

Texto completo

Resumen

Orientador: Flavio Keidi Miyazawa Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Made available in DSpace on 2018-08-07T21:41:01Z (GMT). No. of bitstreams: 1 Xavier_EduardoCandido_D.pdf: 20666026 bytes, checksum: 5e051653d938a813e227b1e2eebcd415 (MD5) Previous issue date: 2006 Resumo: Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes e que geram soluções com garantia de qualidade. Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade. Abstract: In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and produce solutions of very good quality. Doutorado Doutor em Ciência da Computação

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

Ogata, Adriano Kiyoshi Oliveira. "Multialinhamento de seqüências biológicas utilizando algoritmos genéticos." Universidade de São Paulo, 2006. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-09052007-100823/.

Texto completo

Resumen

Dentro da bioinformática uma das atividades mais realizadas é o alinhamento de seqüências biológicas [1]. Seus resultados são utilizados em várias atividades que desdobram-se em áreas de pesquisa interdisciplinares com geração de diversos subprodutos. Sendo uma das primeiras etapas de tais tarefas, o multialinhamento é então importante para garantir a qualidade dos resultados obtidos em vários estudos do material genético. Para este trabalho espera-se a reprodução dos resultados já publicados na área [2]; [3]; [4]; [5]; [6]). A implementação de um programa de multialinhamento global de seqüências biológicas utilizando uma abordagem iterativa estocástica por algoritmo genético, uma forma relativamente recente [7] de se atacar tal problema. Obtenção de um panorama sobre as soluções alternativas existentes Multialignment of biological sequences is one of the most frequently used activities in bioinformatics. The results provided by sequence alignment are used in the solution of other bioinformatics problems. Since a multialignment procedure is one of the first steps of many bioinformatics problems, the condition of an alignment affects the quality of the results obtained for these problems. Multialignment of biological sequences is a complex problem (NP complete) and requires usually heuristics to obtain acceptable performance. Evolutionary algorithms have been used with relevant results. This work aims to find better solutions for the multialignment problem using evolutionary computation. In order to achieve that, this research investigates techniques using evolutionary computation applied to multialignment problem and searches to reproduce their results. Moreover, the development of an approach that performs global multialignment of biological sequences using evolutionary algorithms and an evaluation of the available multialignment techniques are also proposed

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

Silva, Jair da. "Uma familia de algoritmos para programação linear baseada no algoritmo de Von Neumann." [s.n.], 2009. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306741.

Texto completo

Resumen

Orientador: Aurelio R. Leite Oliveira, Marta Ines Velazco Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica Made available in DSpace on 2018-08-13T08:57:24Z (GMT). No. of bitstreams: 1 Silva_Jairda1_D.pdf: 1755258 bytes, checksum: 2ecb493aab3646838f54c2df2012b5d9 (MD5) Previous issue date: 2009 Resumo: Neste trabalho apresentamos uma nova família de algoritmos para resolver problemas de programação linear. A vantagem desta família de algoritmos é a sua simplicidade, a possibilidade de explorar a esparsidade dos dados do problema original e geralmente possuir raio de convergência inicial rápido. Esta família de algoritmos surgiu da generalização da idéia apresentada por João Gonçalves, Robert Storer e Jacek Gondzio, para desenvolver o algoritmo de ajustamento pelo par ótimo. Este algoritmo foi desenvolvido por sua vez tendo como base o algoritmo de Von Neumann. O algoritmo de Von Neumann possui propriedades interessantes, como simplicidade e convergência inicial rápida, porém, ele não é muito prático para resolver problemas lineares, visto que sua convergência é muito lenta. Do ponto de vista computacional, nossa proposta não é utilizar a família de algoritmos para resolver os problemas de programação linear até encontrar uma solução e sim explorar a sua simplicidade e seu raio de convergência inicial geralmente rápido e usá-la em conjunto com um método primal-dual de pontos interiores infactível, para melhorar a eficiência deste. Experimentos numéricos revelam que ao usar esta família de algoritmos em conjunto com um método primal-dual de pontos interiores infactível melhoramos o seu desempenho na solução de algumas classes de problemas de programação linear de grande porte. Abstract: In this work, we present a new family of algorithms to solve linear programming problems. The advantage of this family of algorithms relies in its simplicity, the possibility of exploiting the sparsity of the original problem data and usually to have fast initial ratio of convergence. This family of algorithms arose from the generalization of the idea presented by João Gonçalves, Robert Storer and Jacek Gondzio to develop the optimal pair adjustment algorithm. This algorithm was developed in its own turn based on the Von Neumann's algorithm. It has interesting properties, such as simplicity and fast initial convergence, but it is not very practical for solving linear problems, since its convergence is very slow. From the computational point of view, our suggestion is not to use the family of algorithms to solve problems of linear programming until optimality, but to exploit its simplicity and its fast initial ratio of convergence and use it together with a infeasible primal-dual interior point method to improve its efficiency. Numerical experiments show that using this family of algorithms with an infeasible primal-dual interior point method improves its performance in the solution of some classes of large-scale linear programming problems. Doutorado Doutor em Matemática Aplicada

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

Korbes, André. "Análise de algoritmos da Transformada Watershed." [s.n.], 2010. http://repositorio.unicamp.br/jspui/handle/REPOSIP/259826.

Texto completo

Resumen

Orientador: Roberto de Alencar Lotufo Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Made available in DSpace on 2018-08-15T23:43:15Z (GMT). No. of bitstreams: 1 Korbes_Andre_M.pdf: 12082047 bytes, checksum: 8ff8c998c80a0436fe3a83560ac2e6eb (MD5) Previous issue date: 2010 Resumo: A transformada watershed é uma técnica morfológica de segmentação de imagens inspirada na divisão de superfícies em bacias hidrográficas, tendo diversas formas de definição e de algoritmos. Este trabalho realiza uma análise sistemática da literatura de catorze destes algoritmos. Foram consideradas as principais abordagens existentes desde a introdução do primeiro algoritmo rápido por Vincent e Soille em 1991, até os trabalhos de Cousty et al. em 2009. Para melhor compreensão da área, as definições de transformada watershed são revisitadas, provendo o conjunto de soluções formais possíveis e esperadas dos algoritmos. Na análise destes algoritmos é fornecido pseudocódigo com notação uniformizada e uma implementação operacional Python permitindo abstrair detalhes de programação. Além disto, três algoritmos foram corrigidos para melhor aderência a definição e especificação. Também são identificadas propriedades tais como o comportamento de varredura dos pixels, uso de estratégias em particular, uso de estruturas de dados, entre outras. A compilação das informações sobre os algoritmos permitiu generalizá-los e classificá-los baseado em paradigmas clássicos da computação, a saber a busca em largura e em profundidade. Ambos são embasados na ordem de visitação dos pixels utilizada, sendo a busca em largura semelhante a simulação de inundação enquanto a busca em profundidade simula gotas de água em uma superfície. Foram também realizados estudos comparativos entre as definições implementadas pelos algoritmos, entre as estratégias utilizadas para tratamento de problemas comuns, entre o desempenho obtido pelos programas Python, e de paralelismo e abordagens utilizadas neste último caso. Desta forma, produziu-se um panorama geral e atualizado dos algoritmos de transformada watershed Abstract: The watershed transform is a morphological image segmentation technique inspired on the division of surfaces in catchment basins, with several forms of definition and algorithms. This work accomplishes a survey of the literature on fourteen of these algorithms. The main approaches since the introduction of the first fast algorithm by Vincent and Soille in 1991, until the work of Cousty et al. in 2009 has been considered. For better understanding of the subject, the watershed definitions are revisited, providing the set of formal solutions that are possible and expected from the algorithms. On the analysis of the algorithms it is supplied pseudocode with a uniform notation and a Python operational implementation allowing to abstract programming details. Aside, three algorithms were corrected for better adherence to definition and specification. Also some properties such as the scanning behaviour, use of particular strategies, and use of data structures, among others were identified. The compilation of information of the algorithms allowed to generalise and classify them based on classic paradigms of computing, namely breadth-first and depth-first search. Both are based on the visiting order of the pixels, with the breadth-first similar to a flooding simulation while the depth-first simulates drops of water on a surface Mestrado Engenharia de Computação Mestre em Engenharia Elétrica

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

Olivos, Iparraguirre Johani. "Algoritmos para caminos mínimos." Universidad Nacional de Ingeniería. Programa Cybertesis PERÚ, 2009. http://cybertesis.uni.edu.pe/uni/2009/olivos_ij/html/index-frames.html.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

Muñoz, Jugo Cynthia Mariela. "Algoritmos Divide y Vencerás." Universidad Peruana de Ciencias Aplicadas - UPC, 2007. http://hdl.handle.net/10757/272799.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

Muñoz, Jugo Cynthia Mariela. "Algoritmos de fuerza bruta." Universidad Peruana de Ciencias Aplicadas - UPC, 2007. http://hdl.handle.net/10757/272800.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

Figueiras, Vasco da Rocha. "Algoritmos para genómica comparativa." Master's thesis, Universidade de Aveiro, 2010. http://hdl.handle.net/10773/5634.

Texto completo

Resumen

Mestrado em Engenharia Electrónica e Telecomunicações Com o surgimento da Genómica e da Proteómica, a Bioinformática conduziu a alguns dos avanços científicos mais relevantes do século XX. A Unidade de Investigação e Desenvolvimento do Biocant, parque biotecnológico de Cantanhede, assume actualmente o papel de motor no desenvolvimento da Genómica. O Biocant possui um importante sequenciador de larga escala que permite armazenar um elevado número de genomas, nomeadamente, genomas de bactérias. O estudo proposto reflecte a necessidade do Biocant construir e usufruir de um sistema de informação que ofereça funcionalidades para comparar genomas de bactérias sequenciadas no Biocant com outras semelhantes ou sequenciadas em outros centros de investigação. O objectivo deste trabalho é implementar algoritmos que viabilizem uma análise estatística e a construção de métodos para visualização de dados que auxiliem a interpretação dos resultados estatísticos que surgem da análise e comparação da estrutura primária de genomas na forma de sequências de proteínas. A comparação dos genomas é realizada através do algoritmo BLASTp, porém foram desenvolvidos outros algoritmos para facilitar a realização do algoritmo, armazenamento dos dados e compreensão dos resultados. Pretende-se que deste estudo resulte não só, a construção de um sistema de informação útil, mas também, uma profunda investigação acerca de algoritmos e ferramentas de genómica comparativa. O estudo realizado foca, especificamente, os algoritmos e ferramentas BLAST, o algoritmo FASTA, aplicações de alinhamento múltiplo e bases de dados de genomas. Adicionalmente, é elaborada uma descrição das tecnologias propostas para o desenvolvimento do sistema de informação Proteo, focando as bibliotecas Java usadas para desenvolvimento de interfaces gráficas de utilizador, e o sistema de gestão de base de dados MySQL. Acreditamos que o presente trabalho poderá representar uma mais-valia para o desenvolvimento de outros estudos e sistemas de informação da área de Bioinformática. With the advent of genomics and proteomics, bioinformatics led to some of the most significant scientific breakthroughs of the twentieth century. The Office of Research and Development at Biocant, the biotech park at Cantanhede, has now assumed the leading role in the genomics development. Biocant possesses an important large-scale sequencer that allows the storage of a large number of genomes, including bacteria’s genomes. The proposed study reflects the Biocant’s need to build and make use of an information system that provides functionality to compare the sequenced genomes of bacteria present at Biocant’s R&D facility or against genomes sequenced in other research centers. The main purpose of this work is to implement algorithms that allow a statistical analysis and to build methods for data visualization in order to help the interpretation of the statistical results acquired from the analysis and comparison of the genomes primary structure with a protein sequence format. This comparison is performed using the BLASTp algorithm, but other methods have also been developed to ease the algorithm implementation, data storage and understanding the resulting data. It is our intention that from this study results not only the construction of a useful information system, but also a thorough research on algorithms and tools for comparative genomics. The study focuses, specifically, the BLAST tools and algorithms, the FASTA algorithm, multiple alignment applications and genomes databases. Additionally, it is elaborated a description of the technologies used for developing the Proteo information system, with primary focus on the Java libraries used to develop graphical user interfaces and the system administration of the MySQL database. We believe this work could represent a valuable asset on the development of information systems and new research projects in the Bioinformatics field.

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

Silveira, Luís Fernando Schultz Xavier da. "Algoritmos para união de círculos e polígonos." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-25072016-184451/.

Texto completo

Resumen

Este trabalho aborda dois problemas de geometria computacional: união de círculos e união de (vários) polígonos. Para o problema da união de círculos, os principais algoritmos da literatura são revisados e um algoritmo simples, porém ineficiente, é introduzido. Este algoritmo é então adaptado para resolver o problema da união de polígonos, produzindo um algoritmo que é competitivo com o estado da arte e, dependendo da aplicação, utiliza menos armazenamento. This work deals with two problems from the field of computational geometry: union of circles and union of (many) polygons. For the union of circles problem, the main algorithms in the literature are revised and a simple, albeit inefficient, algorithm is introduced. This algorithm is then adapted to solve the union of polygons problem, resulting in an algorithm that is competitive with the state of the art and, depending on the application, makes use of less storage.

Los estilos APA, Harvard, Vancouver, ISO, etc.

21

Peixoto, Robson Roberto Souza. "Algoritmos para problemas de escalonamento em grades." [s.n.], 2011. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275753.

Texto completo

Resumen

Orientador: Eduardo Candido Xavier Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Made available in DSpace on 2018-08-18T10:12:53Z (GMT). No. of bitstreams: 1 Peixoto_RobsonRobertoSouza_M.pdf: 1268588 bytes, checksum: ff8a093aa133696dcd5bbe31bc4d6e78 (MD5) Previous issue date: 2011 Resumo: Nesta dissertação estudamos algoritmos para resolver problemas de escalonamento de tarefas em grades computacionais. Dado um conjunto de tarefas submetidas a uma grade computacional, deve-se definir em quais recursos essas tarefas serão executadas. Algoritmos de escalonamento são empregados com o objetivo de minimizar o tempo necessário para executar todas as tarefas (makespan) que foram submetidas. Nosso foco é estudar os atuais algoritmos de escalonamento usados em grades computacionais e comparar estes algoritmos. Nesta dissertação apresentamos algoritmos onlines, aproximados e heurísticas para o problema. Como resultados novos, provamos fatores de aproximação para o algoritmo RR quando utilizado para resolver os problemas R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax e R; sit|Tj = L|TPCC é justo. Por fim, definimos uma interface que adiciona replicação de tarefas a qualquer algoritmo de escalonamento, onde nós mostramos a aproximação desta interface, e apresentamos uma comparação via simulação dos algoritmos sem e com replicação. Nossas simulações mostram que, com a utilização de replicação, houve a redução no makespan de até 80% para o algoritmo Min-min. Nas nossas análises também fazemos uso da métrica RTPCC que calcula exatamente a quantidade de instruções que foram usadas para executar todas as tarefas Abstract: In this dissertation, we studied algorithms to solve task scheduling problems in computational grids. Given a task set that was submitted to a computational grid, the problem is to define in which resources these tasks will be executed and the order they will be executed. Scheduling algorithms are used in order to minimize the time required to execute all tasks (makespan). We studied the most recent scheduling algorithms proposed to be used in computational grids, and then compare them using simulations. In this dissertation we also present approximate algorithms and new heuristics for the problem. As new results, we proved approximation factors to the RR algorithm when applied to solve the problems R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax and R; sit|Tj = L|TPCC. Finally, we defined an interface that adds task replication capability to any scheduling algorithm. We then show approximation results for algorithms using this interface, and present a comparison of well know algorithms with and without replication. This comparison is done via simulation. Our simulations show that, with replication, there was up to 80% of reduction in the makespan to some algorithms like the Min-min Mestrado Teoria da Computação Mestre em Ciência da Computação

Los estilos APA, Harvard, Vancouver, ISO, etc.

22

Soares, Antonio Helson Mineiro. "Algoritmos de estimação de distribuição baseados em árvores filogenéticas." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-25032015-111952/.

Texto completo

Resumen

Algoritmos Evolutivos que utilizam modelos probabilísticos de distribuição dos valores das variáveis (para orientar o processo de busca da solução de problemas) são chamados Algoritmos de Estimação de Distribuição (AEDs). Esses algoritmos têm apresentado resultados relevantes para lidar com problemas relativamente complexos. O desempenho deles depende diretamente da qualidade dos modelos probabilísticos construídos que, por sua vez, dependem dos métodos de construção dos modelos. Os melhores modelos em geral são construídos por métodos computacionalmente complexos, resultando em AEDs que requerem tempo computacional alto, apesar de serem capazes de explorar menos pontos do espaço de busca para encontrar a solução de um problema. Este trabalho investiga modelos probabilísticos obtidos por algoritmos de reconstrução de filogenias, uma vez que alguns desses métodos podem produzir, de forma computacionalmente eficiente, modelos que representam bem as principais relações entre espécies (ou entre variáveis). Este trabalho propõe algumas estratégias para obter um melhor uso de modelos baseados em filogenia para o desenvolvimento de AEDs, dentre elas o emprego de um conjunto de filogenias em vez de apenas uma filogenia como modelo de correlação entre variáveis, a síntese das informações mais relevantes desse conjunto em uma estrutura de rede e a identificação de grupos de variáveis correlacionadas a partir de uma ou mais redes por meio de um algoritmo de detecção de comunidades. Utilizando esses avanços para a construção de modelos, foi desenvolvido uma nova técnica de busca, a Busca Exaustiva Composta, que possibilita encontrar a solução de problemas combinatórios de otimização de diferentes níveis de dificuldades. Além disso, foi proposta uma extensão do novo algoritmo para problemas multiobjetivos, que mostrou ser capaz de determinar a fronteira Pareto-ótima dos problemas combinatórios investigados. Por fim, o AED desenvolvido possibilitou obter um compromisso em termos de número de avaliações e tempo de computação, conseguindo resultados similares aos dos melhores algoritmos encontrados para cada um desses critérios de desempenho nos problemas testados. Evolutionary Algorithms that use the distribution of values of variables as probabilistic models (to direct the search process of problem solving) are called Estimation of Distribution Algorithms (EDAs). These algorithms have presented relevant performance in handling relatively complex problems. The performance of such algorithms depends directly on the quality of probabilistic models constructed that, in turn, depend on the methods of model building. The best models are often constructed by computationally complex methods, resulting in AEDs that require high running time although they are able to explore less points in the search space to find the solution of a problem. This work investigates probabilistic models obtained by algorithms of phylogeny reconstruction since some of them can produce models in an efficient way representing the main relationships among species (or among variables). This work proposes some strategies for better use of phylogeny-based models in the development of EDAs, such as the employment of a set of phylogenies instead of only one phylogeny as a model of correlation among variables, the synthesis of the most relevant information from a set of phylogenies into a structure of network and the identification groups of correlated variables from one or more networks by an algorithm of community detection. Using those advances for model construction, a new search technique, called Composed Exhaustive Search, was developed in order to find solutions for combinatorial optimization problems with different levels of difficulty. In addition, an extension of the new algorithm for multi-objective problems was proposed, which was able to determine the Pareto-optimal front of the combinatorial problems investigated. Finally, the developed EDA makes possible to obtain a trade-off in terms of number of evaluations and running time, finding results that are similar to the ones achieved by the best algorithms found for each one of these performance criteria in the problems tested.

Los estilos APA, Harvard, Vancouver, ISO, etc.

23

Francisco, Marcus Vinícius Cardador. "Desenvolvimento de algoritmo para controle de tráfego urbano usando redes neurais e algoritmos genéticos." Pontifícia Universidade Católica de São Paulo, 2009. https://tede2.pucsp.br/handle/handle/18252.

Texto completo

Resumen

Made available in DSpace on 2016-04-29T14:23:53Z (GMT). No. of bitstreams: 1 Marcus Vinicius Cardador Francisco.pdf: 1267870 bytes, checksum: 9cad63d4aeb66e7ee5b764e9855e2b06 (MD5) Previous issue date: 2009-12-15 This research has as goal to introduce an alternative solution for vehicles traffic flow control. Researches on similar subjects around the world were taken as a basement for this study which makes use of a hybrid architecture. This architecture is composed by a back-propagation algorithm, which is responsible for creating and training the networks that will take care of traffic flow control, and a genetic algorithm, responsible for all chromosome relations which will generate new networks based on its previews parents. The results for this combined algorithms shows that errors were decreased if compared to the other researches described below. This makes this a plausible solution. The whole complexity involved on current study as well as on traffic flow control gives many possibilities for development of new solutions and improvements on traffic flow subject O objetivo deste trabalho é prover uma solução alternativa para o gerenciamento de fluxos de tráfego por meio de Redes Neurais. Pesquisas em diferentes partes do mundo dentro de um mesmo âmbito foram analisadas e forneceram uma base concreta para o corrente estudo que utiliza uma arquitetura híbrida. Essa arquitetura é composta por um algoritmo de propagação reversa com a finalidade de criar e treinar as redes destinadas ao gerenciamento dos fluxos de tráfego e por um algoritmo genético incumbido de realizar cruzamentos entre as redes anteriormente geradas em busca de novas redes a partir de suas sucessoras. Os resultados obtidos pela combinação dos algoritmos apresentam, de forma constante, valores de erros inferiores aos dos estudos analisados, tornado-a uma alternativa plausível. A complexidade envolta no presente estudo, bem como nos fluxos de tráfego, abre espaço para o desenvolvimento de novos trabalhos e projetos no âmbito de soluções e melhorias para sistemas de tráfego

Los estilos APA, Harvard, Vancouver, ISO, etc.

24

Oliveira, Igor Carboni. "Complexidade computacional e o problema P vs NP." [s.n.], 2010. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275804.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

25

San, Felice Mário César 1985. "Online facility location and Steiner problems = Problemas online de localização de instalações e de Steiner." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275552.

Texto completo

Resumen

Orientador: Orlando Lee Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Made available in DSpace on 2018-08-27T12:18:11Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_D.pdf: 1457706 bytes, checksum: 4813f4ed44c52462656d56537d73d5dc (MD5) Previous issue date: 2015 Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online Single-Source Rent-or-Buy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rent-or-buy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rent-or-buy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online Prize-Collecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have non-negative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities Doutorado Ciência da Computação Doutor em Ciência da Computação

Los estilos APA, Harvard, Vancouver, ISO, etc.

26

Oliveira, Jefferson Evandi Ricardini Fernandes de. "Emparelhamentos e reticulados: estado-da-arte em algoritmos e parâmetros para as famílias mais flexíveis de sistemas criptográficos." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/3/3141/tde-25112014-144116/.

Texto completo

Resumen

A criptografia de chave pública é uma área do conhecimento sujeita que é tema de intensa atividade contemporânea de pesquisa. Novos protocolos, primitivas e ataques são propostos com frequência, com semelhanças e diferenças mútuas que podem ser mais ou menos evidentes. Algumas primitivas criptográficas de chave pública mostram-se extremamente férteis em termos de flexibilidade, eficiência e segurança. Duas vertentes que se enquadram nesta categoria são os emparelhamentos e os reticulados. Por possuírem semelhanças em suas funcionalidades a despeito de possuírem naturezas completamente díspares, além de exibirem uma versatilidade rara em toda a área de criptografia de chave pública, alguns autores propuseram chamar os reticulados de os novos emparelhamentos, conforme a ordem cronológica em que essas primitivas passaram a atrair interesse mais vívido de pesquisa. Neste cenário, um estudo comparativo entre elas é de razoável interesse, em particular sobre vantagens e desvantagens que o estado da arte revela sobre a eficiência de cada uma delas. A pesquisa aqui relatada contempla esse estudo, e contribui técnicas de implementação eficiente de emparelhamentos (com ênfase no uso de coordenadas afins, pouco exploradas na literatura), novos parâmetros para a construção de reticulados compactos (na forma das chamadas álgebras discretas de Rojo) e uma técnica inovadora para instanciar reticulados na prática (especificamente, um algoritmo simples e natural para amostrar vetores normalmente distribuídos nos reticulados comumente adotados em sistemas criptográficos). Public key cryptography is an area of knowledge undergoing intense research at present. New protocols, primitives and attacks are often proposed, with mutual similarities and differences that may be more or less evident. Some public key cryptographic primitives tend to be extremely prolific in terms of flexibility, efficiency and security. Two trends that fit this category are pairings and lattices. Because of their similar functionalities despite their completely disparate nature, and because of their rare versatility within the whole area of public key cryptography, some authors proposed to call lattices \"the new pairings,\" according to the chronological order by which these primitives began to attract more vivid research interest. In this scenario, a comparative study between them is of reasonable interest, in particular on the advantages and disadvantages that the state of the art reveals about the efficiency of each one. The research reported herein addresses this study, and also contributes efficient pairing implementation techniques (focusing on affine coordinates, which are scarcely explored in literature), new parameters for building compact lattices (in the form of the so-called discrete Rojo algebras) and an innovative technique to instantiate lattices in practical (specifically, a simple and natural algorithm for sampling normally distributed vectors in the lattices that are commonly adopted in cryptographic systems).

Los estilos APA, Harvard, Vancouver, ISO, etc.

27

Silveira, Jefferson Luiz Moisés da 1986. "Algoritmos de aproximação para problemas de empacotamento em faixa com restrições de descarregamento." [s.n.], 2011. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275757.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

28

Zafalon, Geraldo Francisco Donega [UNESP]. "Algoritmos de alinhamento múltiplo e técnicas de otimização para esses algoritmos utilizando Ant Colony." Universidade Estadual Paulista (UNESP), 2009. http://hdl.handle.net/11449/89350.

Texto completo

Resumen

Made available in DSpace on 2014-06-11T19:24:01Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-04-30Bitstream added on 2014-06-13T19:10:03Z : No. of bitstreams: 1 zafalon_gfd_me_sjrp.pdf: 915240 bytes, checksum: 39a35a2fec9d70947eb907760544f707 (MD5) A biologia, como uma ciência bastante desenvolvida, foi dividida em diversas areas, dentre elas, a genética. Esta area passou a crescer em importância nos ultimos cinquenta anos devido aos in umeros benefícios que ela pode trazer, principalmente, aos seres humanos. Como a gen etica passou a apresentar problemas com grande complexidade de resolução estratégias computacionais foram agregadas a ela, surgindo assim a bioinform atica. A bioinformática desenvolveu-se de forma bastante signi cativa nos ultimos anos e esse desenvolvimento vem se acentuando a cada dia, devido ao aumento da complexidade dos problemas genômicos propostos pelos biólogos. Assim, os cientistas da computação têm se empenhado no desenvolvimento de novas técnicas computacionais para os biólogos, principalmente no que diz respeito as estrat egias para alinhamentos m ultiplos de sequências. Quando as sequências estão alinhadas, os biólogos podem realizar mais inferências sobre elas, principalmente no reconhecimento de padrões que e uma outra area interessante da bioinformática. Atrav es do reconhecimento de padrãoes, os bi ologos podem identicar pontos de alta signi cância (hot spots) entre as sequências e, consequentemente, pesquisar curas para doençass, melhoramentos genéticos na agricultura, entre outras possibilidades. Este trabalho traz o desenvolvimento e a comparação entre duas técnicas computacionais para o alinhamento m ultiplo de sequências. Uma e baseada na técnica de alinhamento múltiplo de sequências progressivas pura e a outra, e uma técnica de alinhamento múltiplo de sequências otimizada a partir da heurística de colônia de formigas. Ambas as técnicas adotam em algumas de suas fases estratégias de paralelismo, focando na redu c~ao do tempo de execução dos algoritmos. Os testes de desempenho e qualidade dos alinhamentos que foram conduzidos com as duas estrat egias... Biology as an enough developed science was divided in some areas, and genetics is one of them. This area has improved its relevance in last fty years due to the several bene ts that it can mainly bring to the humans. As genetics starts to show problems with hard resolution complexity, computational strategies were aggregated to it, leading to the start of the bioinformatics. The bioinformatics has been developed in a signi cant way in the last years and this development is accentuating everyday due to the increase of the complexity of the genomic problems proposed by biologists. Thus, the computer scientists have committed in the development of new computational techniques to the biologists, mainly related to the strategies to multiple sequence alignments. When the sequences are aligned, the biologists can do more inferences about them mainly in the pattern recognition that is another interesting area of the bioinformatics. Through the pattern recognition, the biologists can nd hot spots among the sequences and consequently contribute for the cure of diseases, genetics improvements in the agriculture and many other possibilities. This work brings the development and the comparison between two computational techniques for the multiple sequence alignments. One is based on the pure progressive multiple sequence alignment technique and the other one is an optimized multiple sequence alignment technique based on the ant colony heuristics. Both techniques take on some of its stages of parallel strategies, focusing on reducing the execution time of algorithms. Performance and quality tests of the alignments were conducted with both strategies and showed that the optimized approach presents better results when it is compared with the pure progressive approach. Biology as an enough developed science was divided in some areas, and genetics is one of them. This area has improved... (Complete abstract click electronic access below)

Los estilos APA, Harvard, Vancouver, ISO, etc.

29

Castelo, Branco César Augusto Santana. "Algoritmos adaptativos LMS normalizados proporcionais: proposta de novos algoritmos para identificação de plantas esparsas." Universidade Federal do Maranhão, 2016. http://tedebc.ufma.br:8080/jspui/handle/tede/1688.

Texto completo

Resumen

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-06-23T20:42:44Z No. of bitstreams: 1 CesarCasteloBranco.pdf: 11257769 bytes, checksum: 911c33f2f0ba5c1c0948888e713724f6 (MD5) Made available in DSpace on 2017-06-23T20:42:44Z (GMT). No. of bitstreams: 1 CesarCasteloBranco.pdf: 11257769 bytes, checksum: 911c33f2f0ba5c1c0948888e713724f6 (MD5) Previous issue date: 2016-12-12 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPQ) This work proposes new methodologies to optimize the choice of the parameters of the proportionate normalized least-mean-square (PNLMS) adaptive algorithms. The proposed approaches use procedures based on two optimization methods, namely, the golden section and tabu search methods. Such procedures are applied to determine the optimal parameters in each iteration of the adaptation process of the PNLMS and improved PNLMS (IPNLMS) algorithms. The objective function for the proposed procedures is based on the a posteriori estimation error. Performance studies carried out to evaluate the impact of the PNLMS and IPNLMS parameters in the behavior of these algorithms shows that, with the aid of optimization techniques to choose properly such parameters, the performance of these algorithms may be improved in terms of convergence speed for the identification of plants with high sparseness degree. The main goal of the proposed methodologies is to improve the distribution of the adaptation energy between the coefficients of the PNLMS and IPNLMS algorithms, using parameter values that lead to the minimal estimation error of each iteration of the adaptation process. Numerical tests performed (considering various scenarios in which the plant impulse response is sparse) show that the proposed methodologies achieve convergence speeds faster than the PNLMS and IPNLMS algorithms, and other algorithms of the PNLMS class, such as the sparseness controlled IPNLMS (SC-IPNLMS) algorithm. Neste trabalho, novas metodologias para otimizar a escolha dos parâmetros dos algoritmos adaptativos LMS normalizados proporcionais (PNLMS) são propostas. As abordagens propostas usam procedimentos baseados em dois métodos de otimização, a saber, os métodos da razão áurea e da busca tabu. Tais procedimentos são empregados para determinar os parâmetros ótimos em cada iteração do processo de adaptação dos algoritmos PNLMS e PNLMS melhorado (IPNLMS). A função objetivo adotada pelos procedimentos propostos é baseada no erro de estimação a posteriori. O estudo de desempenho realizado para avaliar o impacto dos parâmetros dos algoritmos PNLMS e IPNLMS no comportamento dos mesmos mostram que, com o auxílio de técnicas de otimização para escolher adequadamente tais parâmetros, o desempenho destes algoritmos pode ser melhorado, em termos de velocidade de convergência, para a identificação de plantas com elevado grau de esparsidade. O principal objetivo das metodologias propostas é melhorar a distribuição da energia de ativação entre os coeficientes dos algoritmos PNLMS e IPNLMS, usando valores de parâmetros que levam ao erro de estimação mínimo em cada iteração do processo de adaptação. Testes numéricos realizados (considerando diversos cenários nos quais a resposta impulsiva da planta é esparsa) mostram que as metodologias propostas alcançam velocidades de convergência superiores às dos algoritmos PNLMS e IPNLMS, além de outros algoritmos da classe PNLMS, tais como o algoritmo IPNLMS com controle de esparsidade (SCIPNLMS).

Los estilos APA, Harvard, Vancouver, ISO, etc.

30

Zafalon, Geraldo Francisco Donega. "Algoritmos de alinhamento múltiplo e técnicas de otimização para esses algoritmos utilizando Ant Colony /." São José do Rio Preto : [s.n.], 2009. http://hdl.handle.net/11449/89350.

Texto completo

Resumen

Orientador: José Márcio Machado Banca: Liria Matsumoto Sato Banca: Renata Spolon Lobato Resumo: A biologia, como uma ciência bastante desenvolvida, foi dividida em diversas areas, dentre elas, a genética. Esta area passou a crescer em importância nos ultimos cinquenta anos devido aos in umeros benefícios que ela pode trazer, principalmente, aos seres humanos. Como a gen etica passou a apresentar problemas com grande complexidade de resolução estratégias computacionais foram agregadas a ela, surgindo assim a bioinform atica. A bioinformática desenvolveu-se de forma bastante signi cativa nos ultimos anos e esse desenvolvimento vem se acentuando a cada dia, devido ao aumento da complexidade dos problemas genômicos propostos pelos biólogos. Assim, os cientistas da computação têm se empenhado no desenvolvimento de novas técnicas computacionais para os biólogos, principalmente no que diz respeito as estrat egias para alinhamentos m ultiplos de sequências. Quando as sequências estão alinhadas, os biólogos podem realizar mais inferências sobre elas, principalmente no reconhecimento de padrões que e uma outra area interessante da bioinformática. Atrav es do reconhecimento de padrãoes, os bi ologos podem identicar pontos de alta signi cância (hot spots) entre as sequências e, consequentemente, pesquisar curas para doençass, melhoramentos genéticos na agricultura, entre outras possibilidades. Este trabalho traz o desenvolvimento e a comparação entre duas técnicas computacionais para o alinhamento m ultiplo de sequências. Uma e baseada na técnica de alinhamento múltiplo de sequências progressivas pura e a outra, e uma técnica de alinhamento múltiplo de sequências otimizada a partir da heurística de colônia de formigas. Ambas as técnicas adotam em algumas de suas fases estratégias de paralelismo, focando na redu c~ao do tempo de execução dos algoritmos. Os testes de desempenho e qualidade dos alinhamentos que foram conduzidos com as duas estrat egias... (Resumo completo, clicar acesso eletrônico abaixo) Abstract: Biology as an enough developed science was divided in some areas, and genetics is one of them. This area has improved its relevance in last fty years due to the several bene ts that it can mainly bring to the humans. As genetics starts to show problems with hard resolution complexity, computational strategies were aggregated to it, leading to the start of the bioinformatics. The bioinformatics has been developed in a signi cant way in the last years and this development is accentuating everyday due to the increase of the complexity of the genomic problems proposed by biologists. Thus, the computer scientists have committed in the development of new computational techniques to the biologists, mainly related to the strategies to multiple sequence alignments. When the sequences are aligned, the biologists can do more inferences about them mainly in the pattern recognition that is another interesting area of the bioinformatics. Through the pattern recognition, the biologists can nd hot spots among the sequences and consequently contribute for the cure of diseases, genetics improvements in the agriculture and many other possibilities. This work brings the development and the comparison between two computational techniques for the multiple sequence alignments. One is based on the pure progressive multiple sequence alignment technique and the other one is an optimized multiple sequence alignment technique based on the ant colony heuristics. Both techniques take on some of its stages of parallel strategies, focusing on reducing the execution time of algorithms. Performance and quality tests of the alignments were conducted with both strategies and showed that the optimized approach presents better results when it is compared with the pure progressive approach. Biology as an enough developed science was divided in some areas, and genetics is one of them. This area has improved... (Complete abstract click electronic access below) Mestre

Los estilos APA, Harvard, Vancouver, ISO, etc.

31

Brassolatti, Ivo Roberto. "Dimensionamento de redes GMPLS com base em algoritmos RWA." Universidade de São Paulo, 2006. http://www.teses.usp.br/teses/disponiveis/3/3141/tde-01122006-152832/.

Texto completo

Resumen

As redes atuais buscam a integração dos serviços e tendem ao IP/MPLS sobre DWDM. No futuro, espera-se que as redes sejam do tipo GMPLS, apresentando melhoria na flexibilidade, capacidade de comutação no meio óptico e também um plano de controle único. Tais redes poderão prover a integração de diferentes camadas e tecnologias, além de reduzirem os custos de operação e de provisionamento. Dentre os muitos aspectos desta nova tecnologia, o trabalho proposto concentra-se no estudo do roteamento óptico em redes GMPLS, verificando a relação existente entre algoritmos RWA e o dimensionamento das mesmas. Pesquisas mostram que, ao tentar estabelecer uma rota numa rede totalmente óptica e com tráfego dinâmico, o bloqueio de conexões e o número de falhas podem limitar o seu desempenho. Realizando-se simulações com algoritmos RWA, é possível determinar o número mínimo de comprimentos de onda e avaliar a melhor topologia de rede para uma determinada probabilidade de bloqueio de conexões e de falhas. Este trabalho mostra como simulações com algoritmos RWA auxiliam no dimensionamento de redes GMPLS permitindo determinar a influência destes algoritmos em seu desempenho. Como principais resultados estão o dimensionamento de recursos, a determinação da carga de tráfego de trabalho e da taxa de falha permitida e a seleção do melhor tipo de algoritmo RWA para a rede de pesquisa Kyatera em duas possíveis fases de sua implementação. Today's networks seek integration of services and tend towards lean IP/MPLS over DWDM. In the future, it is expected that the networks will tend towards GMPLS with enhanced flexibility and switching capability in the optical layer and a unified control plane. Such networks will provide integration between different network layers and technologies, besides decrease operating and provisioning costs. Among many aspects of this technology, this study concentrates on GMPLS network optical routing, verifying the relationship between RWA algorithms and network dimensioning. Research shows that when attempting to establish a route in an alloptical network with dynamic traffic, connection blocking and failures can limit performance. Through of RWA algorithms simulation, it is possible to determine the minimum wavelength number and check the best network topology for a given probability of connection blocking and failure. This work shows how RWA simulations can assist in the dimensioning of GMPLS networks and in determining the influence of RWA algorithm on their performance. The main results are resource dimensioning, the determination of working traffic load and the allowed failure rate and the selection of the best RWA algorithm for Kyatera research network in two possible phases of its implementation.

Los estilos APA, Harvard, Vancouver, ISO, etc.

32

Lima, Marina Lemos Rio. "Otimização topológica e paramétrica de vigas de concreto armado utilizando algoritmos genéticos." Universidade de São Paulo, 2011. http://www.teses.usp.br/teses/disponiveis/3/3144/tde-17082011-153639/.

Texto completo

Resumen

Na Engenharia Civil são diversos os métodos aplicados visando à otimização de estruturas. Esta dissertação apresenta um estudo e uma aplicação de um desses métodos: os Algoritmos Genéticos (AG\'s). Os Algoritmos Genéticos são algoritmos de busca, não-determinísticos, que trabalham com amostras do conjunto de soluções e se inspiram na teoria da evolução das espécies para resolver o problema. Neste trabalho de pesquisa buscou-se apresentar as principais técnicas e parâmetros utilizados por diversos autores neste tema. Como objetivo principal pretendeu-se, através dos conhecimentos adquiridos sobre o assunto, aplicá-lo na otimização topológica e paramétrica de vigas de concreto armado, submetidas a um carregamento distribuído. Adotaram-se restrições laterais das variáveis e comportamentais (tensões máximas admissíveis - ELU). Procurou-se trabalhar com variáveis discretas, que melhor representam a realidade do projetista de estruturas. Para aplicação desta técnica implementou-se um programa, em linguagem Java seguindo o paradigma de programação orientada a objetos. O programa foi testado aplicando-se a um problema de otimização abordado por outros autores. Um deles utilizou uma abordagem determinística para a solução do problema. Outro utilizou uma abordagem probabilística, porém com variáveis contínuas. Em 85% dos casos o programa (nomeado AGEN) conseguiu encontrar a solução ótima. Concluiu-se que os algoritmos genéticos são uma técnica bastante robusta, que proporciona resultados significativos, principalmente quando se trata de problemas complexos, com variáveis discretas e restrições em constantes mudanças. As deficiências desta técnica são a sua grande dependência em relação à amostra inicial da população, o seu custo computacional e a calibração de parâmetros. Procurou-se, através deste trabalho, apresentar aos pesquisadores e projetistas do campo da engenharia mais uma ferramenta que utiliza técnicas computacionais para encontrar melhores soluções para otimização de estruturas. Pretendendo-se, assim, estimular o desenvolvimento de mais pesquisas sobre este tema bastante promissor. This work presents a study and application using Genetic Algorithms (GAs) to solve problems that optimization structures, more specifically concrete beans. The GAs are search algorithms, non-deterministics that works with a population of solutions. Its inspired on the evolutions theory of the species to solve problems. In this dissertation sought to show the most used techniques and parameters about this subject. The primary objective was (through the knowledge obtained during this research) to apply it in the topological and parametrical optimization of concrete beams, submitted by a distributed load. Lateral and behavioral constraineds are used. It was tried to work with a discrete variables, which represent more really the context of structures designer. To apply this technique a program was implemented, using the Java language through the oriented object paradigm. The program was tested applying a optimization problem approached by other authors. One of them used a deterministic approach to solution the problem. Another used a probabilistic approach, but with continuous variable. In 85% of the cases the program (called AGEN) get success. It was concluded that genetic algorithms are a very robust technique, which provides significant results, especially in complex problems with discrete variables and constraints on dynamic changes. The weaknesses of this technique are the high dependence on initial population, its computational cost and the parameters calibration. It was, in this work, presenting to scientists and designers in the structural engineering field another tool that uses computational techniques to find better solutions for structures optimization. It pretended to stimulate the development of more research on this topic enough promising.

Los estilos APA, Harvard, Vancouver, ISO, etc.

33

Borin, Edson 1979. "Algoritmos para compressão de microcodigo." [s.n.], 2007. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276200.

Texto completo

Resumen

Orientador: Guido Costa Souza de Araujo Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Made available in DSpace on 2018-08-08T22:09:00Z (GMT). No. of bitstreams: 1 Borin_Edson_D.pdf: 1623538 bytes, checksum: 6e51b4bb1114ccaa088f88712c601000 (MD5) Previous issue date: 2007 Resumo: Microprogramação é uma técnica comum no projeto de unidades de controle em processadores. Além de facilitar a implementação da unidade de controle, o microcódigo pode ser modificado para adicionar novas funcionalidades ou aplicar correções a projetos já existentes. À medida que novas funcionalidades são adicionadas à CPU, a área e o consumo de energia associados ao microcódigo também aumentam. Em um projeto recente de um processador da Intel, direcionado a baixo consumo de energia e área reduzida, estimou-se que a área e o consumo de energia associados ao microcódigo corresponderiam a 20% do total do chip. Neste trabalho, investigamos a utilização de técnicas de compressão para reduzir o tamanho do microcódigo. A partir das restrições impostas no projeto de processadores de alto desempenho, fizemos uma análise qualitativa das técnicas de compressão de código e microcódigo e mostramos que a compressão de microcódigo em dois níveis é a técnica mais adequada para se comprimir o microcódigo nesses processadores. Na compressão de microcódigo em dois níveis, as microinstruções são substituídas por apontadores para dicionários que armazenam os padrões de bits extraídos do microcódigo. Os apontadores são armazenados em uma ROM denominada ¿vetor de apontadores¿ e os padrões de bits residem em ROMs distintas, denominadas ¿dicionários¿. A técnica também permite que as colunas do microcódigo sejam agrupadas em conjuntos de forma a reduzir o número de padrões de bits nos dicionários. O agrupamento de colunas similares é fundamental para minimizar o número de padrões de bits nos dicionários e, conseqüentemente, maximizar a redução do tamanho do microcódigo. A principal contribuição desta tese é um conjunto de algoritmos para agrupar as colunas do microcódigo e maximizar a compressão. Resultados experimentais, com microcódigos extraídos de processadores em produção e em estágios avançados de desenvolvimento, mostram que os algoritmos propostosmelhoram de 6% a 20% os resultados obtidos com os outros algoritmos encontrados na literatura e comprimem o microcódigo em até 50% do seu tamanho original. Ainda neste trabalho, identificamos a necessidade de se comprimir o microcódigo com restrições no número de dicionários e na quantidade de colunas por dicionário. Também provamos que, com essas restrições, o agrupamento de colunas do microcódigo é um problema NP-Completo. Por fim, propomos um algoritmo para agrupar colunas sob estas restrições. Os resultados experimentaismostram que o algoritmo proposto é capaz de produzir bons resultados de compressão Abstract: Microprogramming is a widely known technique used to implement processor control units. Microcode makes the control unit design process easier, as it can be modified to enhance functionality and to apply patches to an existing design. As more features get added to a CPU core, the area and power costs associated with the microcode increase. In a recent Intel internal design, targeted to low power and small footprint, the area and the power consumption costs associated with the microcode approached 20% of the total die. In this work, we investigate the use of compression techniques to reduce the microcode size. Based on the constraints imposed by high performance processor design, we analyze the existing microcode and code compression techniques and show that the two level microcode compression technique is the most appropriate to compress the microcode on high performance processor. This technique replaces the original microinstructions by pointers to dictionaries that hold bit patterns extracted from the microcode. The ¿pointer arrays¿ and the ¿dictionaries¿ are ROMs that store the pointers and the bit patterns, respectively. The technique allows the microcode columns to be grouped into clusters, so that the number of bit patterns inside the dictionaries is reduced. In order to maximize the microcode compression, similar columns must be grouped together. The main contribution of this thesis is a set of algorithms to group similar microcode columns into clusters, so as to maximize the microcode size reduction. Experimental results, using microcodes from production processors and processors in advanced development stages, show that the proposed algorithms improve from 6% to 20% the compression results found by previous works and compress the microcode to 50% of its original size. We show the importance of compressing microcode under design constraints such as the number of dictionaries and the number of columns per dictionary. We also prove that, under these constraints, the problem of grouping similar columns is NP-Complete. Finally, we propose an algorithm to group similar columns under such constraints. The experimental results show that the proposed algorithm provides good compression results Doutorado Arquitetura de Computadores Doutor em Ciência da Computação

Los estilos APA, Harvard, Vancouver, ISO, etc.

34

Bouabci, Mauricio Borges. "Algoritmos de Cluster e Percolação." Universidade de São Paulo, 1998. http://www.teses.usp.br/teses/disponiveis/43/43133/tde-25022014-154840/.

Texto completo

Resumen

O objetivo principal deste trabalho é o de investigar relações entre mapeamentos de modelos de spin em modelos de percolação e a existência de algoritmos de cluster capazes de simular de forma eficiente o modelo. Apresentamos um mapeamento do modelo de Blume-Capel em um modelo de percolação que permite reobter um algoritmo proposto anteriormente por nós através de uma prova de balanço detalhado, o que abre a possibilidade de descrevermos todo o diagrama de fases do modelo em termos de propriedades dos clusters formados. Isto é particularmente interessante, já que o modelo possui um ponto tricrítico, nunca antes analisado em termos de propriedades de percolação. Encontramos também um mapeamento para o modelo de Ashkin-Teller, e através dos algoritmos de cluster resultantes investigamos a possibilidade de existência de uma fase de Baxter Assimétrica. Analisamos também questões relacionadas ao comportamento de tamanho finito de sistemas que apresentam transições de fase de primeira ordem assimétricas. Finalmente, o algoritmo de cluster desenvolvido para o modelo de Blume-CapeI é também generalizado: de forma a podermos aplicá-lo ao estudo do modelo de Blume-Emery-Griffiths. The main goal of this work is to investigate relations between mappings of spin models into percolation models and the possibility of devising an efficient cluster algorithm to simulate the model. We present a mapping of the Blume-Capel model into a percolation model that results in a cluster algorithm proposed previously by us through a detailed balance proof, enabling us to describe the whole phase-diagram in terms of cluster properties. This is particularly appealing, since the model has a tricritical point, a feature not yet analysed in terms of percolation properties. We present also a mapping for the Ashkin-Teller model, and using the obtained cluster algorithms we analyse the possibility of existence of the Asymmetric Baxter phase. We also address questions related to the finite-size behavior of systems in asymmetric first-order phase transitions. Finally, the cluster algorithm developed for the Blume-Capel model is generalized to the study of the Blume-Emery-Griffiths model.

Los estilos APA, Harvard, Vancouver, ISO, etc.

35

Hinz, Verlani Timm. "Algoritmos para Interoperabilidade entre Ontologias." Universidade Catolica de Pelotas, 2008. http://tede.ucpel.edu.br:8080/jspui/handle/tede/38.

Texto completo

Resumen

Made available in DSpace on 2016-03-22T17:26:09Z (GMT). No. of bitstreams: 1 Verlani Hinz.pdf: 1544192 bytes, checksum: cf6c659e0f4abe594675df0afce948c6 (MD5) Previous issue date: 2008-08-06 Nowadays the interest for the theme ontologies has steadily increased, as it aims at to capture consensual knowledge between people and applications, allowing reusing and sharing information. With this purpose, mechanisms are demanded to guarantee semantic interoperability, that is, the identification and compatibility of information. The present study proposes to development the algorithms to interoperability among ontologies. Hence, it intends to obtain more semantic flexibility and to reach better levels of description in the information that characterize the context of a computational environment. Initially, a basic but deep study, was done about the ways of interoperability among ontologies and its applications in different environments. Formality of specification as grammatical of graphs and matrix of adjacencies to represent ontologies and the use of parsers for conversion of code OWL in representation of matrices had also been studied. The patterns Dublin Core and FOAF, were studied and used in order to address the issue of reconciliation of vocabularies. For verification of the applicability of the measure, it was shown to an example of dynamic interoperability of ontologies and an algorithm that can be applied in several scenes Recentemente, tem crescido o interesse sobre o tema Ontologias, pois estas objetivam capturar conhecimento consensual entre pessoas e aplicações, permitindo o reuso e compartilhamento de informações. Para estes propósitos, são necessários mecanismos que garantam a interoperabilidade semântica e compatibilidade de informações. O presente trabalho propõe desenvolver algoritmos para interoperabilidade entre ontologias, utilizando operadores relacionais. Para isso, inicialmente foi feito um estudo básico, mas aprofundado, sobre as formas de interoperabilidade entre ontologias e sua aplicação em diferentes ambientes. Foram estudados também formalismos de especificação como gramática de grafos e matriz de adjacências para representar ontologias, assim como, a utilização de parsers para converter ontologias no formato OWL em representação de matrizes. Os padrões Dublin Core e FOAF, foram estudados e utilizados a fim de tratar a questão da conciliação de vocabulários. Como verificações da aplicabilidade da medida foram demonstrados dois exemplos de interoperabilidade dinâmica de ontologias aplicadas a domínios específicos

Los estilos APA, Harvard, Vancouver, ISO, etc.

36

CAVALCANTI, Cláudio Sebastião Vasconcelos da Cunha. "Algoritmos para composição automática defotografias." Universidade Federal de Campina Grande, 2007. http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/1482.

Texto completo

Resumen

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-17T13:42:57Z No. of bitstreams: 1 CLÁUDIO SABASTIÃO VASCONCELOS DA CUNHA CAVALCANTI - DISSERTAÇÃO PPGCC 2007..pdf: 19270985 bytes, checksum: b54c266f6cdb98e2cbbf305285b6ffdf (MD5) Made available in DSpace on 2018-08-17T13:42:57Z (GMT). No. of bitstreams: 1 CLÁUDIO SABASTIÃO VASCONCELOS DA CUNHA CAVALCANTI - DISSERTAÇÃO PPGCC 2007..pdf: 19270985 bytes, checksum: b54c266f6cdb98e2cbbf305285b6ffdf (MD5) Previous issue date: 2007-07-30 Além de ser uma das mais populares formas de arte, a fotograﬁa também é uma forma de lazer e ferramenta de trabalho. Com a redução dos preços e a conseqüente popularização dos equipamentos e acessórios necessários à fotograﬁa, especialmente o preço das câmeras digitais, é crescente o interesse por novos algoritmos e ferramentas que favoreçam a captura de imagens com maior qualidade. Diante do exposto, a presente dissertação objetivou a proposição e desenvolvimento de algoritmos capazes de detectar e corrigir falhas na composição fotográﬁca. As regras de composição fotográﬁca, em geral, são heurísticas utilizadas por fotógrafos que se difundiram a ponto de serem denominadas de “regras”. Mesmo não sendo consenso entre os fotógrafos, é possível que a implementação destas regras possa levar um fotógrafo amador, sem conhecimento prévio de fotograﬁa, a produzir fotograﬁas de alta qualidade e teor proﬁssional. Neste trabalho são propostas duas alternativas para a correção da composição: um método para correção on-line, no qual a foto ﬁnal só é obtida após satisfeitas algumas condições de qualidade, e outro para a correção off-line, o qual classiﬁca (ou modiﬁca) a imagem a posteriori. Para tanto, são utilizados algoritmos destinados à detecção e correção de problemas no posicionamento do tema. Os resultados foram avaliados em dois experimentos. No primeiro experimento, os usuários concordaram em até 65% com os resultados obtidos pelo sistema, através de uma análise subjetiva. No segundo experimento,foi mostrado como é possível, utilizando-se apenas uma câmera Pan-Tilt-Zoom (câmera dotada de três graus de liberdade sendo dois de rotação e um do campo de visão),localizar e fotografar pessoas em um determinado ambiente a partir das regras de composição desenvolvidas. Besides being one of the most popular forms of art, photography is often used for a wide variety of purposes, including professional and entertainment ones. Nowadays, since cameras (specially digital ones) are less expensive and more popular, there is an increasing need for tools to help photographers (both amateurs and professionals) to obtain photographs of better quality. Within this context, algorithms for detection and correction of errors on the composition of a photograph are proposed in this work. Photographic composition rules are heuristics used by photographers, which became so wides pread that they are now also known as“rules”. Photographers, however, are not unanimous about the use of some of those rules. Despite of that it is possible that the use of photographic composition rules can improve the quality of amateur photographs, leveling them to a professional standard. In this dissertation, two approaches are proposed to automate composition rules: an on-line method, in which a picture is only taken when a number of conditions is satisﬁed; and an off-line method,which classiﬁers or corrects the image after it has been acquired. Hence, algorithms for detecting and correcting problems on subject positioning are used. Two experiments were used to evaluate the performance of the system. The ﬁrst one shows that users agree with the correction performed on 65% of the photographs, through a subjective analysis. By using only a Pan-Tilt-Zoom camera and the composition rules implemented in this work, the second experiment shows howto locate and photograph human subjects ina given environment.

Los estilos APA, Harvard, Vancouver, ISO, etc.

37

Ourique, Luiz Eduardo. "Eficiência probabilística de algoritmos numéricos." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 1990. http://hdl.handle.net/10183/127095.

Texto completo

Resumen

Seguindo as ideias de s. smale, estudamos a eficiencia probabilistica de algoritmos numericos para equacoes diferenciais ordinarias. especial atencao e dada a dois exemplos classicos: os algoritmos de runge-kutta de dois e de quatro estagios, sendo a sua eficiencia estimada em termos de medidas gaussianas. em ambos os casos, sao obtidas estimativas detalhadas que levam a uma expressao para a media do erro global. Following the ideas of S. Smale, we study the probabilistic efficiency of numerical algorithms in ordinary differential equations. Special attention is directed to two classical examples: the algorithms of Runge-Kutta of two and four stages with their efficiency estimated in terms of gaussian measures. In both these cases detailed estimates are given. leading to an expression for the mean global error.

Los estilos APA, Harvard, Vancouver, ISO, etc.

38

Batista, Ana Micaela Gomes. "Algoritmos de minimização de autómatos." Master's thesis, Universidade de Aveiro, 2011. http://hdl.handle.net/10773/9847.

Texto completo

Resumen

Mestrado em Matemática e Aplicações O presente trabalho aborda vários algoritmos de minimização de autómatos. Aqui são apresentadas algumas definições relacionadas com autómatos, como por exemplo relação de equivalência de estados, relação de distinguibilidade de estados e classes de equivalência da relação de equivalência de estados, definições que estão na base dos algoritmos apresentados. É feita uma síntese de vários algoritmos de minimização, como por exemplo o algoritmo de Hopcroft e o algoritmo de Brzozowski, e são apresentadas as respectivas ordens de complexidade. The present work shows several automaton minimization algorithms. Some definitions related to automaton are presented, for example the equivalence relation on states, the distinguishability relation on states and the equivalence classes of equivalence relation on states, which are the basis of the presented algorithms. A synthesis of several minimization algorithms is made, for example the Hopcroft algorithm and the Brzozowski algorithm, and their complexity orders are presented.

Los estilos APA, Harvard, Vancouver, ISO, etc.

39

Samuco, José Maria Eduardo. "Algoritmos de otimização contínua univariada." Master's thesis, Universidade de Aveiro, 2014. http://hdl.handle.net/10773/17709.

Texto completo

Resumen

Mestrado em Matemática e Aplicações - Estatística e Investigação Operacional Nesta dissertação são estudados alguns métodos numéricos de otimização de funções reais contínuas de uma variável real. Nesse sentido, e antes desta abordagem, são analisadas as técnicas clássicas de otimiza ção, sendo feito um estudo de condições de otimalidade de funções convexas e de funções contínuas. O estudo dos métodos numéricos é dividido em três categorias: métodos intervalares de eliminação (mé- todo de busca dicotómica, método de busca por bissecção, método de Fibonacci e método da secção áurea), métodos de aproximação polinomial (método de interpolação quadrática, método de interpolação cúbica e algoritmo de Davies, Swann e Campey) e busca linear inexata. Os métodos aplicam-se a funções unimodais, razão pela qual este conceito é introduzido e é discutida a sua utilização na redução de intervalos de incerteza. No final do estudo de cada método, são apresentados problemas resolvidos, com indicação de todos os passos de cada iteração ou aplicando rotinas em MATLAB, cujos códigos são explicitados ao longo do texto. Estudamos também propriedades dos números de Fibonacci para a verificação de que, em certo sentido, o método de Fibonacci é o método ideal para a contração do intervalo. Essas propriedades permitem também verificar a estreita inter-relação entre este método e o método da secção áurea. In this dissertation some numerical methods for optimization of continuous real functions of a single real variable are studied. In this sense, and before this approach, the classical optimization techniques are analyzed and a study of optimality conditions for convex functions and continuous ones is made. The study of numerical methods is divided into three categories: interval methods of elimination (dichotomous search method, interval halving method, Fibonacci's method and golden section method), polynomial approximation methods (quadratic interpolation method, cubic interpolation method and Davies, Swann and Campey's algorithm) and inexact line search. The methods are applied to unimodal functions, that is why this concept is introduced and its use in reducing uncertainty intervals is discussed. For each method, solved problems are presented, showing all steps of each iteration or applying routines in MATLAB, whose codes are speci ed throughout the text. Properties of Fibonacci numbers are also studied showing that, in a sense, the Fibonacci method is the optimal method for contraction of the interval. These properties allow us also check the close interrelationship between this method and the method of golden section.

Los estilos APA, Harvard, Vancouver, ISO, etc.

40

Coelho, Tiago Filipe Santos. "Algoritmos inteligentes de baixa complexidade." Master's thesis, Universidade de Aveiro, 2013. http://hdl.handle.net/10773/13923.

Texto completo

Resumen

Mestrado em Engenharia Eletrónica e Telecomunicações A domótica é uma área com grande interesse e margem de exploração, que pretende alcançar a gestão automática e autónoma de recursos habitacionais, proporcionando um maior conforto aos utilizadores. Para além disso, cada vez mais se procuram incluir benefícios económicos e ambientais neste conceito, por forma a garantir um futuro sustentável. O aquecimento de água (por meios elétricos) é um dos fatores que mais contribui para o consumo de energia total de uma residência. Neste enquadramento surge o tema “algoritmos inteligentes de baixa complexidade”, com origem numa parceria entre o Departamento de Eletrónica, Telecomunicações e Informática (DETI) da Universidade de Aveiro e a Bosch Termotecnologia SA, que visa o desenvolvimento de algoritmos ditos “inteligentes”, isto é, com alguma capacidade de aprendizagem e funcionamento autónomo. Os algoritmos devem ser adaptados a unidades de processamento de 8 bits para equipar pequenos aparelhos domésticos, mais propriamente tanques de aquecimento elétrico de água. Uma porção do desafio está, por isso, relacionada com as restrições computacionais de microcontroladores de 8 bits. No caso específico deste trabalho, foi determinada a existência de sensores de temperatura da água no tanque como a única fonte de informação externa aos algoritmos, juntamente com parâmetros pré-definidos pelo utilizador que estabelecem os limiares de temperatura máxima e mínima da água. Partindo deste princípio, os algoritmos desenvolvidos baseiam-se no perfil de consumo de água quente, observado ao longo de cada semana, para tentar prever futuras tiragens de água e, consequentemente, agir de forma adequada, adiantando ou adiando o aquecimento da água do tanque. O objetivo é alcançar uma gestão vantajosa entre a economia de energia e o conforto do utilizador (água quente), isto sem que exista necessidade de intervenção direta por parte do utilizador final. A solução prevista inclui também o desenvolvimento de um simulador que permite observar, avaliar e comparar o desempenho dos algoritmos desenvolvidos. Home automation is an area of great interest and growth margin, which aims to achieve autonomous control of housing resources, providing greater comfort to the users. In addition, this concept is increasingly covering economic and environmental concerns, in order to ensure a sustainable future. Water heating (using electric resources) is one of the factors that contribute the most to the total energy consumption of a residence. In this context arises the subject “intelligent algorithms with low complexity”, originated in a partnership between the Department of Electronics, Telecommunications and Informatics (DETI) of the University of Aveiro and Bosch Thermotechnology SA, which targets the development of algorithms entitled "intelligent", in other words, with some capability for learning and autonomous functioning. The algorithms must be adapted to 8-bit processing units in order to equip small appliances, more precisely domestic electric water heaters. A portion of the challenge is therefore related to the computational constraints of 8-bit microcontrollers. In the specific case of this work, it was determined the existence of temperature sensors in the water tank as the only source of information external to the algorithms, along with pre-set user-defined thresholds which establish the maximum and minimum water temperature values. On this basis, in order to predict future drawings of water and thus take appropriate action, anticipating or delaying the heating of the tank’s water, the developed algorithms use information from the hot water consumption profile, observed throughout each week. The goal is to achieve an advantageous management between energy savings and user comfort (hot water), with no need for direct intervention by the end user. The solution conceived also includes the development of a simulator that allows us to observe, evaluate and compare the performance of the algorithms created.

Los estilos APA, Harvard, Vancouver, ISO, etc.

41

Lopes, Cavalcanti Junior Nicomedes. "Clusterização baseada em algoritmos fuzzy." Universidade Federal de Pernambuco, 2006. https://repositorio.ufpe.br/handle/123456789/2619.

Texto completo

Resumen

Made available in DSpace on 2014-06-12T15:59:42Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 Análise de cluster é uma técnica aplicada a diversas áreas como mineração de dados, reconhecimento de padrões, processamento de imagens. Algoritmos de clusterização têm por objetivo particionar um conjunto de dados em clusters de tal forma que indivíduos dentro de um mesmo cluster tenham um alto grau de similaridade, enquanto indivíduos pertencentes a diferentes clusters tenham alto grau de dissimilaridade. Uma importante divisão dos algoritmos de clusterização é entre algoritmos hard e fuzzy. Algoritmos hard associam um indivíduo a somente um cluster. Ao contrário, algoritmos fuzzy associam um indivíduo a todos os clusters através da variação do grau de pertinência do indivíduo em cada cluster. A vantagem de um algoritmo clusterização fuzzy é que este pode representar melhor incerteza e este fato é importante, por exemplo, para mostrar que um indivíduo não é um típico indivíduo de nenhuma das classes, mas tem similaridade em maior ou menor grau com mais de uma classe. Uma forma intuitiva de medir similaridade entre indivíduos é usar medidas de distância tais como a distância euclidiana. Existem muitas medidas de distância disponíveis na literatura. Muitos dos algoritmos de clusterização populares geralmente buscam minimizar um critério baseados numa medida de distância. Através de um processo iterativo estes algoritmos calculam parâmetros de modo a diminuir o valor do critério iteração a iteração até um estado de convergência ser atingido. O problema com muitas das distâncias encontradas na literatura é que elas são estáticas. Para o caso de algoritmos de clusterização iterativos, parece razoável ter distâncias que mudem ou atualizem seus valores de acordo com o que for ocorrendo com os dados e as estruturas de dado do algoritmo. Esta dissertação apresenta duas distâncias adaptativas aplicadas ao algoritmo fuzzy c-means pelo Prof. Francisco de Carvalho. Este algoritmo foi escolhido pelo fato de ser amplamente utilizado. Para avaliar as proposições de distância, experimentos foram feitos utilizando-se conjunto de dados de referência e conjuntos de dados artificiais (para ter resultados mais precisos experimentos do tipo Monte Carlo foram realizados neste caso). Até o momento, comparações das versões do fuzzy c-means, obtidas através da utilização de distâncias adaptativas, com algoritmos similares da literatura permitem concluir que em geral as novas versões têm melhor performance que outros disponíveis na literatura

Los estilos APA, Harvard, Vancouver, ISO, etc.

42

Souza, Francisco das Chagas de. "Algoritmos adaptativos LMS normalizados proporcionais." Florianópolis, 2012. http://repositorio.ufsc.br/xmlui/handle/123456789/96392.

Texto completo

Resumen

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica. Made available in DSpace on 2012-10-26T11:34:42Z (GMT). No. of bitstreams: 0Bitstream added on 2013-07-16T20:55:04Z : No. of bitstreams: 1 309939.pdf: 4352344 bytes, checksum: 0535613da00725ae9a3e9b7d04f2957c (MD5) Neste trabalho, um novo algoritmo LMS normalizado proporcional (PNLMS) é proposto. Tal algoritmo usa fatores de ativação individuais para cada coeficiente do filtro adaptativo, em vez de um fator de ativação global como no algoritmo PNLMS padrão. Os fatores de ativação individuais do algoritmo proposto são atualizados recursivamente a partir dos correspondentes coeficientes do filtro adaptativo. Essa abordagem conduz a uma melhor distribuição da energia de adaptação entre os coeficientes do filtro. Dessa forma, para respostas ao impulso com elevada esparsidade, o algoritmo proposto, denominado algoritmo PNLMS com fatores de ativação individuais (IAF PNLMS), atinge maior velocidade de convergência do que os algoritmos PNLMS padrão e PNLMS melhorado (IPNLMS). Também, uma metodologia de modelagem estocástica dos algoritmos da classe PNLMS é apresentada. Usando essa metodologia, obtém-se um modelo estocástico que prediz satisfatoriamente o comportamento do algoritmo IAF PNLMS tanto na fase transitória quanto na estacionária. Através de simulações numéricas, a eficácia do modelo proposto é verificada. Adicionalmente, uma versão melhorada do algoritmo IAF PNLMS, denominada EIAF PNLMS, é proposta neste trabalho, a qual usa uma estratégia de redistribuição de ganhos durante o processo de aprendizagem, visando aumentar os ganhos atribuídos aos coeficientes inativos quando os ativos aproximam-se da convergência. Resultados de simulação mostram que tal estratégia de redistribuição melhora significativamente as características de convergência do algoritmo

Los estilos APA, Harvard, Vancouver, ISO, etc.

43

Álvaro, Suarez Camilo Andrés. "Algoritmos de controle PID preditivo." reponame:Repositório Institucional da UFSC, 2014. https://repositorio.ufsc.br/xmlui/handle/123456789/132751.

Texto completo

Resumen

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Automação e Sistemas, Florianópolis, 2014. Made available in DSpace on 2015-05-12T04:07:25Z (GMT). No. of bitstreams: 1 333313.pdf: 9333466 bytes, checksum: 2f5c28506b2aa00baf91ae9c8ef458ce (MD5) Previous issue date: 2014 Nesta dissertação são abordados projetos de hibridização de controladores PID com algoritmos de controle preditivo GPC, que procuram resgatar as propriedades desejadas para o controle de processos complexos onde atraso de transporte dominante, instabilidade e fase não-mínima estão presentes. Descreve-se o procedimento de síntese das leis de controle PID preditivas a partir de modelos de primeira e segunda ordem com atraso de transporte, e demonstra-se com estudos de caso que o comportamento destes controladores assim derivados é equivalente ao comportamento do GPC, quando aplica-se um tipo particular de sintonia. Depois avalia-se em simulações numéricas o seu desempenho com relação ao seguimento de referência e rejeição de perturbações, comparando-se com o desempenho do PID clássico sintonizado com a metodologia SIMC, considerada de desempenho satisfatório pela literatura de controle. Finalmente, dado que existe certa complexidade matemática para o cálculo dos parâmetros e síntese da lei de controle PID preditiva, que pode inviabilizá-la em aplicações embarcadas, são propostos métodos de sintonia baseados em aproximações da lei de controle GPC denominados pseudo preditivos. Demonstra-se com estudos de caso e implementação no PLC300, desenvolvido pela WEG Automação, que estes métodos resultam viáveis de embarcar em equipamentos de controle industriais e são eficientes para acelerar o tempo de resposta em processos com atraso de transporte dominante.

Los estilos APA, Harvard, Vancouver, ISO, etc.

44

Barreto, Tarcisio da Silva. "Análise de taxa média de bloqueio em conexões por algoritmos de caminhos mínimos: algoritmo de Yen e algoritmo genético." Universidade Federal Rural do Semi-Árido, 2014. http://bdtd.ufersa.edu.br:80/tede/handle/tede/526.

Texto completo

Resumen

Made available in DSpace on 2016-08-31T13:33:41Z (GMT). No. of bitstreams: 1 TarcisioSB_DISSERT.pdf: 1571314 bytes, checksum: 86e8646fa8da6455187767e219181490 (MD5) Previous issue date: 2014-12-15 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Studies on connections lock in computer networks have been gaining prominence in recent research focused on computational communication and technology. Several researchers have used various methods in order to identify and minimize the blocking rate that prevent a connection is established. This paper presents a blocking rate analysis in connections of shortest paths algorithms. They have on the performance of a transparent optical network. Two algorithms will be used to perform the analysis and simulations, the Genetic Algorithm (AG) and the algorithm Yen (AY). The Genetic Algorithm is based on Computational Intelligence (CI) and the Yen algorithm is based on the principle of finding and identifying the K shortest paths. Numerical simulations performed on different network scenarios show that the greater the number of connections, the higher the blocking rate in the connections. This study will help to identify which algorithm behaves better in the specific cases described in this work Os estudos sobre bloqueio de conexões em redes de computadores vêm ganhando destaque em recentes pesquisas voltadas à comunicação computacional e tecnologia. Vários pesquisadores têm utilizado diversos métodos buscando identificar e minimizar ao máximo a taxa média de bloqueio que impedem que uma conexão seja estabelecida. Este trabalho apresenta uma análise de taxa média de bloqueio em conexões por algoritmos de caminhos mínimos. Têm sobre o desempenho de uma rede ótica transparente. Serão utilizados dois algoritmos para realizar a análise e as simulações, o Algoritmo Genético (AG) e o Algoritmo de Yen (AY). O Algoritmo Genético fundamentado por Inteligência Computacional (IC) e o Algoritmo de Yen baseado no princípio de encontrar e identificar os K menores caminhos. Simulações numéricas realizadas em diferentes cenários da rede mostram que, quanto maior o número de conexões, maior será a taxa média de bloqueio nas conexões. Através desse estudo será possível identificar qual algoritmo se comporta melhor para os casos específicos descritos nesse trabalho

Los estilos APA, Harvard, Vancouver, ISO, etc.

45

Andrade, Carlos Eduardo de 1981. "Evolutionary algorithms for some problems in telecommunications = Algoritmos evolutivos para alguns problemas em telecomunicações." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275653.

Texto completo

Resumen

Orientadores: Flavio Keidi Miyazawa, Mauricio Guilherme de Carvalho Resende Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Made available in DSpace on 2018-08-27T21:53:09Z (GMT). No. of bitstreams: 1 Andrade_CarlosEduardode_D.pdf: 4654702 bytes, checksum: 566cb3ea8fc876147ffa6df2ec8482b3 (MD5) Previous issue date: 2015 Resumo: Nos últimos anos, as redes de telecomunicação tem experienciado um grande aumento no fluxo de dados. Desde a utilização massiva de vídeo sob demanda até o incontável número de dispositivos móveis trocando texto e vídeo, o tráfego alcançou uma escala capaz de superar a capacidade das redes atuais. Portanto, as companhias de telecomunicação ao redor do mundo tem sido forçadas a aumentar a capacidade de suas redes para servir esta crescente demanda. Como o custo de instalar uma infraestrutura de rede é geralmente muito grande, o projeto de redes usa fortemente ferramentas de otimização para manter os custos tão baixos quanto possível. Nesta tese, nós analisamos vários aspectos do projeto e implementação de redes de telecomunicação. Primeiramente, nós apresentamos um novo problema de projeto de redes usado para servir demandas sem fio de dispositivos móveis e rotear tal tráfego para a rede principal. Tais redes de acesso são baseadas em tecnologias sem fio modernos como Wi-Fi, LTE e HSPA. Este problema consideramos várias restrições reais e é difícil de ser resolvido. Nós estudamos casos reais nas vizinhanças de uma grande cidade nos Estados Unidos. Em seguida, nós apresentamos uma variação do problema de localização de hubs usado para modelar as redes principais (backbones ou laços centrais). Este problema também pode ser utilizado para modelar redes de transporte de cargas e passageiros. Nós também estudamos o problema de clusterização correlacionada com sobreposições usado para modelar o comportamento dos usuários quando utilizam seus equipamentos móveis. Neste problema, nós podemos rotular um objeto usando múltiplos rótulos e analisar a conexão entre eles. Este problema é adequado para análise de mobilidade de equipamentos que pode ser usada para estimar o tráfego em uma dada região. E finalmente, nós analisamos o licenciamento de espectro sobre uma perspectiva governamental. Nestes casos, uma agência do governo deseja vender licenças para companhias de telecomunicação para que operem em uma dada faixa de espectro. Este processo usualmente é conduzido usando leilões combinatoriais. Para todos problemas, nós propomos algoritmos genéticos de chaves aleatórias viciadas e modelos de programação linear inteira mista para resolvê-los (exceto para o problema de clusterização correlacionada com sobreposição, devido sua natureza não-linear). Os algoritmos que propusemos foram capazes de superar algoritmos do estado da arte para todos problemas Abstract: Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances Abstract: In last twenty years, telecommunication networks have experienced a huge increase in data utilization. From massive on-demand video to uncountable mobile devices exchanging text and video, traffic reached scales that overcame the network capacities. Therefore, telecommunication companies around the world have been forced to increase their capacity to serve this increasing demand. As the cost to deploy network infrastructure is usually very large, the design of a network heavily uses optimization tools to keep costs as low as possible. In this thesis, we analyze several aspects of the design and deployment of communication networks. First, we present a new network design problem used to serve wireless demands from mobile devices and route the traffic to the core network. Such access networks are based on modern wireless access technologies such as Wi-Fi, LTE, and HSPA. This problem has several real world constraints and it is hard to solve. We study real cases of the vicinity of a large city in the United States. Following, we present a variation of the hub-location problem used to model these core networks. Such problem is also suitable to model transportation networks. We also study the overlapping correlation clustering problem used to model the user's behavior when using their mobile devices. In such problem, one can label an object with multiple labels and analyzes the connections between them. Although this problem is very generic, it is suitable to analyze device mobility which can be used to estimate traffic in geographical regions. Finally, we analyze spectrum licensing from a governmental perspective. In these cases, a governmental agency wants to sell rights for telecommunication companies to operate over a given spectrum range. This process usually is conducted using combinatorial auctions. For all problems we propose biased random-key genetic algorithms and mixed integer linear programming models (except in the case of the overlapping correlation clustering problem due its non-linear nature). Our algorithms were able to overcome the state of the art algorithms for all problems Doutorado Ciência da Computação Doutor em Ciência da Computação

Los estilos APA, Harvard, Vancouver, ISO, etc.

46

Flores, Vega Christian Humberto, and Ku Antonio Eugenio Li. "Diseño De Una Naríz Electrónica Como Discriminador De Olores Utilizando Algoritmos Genéticos Y Redes Neuronales Artificiales." Bachelor's thesis, Universidad Ricardo Palma. Programa Cybertesis PERÚ, 2007. http://cybertesis.urp.edu.pe/urp/2007/li_ca/html/index-frames.html.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

47

Meneses, Pilco Sebastian Alonso. "Diseño de un algoritmo genético para la optimización de distancias en ambientes tridimensionales." Bachelor's thesis, Pontificia Universidad Católica del Perú, 2014. http://tesis.pucp.edu.pe/repositorio/handle/123456789/5723.

Texto completo

Resumen

La problemática que el presente proyecto de fin de carrera pretende afrontar es una variante del problema del TSP, donde se busca la minimización de costos y distancias en relación con las rutas en un espacio de tres dimensiones. Básicamente como se explicó en el párrafo anterior, el objetivo radica en buscar un recorrido pasando por varios puntos optimizando costo o distancia. Sin embargo esto aplica para un escenario de dos dimensiones, lo cual es perfectamente aplicable a problema de delivery, ruteo, entre otros. No obstante existen problemas que se escapan de ese contexto de dos dimensiones, y resulta necesario plantearlos en tres dimensiones. Justamente a través del presente trabajo, se busca realizar una adaptación de un algoritmo genético que permita solucionar dicho problema. En específico, el presente trabajo buscará brindar una propuesta de solución para la búsqueda de una ruta óptima entre puntos de soldadura que debe recorrer un brazo mecánico. Al conseguir una ruta óptima, se logrará minimizar la cantidad de movimientos que debe hacer el brazo mecánico, así como consecuentemente los costos. Tesis

Los estilos APA, Harvard, Vancouver, ISO, etc.

48

Soncco, Álvarez José Luis. "Ordenação por reversões de permutações sem sinal usando uma abordagem de algoritmos genéticos." reponame:Repositório Institucional da UnB, 2013. http://repositorio.unb.br/handle/10482/13824.

Texto completo

Resumen

Dissertação (mestrado)—Universidade de Brasília, Departamento de Ciência da Computação, 2013. Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-07-15T16:43:11Z No. of bitstreams: 1 2013_JoseLuisSonccoAlvarez.pdf: 1018122 bytes, checksum: 9dd7f3ffe2e2bdb1cb9b764e37a8d6a1 (MD5) Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-08-02T13:47:05Z (GMT) No. of bitstreams: 1 2013_JoseLuisSonccoAlvarez.pdf: 1018122 bytes, checksum: 9dd7f3ffe2e2bdb1cb9b764e37a8d6a1 (MD5) Made available in DSpace on 2013-08-02T13:47:05Z (GMT). No. of bitstreams: 1 2013_JoseLuisSonccoAlvarez.pdf: 1018122 bytes, checksum: 9dd7f3ffe2e2bdb1cb9b764e37a8d6a1 (MD5) Ordenação de permutações por reversões é um dos problemas mais desafiantes relacionados com a análise da distância evolutiva entre organis- mos, cujos resultados podem ser usados na construção de árvores filogenéticas baseadas nesta distância. No caso de permutações com sinal, o problema pode ser resolvido em tempo linear, porém, no caso de permutações sem sinal o problema é mais complexo, já que foi demonstrado ser NP-difícil e com uma questão ainda em aberto: se é ou não NP completo; este foi o motivo pelo qual foram propostos diversos algoritmos de aproximação e de computação evolucionária. Neste trabalho, é proposto um algoritmo genético(AG) padrão para resolver o problema de ordenação de permutações sem sinal. Este enfoque está baseado no método proposto por Auyeung e Abraham, que usa soluções exatas para o caso de permutações com sinal, para resolver a versão do problema com permutações sem sinal. Adicionalmente, foi proposto um algoritmo genético melhorado (hibrido), que usa uma heurística de eliminação de pontos de quebra em gerações iniciais. Diversos experimentos foram feitos tomando como entrada permutações gera- das aleatoriamente, escolhendo um elemento aleatório sobre um conjunto de números, ou aplicando reversões aleatórias sobre uma permutação ordenada. Ademais, foram usadas permutações de Gollan as quais sabemos que podem ser ordenadas usando n — 1 reversões, onde n é o comprimento da permutação. Desde que muitos enfoques de AG's usaram mecanismos de controle impreci- sos para validar a precisão das suas respostas, foi necessário um grande esforço para desenvolver uma algoritmo de aproximação confiável. Dando origem a um desenvolvimento teórico baseado no algoritmo de raio de aproximação 1.5 proposto por Christie, e sua posterior implementação. Os experimentos mostraram que ambos AG fornecem respostas que são melhores do que aquelas fornecidas por métodos relacionados prévios, tanto como os que são fornecidos pelo algoritmo de raio de aproximação 1.5 corrigido. ______________________________________________________________________________ ABSTRACT Sorting permutations by reversals is one of the most challenging problems related to the analysis of the evolutionary distance between organisms, whose results can be used in the construction of phylogenetic trees bases on this distance. In the case of signed permutations, the problem can be solved in linear time, however in the case of unsigned permutations the problem is more complex, since it was shown to be NP-hard and it is unknown whether it is NP-complete or not; this fact motivated the proposal of several approximation, and evolutionary computing algorithms. In this work, we propose genetic algorithms (GA) to solve the problem of sorting unsigned permutations. Initially, we propose a standard GA approach based on the method proposed by Auyeung and Abraham, which uses exact polynomial solutions for the case of signed permutations, for solving the problem with unsigned permutations. Further, we propose an improved genetic algorithm, which uses the heuristic of elimination of break points in early generations and then the standard approach. Several experiments were made using as inputs permutations generated randomly by choosing a random element over a set of numbers, and by applying random reversals over an sorted permutation. Also, was used Gollan permutations that it's well-known that can be sorted by n 1 reversals, where n is the length of the permutation. Since previous GA approaches have used imprecise control mechanisms for checking the accuracy of their answers, a great deal of e ort was necessary in order to develop a reliable approximate algorithm. This gave rise to a theoretical development based on the well-known Christie's 1.5 ratio approximation algorithm and its further implementation. Experiments showed that both AG approaches compute answers that are better than the ones computed by previous approaches as well as than the ones computed with the adjusted correct 1.5 approximation algorithm.

Los estilos APA, Harvard, Vancouver, ISO, etc.

49

Meira, Luis Augusto Angelotti 1979. "Algoritmos para problemas de classificação e particionamento em grafos." [s.n.], 2007. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276073.

Texto completo

Resumen

Orientador: Flavio Keidi Miyazawa Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Made available in DSpace on 2018-08-11T20:54:55Z (GMT). No. of bitstreams: 1 Meira_LuisAugustoAngelotti_D.pdf: 974332 bytes, checksum: 7097ff3ed310db70e5026afabc41ceb6 (MD5) Previous issue date: 2007 Resumo: O trabalho desenvolvido neste doutorado consistiu em conceber algoritmos para uma série de problemas NP-dificeis sob a abordagem de aproximabilidade, complementado com resultados heurísticos e também de programação inteira. O estudo foi focado em problemas de classificação e particionamento em grafos, como classificação métrica, corte balanceado e clusterização. Houve um equilíbrio entre teoria e aplicabilidade, ao obterse algoritmos com bons fatores de aproximação e algoritmos que obtiveram soluções de qualidade em tempo competitivo. O estudo concentrou-se em três problemas: o Problema da Classificação Métrica Uniforme, o Problema do Corte Balanceado e o Problema da Localização de Recursos na versão contínua. Inicialmente trabalhamos no Problema da Classificação Métrica Uniforme, para o qual propusemos um algoritmo O (logn)-aproximado. Na validação experimental, este algoritmo obteve soluções de boa qualidade em um espaço de tempo menor que os algoritmos tradicionais. Para o Problema do Corte Balanceado, propusemos heurísticas e um algoritmo exato. Experimentalmente, utilizamos um resolvedor de programação semidefinida para resolver a relaxação do problema e melhoramos substancialmente o tempo de resolução da relaxação ao construir um resolvedor próprio utilizando o método de inserção de cortes sobre um sistema de programação linear. Finalmente, trabalhamos com o problema de Localização de Recursos na variante contínua. Para este problema, apresentamos algoritmos de aproximação para as métricas l2 e l2 2. Este algoritmo foi aplicado para obter algoritmos de aproximação para o problema k-Means, que 'e um problema clássico de clusterização. Na comparação ao experimental com uma implementação conhecida da literatura, os algoritmos apresentados mostraram-se competitivos, obtendo, em vários casos, soluções de melhor qualidade em tempo equiparável. Os estudos relativos a estes problemas resultaram em três artigos, detalhados nos capítulos que compõem esta tese Abstract: We present algorithms for combinatorial optimization NP-hard problems on classification and graph partitioning. The thesis concerns about theory and application and is guided by an approximation algorithms approach, complemented with heuristics and integer programming. We proposed good approximation factor algorithms as well as algorithms that find quality solutions in competitive time. We focus on three problems: the Metric Labeling Problem, the Sparsest Cut Problem and the Continuous Facility Location Problem. For the Metric Labeling Problem, we proposed an O(log n)-approximation algorithm. In the experimental analysis, this algorithm found high quality solutions in less time than other known algorithms. For the Sparsest Cut Problem we proposed heuristics and an exact algorithm. We built an SDP Solver to the relaxed formulation using a semi-infinity cut generation over linear programming. This approach considerably reduces the time used to solve the semi definite relaxation compared to an open source semi definite programming solver. Finally, for the Continuous Facility Location Problem we present approximation algorithms to the l2 and l2 2 distance function. These algorithms are used to obtain approximation algorithms to the k-Means Problem, which is a basic clustering problem. The presented algorithms are competitive since they obtain in many cases better solutions in equivalent time, compared to other known algorithms. The study of these problems results in three papers, which are detailed in chapters that make this thesis Doutorado Otimização Combinatoria Doutor em Ciência da Computação

Los estilos APA, Harvard, Vancouver, ISO, etc.

50

Silva, Elivaldo Elenildo da. "Otimização de estruturas de concreto armado utilizando algoritmos genéticos." Universidade de São Paulo, 2001. http://www.teses.usp.br/teses/disponiveis/3/3144/tde-21022002-112505/.

Texto completo

Resumen

Neste trabalho são apresentadas duas importantes áreas de pesquisa voltadas para problemas de otimização: a Programação Matemática e, especialmente, os Algoritmos Genéticos. São classificados grande parte dos métodos clássicos da Programação Matemática, com uma breve apresentação das suas classes de subproblemas, bem como detalhes de alguns métodos. O desenvolvimento da ciência que explica a evolução das espécies é descrito, como uma ponte para a compreensão da técnica dos Algoritmos Genéticos. Apresentam-se as diferenças básicas entre os Métodos Clássicos e os Algoritmos Genéticos, com posterior análise das vantagens e desvantagens entre estas duas classes de ferramentas de otimização. São apresentados os principais parâmetros de influência no funcionamento de um Algoritmo Genético e algumas recomendações quanto às suas configurações. A essência desse trabalho se constitui em alguns exemplos de otimização de estruturas de concreto armado, como o de um trecho de Pilar dimensionado à Flexão Composta Obliqua e um Pórtico Plano de Concreto Armado de Cinco Pavimentos. Finalizando, conclui-se pela tendência promissora dos Algoritmos Genéticos para os próximos anos, o que tornará esta técnica uma das mais importantes e empregadas na resolução de uma vasta gama de aplicações. This work addresses two important issues of Optimization: Mathematical Programming and Genetic Algorithms. First, classes of optimization problems, that can be handled by the classical methods of Mathematical Programming, are briefly presented. After that, the techniques of Genetic Algorithms are displayed in detail. Such methods are inspired by the laws that rules the evolution of the species. The basic differences between the Mathematical Programming and Genetic Algorithms are deeply discussed. The main parameters that control Genetic Algorithms are described and some recommendations about their values are made.The work is concluded y some optimization examples of reinforced concrete structures, as a column under combined axial load and bi-axial bending and a five floor reinforced concrete plane frame.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Tesis sobre el tema "Algoritmos"

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros