Cette thèse porte sur des classes d'objets combinatoires, qui modélisent des données en bio-informatique. Nous étudions notamment deux méthodes de mutation des gènes à l'intérieur du génome : la duplication et l'inversion. Nous étudions d'une part le problème de la duplication-miroir complète avec perte aléatoire en termes de permutations à motifs exclus. Nous démontrons que la classe de permutations obtenue avec cette méthode après p duplications à partir de l'identité est la classe de permutations qui évite les permutations alternées de longueur 2^p+1. Nous énumérons également le nombre de duplications nécessaires et suffisantes pour obtenir une permutation quelconque de longueur n à partir de l'identité. Nous proposons également deux algorithmes efficaces permettant de reconstituer deux chemins différents entre l'identité et une permutation déterminée. Nous donnons enfin des résultats connexes sur d'autres classes proches. La restriction de la relation d'ordre < induite par le code de Gray réfléchi à l'ensemble des compositions et des compositions bornées induit de nouveaux codes de Gray pour ces ensembles. La relation d'ordre < restreinte à l'ensemble des compositions bornées d'un intervalle fournit encore un code de Gray. L'ensemble des n compositions bornées d'un intervalle généralise simultanément l'ensemble produit et l'ensemble des compositions d'un entier et donc la relation < définit de façon unifiée tous ces codes de Gray. Nous réexprimons les codes de Gray de Walsh et Knuth pour les compositions (bornées) d'un entier à l'aide d'une unique relation d'ordre. Alors, le code de Gray deWalsh pour des classes de compositions et de permutations devient une sous-liste de celui de Knuth, lequel est à son tour une sous-liste du code de Gray réfléchi.

Ce mémoire se veut une synthèse, destinée à la communauté combinatoricienne, de quelques outils développés pour aborder le problème d'Hurwitz ainsi qu'une présentation des résultats récoltés. Le problème d'Hurwitz consiste à évaluer, dans un groupe symétrique, le nombre (dit d'Hurwitz) de factorisations transitives de la permutation identité dont on a imposé le type cyclique des facteurs. Nous décrivons tout d'abord les origines topologiques de ce problème à travers le dénombrement des revêtements ramifiés de la sphère. Nous présentons également un cadre algébrique naturel, le monoïde des permutations scindées, qui permet d'exprimer les nombres d'Hurwitz comme coefficients de structure de l'algèbre de ce monoïde, plus précisément de la sous-algèbre engendrée par les classes de conjugaison, dont une base naturelle est indexée par les multipartitions (ou partitions scindées). La théorie des représentations de cette algèbre fournit un algorithme pour calculer les nombres d'Hurwitz à une partition dont la complexité (minimale, uniforme et exponentielle) est bien meilleure que celle d'une approche naïve. Ce cadre algébrique donne par ailleurs une formule décrivant les séries d'Hurwitz à plusieurs partitions comme polynômes en les séries d'Hurwitz à une seule partition. Nous présentons secondement le cadre géométrique dans lequel s'expriment d'une part la formule ELSV, laquelle décrit les nombres d'Hurwitz à une partition comme fonctions de certaines intégrales, d'autre part un théorème de M. Kazarian exprimant les séries de Hurwitz à une partition comme polynômes en certaines séries formelles dont l'étude asymptotique est achevée. Une fois décrit le fonctionnement de ce cadre intégral, nous récoltons l'asymptotique de tous les nombres d'Hurwitz

The main goal of this thesis is to investigate the complexity of a variety of problems related to text indexing and text searching. We present new data structures that can be used as building blocks for full-text indices which occupies minute space (FM-indexes) and wavelet trees. These data structures also can be used to represent labeled trees and posting lists. Labeled trees are applied in XML documents, and posting lists in search engines. The main emphasis of this thesis is on lower bounds for time-space tradeoffs for the following problems: the rank/select problem, the problem of representing a string of balanced parentheses, the text retrieval problem, the problem of computing a permutation and its inverse, and the problem of representing a binary relation. These results are divided in two groups: lower bounds in the cell probe model and lower bounds in the indexing model. The cell probe model is the most natural and widely accepted framework for studying data structures. In this model, we are concerned with the total space used by a data structure and the total number of accesses (probes) it performs to memory, while computation is free of charge. The indexing model imposes an additional restriction on the storage: the object in question must be stored in its raw form together with a small index that facilitates an efficient implementation of a given set of queries, e.g. finding rank, select, matching parenthesis, or an occurrence of a given pattern in a given text (for the text retrieval problem). We propose a new technique for proving lower bounds in the indexing model and use it to obtain lower bounds for the rank/select problem and the balanced parentheses problem. We also improve the existing techniques of Demaine and Lopez-Ortiz using compression and present stronger lower bounds for the text retrieval problem in the indexing model. The most important result of this thesis is a new technique for cell probe lower bounds. We demonstrate its strength by proving new lower bounds for the problem of representing permutations, the text retrieval problem, and the problem of representing binary relations. (Previously, there were no non-trivial results known for these problems.) In addition, we note that the lower bounds for the permutations problem and the binary relations problem are tight for a wide range of parameters, e.g. the running time of queries, the size and density of the relation.

