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

Orientador: T.M. Viswanathan / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-14T18:55:37Z (GMT). No. of bitstreams: 1 Datta_Karabi_D.pdf: 1911726 bytes, checksum: 53a7f5d3f9aa2cb5a34874a76c56abb6 (MD5) Previous issue date: 1982 / Resumo: Não informado. / Abstract: Not informed. / Doutorado / Doutor em Matemática

Orientador: Roberto de Alencar Lotufo / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e Computação / Made available in DSpace on 2018-08-03T16:19:35Z (GMT). No. of bitstreams: 1 Zampirolli_FranciscodeAssis_D.pdf: 1636054 bytes, checksum: 4a735d10a69d449de502f78d4b02f2e8 (MD5) Previous issue date: 2003 / Doutorado

En el campo de la robótica, se han desarrollado distintos algoritmos y métodos con el objetivo de mejorar la interacción de los robots con las personas y con su entorno de trabajo en tiempo real; es así, como el sistema reacciona y evoluciona constantemente ante cambios que podrían ocurrir durante su funcionamiento. Para alcanzar los objetivos mencionados, una de las habilidades que se le confiere a la máquina es la capacidad de detectar, registrar y reconocer objetos. La presente tesis es un trabajo de investigación aplicada que tiene como objetivo desarrollar un procedimiento que permita a un sistema robótico reconocer y detectar objetos en tiempo real dentro de un entorno controlado; para ello, nos enfocamos en utilizar dos métodos conocidos de reconocimientos de objetos (métodos SIFT y SURF) con los cuales categorizaremos un objeto de un dominio predefinido y comparamos los resultados obtenidos. Se eligieron el método SIFT y el método SURF por la similitud en los pasos que siguen para obtener la información de un objeto; cabe resaltar que el método SURF es un método alterno al SIFT. Los resultados finales mostraron una mejor predicción en la categorización utilizando el método SIFT, pero ésta requería de mayor tiempo para extraer los puntos característicos de los objetos. Por otro lado, el método SURF generaba más puntos característicos de los objetos y en mejor tiempo. La extracción de puntos de interés se analizó en tiempo real; mientras, que la etapa de categorización no consideró este parámetro, sino la cantidad de puntos de interés necesarios para predecir con exactitud la categoría de un objeto. / Tesis

La presente tesis tiene por objetivo la elaboración de un algoritmo para el análisis cinemático inverso de mecanismos en el espacio, el cual abarcar mecanismos clásicos y mecanismos empleados en la actualidad, tales como brazos robóticos. Con el fin de realizar el análisis cinemático de diversos mecanismos usando el mismo algoritmo, se plantea el uso de un método iterativo para la evaluación de las ecuaciones de movimiento. En este proceso se usan los parámetros de Euler como sistema de coordenadas generalizadas, así como la pseudo-inversión para la resolución de la inversión del jacobiano y el método de Newton-Raphson como método de minimización. Además, se presenta una librería de juntas para el modelamiento de diferentes tipos de juntas entre eslabones, permitiendo el estudio de diversos mecanismos. El algoritmo se implementa en el programa de Matlab, emplea archivos tipo texto para el ingreso de información y ofrece una interfaz tipo GUI para la obtención de diversas gráficas requeridas por el usuario. Durante la elaboración del algoritmo se presentaron dificultades en la eliminación de restricciones redundantes y evasión de singularidades del mecanismo, en específico en mecanismos contenidos en un plano. Esta dificultad fue superada empleando modelos depurados por parte del usuario. Para la validación del algoritmo se desarrollaron dos ejemplos de aplicación, un mecanismo clásico Biela-Manivela-Corredera y un brazo robótico tipo esférico. Los resultados obtenidos en estos ejemplos usando el algoritmo implementado y los obtenidos por otros autores son similares, apreciándose una adecuada correspondencia en los valores de posición, velocidad y aceleración. El algoritmo elaborado e implementado presenta subrutinas específicas y una librería de juntas que pueden ser empleados en un programa para el análisis cinemático y dinámico de mecanismos espaciales a ser desarrollado en un futuro. / Tesis

No description available.

No description available.

