Ce travail traite principalement de l'énumération d'extensions de structures combinatoires classiques appelées chemins de Dyck et fonctions de stationnement. Ces structures, très étudiées en raison de leur rôle fondamental dans de multiples contextes combinatoires, sont aussi étroitement liées à la théorie de la représentation, à la théorie des fonctions symétriques et à la géométrie algébrique, entre autres. En particulier, elles sont liées à l'étude combinatoire des espaces coinvariants diagonaux DRk,n, introduits par Garsia et Haiman, qui sont des représentations du groupe symétrique Gn sur des espaces de polynômes en k jeux de n variables. Dans le cas bivarié, il a été conjecturé que les séries de Hilbert des espaces coinvariants diagonaux « augmentés » DRm2,n et de leur sous-représentation signe DRm2,nɛ sont respectivement égales à une somme de statistiques sur les fonctions de m-stationnement et sur les chemins de m-Dyck. Il existe également une conjecture plus générale pour la série de Frobenius de ces espaces qui s'appelle la conjecture « shuffle » (Haglund et al., 2005). Dans le cas trivarié, Haiman a conjecturé en 1994 les dimensions suivantes : dim(DR3,nɛ) = 2/n(n+1) (4n+1 n-1) et dim(DR3,n) = 2n (n+1)n-2. D'autre part, en 2006, Chapoton a démontré que les intervalles dans le treillis de Tamari sont comptés par 2/n(n+1) (4n+1 n-1). Motivé par ses travaux sur le cas trivarié et par les deux conjectures précédentes, Bergeron a introduit le treillis de m-Tamari et étendu certaines questions concernant les chemins de m-Dyck et les fonctions de m-stationnement pour rendre compte du cas trivarié. Il a conjecturé que : dim(DRm3,nɛ) = m+1/n(mn+1) ((m+1)2n+m n-1), que : dim(DRm3,n) = (m+1)n(mn+1)n-2, et que ces deux cardinalités comptent respectivement les intervalles et les intervalles de stationnement du treillis de m-Tamari. Dans cette thèse, nous démontrons une généralisation commune de ces deux conjectures énumératives que nous avons énoncée avec Bergeron. Plus précisément, avec Mireille Bousquet-Mélou et Guillaume Chapuy, nous avons démontré que la série de Frobenius d'une certaine représentation combinatoire sur les intervalles de stationnement du treillis de m-Tamari est donnée par : Ʃ λ=(λ1,…,λl)˫n (mn+1)l-2 II 1≤i≤l ((m+1)λi λi) Pλ/Zλ. Cette démonstration équivaut à résoudre un nouveau type d'équations différentielles à variable catalytique. Toujours avec Bergeron, nous avons conjecturé que le produit tensoriel de cette représentation combinatoire et de la représentation signe ɛ est isomorphe à DRm3,n. Nous avons également formulé une généralisation de la conjecture « shuffle » en proposant une formule combinatoire explicite pour la série de Frobenius graduée de DRm3,n. Ceci renforce notre hypothèse que l'étude des intervalles du treillis de m-Tamari est bel et bien en lien avec l'étude des espaces DRm3,n. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : combinatoire algébrique, combinatoire énumérative, représentations du groupe symétrique, fonctions génératrices, statistiques.

Dans ce document, nous étudions l’évitabilité de différentes formes de répétitions dans les mots. En particulier 3 des 6 chapitres sont dédiés aux répétitions abéliennes en lien notamment avec deux questions d’Erdős de 1957 et 1961. Nous commençons par montrer qu’il existe un algorithme décidant, sous certaines conditions, si un mot morphique évite des puissances abéliennes. Cet algorithme élargit la classe sur laquelle les précédents algorithmes pouvaient décider. Une généralisation de cet algorithme nous permet de montrer que les longs carrés abéliens sont évitables sur l’alphabet ternaire et que les carrés additifs sont évitables sur Z2 . Le premier résultat répond à une question ouverte de Mäkelä datant de 2003 alors que le deuxième rappelle la question ouverte de 1994 concernant l’évitabilité des carrés additifs sur Z.Une autre généralisation de notre algorithme permet d’étudier l’évitabilité des motifs au sens abélien. Nous montrons que les motifs binaires de longueur supérieure à 14 sont évitables sur l’alphabet binaire, améliorant la précédente borne de 118.Nous donnons des conditions suffisantes pour qu’un morphisme soit sans longues puissances nème k-abéliennes. Ce résultat nous permet de calculer, pour tout k ≥ 3, le nombre minimum de carrés k-abéliens qu’un mot binaire infini doit contenir en facteur. Il permet aussi de montrer que les longs carrés 2-abéliens sont évitables sur l’alphabet binaire et qu’il existe un mot ternaire qui ne contient qu’un seul carré 2-abélien en tant que facteur.Enfin, nous proposons une classification complète des formules binaires en fonction de la taille d’alphabet qu’il faut pour les éviter et du taux de croissance (exponentiel ou polynomial) du langage les évitant. / In this document, we study the avoidability of different kind of repetitions in words. We firstshow that under some conditions one can decide whether a morphic word avoids abelian n-thpowers. This algorithm can decide over a wider class of morphism than the previousalgorithms. We generalize this algorithm and use it to show that long abelian squares areavoidable over the ternary alphabet and that additive squares are avoidable over Z2 . The firstresult answers a weak version of a question formulated by Mäkelä in 2003 and the second oneis related to an open question from 1994 about the avoidability of additive squares over Z.Another generalization of this algorithm can be used to study avoidability of patterns in theabelian sense. In particular, we show that binary patterns of length more than 14 areavoidable over the binary alphabet in the abelian sense. This improves considerably theprevious bound of 118.We give sufficient conditions for a morphism to be long k-abelian n-th power-free. This resultallows us to compute for every k ≥ 3 the number of different k-abelian squares that a binaryword must contain. We prove that long 2-abelian squares are avoidable over the binaryalphabet and that over the ternary alphabet there exists a word that contains only one 2-abelian square.We also give a complete classification of binary formulas based on the size of the smallestalphabet over which they are avoidable and on the growth (exponential or polynomial) of theassociated language.