The main goal of this thesis is to investigate the complexity of a variety of problems related to text indexing and text searching. We present new data structures that can be used as building blocks for full-text indices which occupies minute space (FM-indexes) and wavelet trees. These data structures also can be used to represent labeled trees and posting lists. Labeled trees are applied in XML documents, and posting lists in search engines. The main emphasis of this thesis is on lower bounds for time-space tradeoffs for the following problems: the rank/select problem, the problem of representing a string of balanced parentheses, the text retrieval problem, the problem of computing a permutation and its inverse, and the problem of representing a binary relation. These results are divided in two groups: lower bounds in the cell probe model and lower bounds in the indexing model. The cell probe model is the most natural and widely accepted framework for studying data structures. In this model, we are concerned with the total space used by a data structure and the total number of accesses (probes) it performs to memory, while computation is free of charge. The indexing model imposes an additional restriction on the storage: the object in question must be stored in its raw form together with a small index that facilitates an efficient implementation of a given set of queries, e.g. finding rank, select, matching parenthesis, or an occurrence of a given pattern in a given text (for the text retrieval problem). We propose a new technique for proving lower bounds in the indexing model and use it to obtain lower bounds for the rank/select problem and the balanced parentheses problem. We also improve the existing techniques of Demaine and Lopez-Ortiz using compression and present stronger lower bounds for the text retrieval problem in the indexing model. The most important result of this thesis is a new technique for cell probe lower bounds. We demonstrate its strength by proving new lower bounds for the problem of representing permutations, the text retrieval problem, and the problem of representing binary relations. (Previously, there were no non-trivial results known for these problems.) In addition, we note that the lower bounds for the permutations problem and the binary relations problem are tight for a wide range of parameters, e.g. the running time of queries, the size and density of the relation.

Dans les industries agro-alimentaires ainsi que dans d'autres secteurs d'activités, l'analyse sensorielle est la clé pour répondre aux attentes des consommateurs. Cette discipline est le plus souvent basée sur l'établissement de profils sensoriels à partir de notes attribuées par des juges entraînés selon une liste de descripteurs (variables sensorielles). Dans ce type d'étude, il importe d'étudier la performance des juges et d'en tenir compte dans l'établissement des profils sensoriels. Dans cette perspective, nous proposons une démarche qui permet de procurer des indicateurs de performance du jury et de chacun des juges et de tenir compte de cette performance pour une détermination d'un tableau moyen. Des tests d'hypothèses pour évaluer la significativité de la contribution des juges à la détermination du compromis sont également proposés.<br />Depuis une vingtaine d'années, les courbes temps-intensité (TI) qui permettent de décrire l'évolution d'une sensation au cours de l'expérience sont de plus en plus populaires parmi les praticiens de l'analyse sensorielle. La difficulté majeure pour l'analyse des courbes TI provient d'un effet juge important qui se traduit par la présence d'une signature propre à chaque juge. Nous proposons une approche fonctionnelle basée sur les fonctions B-splines qui permet de réduire l'effet juge en utilisant une procédure d'alignement de courbes.<br />D'autres données sensorielles au cours du temps existent telles que le suivi de la dégradation organoleptique de produits alimentaires. Pour les étudier, nous proposons la modélisation par des chaînes de Markov cachées, de manière à pouvoir ensuite visualiser graphiquement la suivi de la dégradation.

We examine a phase transition in a model of random spatial permutations which originates in a study of the interacting Bose gas. Permutations are weighted according to point positions; the low-temperature onset of the appearance of arbitrarily long cycles is connected to the phase transition of Bose-Einstein condensates. In our simplified model, point positions are held fixed on the fully occupied cubic lattice and interactions are expressed as Ewens-type weights on cycle lengths of permutations. The critical temperature of the transition to long cycles depends on an interaction-strength parameter α. For weak interactions, the shift in critical temperature is expected to be linear in α with constant of linearity c. Using Markov chain Monte Carlo methods and finite-size scaling, we find c = 0.618 ± 0.086. This finding matches a similar analytical result of Ueltschi and Betz. We also examine the mean longest cycle length as a fraction of the number of sites in long cycles, recovering an earlier result of Shepp and Lloyd for non-spatial permutations. The plan of this paper is as follows. We begin with a non-technical discussion of the historical context of the project, along with a mention of alternative approaches. Relevant previous works are cited, thus annotating the bibliography. The random-cycle approach to the BEC problem requires a model of spatial permutations. This model it is of its own probabilistic interest; it is developed mathematically, without reference to the Bose gas. Our Markov-chain Monte Carlo algorithms for sampling from the random-cycle distribution - the swap-only, swap-and-reverse, band-update, and worm algorithms - are presented, compared, and contrasted. Finite-size scaling techniques are used to obtain information about infinite-volume quantities from finite-volume computational data.