Esse trabalho tem dois objetivos principais: o primeiro deles consiste em apresentar o estado da arte sobre processos de otimização combinatorial dando uma ênfase especial ao método Simulated Annealing (SA). São apresentados seu histórico, funcionalidades, algoritmo genérico e propostas de paralelização presentes na literatura. Além disso, é apresentado o algoritmo de geração de redes aleatórias contínuas, algoritmo, esse, projetado por pesquisadores do Instituto de Física da UFRGS que utiliza o método SA para gerar redes que atendam certas restrições. O segundo objetivo consiste empropor a paralelização desse algoritmo visando diminuir significativamente o tempo de geração de cada rede, que com o algoritmo seqüencial chega a demorar mais de um mês. Nessa etapa foi utilizada uma adaptação de um dos métodos propostos pela literatura juntamente com a técnica de divisão de domínio. Os resultados obtidos mostraram-se satisfatórios tanto em relação à qualidade numérica quanto à diminuição do tempo de processamento. Além disso, discute-se no trabalho a genericidade da proposta de paralelização a outros problemas baseados em SA. / This work has two main goals: the first one is to present the state of the art on combinatorial optimization processes, with a special emphasis to the Simulated Annealing (SA) method. The work presents its history, features, generic algorithm and proposed parallelization present in the literature. Moreover, the algorithm to generate random networks continued is presented. This algorithm was designed by researchers of the UFRGS Physics Institute and it uses the SA method. The second goal of this work is to propose a parallelization for this algorithm in order to decrease significantly the generation time of each network, that with the sequential algorithm reaches more than months. To do that was used an adaptation of one of the methods proposed by literature together with the domain partitioning technical. The results were satisfactory in terms of the numerical quality and in the decrease of the processing time. In addition, this work discusses the genericity of the proposed parallelization to other problems based on SA.

Made available in DSpace on 2016-08-29T15:33:23Z (GMT). No. of bitstreams: 1 tese_9295_Brenno Albino Lugon.pdf: 621313 bytes, checksum: fb6acacfa7bc1521bfdde981f176a251 (MD5) Previous issue date: 2015-11-06 / CAPES / Neste trabalho, utilizamos o algoritmo paralelo híbrido SPIKE um precondicionador para um método iterativo não estacionário combinando as arquiteturas de memoria distribuída e compartilhada,MPI e OpenMP. A fim de obter um bom precondicionador, resolvemos um conjunto de problemas combinatórios como reordenamentos e particionamento de grafos. Apresentamos os resultados avaliando a influencia de cada estrategia na  convergência e tempo de CPU do método iterativo.

Esse trabalho tem dois objetivos principais: o primeiro deles consiste em apresentar o estado da arte sobre processos de otimização combinatorial dando uma ênfase especial ao método Simulated Annealing (SA). São apresentados seu histórico, funcionalidades, algoritmo genérico e propostas de paralelização presentes na literatura. Além disso, é apresentado o algoritmo de geração de redes aleatórias contínuas, algoritmo, esse, projetado por pesquisadores do Instituto de Física da UFRGS que utiliza o método SA para gerar redes que atendam certas restrições. O segundo objetivo consiste empropor a paralelização desse algoritmo visando diminuir significativamente o tempo de geração de cada rede, que com o algoritmo seqüencial chega a demorar mais de um mês. Nessa etapa foi utilizada uma adaptação de um dos métodos propostos pela literatura juntamente com a técnica de divisão de domínio. Os resultados obtidos mostraram-se satisfatórios tanto em relação à qualidade numérica quanto à diminuição do tempo de processamento. Além disso, discute-se no trabalho a genericidade da proposta de paralelização a outros problemas baseados em SA. / This work has two main goals: the first one is to present the state of the art on combinatorial optimization processes, with a special emphasis to the Simulated Annealing (SA) method. The work presents its history, features, generic algorithm and proposed parallelization present in the literature. Moreover, the algorithm to generate random networks continued is presented. This algorithm was designed by researchers of the UFRGS Physics Institute and it uses the SA method. The second goal of this work is to propose a parallelization for this algorithm in order to decrease significantly the generation time of each network, that with the sequential algorithm reaches more than months. To do that was used an adaptation of one of the methods proposed by literature together with the domain partitioning technical. The results were satisfactory in terms of the numerical quality and in the decrease of the processing time. In addition, this work discusses the genericity of the proposed parallelization to other problems based on SA.