Orientador: Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-14T18:03:51Z (GMT). No. of bitstreams: 1 Euzebio_MarcosJoseCandido_M.pdf: 2101753 bytes, checksum: a1464738af508bc0a32d3aec71592a14 (MD5) Previous issue date: 1987 / Resumo: O objetivo deste trabalho é apresentar uma descrição da implementação de um protótipo para o RSA: o PRSA. O RSA é um sistema criptográfico de chave pública e tem sido reconhecido como uma das idéias mais brilhantes que apareceram nos últimos anos na área da criptografia. Sua implementação traz uma série de desafios, dentro de um espectro que vai da Teoria dos Números à. Análise de Complexidade de Algoritmos. A implementação de um protótipo para o RSA serve para estudar os gargalos que tornam a utilização prática do sistema inviável hoje em dia, mas além disso, permitiu o estudo de vários problemas correlatos à implementação do RSA, que se apresenta como um fértil campo para pesquisas. Este trabalho está organizado em três capítulos, onde são expostos vários aspectos da implementação do protótipo e cinco apêndices. No capítulo 1 são feitas algumas considerações a respeito de conceitos básicos de criptografia, com intenção de situar o contexto principal em que o trabalho foi feito. São feitas algumas definições gerais de sistemas criptográficos e é apresentado o RSA. O capítulo 2 se constitui dos principais algoritmos utilizados na implementação do programa. Além. dos algoritmos mais de alto nível em geral encontrados em artigos e livros da área, tentou-se apresentar alguns pontos a respeito da geração de números aleatórios e da aritmética de números de precisão múltipla. Já o capítulo 3 contém informações mais específicas do protótipo. É apresentada a organização modular do programa e a forma. de representação interna dos números de precisão múltipla. Além disso são mostrados dois testes de desempenho do protótipo: 1) Velocidade de ciframento e deciframento e 2) Eficiência da geração de números primos. Estas duas operações são as mais importantes na implementação do RSA. É falado também de algumas experiências feitas para permitir uma maior visualização práqca do desempenho do algoritmo de Rabin para teste de primalidade. Finalmente nos apêndices podem ser encontrados demonstrações de uso do PRSA, tabelas de números primos e uma descrição mais pormenorizada dos módulos componentes do programa. / Abstract: The main goal of this work is to present a description of the implementation of a prototype of the RSA criptosystem. The RSA is a public key cipher and has been considered one of the best inventions. in the last years in the criptography area. Its implementation brings a lot of problems, ranging from Number Theory to Analysis of Complexity of AIgorithms. The implemented proiotype was used to investigate some computing bottlenecks that make the practical use of the RSA criptosystem not interesting today, and to study others problems that arise in the implementation. This work is divided in three chapters and tive appendixes. In Chapter 1, in order to show the context where the work was made, are presented some" basic concepts of criptography. The RSA is described in this chapter too. The chapter 2 is formed with the main algorithms that the program use. There are some algorithins more easily found in criptography literature and some commonly found in seminumerical-algorithm literature. Chapter 3 describes other aspects of the program. There are informations about the way multiple precision numbers are represented internally by the program, one overview of the organization of the program modules and some tests made with the prototype in three machines: PC, VAX - 785 and D - 8000. . The appendixes contain some results obtained by the prototype and some demonstrations of its use. / Mestrado / Mestre em Ciência da Computação

Orientador : Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-14T19:20:08Z (GMT). No. of bitstreams: 1 Gomes_MarciaAparecida_M.pdf: 1272549 bytes, checksum: 9056c206ee1973c9ef5f560cca5419a3 (MD5) Previous issue date: 1981 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

