Orientador: Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T16:09:33Z (GMT). No. of bitstreams: 1 Westrupp_RodrigoBittencourt_M.pdf: 8956528 bytes, checksum: 799d2f354f5bf1cebe0535350cf9622b (MD5) Previous issue date: 1999 / Resumo: Nesta dissertação, apresentamos uma generalização do diagrama de Voronoi: consideramos diagramas de Voronoi de ordem k no plano projetivo orientado T². Este espaço admite retas orientadas assim como muitos outros conceitos geométricos fundamentais de maneira consistente. Neste contexto, demonstramos várias propriedades de diagramas de Voronoi, algumas delas intrínsecas a T². Por exemplo, o diagrama de Voronoi de ordem k de um conjunto de n sítios em T² tem um número exato de regiões e é antípoda do diagrama de Voronoi de ordem n - k do mesmo conjunto de sítios, para todo k : 1 < k < n. Finalmente, apresentamos uma generalização, de R² para T², de dois algoritmos para construção de diagramas de Voronoi de ordem k. O primeiro algoritmo constrói os diagramas de Voronoi de todas as ordens para busca dos k vizinhos mais próximos, em tempo e espaço ótimos; enquanto o segundo é um algoritmo incremental randomizado on-line para construir o diagrama de Voronoi de cada ordem, independentemente. Para este segundo algoritmo, apresentamos um novo método para localização de pontos, o qual reduz a complexidade de tempo por um fator logarítmico e que é muito mais simples que o original. / Abstract: In this dissertation, we present a generalization of the Voronoi diagram: we consider order k Voronoi diagrams in the oriented projective plane T². This space handles oriented lines as well as many other fundamental geometric concepts in a consistent way. In this context, we show several properties of Voronoi diagrams, some of them intrinsic to T². For example, the order k Voronoi diagram of a set of n sites in T² has an exact number of regions. Furthermore, this diagram is antipodal to the order n - k Voronoi diagram of the same set of sites, for all k : 1 < k < n. Finally, we present a generalization, from R² to T², of two algorithms for constructing order k Voronoi diagrams. The first one constructs all Voronoi diagrams for k nearest neighbor search, in optimal time and space, and the other is an on-line randomized incremental algorithm for constructing each order k Voronoi diagram, independently. For this second algorithm, we present a new method for point location which improves the time complexity by a logarithmic factor and which is much simpler than the original one. / Mestrado / Mestre em Ciência da Computação

Estendemos o trabalho de Vincent Rijmen e Joan Daemen na estratégia de trilha larga, uma metodologia de projeto para primitivas criptográficas simétricas eficientes e demonstravelmente resistentes às técnicas de criptanálise diferencial e linear. Preocupamo-nos principalmente com a melhoria na eficiência de primitivas projetadas de acordo com a estratégia de trilha larga. Investigamos duas linhas distintas de pesquisa: a aplicabilidade da técnica de bitslicing à implementação em software de primitivas baseadas na estratégia de trilha larga; e o projeto de S-boxes estruturadas com implementação eficiente em hardware e bitslicing, e especificamente, o uso de S-boxes invariantes por rotação, que exibem propriedades vantajosas para implementação. Também implementamos e otimizamos algumas primitivas criptográficas em plataformas de software selecionadas, para substanciar e aprimorar as afirmações de eficiência da estratégia de trilha larga. Ademais, aplicamos nosso conhecimento e técnicas propostas ao projeto de novas primitivas criptográficas altamente eficientes, em particular a função de hash MAELSTROM-0 e a cifra de bloco legada FUTURE. / We extend the work of Vincent Rijmen and Joan Daemen on the Wide Trail strategy, a design methodology for symmetric-key cryptographic primitives which are efficient and provably secure against differential and linear cryptanalysis. We concern ourselves mainly with improving the efficiency of primitives designed according to the Wide Trail strategy. To that end, we investigate two distinct lines of research: the applicability of the bitslicing technique to the software implementation of primitives based on the Wide Trail strategy; and the design of structured S-boxes with efficient implementation in hardware and bitslicing, and specifically, the use of rotation-symmetric S-boxes, which exhibit advantageous implementation properties. We also perform general implementation and optimization work on selected software platforms, to further realize the claims of efficiency of the Wide Trail strategy. Additionally, we apply our expertise and proposed techniques to the design of new highly-efficient cryptographic primitives, in particular the hash function MAELSTROM-0 and the legacy-level block cipher FUTURE.

