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).

La recherche de la solution optimale d'un problème combinatoire est souvent très longue puisque, d'une manière générale, le temps de résolution est une fonction exponentielle de la taille de ce problème. Dès l'instant où on se place dans un contexte temps réel, c'est-à-dire chaque fois qu'on impose une limite au temps de calcul alloué, les algorithmes d'optimisation classique s'avèrent, à quelques rares exceptions près , impuissants, et on doit se contenter d'utiliser des méthodes heuristiques. La présente étude porte sur l'évaluation de celles qui sont susceptibles d'apporter une réponse satisfaisante à certains problèmes d'ordonnancement. Trois types d'approches sont étudiées : - les heuristiques non convergentes, - les heuristiques convergentes, - les méthodes d'apprentissage. L'évaluation de leurs performances est réalisée sur le double critère de la qualité de la solution et du temps de calcul nécessaire à leur mise en œuvre.

L'introduction des polynômes de Macdonald (Macdonald, 1988) comme des vecteurs propres associés à certains opérateurs reliés à la physique et comme une généralisation de quelques-unes des bases les plus importantes de l'anneau des fonctions symétriques, a donné lieu à un nombre remarquable de résultats dans divers domaines de l'algèbre, la combinatoire et la géométrie algébrique, entre autres. Ce travail présente un des liens entre la théorie des fonctions symétriques et la théorie des représentations des groupes, donné par les polynômes de Macdonald et les modules de Garsia-Haiman. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire algébrique, Combinatoire énumérative, Fonctions symétriques, Modules de Garsia-Haiman, Polynômes de Macdonald, Théorie des représentations.