Orientador : Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-17T11:16:35Z (GMT). No. of bitstreams: 1 Jacometti_WelsonRegis_M.pdf: 4160475 bytes, checksum: 914752317c391c2d889ba8be86393cd4 (MD5) Previous issue date: 1992 / Resumo: Esta tese discute o projeto e a implementação de um ambiente de programação voltado para o desenvolvimento de algoritmos e estruturas de dados em Geometria Computacional chamado Geolab. Este ambiente provê o suporte necessário para a implementação de algoritmos geométricos através de uma biblioteca de objetos geométricos básicós e de um conjunto significativo de algoritmos fundamentais como algoritmos para construção de envoltórias convexas, diagramas de Voronoi, árvores espalhadas mínimas, etc. Tanto o conjunto de objetos básicos como o de algoritmos fundamentais podem ser ampliados através de mecanismos do ambiente que permitem que novas construções sejam incorporadas dinamicamente. O ambiente dispõe ainda de ferramentas que permitem a inclusão dinâmica de novos modos de operação junto à sua interface, complementando a gama de facilidades para o desenho de novos objetos (ou variações para os objetos já existentes) e a implementação de algoritmos geométricos dinâmicos ou que realizam preprocessamento. Objetos e algoritmos geométricos são mapeados em classes em C++ que especificam protocolos para sua manipulação pelo ambiente. Novas entidades interagem homogeneamente com o ambiente satisfazendo estes protocolos. Algoritmos geométricos podem ser animados. Animação per se é conseguida graças à introdução de código adicional no corpo dos algoritmos, através do qual o ambiente permite controla.ra velocidade e o nível de detalhes de uma animação. Existe também um outro tipo de animação, chamado dynamic move, conseguida através de um dos modos funcionais do Geolab e que consiste na execução repetitiva de um algoritmo enquanto sua entrada sofre modificações / Abstract: Not informed / Mestrado / Mestre em Ciência da Computação

Orientador: João Mauricio Rosario / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-07-19T07:21:01Z (GMT). No. of bitstreams: 1 Campos_Renatode_M.pdf: 2398471 bytes, checksum: d6570ac727261d27c8ef8113a5b5af07 (MD5) Previous issue date: 1993 / Resumo: Atualmente, as tarefas a serem executadas por robôs estão se tornando mais complexas. Nesse contexto encontra-se, por exemplo, a integração de robôs aos sistemas CIM (Computer Integrated Manufaturing), e a necessidade de se definir trajetórias matematicamente, via um sistema CAD (programação off-line), sendo inviável a programação por aprendizagem. Com a programação off-line, a exatidão do sistema robótico torna-se essencial para o sucesso da operação programada. Este trabalho visa o estudo e implementação de um procedimento para. estimativa de parãmetros geométricos e calibração para robôs, consistindo basicamente de quatro fases: 1. Modelagem geométrica do sistema robótico e de seu erro através do jacobiano de sua matriz de posicionamento; 2. Sequência de medidas de posicionamento por um sistema externo; 3. Estimativa de parãmetros através de um algoritmo que tem como entrada as medidas geradas na segunda fase e um valor inicial arbitrário para os parãmetros, que-deve convergir usando o critério de mínimos quadrados; 4. Implementação dos valores dos parãmetros estimados no software de controle e programação off-line do robô. São realizadas simulações do algoritmo de estimativa, onde é analisado a influência de variáveis do procedimento, com relação à precisão na estimativa. É efetuado um experimento prático de estimativa dos parâmetros do robô MANUTEC r3, tendo como dispositivo de medidas, uma mesa tridimensional. É realizado um outro procedimento visando a estimativa de parâmetros do mesmo robô, porém com as medidas feitas através de uma ferramenta e peça de calibração dedicada para esta finalidade. Os resultados obtidos utilizando-se estes dois dispositivos são comparados. São propostas duas diferentes soluções visando a correção de erros de posicionamento entre um robô e seu painel de operação em intervenções submarinas / Abstract: Not informed. / Mestrado / Mestre em Engenharia Mecânica