Orientadores : Fernando Jose von Zuben, Fernando Gomide / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-01T05:02:44Z (GMT). No. of bitstreams: 1 Delgado_MyriamRegattieriDeBiasedaSilva_D.pdf: 4765721 bytes, checksum: f60332f2cb99a4765a8c89304a3faadb (MD5) Previous issue date: 2002 / Doutorado

Orientador : Kil Jin Park / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Agricola / Made available in DSpace on 2018-08-01T06:51:59Z (GMT). No. of bitstreams: 1 Alonso_LuisFelipeToro_D.pdf: 3489017 bytes, checksum: 74f7e25fc15f5c6b3d02144988c92cf2 (MD5) Previous issue date: 2001 / Doutorado

Made available in DSpace on 2014-06-12T18:34:09Z (GMT). No. of bitstreams: 2 arquivo994_1.pdf: 594849 bytes, checksum: bae437699c217a484a971da9a8e6c683 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O problema de Fatorização de Inteiros, assim como os outros em NP, pode ser reduzido em tempo polinomial para o problema de Satisfabilidade, devido ao Teorema de Cook. O problema de Satisfabilidade, por sua vez, pode ser reduzido facilmente ao problema de Programação Inteira. Este trabalho apresenta uma dessas reduções, isto é, Fatorização &#1048576;! Programação Inteira e algumas particularidades encontradas. Obtemos uma redução de ordem O(n2) no número de dígitos binários de um inteiro N a ser fatorado e, além disso, encontramos algumas propriedades locais da matriz final que podem auxiliar um possível estágio de pré-processamento

Orientador: Neucimar Jeronimo Leite / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-25T05:06:21Z (GMT). No. of bitstreams: 1 Silva_LuizEduardoda_M.pdf: 9237961 bytes, checksum: 8c346a17336b4f823de92d2b4a21eb19 (MD5) Previous issue date: 1999 / Resumo: Esta dissertação apresenta um algoritmo para combinar duas imagens coloridas, contendo uma região de interseção em comum, através de um método denominado fotomosaico. A combinação das imagens é estabelecida a partir de uma linha de costura que não deve ser perceptível a um observador e que determina onde uma imagem começa e a outra termina. O algoritmo apresentado neste trabalho é baseado nas transformações morfológicas de linha divisora de águas (watershed) e reconstrução. / Abstract: This work introduces an algorithm for combining two color images with common intersection region by a method named photomosaicking. In this method, we search for a non-perceptible seam line which indicates in the final photomosaic where one image begins and other one ends. The algorithm presented here is based mainly on the watershed and reconstruction morphological transformations. / Mestrado / Mestre em Ciência da Computação

