Algoritmos Divide y Vencerás, búsqueda binaria, análisis de tiempos para algoritmos. Divide y Vencerás Masther Theorem.

Algoritmos de fuerza bruta.

Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro de Ciencias Fisicas e Matematicas / Made available in DSpace on 2012-10-17T00:29:18Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-08T21:30:14Z : No. of bitstreams: 1 108854.pdf: 4253419 bytes, checksum: 4c4ed0bb6cbe75bc06c63b7e2db4f2f8 (MD5) / Neste trabalho analisamos, em particular, um algoritmo que segue a trajetória central associada a um problema de complementariedade linear monótona, gerando pontos em vizinhanças grandes da trajetória. Esse algoritmo baseia-se em passos que procuram uma aproximação rápida da face ótima do problema, e, quando houver necessidade, em passos corretores, que provocam uma aproximação à trajetória central. A trajetória central termina no ponto conhecido como ótimo central, que é o centro analítico da face ótima. Neste trabalho mostramos como este algoritmo gera seqüências que convergem para o ótimo central, e como o algoritmo de centralização é acelerado pela aproximação desse ponto.

Orientador: Jose Mario Martinez / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-14T00:40:39Z (GMT). No. of bitstreams: 1 Santos_SandraAugusta_M.pdf: 3299632 bytes, checksum: 99345cc4fd3341d3d1424714dde44703 (MD5) Previous issue date: 1991 / Resumo: Neste trabalho, definimos dois algoritmos gerais de região de confiança para o problema de minimização restrita a um conjunto fechado arbitrário. Provamos convergência a pontos que satisfazem condições necessárias de primeira ordem e quando usamos a Hessiana da função objetivo no modelo, provamos que condições de segunda ordem são satisfeitas. Considerando-se a implementabilidade destes algoritmos, analisamos o caso em que a restrição é uma bola euclidiana. Desenvolvemos uma implementação computacional e fizemos um conjunto de experimentos numéricos. / Abstract: Not informed. / Mestrado / Mestre em Matemática Aplicada

Orientador : Jose Mario Martinez / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-14T07:49:03Z (GMT). No. of bitstreams: 1 Biagio_MariaAmelia_M.pdf: 1968266 bytes, checksum: ebd312610afad08ff2e4663106d4088e (MD5) Previous issue date: 1981 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

Orientador: João Marcos Travassos Romano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-20T01:21:35Z (GMT). No. of bitstreams: 1 Gimenez_JoseRobertoBollis_D.pdf: 9975776 bytes, checksum: fe5ab296cb5d89e0d24ca1deacbb78d1 (MD5) Previous issue date: 1995 / Resumo: o trabalho apresentado nesta tese é dedicado ao entendimento e busca de soluções para o problema de instabilidade numérica inerente dos algoritmos de minimos quadrados rápidos. A ênfase do tratamento é dirigida a viabilizar e aperfeiçoar a aplicação destes algoritmos em sistemas de processamento digital de sinais, especialmente na área de transmissão de dados, onde os fenômenos de ocorrência de eco e interferência inter-simbólica exigem procedimentos de filtragem adaptativa em tempo real. Os métodos de ITÚnimosquadrados clássico e recursivo são tratados no Capítulo 1, juntamente com os processos de filtragem digital adaptativa aos quais eles se aplicam. Os algoritmos rápidos são introduzidos no Capítulo 2, onde se procurou elaborar um texto que reuna as principais informações existentes sobre o assunto na literatura. Estes dois primeiros capítulos utilizam uma abordagem clara e ao mesmo tempo inédita do funcionamento dos algoritmos de minimos quadrados, representando uma contribuição no campo didático. Contribuições importantes para o entendimento do problema da instabilidade numérica em vários algoritmos de minimos quadrados são apresentadas no Capítulo 3. Diversas formas de análise são desenvolvidas para explicar a origem e a propagação do fenômeno da instabilidade numérica, incluindo um modelo que descreve o comportamento do processo corruptivo. No Capítulo 4 são discutidos os principais métodos de estabilização existentes. Também é apresentado um método novo, que representa uma significativa evolução técnica na área, sobretudo quando se deseja atender um compromisso entre complexidade computacional e estabilidade numérica. Resultados de simulações e comparações do novo método com outros existentes são apresentados no Capítulo 5, com o objetivo de validar o novo método como um instrumento adequado ao controle da instabilidade numérica nos algoritmos rápidos / Abstract: The work described in this thesis is concerned with the understanding and solution of the numerical instability problem presented by the fast least square algorithm. The emphasis is on the application and performance achieved by the algorithms in digital signal processing systems, specially in data transmission, where the echo phenomena and intersymbol interference effects makes the on-line adaptive filtering process a mandatory technique. The traditional and recursive least square methods are presented in Chapter 1, so are their applications on the adaptive digital filtering processo The fast least square algorithms are introduced in Chapter 2. In this chapter we gathered the important information found in the technical literature about the topic.These two first chapters represent a contribution in the didactic area, as they present a clear and original approach to the least square algorithm operation. In Chapter 3, we present important contributions to the understanding of the numerical instability problem in various least square algorithms. Also, we develop several kinds of theoretical and experimental analysis in order to explain the origin and growing of the numerical instability phenomenon, inc1uding a mathematical model that describes the behaviour of the corruptive processo. In Chapter 4, we discusse the existing stabilization methods. Also, we propose a new method, which represents a signiftcant technical improvement in the area, mainly if the goal is a tradeoff between computational complexity and numerical stability. A series of simulation results and comparisons between the new method and the existing ones are presented in Chapter 5 with the objective of validating the proposed methodas an adequate tool to prevent the numerical instability in the fast least square algorithms / Doutorado / Doutor em Engenharia Elétrica

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

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.