Le but de cette thèse est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée; nous obtenons des interprétations combinatoires et des extensions de résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer.

Malgré sa complexité de résolution, le problème de SATisfaisabilité est une excellente et compétitive approche pour résoudre un large éventail de problèmes. Cela génère une forte demande pour une résolution de SAT haute performance de la part des industriels. Au fil du temps, de nombreuses approches et optimisations différentes ont été développées pour résoudre le problème plus efficacement. Ces innovations ont été faites sans prendre en compte le développement des micro processeurs actuels qui voient le nombre de leur cœurs de calcul augmenter. Cette thèse présente un nouveau type d'algorithme parallèle basé sur une forte collaboration où un processus riche est en charge de l'évaluation de l'arbre de recherche et où des processus pauvres fournissent des informations partielles ou globales, heuristiques ou logiques afin de simplifier la tâche du riche. Pour concrétiser ce solveur et le rendre efficace, nous avons étendu la notion de chemin de guidage à celle d'arbre de guidage. L'arbre de recherche est totalement partagé en mémoire centrale et tous les processeurs peuvent y travailler en même temps. Ce nouveau solveur est appelé MTSS pour Multi-Threaded SAT Solver. De plus, nous avons implémenté une tâche pour les processus riche et pauvres qui leur permet d'exécuter un solveur SAT externe, et cela, avec ou sans échange de lemmes afin de paralléliser tous types de solveurs (dédiés aux formules industrielles ou aléatoires). Ce nouvel environnement facilite la parallélisation des futures implémentations pour SAT. Quelques exemples et expérimentations, avec ou sans échange de lemmes, de parallélisation de solveurs externes sont présentées, mais aussi des résultats sur les performances de MTSS. Il est intéressant de noter que certaines accélérations sont super linéaires.

Ce manuscrit décrit les travaux de recherche effectués au cours de ma thèse, au sein de l'équipe informatique et recherche opérationnelle du laboratoire CREAM1, en collaboration avec le laboratoire LISA 2, et avec le soutien du Conseil Général de la ville d'Angers. Ces travaux de recherche se situent à l'intersection des domaines de l'optimisation combinatoire et des systèmes multi-agents. Ils s'inscrivent dans la continuité des propositions de modèles ou de plates-formes pour les métaheuristiques parallèles. Ce rapport réunit différentes notions du parallélisme, du paradigme multi-agents et des métaheuristiques afin d'apporter des méthodes de résolution performantes (robustes et autoadaptatives) à des problèmes d'optimisation combinatoire réels. Il démontre que l'introduction de stratégies de parallélisation et d'échange d'informations à un algorithme à population permet à ce dernier d'améliorer considérablement ses facultés de recherche de solutions. En outre, l'utilisation des agents mobiles permet une exploitation optimale des ressources de calcul inutilisées dans un organisme (laboratoire, entreprise) et de favoriser ainsi l'autonomie des processus de calcul pour pouvoir gérer les éventuelles pannes dans un réseau. Le succès de cette approche dans la résolution d'un problème de tournées de véhicules et d'un problème d'ordonnancement de production, montre l'intérêt pratique de ces méthodes et leurs retombées économiques potentielles. Ce travail de recherche représente l'une des premières explorations des possibilités offertes par deux domaines fort prometteurs de l'intelligence artificielle distribuée et de la recherche opérationnelle. L'union de méthodes auto-adaptatives et d'une puissance de calcul imposante pourrait fort bien se révéler un outil performant pour la résolution de problèmes d'une telle envergure.

.