Darbe tiriamas kėlinių, derinių, poaibių ir Grėjaus kodų generavimo algoritmų sudėtingumas. Atliekama algoritmų analizė. Tyrimo tikslams sukurta programa realizuojanti minėtus algoritmus. / The complexity research of permutations, combinations, subsets and Gray codes generating algorithms is provided in this paper. Algorithms are analyzed and implemented in the application developed for research purposes.

Title: Extremal combinatorics of matrices, sequences and sets of permutations Author: Josef Cibulka Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr., Department of Applied Mathematics Abstract: This thesis studies questions from the areas of the extremal theory of {0, 1}-matrices, sequences and sets of permutations, which found many ap- plications in combinatorial and computational geometry. The VC-dimension of a set P of n-element permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. We show lower and upper bounds quasiexponential in n on the maximum size of a set of n-element permutations with VC-dimension bounded by a constant. This is used in a paper of Jan Kynčl to considerably improve the upper bound on the number of weak isomorphism classes of com- plete topological graphs on n vertices. For some, mostly permutation, matrices M, we give new bounds on the number of 1-entries an n × n M-avoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2 n/2 1-entries that avoids one specific k-permutation matrix. We also give almost tight bounds on the maximum number of 1-entries in matrices avoiding a fixed layered...

Submitted by (lucia.rodrigues@ufrpe.br) on 2017-03-29T14:53:15Z No. of bitstreams: 1 Walfrido Siqueira Campos Junior.pdf: 422142 bytes, checksum: a769780b0d11bc646f87ad7036267f6b (MD5) / Made available in DSpace on 2017-03-29T14:53:15Z (GMT). No. of bitstreams: 1 Walfrido Siqueira Campos Junior.pdf: 422142 bytes, checksum: a769780b0d11bc646f87ad7036267f6b (MD5) Previous issue date: 2014-06-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work consists of the presentation of a simple permutation, seen as function. This function is bijective, hence admits inverse (inverse permutation). The composition of this function with the same it is also bijective (composed permutation). We will also see the permutations with repetition, circular without repetition and repetition, beyond chaotic permutations, which are those in which no element occupies its original position. The work is also part of the de nition and presentation of a group of permutations consisting of 3 properties in which the composition of functions satisfy all of them. This is our highest goal. Still show the parity of the permutation, as well as their applications in cases of determinants. / Este trabalho consta da apresentação de uma permutação simples, vista na forma de função. Essa função é bijetora, portanto admite inversa (permutação inversa). A composição dessa função com ela mesma, também é bijetora (permutação composta). Veremos também as permutações com repetição, circulares sem repetição e com repetição, além das permutações caóticas, que são aquelas em que nenhum elemento ocupa sua posição inicial. O trabalho consta também da definição e apresentação de um Grupo das permutações que consiste em 3 propriedades na qual a composição das funções satisfazem todas elas. Esse e o nosso maior objetivo. Mostraremos ainda a paridade da permutação, bem como suas aplicações em casos de determinantes.