En este trabajo de tesis se muestra el diseño de una nariz electrónica con 6 sensores semiconductores (Figaro), donde dicha matriz de sensores se hace indispensable debido a que la discriminación de olores no se determina por la particularidad de un sensor sino de su interpretación en conjunto. El diseño de la nariz electrónica consta de (1) una etapa de acondicionamiento de flujo de aire, (2) una cámara de muestra, (3) una cámara de medida y (4) una etapa de captura y procesamiento de datos. El sistema esta caracterizado para trabajar en condiciones de 20° ± 2 °C, 65 ± 5% R.H., sin estas condiciones no se puede efectuar una medición. Parte de su construcción está hecha con accesorios de acero inoxidable para reducir toda posible interferencia. Asimismo, la matriz de sensores está diseñada de una manera, para poder reemplazar rápidamente un sensor por motivo de mantenimiento, o colocar otros tipos de sensores para una investigación futura que requiera otros parámetros. El procesamiento de datos de la nariz electrónica fue realizado mediante el uso de Redes Fuzzy ARTMAP y Algoritmos Genéticos. Donde, se desarrolló una operación de entrenamiento de la Red Neuronal, para discriminar y/o clasificar olores de alcohol, vino, jugo de naranja y cerveza. El número total de variables utilizadas fue 60, de los 6 sensores utilizados (10 parámetros extraídos por cada sensor). Tal conjunto de variables fue utilizado para dos tipos de clasificación; la primera clasificación, empleando sólo las Redes Fuzzy ARTMAP que dieron como resultado una clasificación del 100% con un valor de Wija = 474,4247 (parámetro que mide el grado de dificultad computacional); y, en una segunda clasificación, utilizando selección de variables (con Algoritmos Genéticos) y Redes Fuzzy ARTMAP obteniendo una clasificación al 100%, pero con un valor de Wija igual a 5,7 y utilizando una sola variable de un solo sensor. Entonces se concluye que con esta selección de variables se reducen costos y tiempo computacional, debido que con un solo sensor podemos discriminar los 04 olores mencionados anteriormente.

Made available in DSpace on 2019-04-05T23:01:10Z (GMT). No. of bitstreams: 0 Previous issue date: 2003-08-01 / Many real world entities can be represented by a combination of discrete and continuous attributes. In domains with this kind of representation, concept formation systems have a problem due to the use of different evaluation functions for each type of attribute. In this dissertation, this problem is analyzed specifically in probabilistic concept formation systems (PCFS). In such systems, the evaluation function for discrete and continuos attributes has different behavior which results in an unbalanced contribution for each attribute-type evaluation function inside the main evaluation function. Indeed, a bias occurs in hierarchy building, affecting directly the quality of the generated concepts. Basically, this work studies the quality of the generated concepts in terms of its predictability. Since PCFS are generally incremental, they change concept prdicatability for each new entity analyzed. This work describes an approach based on the difference between the individual predictability gain for each attribute type. Indeed, it also favors the creation of concept hierarchies that maximize the individual predictability gain for each attribute. This approch means a way to work around the unbalanced contribution problem in attribute-driven evaluation functions environments. Experiments using the approach presented here have shown higher quality concepts, in terms of predictability, when compared with related works. / Muitas entidades do mundo real podem ser representadas através da combinação de atributos discretos e contínuos. O problema básico da formação de conceitos, em domínios com esta representação, deve-se ao uso de diferentes funções de avaliação para cada tipo de atributo. Nesse trabalho, esse problema será analisado especificamente em sistemas de formação de conceitos probabilísticos (SFCP). A análise do problema aponta diferentes comportamentos para as funções de avaliação dos atributos discretos e contínuos. Essa diferença resulta numa participação desbalanceada das funções de avaliação, para cada tipo de atributo, na função de avaliação geral. Isso, conseqüentemente, gera uma tendência na criação da hierarquia, afetando diretamente a qualidade dos conceitos gerados. Basicamente, este trabalho se concentra em estudar a qualidade dos conceitos em termos da capacidade de inferência dos mesmos. Em SFCP, devido o caráter incremental dos mesmos, a cada nova entidade classificada a capacidade de inferência dos conceitos sofre modificações. Essas modificações são de diferente intensidade para cada tipo de atributo. A proposta de solução desse trabalho está baseada no ganho individual de capacidade de inferência para cada tipo de atributo, discretos e contínuos. Assim, busca-se a criação de uma da hierarquia de conceitos que também promova o maior ganho em capacidade de inferência para cada tipo de atributo. A abordagem aqui proposta constitui uma forma de contornar a predominância na função de avaliação geral. Experimentos realizados para medir a qualidade dos conceitos gerados pela proposta apresentada mostraram resultados superiores em comparação com trabalhos similares.