Ingeniero Civil en Computación / La resolución de diversos problemas en ciencia e ingeniería, requiere el apoyo de soluciones y herramientas computacionales que permitan representar, visualizar y modelar sus objetos de estudio, como superficies, terrenos o células. Una forma de representar estos objetos es mediante el uso de mallas geométricas, sobre las cuales se realizan operaciones y simulaciones para modelar los problemas inherentes a cada disciplina. Uno de los principales problemas asociados a trabajar con mallas geométricas, es el tiempo que demoran en ser procesadas. Con el auge de las tarjetas y procesadores gráficos (GPU), se han investigado nuevas técnicas que permitan usar el poder de computo de estas unidades, para desarrollar e implementar estos algoritmos. Actualmente se cuenta con una librería (llamada Cleap), la cual permite realizar la operación de triangulación de Delaunay en Paralelo usando GPU s de marca Nvidia. A ella, se desea integrar otros algoritmos que trabajen con mallas geométricas, como algoritmos de suavizado y simplificación, además de comparar su rendimiento y calidad con otras implementaciones ya existentes. En este trabajo, se investigó sobre algoritmos de suavizado, triangulación y simplificación de mallas geométricas, y luego se implementaron versiones de los dos primeros, los cuales fueron integrados en Cleap, y se comparó el rendimiento y calidad de sus soluciones. Con respecto al algoritmo de simplificación, solo se llegó hasta la fase de investigación teórica, pero se obtuvo la información y conocimientos necesarios para implementar e integrar una versión de este algoritmo. Los resultados muestran que el uso de la GPU permite reducir considerablemente los tiempos de ejecución, cuando se trabaja con mallas de gran tamaño, en comparación a sus contrapartes secuenciales, y que la calidad de sus resultados es similar o incluso mejor a la de las implementaciones conocidas actualmente. Estos resultados también muestran que no siempre lo que se espera teóricamente, ocurre en la práctica, debido a problemas y fallos que ocurren al realizar cálculos con error asociado, y detalles particulares asociados a una arquitectura o plataforma determinada.

A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista.

A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista.

Resumo: Este trabalho propõe algoritmos determinísticos que, dado um conjunto com n chaves, constroem em tempo esperado O(n) uma função hash com tempo de busca no pior caso O(1), a qual mapeia sem colisão as chaves para o conjunto {0, . . . , n-1}. Esses esquemas de hashing perfeitos e mínimos são meras variantes dos esquemas aleatorizados de Botelho, Kohayakawa e Ziviani (2005) e Botelho, Pagh e Ziviani (2007) e mostraram resultados empíricos equivalentes aos dos algoritmos originais. As variantes determinísticas foram implementadas a partir dos códigos dos esquemas originais desenvolvidos na biblioteca CMPH pelos próprios autores, a qual é mantida no SourceForge.net. Todos os esquemas foram alimentados com os mesmos conjuntos de chaves, para que pudessem ser comparados com justiça. Foram executados testes para conjuntos com até 25 000 000 de chaves. Ademais, os esquemas propostos contam evidentemente com a vantagem de sempre produzirem a mesma hash para um mesmo conjunto de chaves. Esse comportamento determinístico pode ser útil para o desenvolvimento dum esquema dinâmico de hashing, em que figuram operações como inserção e deleção de chaves, inspirado num dos excelentes esquemas estáticos abordados. Um dos esquemas de Botelho, Pagh e Ziviani (2007), por exemplo de excelência, constrói hashes representáveis por apenas aproximadamente 2,62 bits por chave. Tal resultado é muito próximo da cota inferior justa conhecida, de aproximadamente 1,44 bits por chave. Tanto as versões determinísticas propostas quanto as originais mostram-se práticas para aplicações reais de Hashing. No entanto, na fundamentação teórica do trabalho de Botelho, Kohayakawa e Ziviani (2005) ainda restava uma conjectura. A presente dissertação também propõe uma demonstração para a conjectura e encerra a corretude do esquema.

A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista.