Orientador: Jorge Stolfi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-25T10:03:56Z (GMT). No. of bitstreams: 1 Andrade_MarcusViniciusAlvim_D.pdf: 7188017 bytes, checksum: 2bebda4708b2cb122cfd9a807ac2f471 (MD5) Previous issue date: 1999 / Resumo: Neste trabalho desenvolvemos um conjunto de ferramentas para a representação e manipulação exatas de mapas esféricos (mapas sobre a esfera formados por arcos de círculos, não necessariamente máximos) adequados para a implementação de sistemas de informações geográficas (SIGs). Na primeira parte deste trabalho, descrevemos a estrutura de dados SMC (Spherical Maps by Corners) para representar a topologia de mapas esféricos. Esta estrutura permite a representação de mapas bastante gerais, incluindo arestas ovais (não incidentes a nenhum vértice), vértices isolados (não incidentes a nenhuma aresta), e faces com múltiplas bordas. Definimos também um conjunto de operadores topológicos para construir, percorrer e modificar esta estrutura. Na segunda parte, definimos os círculos racionais, um subconjunto denso dos círculos sobre a esfera S2 que podem ser representados de maneira exata. Baseados neste conceito, definimos representações exatas para pontos e arcos de círculos na esfera, sendo que o conjunto dos pontos representáveis exatamente (os pontos sub-racionais) inclui todos os pontos de interseção entre círculos racionais. Desenvolvemos também algoritmos exatos para as operações geométricas básicas sobre círculos racionais, incluindo interseção, posição relativa, ordenação de pontos sobre um círculo e ordenação de círculos em torno de um ponto. Na terceira parte, baseados nos resultados descritos nas duas partes anteriores, desenvolvemos algoritmos exatos para localização de pontos num mapa esférico, e para sobreposição de dois mapas esféricos. Observamos também que boa parte das operações geométricas usadas em SIGs (por exemplo, interseção de regiões, localização de pontos, extração de detalhes, recortes) podem ser reduzidas a problemas de sobreposição. Finalmente, mostramos que este conjunto de ferramentas é econômico e eficiente o bastante para servir de base para a implementação de SIGs. Todos os algoritmos apresentados neste trabalho foram implementados (em Modula-3) na forma de uma biblioteca genérica para a representação e manipulação exatas de mapas esféricos / Abstract: In this dissertation we develop a tool kit for the exact representation and manipulation of spherical maps (maps on the sphere composed by arcs of circles, not necessarily geodesic ones), suitable for the implementation of geographical information systems (GIS). Firstly, we describe the data structure SMC (spherical maps by corners) which we developed to represent the topology of spherical maps. It allows the representation of fairly general maps, including maps that have oval edges (not incident to any vertex), isolated vertices (not incident to any edge), and faces with multiple borders. We also define a set of topological operators to build, traverse and modify this structure. Secondly, we define the rational circles, a dense subset of circles on the sphere S2 which can be exactly represented. Based on this concept, we develop an exact representation of points, circles and circular arcs on the sphere, such that the set of exactly representable points (sub-rational points) includes all points of intersection of two rational circles. We also develop exact algorithms for basic geometric operations with rational circles, including intersection, relative position, circular ordering of points on rational circles, and circular ordering of circles around a point. Thirdly, we use these tools to develop exact algorithms for point location on spherical maps, and to compute the overlay of two spherical maps. We note that most geometric operations used in GIS (region intersection, point location, feature extraction, clipping etc) can be reduced to map overlay. Finally, we show that the proposed tool kit is economical and efficient enough to be used as the basis for the implementation of a GIS. All algorithms described in this text were implemented (in Modula-3) as a general-purpose library for the exact representation and manipulation of spherical maps / Doutorado / Doutor em Ciência da Computação

Orientador: Clovis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-25T20:11:39Z (GMT). No. of bitstreams: 1 VillasBoas_FernandoRocha_D.pdf: 2584878 bytes, checksum: a86558e66dd32b2c2a27f0fcdc53b888 (MD5) Previous issue date: 2000 / Resumo: Nesse trabalho estudamos, no contexto de métodos de pontos interiores para programação linear, algumas possíveis vantagens de se adiar as escolhas do parâmetro de penalização e do tamanho de passo, que ocorrem tanto quando usamos o método de Newton para resolver o sistema de Karush-Kuhn- Thcker, como quando aplicamos um esquema preditor-corretor. Nós mostramos que, tanto para um passo de Newton quanto para um passo preditor-corretor, o próximo iterando pode ser expresso como uma função linear do parâmetro de penalização J1 e, no caso de um passo preditor-corretor, como uma função quadrática de J1. Mostramos também que essa parametrização é útil para garantir, por exemplo, a não-negatividade do próximo iterando ou sua proximidade da trajetória central. Resultados computacionais dessas estratégias são apresentados e comparados com PCx, uma implementação do método preditor-corretor de Mehrotra / Abstract: We study, in the context of interior-point methods for linear programming, some possible advantages of postponing the choice of the per. ",lty parameter and the step length, which happens both when we apply Newton's method to the Karush-Kuhn-Thcker system and when we apply a predictor-corrector scheme. We show that for a Newton or a strictly predictor step the next iterate can be expressed as a linear function of the penalty parameter J1, and, in the case of a predictor-corrector step, as a quadratic function of J1. We also show that this parameterization is useful to guarantee either the non-negativity of the next iterate or the proximity to the central path. Computational results of these strategies are shown and compared with PCx, an implementation of Mehrotra's predictor-corrector method / Doutorado / Doutor em Matemática Aplicada