Les pyrrolamides constituent une famille de produits naturels dotés de diverses activités biologiques et synthétisés par des actinobactéries. La congocidine et la distamycine, les molécules les plus connues de cette famille, sont capables de se lier à l'ADN de façon non covalente selon une certaine spécificité de séquence (succession de 4 paires de base A/T). Récemment, les gènes et la voie de biosynthèse de la congocidine ont été identifiés et caractérisés chez S. ambofaciens. Ceci a révélé un mécanisme original impliquant notamment de nouvelles enzymes et de nouvelles voies pour la biosynthèse des trois précurseurs nécessaires à l’assemblage de la congocidine. Nous avons entrepris d’étudier la régulation de la biosynthèse de la congocidine chez S. ambofaciens et d’isoler et de caractériser les groupes de gènes de biosynthèse de deux autres pyrrolamides, la distamycine et les pyrronamycines (produites respectivement par S distallicus et un streptomyces non caractérisé). L'objectif de cette étude est, dans un premier temps, d’améliorer notre compréhension des mécanismes impliqués lors de la biosynthèse de ces molécules (comme le mécanisme d’incorporation des pyrroles) et, par la suite, de manipuler les gènes identifiés pour synthétiser de nouvelles molécules pyrrolamides hybrides. / Pyrrolamides constitute a family of natural products with various biological activities, synthesized by actinobacteria. Congocidine (also called netropsin) and distamycin are the best characterized pyrrolamides, largely studied due to their ability to bind into the minor groove of the DNA double helix in a sequence specific manner (succession of four A/T bases). Recently, the congocidine biosynthetic pathway has been characterized in Streptomyces ambofaciens. We showed that an iterative Non Ribosomal Peptide Synthetase with an unusual architecture assembles congocidine, using precursors with undocumented biosynthetic pathways. With the aim of developing a combinatorial biosynthesis approach for the development of new pyrrolamides, we undertook the study of the regulation of congocidine biosynthesis in S. ambofaciens and the isolation of the distamycin and pyrronamycins biosynthetic gene clusters. Characterization of these clusters will result in a more detailed understanding of pyrrolamide biosynthesis (e.g. mechanism of pyrrole polymerization), and provide new tools (enzymes) and building blocks (precursors) necessary for combinatorial biosynthesis.

Dans le cadre de l'étude des ensembles de pavages, nous nous sommes concentrés sur le cas des pavages de zonotopes (figures d'un espace formées de toutes les combinaisons linéaires d'un ensemble de vecteurs donnés). Après avoir défini un graphe dual d'un pavage de zonotope planaire (par l'utilisation de la relation d'adjacence liant les tuiles), nous avons montré la relation biunivoque qui lie les deux classes d'objets. Nous avons alors étudié comment l'opération de flip (qui est un réarrangement local de tuiles) peut s'exprimer sur le dual, permettant par la suite de construire l'ensemble des pavages du zonotope associé. Cette méthode ne pouvant que très difficilement s'adapter aux cas de dimensions supérieures (zonotopes non planaires), nous avons alors mis au point une méthode de décomposition permettant d'étudier un pavage en nous focalisant sur les propriétés de pavages plus petits. Ce type de méthode nous a permis de démontrer des résultats forts de reconstruction et de structure dans le cas de pavages de dimension 2. De plus, ceci nous a permis de démontrer des résultats de connexité dans certains cas particuliers de dimensions supérieures. Le choix des pavages de zonotopes étend naturellement certains pavages étudiés classiquement (tels que les pavages de dominos sur une grille carrée ou de losanges sur une grille triangulaire). En effet, ils ne peuvent être définis sur une grille, et sont définis en toute dimension.

Dans cette thèse, on s'intéresse au billard dans un polyèdre. On étudie cette application, en codant les orbites sur un alphabet fini. On étudie alors deux problèmes: la complexité des mots infinis obtenus, et l'existence de trajectoires périodiques. On montre que la complexité est reliée à la notion de diagonale généralisée : une diagonale généralisée est une trajectoire de billard, qui part d'une arête et qui arrive à une arête. On obtient alors, au premier chapitre, une nouvelle preuve du calcul de la complexité d'une rotation du tore $\mathbb(T)^2$, totalement irrationnelle. Cette preuve permet de plus, d'obtenir une estimation de la complexité directionnelle du billard dans certains prismes droits. Au deuxième chapitre, on obtient, grâce aux diagonales généralisées, une estimation de la complexité globale du billard cubique. On donne alors au chapitre trois une estimation valable dans n'importe quel polyèdre convexe: On montre en fait que le billard est d'entropie topologique nulle. Le chapitre quatre traite alors du problème des orbites périodiques. On donne une condition suffisante, pour qu'un mot soit stable. On montre de plus l'existence d'une trajectoire périodique dans le tétraèdre régulier. Pour finir on s'intéresse, dans le chapitre cinq, à une sous classe d'échange de rectangles. On montre que ces applications sont ergodiques, et de complexité quadratique. Ces applications sont reliées au billard puisque, à direction fixée, l'application de premier retour est une application affine par morceaux.

L'objet de cette thèse est l'étude des liens existant entre la combinatoire de l'écriture d'un nombre réel en base entière ou sous la forme d'une fraction continue et le caractère algébrique ou transcendant de ce nombre réel (une conjecture de Borel prévoit que tout irrationnel algébrique est un nombre absolument normal: ses écritures en bases entières ont la même propriété que celle d'une suite aléatoire de chiffres).