Orientador : Prof. Dr. Luis Carlos Erpen de Bona / Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 10/09/2015 / Inclui referências : f. 97-101 / Resumo: O algoritmo Barnes-Hut é um método aproximado amplamente usado para na simulação gravitacional de N-Corpos, que envolve a construção e eaminliamento de árvores esparsas a cada passo de simulação e assim reduzindo a complexidade computacional e possibilitando a solução de problemas práticos de grande escala, A natureza irregular desse código de eaminliamento em árvore apresenta desafios interessantes na sua computação em sistemas paralelos. Desafios adicionais ocorrem nesse tipo de padrão de computação paralela quando se deseja utilizar de maneira eficaz a capacidade computacional de arquiteturas de GPUs (processadores gráficos multieore de propósito geral), Oetrees são estruturas de dados que representam de maneira eficiente as informações de dados espaciais em várias áreas tais como computação científica, computação gráfica, processamento de imagens, dentre outras. Nosso enfoque nesse trabalho é de tratar explicitamente os padrões dinâmicos irregulares de acesso a dados em memória com o remapeamento de dados e transformações de lavouts, dependendo das estruturas acessadas. Também é feito o controle explicito, por programa, de fluxos divergentes de execuções em threads. Apresentamos uma nova estrutura de dados compacta para lavouts de oetrees esparsas, bem como algoritmos paralelos para GPUs, tanto para transformações de lavouts como para eaminliamento paralelo usando a técnica de simulação de "warps"-largos (SWW, Simulated Wide-Warps), Os benefícios de nossas técnicas ocorrem devido à transposição do algoritmo de eamin- nhamento na árvore para execução em padrões mais regulares, possibilitando uma melhor adaptação ao modelo GPU paralelo, A estrutura de dados permite explorar localidades de acessos à memória durante os percursos, ao mesmo tempo conservando espaço em memória eaehe ou em memória compartilhada (scratchpad). Desta forma a memória rápida intra-eore pode ser dedicada a acelerar eaminliamentos. Controle divergência de fluxos também é delimitado de maneira algorítmica, impondo uma execução uniforme na maior parte dos segmentos de execução. Nossos experimentos mostram melhoria de desempenho significativa em relação às soluções em GPU mais conhecidas para este algoritmo. Desenvolvemos um novo algoritmo paralelo eficiente que gera diretamente de uma só vez as oetrees implícitas comprimidas, como um método massivamente paralelo. Este método traz uma nova visão para tratar de forma eficiente com a natureza irregular também presente na construção de oetrees esparsas, O algoritmo proposto de geração massivamente paralela de oetrees esparsas tem aplicação imediata em nossa implementação GPU paralela da simulação Barnes-Hut e em outros métodos de N-eorpos, As técnicas e algoritmos propostos nesta tese também poderão ser aplicadas em outros contextos. Palavras-chave: Algoritmo Massivamente Paralelo para Geração de Octrees; Octrees esparsas; Octree implícita; Probleamas de N-Corpos; Barnes-Hut; GPGPIJ; WarpsLargos Simulados em Software; CIJDA; Algoritmo Paralelo irregular; Algoritmos paralelos; Manycore Computing; Acelerador de Computação; / Abstract: The Barnes-Hut algorithm is a widely used approximation method for the N-Body simulation problem, which involves the construction and traversal of sparse trees at each simulation step and thus reducing the complexity to solve large/praetieal problems. The irregular nature of this tree walking code presents interesting challenges for its computation on parallel systems. Additional problems arise in effectively exploiting the processing capacity of GPU architectures. Octrees are data structures that efficiently represent spatial data in many fields such as scientific computing, computer graphics and image processing, among others. In this work we explicitly deal with dynamic irregular patterns in data accesses with data remapping and data transformation, depending on the data structures being accessed, and by controlling the execution flow divergence of threads. We present a new compact data-strueture for sparse octree layouts, and also GPU parallel algorithms for tree transformation and parallel walking using software Simulated Wide-Warps (SWW), Benefits of our techniques are in transposing the tree algorithm to execute regular patterns to match the GPU parallel model. The data structure allows exploring localities during traversals, at the same time conserving space in caches or scratchpad memory. This way fast intra-eore memory can be dedicated to speed up traversals. Control flow divergence is also algorithmically constrained, enforcing a mostly uniform execution of threads. Our experiments show significant performance improvement over the best known GPU solutions to this algorithm. We have developed a novel efficient parallel algorithm that directly generates entire compressed implicit octrees at once, as a massively parallel method. This method brings new insight on how to efficiently deal with the irregular nature of algorithms for constructing sparse octrees. The proposed algorithm has immediate application to our GPU parallel Barnes-Hut implementation and other N-Body methods. We envision that the techniques and algorithms proposed in this dissertation can also be applied in other contexts. Keywords: Massively Parallel Octree Generation Algorithm; Sparse Octrees; Implicit Octree; N-Body; Barnes-Hut; GPGPU; Software Simulated Wide-Warp; CUDA; Irregular Parallel Algorithm; Parallel algorithms; Many core Computing; Accelerator Computing;