Orientador: Wagner C. Amaral / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-13T23:48:07Z (GMT). No. of bitstreams: 1 Nazzetta_RubenMario_M.pdf: 10450932 bytes, checksum: 00ecca7925c1cfde8dd3935e1d1de96a (MD5) Previous issue date: 1991 / Resumo: O presente trabalho detalha o desenvolvimento de um sistema baseado em conhecimento para o auxílio nas tarefas de configuração e supervisão de algoritmos de modelagem e controle de processos. O sistema consta dos seguintes módulos: Módulo de controle onde encontram-se os algoritmos de controle, de três termos (PID), de Variância Mínima Generalizada (GMV) e o Controlador Preditivo Generalizado (GPC); Módulo de identificação com o algoritmo de matriz estendida; Módulo de detecção de não estacionariedades do processo, baseado no algoritmo do erro previsto; Máquina de inferência com encadeamento reverso, utilizada junto com a Base de Conhecimento de Configuração; Máquina de inferência com encadeamento direto, utilizada com a Base de Conhecimento de supervisão; Base de Dados; e Interface Homem-Máquina. A Base de Dados, acessível a ambas as máquinas de inferência é composta de fatos escritos em linguagem natural. As bases de conhecimento possuem a estrutura de regras de produção do tipo SE <<condição>> então <<conclusão>>. A máquina de inferência de configuração obtém os valores dos objetos utilizados nos algoritmos de controle e identificação para satisfazer os requisitos de desempenho especificados ... Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: Not informed. / Mestrado / Mestre em Engenharia Elétrica

Orientador : Clovis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica. / Made available in DSpace on 2018-07-13T23:49:57Z (GMT). No. of bitstreams: 1 Machado_ArleneFortunato_D.pdf: 7694121 bytes, checksum: 0d9d500491ffd36e83900ea3de723bc0 (MD5) Previous issue date: 1991 / Resumo: Este trabalho apresenta um estudo de uma generalização de um problema de seleção de vértices em digrafos e propõe a resolução deste problema através de métodos iterativos, em que em cada iteração, um problema de seleção é resolvido. A importância deste problema é devida ao seu relacionamento com alguns problemas clássicos de otimização (designação, bemparelhamento bipartido de custo máximo, fluxo de custo mínimo). É também, apresentado um estudo para um problema de seleção de vértices de um digrafo, estabelecendo relações entre este problema e o de b-emparelhamento máximo bipartido. Algoritmos para os problemas de b-emparelhamento máximo bipartido, seleção de vértices e seleção de vértices generalizada são desenvolvidos. Os algoritmos apresentados para um mesmo problema são comparados entre si / Abstract: A generalization of a vertex selection problem is presented and a resolution of this problem using an iterative method is proposed. A vertex selection problem is solved in each iteration of this method. The importance of this problem lies on its relationship to some classical optimization problems (assignment, maximum cost bipartite b-matching, minimum cost flow). A study of a vertex selection problem in a digraph is also presented. A relationship between this problem and the maximum bipartite b-matching problem is established. Algorithms to solve the maximum bipartite b-matching, the vertex selection and the generalized vertex selection problems are developed and the algorithms for each of the problems are compared. / Doutorado / Doutor em Engenharia Elétrica