Orientador: João Meidanis / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T00:56:27Z (GMT). No. of bitstreams: 1 GomesMira_CleberValgas_D.pdf: 1443128 bytes, checksum: adcf8d553b49f20bbad0fc0f56cc2aba (MD5) Previous issue date: 2007 / Resumo: O sucesso na obtenção de cadeias completas de DNA de alguns organismos tem incentivado a busca de novas técnicas computacionais capazes de analisar esse montante de informação para aplicá-lo na descoberta de novos remédios, aumento da produção de alimentos e investigação do processo de evolução dos seres vivos, entre outras aplicações. A comparação de seqüências de DNA (ou RNA) de diferentes espécies é uma das técnicas importantes para desvendar novas propriedades biológicas. Uma das maneiras de se comparar dois genomas é analisar como os dois se distinguem com base em certas mutações chamadas eventos de rearranjo em genomas. Nessa técnica de comparação, um genoma é modelado como uma seqüência de regiões que são conservadas em um conjunto de genomas. O problema de rearranjos em genomas consiste genericamente em encontrar, dados dois genomas como entrada e um conjunto de tipos de eventos de rearranjo permitidos, uma seqüência mínima de tais eventos de rearranjo que transforme um genoma em outro. No formalismo clássico de rearranjos em genomas, um genoma tem sido modelado como um conjunto de seqüências de inteiros. Cada número inteiro representa um gene e o seu sinal representa a orientação do gene no genoma. O problema de rearranjos em genomas nesse modelo é analisado de forma geral por meio de diversos diagramas e grafos que representam certas propriedades do par de genomas na entrada do problema. Neste trabalho, usamos um novo modelo para rearranjos em genomas proposto por Meidanis e Dias [39]: o formalismo algébrico. Em vez de se basear na análise de diagramas, o formalismo algébrico usa permutações na modelagem de genomas e, principalmente, utiliza resultados de grupos de permutações para analisar as propriedades de genomas e os efeitos de eventos de rearranjo. A motivação para o desenvolvimento do formalismo algébrico é a possibilidade de formalização de argumentos sobre rearranjos por meio de métodos algébricos, em vez da utilização de recursos gráficos como é feito no formalismo clássico. Esperamos que, por meio do desenvolvimento de um novo formalismo para o tratamento de problemas de rearranjos em genomas, algoritmos mais eficientes para a resolução desses problemas, ou maneiras mais simples de demonstrar alguns dos resultados clássicos na área sejam encontrados com maior facilidade. Nesse trabalho, apresentamos duas soluções simples e eficientes derivadas diretamente do formalismo algébrico para dois problemas de rearranjos em genomas (o problema de rearranjos em genomas por intercâmbio de blocos e reversões com sinais e o problema de rearranjo em genomas por fissões, fusões e reversões com sinais). Também discutimos e propomos um algoritmo polinomial para o problema de rearranjos em genomas por transposições generalizadas. Acreditamos que o sucesso na solução desses problemas possa ser estendido para outros problemas de rearranjos em genomas com a consolidação dos conceitos fundamentais do formalismo algébrico. Esperamos com essa tese convencer o leitor de que o formalismo algébrico é um modelo representativo e poderoso para tratar genomas compostos por cromossomos circulares e ao lidar com a atribuição de pesos a eventos de rearranjo. Por outro lado, não defendemos que o formalismo clássico seja simplesmente substituído pelo formalismo algébrico. Ambos os formalismos podem ser beneficiados por um processo semelhante, porém em menor escala, ao sucesso do desenvolvimento da Geometria Analítica e da Geometria Tradicional / Abstract: The success in obtaining complete sequences of DNA of some species has encouraged the search for new computational techniques for the analysis of such huge amount of information. One hopes that the results of this research could be applied for the development of new medicines, increasing food crops productivity, better understanding of the evolutionary process in live beings, among other applications. One technique for the genome analysis is the comparison of DNA (or RNA) sequences from different species. Such a comparison may reveal the similarities and differences between the genomes, which could be used in phylogeny reconstruction for instance. Two genomes can be compared by the analysis of their differences based on mutational events called genome rearrangements. The genome rearrangement problem (also called a sorting problem) consists of finding a minimum sequence of rearrangement events that transforms one genome into another and the number of rearrangement events in the sequence is called the genomic distance. In the classical formalism for genome rearrangements, a genome is usually modeled by a set of sequences of integers. Each integer represents a gene and its sign stands for the orientation of the gene in the genome. The genome rearrangement problem in this model is analyzed generally with tools such as diagrams and graphs that convey the properties of the genomes in the problem input. We use instead a new model for genome rearrangements proposed by Meidanis and Dias [39]: the algebraic formalism. Instead of being based on the analysis of diagrams, the algebraic formalism uses permutations to model genomes and the results from permutation group theory for the analysis of the properties of genomes and the effects of rearrangement events. The motivation for the development of the algebraic formalism is the possibility of stating arguments more formally by means of algebraic methods than by using graphical resources as the classical formalism does. We hope that more efficient algorithms for genome rearrangement problems or simpler proofs for classical results in the area will be more easily found due to the development of a new formalism. We present a simple, efficient solution based on the algebraic formalism for two genome rearrangement problems (the problem of genome rearrangements by block-interchanges and signed reversals and the problem of genome rearrangements by fissions, fusions, and signed reversals). We also discuss and offer a solution for the problem of genome rearrangements by generalized transpositions. We believe that the success in solving those genome rearrangement problems could be extended to other problems by consolidating the fundamental concepts of the algebraic formalism. We hope that the reader will be convinced that the algebraic formalism is representative and powerful in dealing with circular chromosomes and modeling the assignment of weights to rearrangement events. On the other hand, we do not argue in favor of a substitution of the classical formalism by the algebraic formalism. Both of these formalisms could profit by a similar, even though on a smaller scale, success of the development of the Analytic Geometry and the Traditional Geometry / Doutorado / Doutor em Ciência da Computação