Orientador: Fernando Eduardo Torres Orihuela / 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-27T14:35:36Z (GMT). No. of bitstreams: 1 Paula_AnaRachelBritode_M.pdf: 1519694 bytes, checksum: 61b845f0f57e58e56f6a1f759fc9a382 (MD5) Previous issue date: 2015 / Resumo: A dissertação "Polinômios de Permutação e Palavras Balanceadas" tem como principal objetivo estudar a influência dos polinômios de permutação na teoria de códigos mediante o conceito de palavra balanceada. A base do trabalho é o artigo "Permutacion polynomials and aplications to coding theory" de Yann Laigke-Chapuy. Expomos os conceitos básicos de polinômios de permutação como algumas de suas características, exemplos e métodos para identificação dos mesmos. Em seguida trataremos dos códigos lineares com ênfase nos binários explorando particularmente a conjectura de Helleseth / Abstract: The main goal in writing this dissertation is the study of the influence of the Theory of Permutation Polynomials in the context of Coding Theory via the concept of balanced word. Our basic reference is the paper "Permutation polynomials and applications to coding theory" by Y. Laigke- Chapury. Our plan is to introduce the basic concepts in Coding Theory, Permutation Polynomials; then we mainly consider the long-standing open Helleseth¿s conjecture / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Recentemente, Barak et al. (2004) exibiram construções de extratores e dispersores determinísticos (funções computáveis em tempo polinomial) com parâmetros melhores do que era anteriormente possível. Introduziremos os conceitos envolvidos em tal trabalho e mencionaremos suas aplicações; em particular, veremos como é possível obter cotas muito melhores para o problema Ramsey bipartido (um problema bem difícil) utilizando as construções descritas no artigo. Também apresentamos resultados originais para melhorar tais construções. Tais idéias são inspiradas no trabalho de Anup Rao (2005) e utilizam o recente êxito de Jean Bourgain (2005) em obter extratores que quebram a \"barreira 1/2\". / Recently, Barak et al. (2004) constructed explicit deterministic extractors and dispersers (these are polynomial-time computable functions) with much better parameters than what was known before. We introduce the concepts involved in such a construction and mention some of its applications; in particular, we describe how it is possible to obtain much better bounds for the bipartite Ramsey problem (a very hard problem) using the machinery developed in that paper. We also present some original results that improve on these constructions. They are inspired by the work of Anup Rao (2005) and uses the recent breakthrough of Jean Bourgain (2005) in obtaining 2-source extractors that break the \"1/2-barrier\".

Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas. / A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.

A árvore de sufixos é uma estrutura dados, que representa em espaço linear todos os fatores de uma palavra, com diversos exemplos de aplicações práticas. Neste trabalho, definimos uma estrutura mais geral: a árvore de Ukkonen. Provamos para ela diversas propriedades combinatórias, dentre quais, a minimalidade em um sentido preciso. Acreditamos que a apresentação aqui oferecida, além de mais geral que as árvores de sufixo, tem a vantagem de oferecer uma descrição explícita da topologia da árvore, de seus vértices, arestas e rótulos, o que não vimos em nenhum outro trabalho. Como aplicações, apresentamos também a árvore esparsa de sufixos (que armazena apenas um subconjunto dos sufixos) e a árvore de k-fatores (que armazena apenas os segmentos de comprimento k, ao invés dos sufixos) definidas como casos particulares das árvores de Ukkonen. Propomos para as árvores esparsas um novo algoritmo de construção com tempo O(n) e espaço O(m), onde n é tamanho da palavra e m é número de sufixos. Para as árvores de k-fatores, propomos um novo algoritmo online com tempo e espaço O(n), onde n é o tamanho da palavra. / The suffix tree is a data structure that represents, in linear space, all factors of a given word, with several examples of practical applications. In this work, we define a more general structure: the Ukkonen\'s tree. We prove many properties for it, among them, its minimality in a precise sense. We believe that this presentation, besides being more general than the suffix trees, has the advantage of offering an explicit description of the tree topology, its vertices, edges and labels, which was not seen in any other work. As applications, we also presents the sparse suffix tree (which stores only a subset of the suffixes) and the k-factor tree (which stores only the substrings of length k, instead of the suffixes), both defined as Ukkonen\'s tree special cases. We propose a new construction algorithm for the sparse suffix trees with time O(n) and space O(m), where n is the size of the word and m is the number of suffixes. For the k-factor trees, we propose a new online algorithm with time and space O(n), where n is the size of the word.

