Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-10-30T13:59:20Z No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-11-23T12:29:01Z (GMT) No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) / Made available in DSpace on 2018-11-23T12:29:01Z (GMT). No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) Previous issue date: 2018-09-13 / O objetivo desse trabalho é apresentar algumas classes clássicas e outras mais recentes de polinômios de permutação sobre corpos finitos. A fim de atingir esse objetivo, apresentamos a construção e uma lista de propriedades de corpos finitos, bem como uma introdução à teoria dos polinômios sobre corpos finitos. / The main goal of this text is to present some known classes of permutation polynomials over finite fields. With this goal, we begin by presenting the construction and some properties of finite fields, as well as an introduction to the theory of polynomials over finite fields.

Orientador: João Meidanis / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T17:01:05Z (GMT). No. of bitstreams: 1 Feijao_PedroCipriano_D.pdf: 1943126 bytes, checksum: 4c547e8c568bbd0f2eb8235dfde05524 (MD5) Previous issue date: 2012 / Resumo: Rearranjo de genomas é o nome dado a eventos onde grandes blocos de DNA trocam de posição durante o processo evolutivo. Com a crescente disponibilidade de sequências completas de DNA, a análise desse tipo de eventos pode ser uma importante ferramenta para o entendimento da genômica evolutiva. Vários modelos matemáticos de rearranjo de genomas foram propostos ao longo dos últimos vinte anos. Nesta tese, desenvolvemos dois novos modelos. O primeiro foi proposto como uma definição alternativa ao conceito de distância de breakpoint. Essa distância é uma das mais simples medidas de rearranjo, mas ainda não há um consenso quanto à sua definição para o caso de genomas multi-cromossomais. Pevzner e Tesler deram uma definição em 2003 e Tannier et al. a definiram de forma diferente em 2008. Nesta tese, nós desenvolvemos uma outra alternativa, chamada de single-cut-or-join (SCJ). Nós mostramos que, no modelo SCJ, além da distância, vários problemas clássicos de rearranjo, como a mediana de rearranjo, genome halving e pequena parcimônia são fáceis, e apresentamos algoritmos polinomiais para eles. O segundo modelo que apresentamos é o formalismo algébrico por adjacências, uma extensão do formalismo algébrico proposto por Meidanis e Dias, que permite a modelagem de cromossomos lineares. Esta era a principal limitação do formalismo original, que só tratava de cromossomos circulares. Apresentamos algoritmos polinomiais para o cálculo da distância algébrica e também para encontrar cenários de rearranjo entre dois genomas. Também mostramos como calcular a distância algébrica através do grafo de adjacências, para facilitar a comparação com outras distâncias de rearranjo. Por fim, mostramos como modelar todas as operações clássicas de rearranjo de genomas utilizando o formalismo algébrico / Abstract: Genome rearrangements are events where large blocks of DNA exchange places during evolution. With the growing availability of whole genome data, the analysis of these events can be a very important and promising tool for understanding evolutionary genomics. Several mathematical models of genome rearrangement have been proposed in the last 20 years. In this thesis, we propose two new rearrangement models. The first was introduced as an alternative definition of the breakpoint distance. The breakpoint distance is one of the most straightforward genome comparison measures, but when it comes to defining it precisely for multichromosomal genomes, there is more than one way to go about it. Pevzner and Tesler gave a definition in a 2003 paper, and Tannier et al. defined it differently in 2008. In this thesis we provide yet another alternative, calling it single-cut-or-join (SCJ). We show that several genome rearrangement problems, such as genome median, genome halving and small parsimony, become easy for SCJ, and provide polynomial time algorithms for them. The second model we introduce is the Adjacency Algebraic Theory, an extension of the Algebraic Formalism proposed by Meidanis and Dias that allows the modeling of linear chromosomes, the main limitation of the original formalism, which could deal with circular chromosomes only. We believe that the algebraic formalism is an interesting alternative for solving rearrangement problems, with a different perspective that could complement the more commonly used combinatorial graph-theoretic approach. We present polynomial time algorithms to compute the algebraic distance and find rearrangement scenarios between two genomes. We show how to compute the rearrangement distance from the adjacency graph, for an easier comparison with other rearrangement distances. Finally, we show how all classic rearrangement operations can be modeled using the algebraic theory / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks.<p><p>Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into one another using as few operations as possible, with the additional constraint that the set of allowed operations is fixed beforehand; we are also interested in computing the corresponding distances between those objects, i.e. merely computing the minimum number of operations rather than an optimal sequence. Genome rearrangement problems can often be formulated as sorting problems on permutations (viewed as linear orderings of {1,2,n}) using as few (allowed) operations as possible. In this thesis, we focus among other operations on ``transpositions', which displace intervals of a permutation. Many questions related to sorting by transpositions are open, related in particular to its computational complexity. We use the disjoint cycle decomposition of permutations, rather than the ``standard tools' used in genome rearrangements, to prove new upper bounds on the transposition distance, as well as formulae for computing the exact distance in polynomial time in many cases. This decomposition also allows us to solve a counting problem related to the ``cycle graph' of Bafna and Pevzner, and to construct a general framework for obtaining lower bounds on any edit distance between permutations by recasting their computation as factorisation problems on related even permutations.<p><p>Haplotype networks are graphs in which a subset of vertices is labelled, used in comparative genomics as an alternative to trees. We formalise a new method due to Cassens, Mardulyn and Milinkovitch, which consists in building a graph containing a given set of partially labelled trees and with as few edges as possible. We give exact algorithms for solving the problem on two graphs, with an exponential running time in the general case but with a polynomial running time if at least one of the graphs belong to a particular class.<p>/<p>La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes.<p><p>Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées.<p><p>Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Philosophiae Doctor - PhD / In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs Γn that are embeddable into the strong product L1(Kn)⊠  K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, Γn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of Γn and Hn and determine their parameters. / South Africa

