Quelques problèmes combinatoires et algorithmiques sur les classes de permutations
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
This work is dedicated to the study of permutation classes, with both an algorithmic and a combinatorial point of view. It uses in most of its developments the substitution decomposition of permutations, represented by their decomposition trees. These trees are the combinatorial counterpart of the common interval trees of permutations used in algorithmics. We fîrst deal with pattern matching problems in permutations: fînding an occurrence of a pattern in a permutation, and finding a longest common pattern between two (or among a set of) permutations. These problems are NP-hard, and by imposing some restrictions to the class of separable permutations, we describe in this restricted framework polynomial solutions, when they exist. Then, we offer a combinatorial analysis of some models of genome evolution. In the tandem duplication-random loss model, we characterize as a pattern-avoiding permutation class the permutations obtained after p steps of evolution. We also study the model of perfect sorting by reversals: in this case we give a precise complexity analysis of a previously known algorithm Computing optimal evolution scenarios. Finally, we study the class of pin-permutations, which plays a key role in a procedure allowing the automatic computation of the generating functions of some permutation classes. We give a characterization of the decomposition trees of pin-permutations, the rational generating function of the class, and a polynomial algorithm to test whether a permutation class contains a finite number of proper pin-permutations
Abstract FR:
Ce travail étudie les classes de permutations, avec les deux points de vue combinatoire et algorithmique. Il y est fréquemment fait usage de la décomposition par substitution des permutations, à travers leurs arbres de décomposition. Ces arbres sont le pendant combinatoire des arbres des intervalles communs des permutations utilisés en algorithmique. D'abord, on s'intéresse à la recherche de motifs dans les permutations : occurrence d'un motif dans une permutation, et recherche de plus grand motif commun à deux (ou à un ensemble de) permutations. Ces problèmes sont NP-difficiles, et en introduisant des restrictions à la classe des permutations séparables, on y apporte dans ce cadre restreint des solutions polynomiales, lorsqu'elles existent. Ensuite, on analyse combinatoirement certains modèles pour l'évolution des génomes. Dans le modèle de duplication en tandem avec perte aléatoire, on caractérise comme classe de permutations à motifs exclus les permutations obtenues après p étapes d'évolution. L'autre modèle étudié est celui du tri parfait par renversements, où on donne une analyse de complexité fine d'un algorithme préexistant pour le calcul de scénario d'évolution optimal. Enfin, on étudie la classe des permutations en épingles, qui joue un rôle clé dans un processus permettant d'obtenir de manière systématique les séries génératrices de certaines classes de permutations. On donne une caractérisation des arbres de décomposition des permutations en épingles, la série génératrice rationnelle de cette classe, et un algorithme polynomial pour tester si une classe de permutations contient un nombre fini de permutations en épingles propres.