O principal objetivo deste trabalho é estudar diversas aplicações de combinatória infinita em espaços de funções contínuas, definidas em espaços compactos Hausdorff. Usando combinatória infinita para uma álgebra de Boole, por meio da dualidade de Stone, obtemos um espaço compacto Hausdorff. Com certas propriedades na álgebra de Boole é possível analisar propriedades analíticas no espaço de funções contínuas definidas em tal espaço. Especificamente, analisamos a propriedade de Grothendieck. Também analisamos a relação entre o espaço de funções contínuas e o espaço compacto Hausdorff sobre o qual é definido. Apresentamos um resultado que permite obter diversos resultados conhecidos de uma maneira uniforme (só usando fatos de topologia e teoria de conjuntos), dotando o espaço de funções contínuas de uma ordem peculiar. Finalmente, estudamos um pouco de jogos topológicos mediante diversos exemplos. / The main purpose of this work is to study some infinite combinatorics applications in spaces of continuous functions, defined in Hausdorff compact spaces. Using infinite combinatorics in Boolean algebras, through Stone duality, we obtain a compact Hausdorff space. With certain properties in Boolean algebras it is possible to analyze analytic properties in the space of continuous functions defined in such space. Specifically, we analyze the Grothendieck property. We also analyze the relationship between the space of continuous functions and the compact Hausdorff space on which it is defined. We present a result that allows to obtain several known results in a uniform way (only using facts of topology and set theory), giving the space of continuous functions a peculiar order. Finally, we study some topological games through several examples.

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Entre os maiores desafios existentes para a cultura da soja, os estresses bióticos e abióticos se destacam e a incidência de patógenos como a ferrugem asiática, causam grandes perdas aos produtores. No Brasil, a ferrugem é a principal causa de prejuízos nas lavouras e estratégias para o seu controle mais eficiente são necessárias. O melhoramento genético para a tolerância constitui uma importante ferramenta para manter a ferrugem em níveis abaixo de dano econômico por um período mais duradouro. Outro aspecto importante da cultura da soja é relacionado com a sua utilização, destacando-se a produção de farelo com alto teor de proteína e de óleo comestível e combustível. Apesar de apresentar uma rica composição nutricional, o seu uso direto na alimentação humana ainda não é comum no Brasil. Uma das formas de incluir a soja na dieta é na forma de hortaliça, também conhecida como Edamame, em que as vagens são colhidas ainda verdes ou imaturas (estádio R6) e os grãos consumidos após breve cozimento. Contudo, poucos esforços têm sido dedicados para desenvolver novos genótipos com boa performance agronômica e adequados ao consumo humano. O presente trabalho teve o objetivo de avaliar genótipos de soja para a produção de soja hortaliça que apresentem tolerância à ferrugem. Para isto foram realizados cruzamentos entre seis genitores com boas características agronômicas em um esquema dialélico 6x6, gerando 15 cruzamentos. Estes genótipos foram avaliados nas gerações F2 e F3 para a produtividade e o tamanho das sementes, sendo que na geração F3, foram adicionados outros dez caracteres. Nas duas gerações, foi estimada a sua tolerância à ferrugem, utilizando manejos diferentes da doença com fungicidas. Foram realizadas análises de variância individuais e conjuntas, agrupamento de médias, análises dialélicas, tendo sido estimados os coeficientes de herdabilidade e correlações entre os caracteres. As análises mostraram a existência de variabilidade entre os genótipos avaliados e indicaram que os cruzamentos apresentaram desempenho superior aos genitores para caracteres importantes. O uso dos diferentes manejos da ferrugem com fungicidas mostrou-se eficiente uma vez que foi possível identificar genótipos tolerantes. Além disso, foram detectadas interações genótipos x ambientes significativas, fato que representou um desafio para a seleção dos melhores genótipos. Os genitores BRS 267, USP 13-66.136 e USP 13-19.007 destacaram-se por apresentar estimativas altas de capacidade de combinação e os cruzamentos USP 13-66.136 x USP 13-19.007, USP 13-66.136 x USP 13-19.034, BRS 267 x USP 13-19.007 e Tengamine x USP 13-19.007 apresentaram os melhores desempenhos. As estimativas de capacidade específica de combinação (Sii) dos genitores indicaram a existência de divergência entre eles e os caracteres apresentaram altas herdabilidades. A magnitude e a significância das correlações indicaram a possibilidade de seleção de genótipos precoces com sementes grandes e, também, evidenciaram que a seleção de genótipos com período mais longo entre R6 e R7 (SGR6) beneficia a produtividade. Portanto, foi possível identificar genitores e cruzamentos promissores para o desenvolvimento de novas linhagens apropriadas para a produção de soja hortaliça com tolerância à ferrugem. / Among the major challenges for soybean cultivation, biotic and abiotic stresses stand out and the incidence of pathogens such as Asian rust can cause extensive losses to farmers. In Brazil, rust is the main cause of crop damage and strategies for a more efficient control are necessary. Breeding for tolerance is an important tool to keep rust below economic damage for a longer period. Another important aspect of the soybean crop is related to its use, which is directed to the production of high-protein meal, edible oil and fuel. Although this legume has a rich nutritional composition, its direct use in the diet is still not common in Brazil. One of the ways to use soybean as food is in the form of vegetable, also known as Edamame, in which the pods are harvested green or immature (R6 stage) and the grains consumed after brief cooking. However, few efforts have been devoted to developing new soybean genotypes with good agronomic performance and characteristics suitable for human consumption. The present research had the objective of evaluating soybean genotypes for the production of vegetable soybean with rust tolerance. For this, crosses between six parents with good agronomic characteristics were performed in a 6x6 diallel scheme, generating 15 crosses. These genotypes were evaluated in the F2 and F3 generations for seed yield and size, and in the F3 generation, ten other traits were added. In both generations, tolerance to rust was estimated in experiments designed for different managements of the disease with fungicides. Individual and joint analyzes of variance, grouping of means, diallel analyzes, and estimation of heritability and correlation coefficients were performed. The analyzes showed the existence of variability among the evaluated genotypes and indicated that the crosses presented superior performance to the parents for important traits. The use of different rust managements with fungicides was efficient, since it was possible to identify tolerant genotypes. In addition, significant genotypes x environments interactions were detected, a fact that represented a challenge for the selection of the best genotypes. The parents BRS 267, USP 13-66136 and USP 13-19007 stood out for presenting high estimates of general combining ability and the crosses USP 13-66136 x USP 13-19007, USP 13-66136 x USP 13-19034, BRS 267 x USP 13-19007 and Tengamine x USP 13-19.007 presented the best performances. Estimates of specific combining ability (Sii) of the parents indicated divergence between them and the traits showed high estimates of heritability. The magnitude and significance of the correlations indicated the possibility of selecting early genotypes with large seeds and showed that the selection of genotypes with a longer period between R6 and R7 (SGR6) benefits seed yield. Therefore, it was possible to identify promising parents and crosses for the development of new lines suitable for the production of vegetable soybean with rust tolerance.

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