In 1972, professor Grigore Moisil, the most famous Romanian academician for Mathematics, said about Combinatorics, that it is “an opportunity of a renewed gladness”, because “each problem in the domain asks for its solving, an expenditure without any economy of the human intelligence”. More, the research methods, used in Combinatorics, are different from a problem to the other! This is the explanation for the existence of my actual paper, in which I propose to teach Combinatorics, using selected problems. MS classification: 05A05, 97D50.

Philosophiae Doctor - PhD / In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1,2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+l(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn' and neighbourhood designs of their line graphs, £1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of Ll(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, the basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs Rn that are embeddable into the strong product Ll(Kn) ~ K2' of triangular graphs and K2' a class that at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, Rn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of Rn and Hn and determine their parameters. The discussion is concluded with a look at complements of Rn and Hn, respectively denoted by Rn and Hn. Among others, the complements rn are contained in the union of the categorical product Ll(Kn) x Kn' and the categorical product £1(Kn) x Kn (where £1(Kn) is the complement of the iii triangular graph £1(Kn)). As with the other graphs, we have also considered codes from the span of incidence matrices of Rn and Hn and determined some of their properties. In each case, automorphisms of the graphs, designs and codes have been determined. For the codes from incidence designs of triangular graphs, embeddings of Ll(Kn) x K2 and complements of complete porcupines, we have exhibited permutation decoding sets (PD-sets) for correcting up to terrors where t is the full error-correcting capacity of the codes. For the remaining codes, we have only been able to determine PD-sets for which it is possible to correct a fraction of t-errors (partial permutation decoding). For these codes, we have also determined the number of errors that can be corrected by permutation decoding in the worst-case.

Masters of Science / The multivariate two-sample tests provide a means to test the match between two multivariate distributions. Although many tests exist in the literature, relatively little is known about the relative power of these procedures. The studies reported in the thesis contrasts the effectiveness, in terms of power, of seven such tests with a Monte Carlo study. The relative power of the tests was investigated against location, scale, and correlation alternatives. Samples were drawn from bivariate exponential, normal and uniform populations. Results from the power studies show that there is no single test which is the most powerful in all situations. The use of particular test statistics is recommended for specific alternatives. A possible supplementary non-parametric graphical procedure, such as the Depth-Depth plot, can be recommended for diagnosing possible differences between the multivariate samples, if the null hypothesis is rejected. As an example of the utility of the procedures for real data, the multivariate two-sample tests were applied to photometric data of twenty galactic globular clusters. The results from the analyses support the recommendations associated with specific test statistics.

[pt] Esta dissertação de mestrado analisa um problema de programação de máquinas em série com datas de entrega e ganhos cumulativos sob incerteza. Em particular, este trabalho considera situações reais na quais os tempos de processamento e datas de liberação são estocásticos. O objetivo principal deste trabalho é a resolução deste problema de programação de máquinas em série em um ambiente estocástico buscando analisar a relação entre diferentes niveis de incerteza e o benefício esperado. Visando atingir este objetivo, primeiramente uma heurística é proposta utilizando-se da técnica de biased-randomization para a versão determinística do problema. Então, esta heurística é extendida para uma metaheurística a partir do encapsulamento dentro da estrutura de um variable neighborhood descend. Finalmente, a metaheurística é extendida para uma simheurística a partir da incorporação da simulação de Monte Carlo. De acordo com os experimentos computacionais, o nível de incerteza tem um impacto direto nas soluções geradas pela simheurística. Além disso, análise de risco foram desenvolvidas utilizando as conhecidas métricas de risco: value at risk e conditional value at risk. / [en] This master s thesis analyzes the Permutation Flow-shop Scheduling Problem with Delivery Dates and Cumulative Payoffs under uncertainty conditions. In particular, the work considers the realistic situation in which processing times and release dates are stochastics. The main goal is to solve this Permutation Flow-shop problem in the stochastic environment and analyze the relationship between different levels of uncertainty and the expected payoff. In order to achieve this goal, first a biased-randomized heuristic is proposed for the deterministic version of the problem. Then, this heuristic is extended into a metaheuristic by encapsulating it into a variable neighborhood descent framework. Finally, the metaheuristic is extended into a simheuristic by incorporating Monte Carlo simulation. According to the computational experiments, the level of uncertainty has a direct impact on the solutions provided by the simheuristic. Moreover, a risk analysis is performed using two well-known metrics: the value at risk and the conditional value at risk.

Les travaux présentés dans cette thèse de doctorat relèvent de la combinatoire algébrique et de la théorie des groupes. Précisément, ils apportent une contribution au domaine de recherche qui étudie le comportement des profils des groupes oligomorphes.La première partie de ce manuscrit introduit la plupart des outils qui nous seront nécessaires, à commencer par des éléments de combinatoire et combinatoire algébrique.Nous présentons les fonctions de comptage à travers quelques exemples classiques, et nous motivons l'addition d'une structure d'algèbre graduée sur les objets énumérés dans le but d'étudier ces fonctions.Nous évoquons aussi les notions d'ordre et de treillis.Dans un second temps, nous donnons un aperçu des définitions et propriétés de base associées aux groupes de permutations, ainsi que quelques résultats de théorie des invariants. Nous terminons cette partie par une description de la méthode d'énumération de Pólya, qui permet de compter des objets sous une action de groupe.La deuxième partie est consacrée à l'introduction du domaine dans lequel s'inscrit cette thèse, celui de l'étude des profils de structures relationnelles, et en particulier des profils orbitaux. Si G est un groupe de permutations infini, son profil est la fonction de comptage qui envoie chaque entier n > 0 sur le nombre d'orbites de n-sous-ensembles, pour l'action induite de G sur les sous-ensembles finis d'éléments.Cameron a conjecturé que le profil de G est équivalent à un polynôme dès lors qu'il est borné par un polynôme. Une autre conjecture, plus forte, a été plus tard émise par Macpherson : elle implique une certaine structure d'algèbre graduée sur les orbites de sous-ensembles, créée par Cameron et baptisée algèbre des orbites, soutenant que si le profil est borné par un polynôme, alors l'algèbre des orbites est de type fini.Comme amorce de notre étude de ce problème, nous développons quelques exemples et faisons nos premiers pas vers une résolution en examinant les systèmes de blocs des groupes de profil borné par un polynôme --- que nous appelons P-oligomorphes ---,ainsi que la notion de sous-produit direct.La troisième partie démontre une classification des groupes P-oligomorphes, notre résultat le plus important et dont la conjecture de Macpherson se révèle un corollaire.Tout d'abord, nous étudions la combinatoire du treillis des systèmes de blocs,qui conduit à l'identification d'un système généralisé particulier, constituébde blocs ayant de bonnes propriétés. Nous abordons ensuite le cas particulier o`u il se limite à un seul bloc de blocs, pour lequel nous établissons une classification. La preuve emprunte à la notion de sous-produit direct pour gérer les synchronisations internes au groupe, et a requis une part d'exploration informatique afin d'être d'abord conjecturée.Dans le cas général, nous nous appuyons sur les résultats précédents et mettons en évidence la structure de G comme produit semi-direct impliquant son sous-groupe normal d'indice fini minimal et un groupe fini. Ceci permet de formaliser une classification complète des groupes P-oligomorphes,et d'en déduire la forme de l'algèbre des orbites : (à peu de choses près) une algèbre d'invariants explicite d'un groupe fini. Les conjectures de Macpherson et de Cameron en découlent, et plus généralement une compréhension exhaustive de ces groupes.L'annexe contient des extraits du code utilisé pour mener la preuve à bien,ainsi qu'un aperçu de celui qui a été produit en s'appuyant sur la nouvelle classification, qui permet de manipuler les groupes P-oligomorphes en usant d'une algorithmique adaptée. Enfin, nous joignons ici notre première preuve, plus faible, des deux conjectures. / This PhD thesis falls under the fields of algebraic combinatorics and group theory. Precisely,it brings a contribution to the domain that studies profiles of oligomorphic permutation groups and their behaviors.The first part of this manuscript introduces most of the tools that will be needed later on, starting with elements of combinatorics and algebraic combinatorics.We define counting functions through classical examples ; with a view of studying them, we argue the relevance of adding a graded algebra structure on the counted objects.We also bring up the notions of order and lattice.Then, we provide an overview of the basic definitions and properties related to permutation groups and to invariant theory. We end this part with a description of the Pólya enumeration method, which allows to count objects under a group action.The second part is dedicated to introducing the domain this thesis comes withinthe scope of. It dwells on profiles of relational structures,and more specifically orbital profiles.If G is an infinite permutation group, its profile is the counting function which maps any n > 0 to the number of orbits of n-subsets, for the inducedaction of G on the finite subsets of elements.Cameron conjectured that the profile of G is asymptotically equivalent to a polynomial whenever it is bounded by apolynomial.Another, stronger conjecture was later made by Macpherson : it involves a certain structure of graded algebra on the orbits of subsetscreated by Cameron, the orbit algebra, and states that if the profile of G is bounded by a polynomial, then its orbit algebra is finitely generated.As a start in our study of this problem, we develop some examples and get our first hints towards a resolution by examining the block systems ofgroups with profile bounded by a polynomial --- that we call P-oligomorphic ---, as well as the notion of subdirect product.The third part is the proof of a classification of P-oligomorphic groups,with Macpherson's conjecture as a corollary.First, we study the combinatorics of the lattice of block systems,which leads to identifying one special, generalized such system, that consists of blocks of blocks with good properties.We then tackle the elementary case when there is only one such block of blocks, for which we establish a classification. The proof borrows to the subdirect product concept to handle synchronizations within the group, and relied on an experimental approach on computer to first conjecture the classification.In the general case, we evidence the structure of a semi-direct product involving the minimal normal subgroup of finite index and some finite group.This allows to formalize a classification of all P-oligomorphic groups, the main result of this thesis, and to deduce the form of the orbit algebra: (little more than) an explicit algebra of invariants of a finite group. This implies the conjectures of Macpherson and Cameron, and a deep understanding of these groups.The appendix provides parts of the code that was used, and a glimpse at that resulting from the classification afterwards,that allows to manipulate P-oligomorphic groups by apropriate algorithmics. Last, we include our earlier (weaker) proof of the conjectures.

No description available.