O principal objetivo deste trabalho é estudar diversas aplicações de combinatória infinita em espaços de funções contínuas, definidas em espaços compactos Hausdorff. Usando combinatória infinita para uma álgebra de Boole, por meio da dualidade de Stone, obtemos um espaço compacto Hausdorff. Com certas propriedades na álgebra de Boole é possível analisar propriedades analíticas no espaço de funções contínuas definidas em tal espaço. Especificamente, analisamos a propriedade de Grothendieck. Também analisamos a relação entre o espaço de funções contínuas e o espaço compacto Hausdorff sobre o qual é definido. Apresentamos um resultado que permite obter diversos resultados conhecidos de uma maneira uniforme (só usando fatos de topologia e teoria de conjuntos), dotando o espaço de funções contínuas de uma ordem peculiar. Finalmente, estudamos um pouco de jogos topológicos mediante diversos exemplos. / The main purpose of this work is to study some infinite combinatorics applications in spaces of continuous functions, defined in Hausdorff compact spaces. Using infinite combinatorics in Boolean algebras, through Stone duality, we obtain a compact Hausdorff space. With certain properties in Boolean algebras it is possible to analyze analytic properties in the space of continuous functions defined in such space. Specifically, we analyze the Grothendieck property. We also analyze the relationship between the space of continuous functions and the compact Hausdorff space on which it is defined. We present a result that allows to obtain several known results in a uniform way (only using facts of topology and set theory), giving the space of continuous functions a peculiar order. Finally, we study some topological games through several examples.

Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.