Le présent travail porte sur la classification de structures arborescentes selon leurs symétries. Plus précisément, il fait l'objet de celle des arbres plans, des 2-arbres k-gonaux exterplanaires, des 2-arbres k-gonaux sans sommets de degré 4 et des 2-arbres polygonaux exterplanaires. Ceci est fait en déterminant le développement moléculaire de ceux-ci vus comme espèces de structures. Le développement moléculaire des arbres plans est obtenu à l'aide du théorème de dissymétrie des arbres R-enrichis (voir Bergeron, Labelle et Leroux, 1994) et par l'utilisation d'une formule d'addition pour Ck(B) où B est une espèce et Ck est l'espèce des cycles orientés de longueur k. Cette formule se trouve dans (Ducharme, 2005). En généralisant cette formule au cas où B est pondérée, nous obtenons le développement moléculaire des arbres plans pondérés par la distribution des degrés de leurs sommets. En ce qui a trait aux 2-arbres k-gonaux exterplanaires, une telle classification pour k = 3 a été faite dans (Labelle, Lamathe et Leroux, 2003; Lamathe 2003) et pour k = 4,5 dans (Ducharme, 2005) en utilisant des formules d'addition d'espèces auxiliaires exprimant des espèces pointées qui, à l'aide d'un théorème de dissymétrie, peuvent exprimer les espèces des 2-arbres k-gonaux exterplanaires. Le seul résultat manquant dans (Ducharme, 2005), pour obtenir le développement moléculaire des 2-arbres k-gonaux exterplanaires, est celui des 2-arbres k-gonaux exterplanaires pointés en un polygone. Celui-ci est obtenu par l'énumération de classes diédrales de mots dont les lettres représentent chacune un type d'isomorphie de 2-arbres k-gonaux exterplanaires pointés en une arête orientée. C'est aussi par l'énumération de classes diédrales que nous obtenons une nouvelle formule d'addition de Pn donnant le développement moléculaire de Pn(B) en fonction de celui des puissances de l'espèce B où Pn est l'espèce des polygones de taille n (cycles non orientés de longueur n). Les espèces apparaissant dans cette formule sont de la forme Pbic 2i (N, M, L) ou Cj(K) où K, L, M et N sont des espèces moléculaires, i|k, j|k et Pbic 2i (X, Y, Z) est une espèce moléculaire de polygones bicolorés. Nous donnons également une condition pour déterminer si Pbic 2i (N₁, M₁, L₁) et Pbic 2j (N₂, M₂, L₂) sont isomorphes dans le cas où N₁, M₁, L₁, N₂, M₂ et L₂ sont des espèces asymétriques. Comme le développement moléculaire des différentes espèces pointées de 2-arbres k-gonaux exterplanaires ne font appel qu'à des espèces asymétriques et aux espèces Ci et Pbic 2i(X, Y, Z) dans lesquelles on a substitué des espèces asymétriques, on peut facilement regrouper les termes semblables pour obtenir le développement moléculaire des 2-arbres k-gonaux exterplanaires. Les coefficients de ce développement moléculaire sont exprimés en fonction de ceux des puissances entières de l'espèce des 2-arbres k-gonaux exterplanaires pointés en une arête orientée. Ces derniers coefficients sont obtenus par inversion de Lagrange. Pour le cas des 2-arbres k-gonaux sans sommets de degré 4, nous faisons une distinction entre les types dont le groupe d'isomorphismes d'ordre 2 est généré par une rotation non trivial et ceux dont le groupe est généré par une réfexion. Ceux-ci sont isomorphes à NE₂ (M) mais seront respectivement associés à l'espèce NC₂ (M) et à l'espèce Pbic 2 (N, M, 1). En plus, seules certaines classes diédrales de mots, dont les lettres représentent chacune un type d'isomorphie de 2-arbres k-gonaux sans sommets de degré 4 pointés en une arête externe orientée dont les sommets sont de degré 2, représentent un type de 2-arbres k-gonaux sans sommets de degré 4. Les coefficients du développement moléculaire des 2-arbres k-gonaux sans sommets de degré 4 sont ensuite exprimés en fonction des coefficients de celui de puissances d'espèces asymétriques obtenus encore par inversion de Lagrange. Le cas des 2-arbres polygonaux exterplanaires est très similaire au cas des 2-arbres k-gonaux exterplanaires où k est pair. L'étiquetage est effectué aux sommets plutôt qu'aux polygones, ce qui occasionne des changements mineurs aux définitions des classes diédrales à énumérer. Les espèces moléculaires de leur développement moléculaire peuvent encore être décrites à l'aide d'espèces asymétriques et de Ci et Pbic 2j (X, Y, Z) où i et j sont des entiers. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Arboresence, 2-arbres, Exterplanaire, Moléculaire, Développement.

Reproduction de : Thèse de doctorat : Informatique : Clermont-Ferrand 2 : 2005. / Thèse avec deux annexes. Titre provenant de l'écran-titre. Bibliogr. p. 175-186.

L'objet de cette thèse est d'étudier les liens entre la géométrie discrète et la combinatoire des mots. Le fait que les figures discrètes soient codées par des mots sur l'alphabet à quatre lettres Σ = {0.1.0,1}, codage introduit par Freeman en 1961, justifie l'utilisation de la combinatoire des mots dans leur étude. Les droites discrètes sont des objets bien connus des combinatoriciens, car étant identifiés par les mots Sturmiens. dont on trouve déjà une description assez complète dans les travaux de Christoffel à la fin du XIXe siècle à la suite de travaux précurseurs de Bernouilli et Markov. Alors que l'on comprend bien la structure des droites discrètes, on connait beaucoup moins bien les courbes en général. Cet ouvrage porte sur l'étude de propriétés géométriques de courbes fermées, codées sur l'alphabet Σ . On s'intéresse tout d'abord à la représentation des chemins dans le plan discret Z² et de ceux qui codent les polyominos. Dans un premier temps, l'emploi d'une structure arborescente quaternaire permet d'élaborer un algorithme optimal afin de tester si un mot quelconque sur Σ code un polyomino ou non. Ce résultat est fondamental d'abord parce qu'il est nouveau, élégant et qu'il se généralise en dimension supérieure. En outre, la linéarité de ce test rend les algorithmes subséquents vraiment efficaces. À la suite de résultats précurseurs de Lyndon. Spitzer et Viennot sur la factorisation des mots, il existe une interprétation combinatoire de la convexité discrète. En géométrie algorithmique, des algorithmes linéaires furent établis par McCallum et Avis en 1979, puis par Melkman en 1987, pour calculer l'enveloppe convexe d'un polygone. Debled-Rennesson et al. ont obtenu en 2003, un algorithme linéaire pour décider de la convexité discrète d'un polyomino par des méthodes arithmétiques. Nous avons obtenu grâce aux propriétés spécifiques des mots de Lyndon et de Christoffel un algorithme linéaire pour tester si un polyomino est digitalement convexe. L'algorithme obtenu est extrêmement simple et s'avère dix fois plus rapide que celui de Debled-Rennesson et al. Finalement, le calcul de la plus longue extension commune à deux mots en temps constant -obtenu par Gusfield à l'aide des arbres suffixes -et le théorème de Fine et Wilf permettent d'élaborer de nouveaux algorithmes qui, grâce à la caractérisation de Beauquier-Nivat, testent si un polyomino pave le plan par translation. En particulier, on obtient un algorithme optimal en O(n) pour détecter les pseudo-carrés. Dans le cas des pseudo-hexagones ayant des facteurs carrés pas trop longs on obtient également un algorithme linéaire optimal, tandis que pour les pseudo-hexagones quelconques nous avons obtenu un algorithme en O(n(log n)³) que nous croyons ne pas être optimal. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, Géométrie discrète, Droites digitales, Pavages du plan, Algorithmique.

Étude de certains problèmes d'optimisation combinatoire. Le premier concerne un problème de régulation de trafic pour lequel on donne une formulation mathématique et on propose une méthode permettant de le résoudre. Le deuxième problème traité est un des problèmes de la physique statistique qui relève de la combinatoire et de l'optimisation, celui du fondamental d'un verre de spins (modèle d'Ising). Enfin on étudie, deux autres problèmes d'optimisation combinatoire: l'absorbant et le Ki-recouvrement de poids minimum

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Cette thèse s'intéresse à l'étude de deux problèmes d'optimisation pour la production d’énergie électrique. Le premier est un problème académique très étudié : le Unit Commitment Problem (UCP). Le second est un problème de planification des débits d'eau dans un réseau hydro-électrique issu d'une application industrielle. Ces deux problèmes sont des problèmes NP-complets très difficiles car ils sont non linéaires, fortement contraints et que la taille des données est importante. Dans la première partie de cette thèse, nous proposons DYNAMOP. Il s'agit d'un algorithme génétique qui guide la recherche effectuée par la programmation dynamique en manipulant des solutions représentées sous forme de chemins du graphe d’états. Cette représentation est avantageuse car, d'une part, elle facilite la mise en place d'hybridations avec la programmation dynamique et, d'autre part, elle permet de proposer des opérateurs évolutionnaires efficaces tenant compte les dépendances entre les variables. DYNAMOP est appliqué aux deux problèmes de production d'énergie. La qualité des résultats permet d'affirmer que cette méthode est bien adaptée à la résolution de ce type de problèmes. Dans la seconde partie, nous présentons MO-DYNAMOP une extension de DYNAMOP à l'optimisation multi-objectif. MO-DYNAMOP est évalué sur une version bi-objectif de l'UCP nécessitant l'utilisation d'une représentation indirecte. Une solution partielle sera ainsi décodée en un ensemble de solutions complètes Pareto équivalentes ce qui rend difficile l'évaluation sa qualité. Nous proposons donc plusieurs adaptations des stratégies usuelles d'assignation de fitness et comparons les méthodes obtenues à la littérature. / In this thesis, two energy production problems are studied. The first is a well known academic problem: the Unit Commitment Problem (UCP). The second one is a hydro scheduling problem with a real world application. These two problems are very hard NP-complete problems because they are non-linear, highly constrained, and the data size is large. In the first part of this thesis we propose DYNAMOP. It is a genetic algorithm that uses a representation based on a path in the graph of states of dynamic programming. The advantages of this representation are that it makes it easy to propose efficient evolutionary operators taking the dependencies into account, and that it facilitates the hybridization with dynamic programming. DYNAMOP is tested  on the two energy production problems. The results confirm the competitiveness of the proposed method to solve energy problems. In the second part, we present MO-DYNAMOP, which is an extension of DYNAMOP to multi-objective combinatorial optimization problems. MO-DYNAMOP is applied to a bi-objective version of the UCP, but this implies an indirect representation, which is problematic. Indeed, in this case, decoding a genotypic solution involves the resolution of a multi-objective problem. Then many Pareto equivalent phenotypic solutions can be produced from one genotypic solution. We propose and compare 3 decoding strategies to solve this difficulty. A comparison study beetween MO-DYNAMOP and methods previously proposed for the bi-objective UCP is performed. Experiments indicate that MO-DYNAMOP performs considerably better.

L'etude et la comprehension de phenomenes naturels qu'il<br />semble difficile de predire, tels les<br />tremblements de terre et les raz de maree intriguent depuis quelques<br />temps un certain nombre de physiciens. En effet, il semble que les<br />modeles classiques bases sur des fonctions d'etat continues<br />peuvent difficilement expliquer les phenomenes observes.<br /><br />En 1987, Bak, Tang et Wiesenfeld introduisent un modele base<br /> sur un automate particulier dont l'etude experimentale montre<br /> des caracteristiques proches de celles observees pour des<br /> tremblements de terre. Cet automate est appele automate du tas de sable.<br /><br /> En 1990, Dhar, Ruelle, Sen et<br />Verma etudient les proprietes mathematiques<br />de l'automate du tas de sable. Cet article jette les bases d'une théorie algebrique et combinatoire des<br />etats critiques du systeme en montrant que ceux-ci forment un<br />groupe abelien fini.<br /><br />Cette these porte essentiellement sur l'etude de ce groupe d'un<br />point de vue algorithmique, combinatoire et algebrique. Nous<br />etudions dans un premier temps la complexite de l'operateur de<br />groupe. Puis nous etudions le groupe sur quelques familles de<br />graphes connues avant de montrer que le groupe d'un graphe planaire<br />est isomorphe au groupe de chacun de ses duaux geometriques.<br /><br />Nous montrons comment associer à un groupe abelien fini un<br />idéal de polynomes et dans le cas du groupe du Tas de Sable, nous<br />donnerons une caracterisation de l'operateur de groupe en terme de<br />reduction de polynome.

Ce mémoire fait partie du domaine de la combinatoire des mots et plus particulièrement de l'étude de la complexité palindromique (le nombre de facteurs palindromes) des mots infinis. La conjecture de Hof, Knill et Simon, énoncée pour la première fois en 1995, donne une caractérisation des points fixes dont la complexité palindromique est infinie. Récemment, elle a été résolue pour les points fixes sur un alphabet binaire (Tan, 2007). Dans ce mémoire, nous la démontrons pour les points fixes de morphismes uniformes sur un alphabet binaire (ce n'est pas plus général que le résultat de Tan). De plus, notre approche permet d'obtenir une démonstration d'un résultat similaire pour les points fixes contenant une infinité d'antipalindromes. Afin d'atteindre notre objectif, nous établissons un ensemble de résultats combinatoires sur les mots. En effet, nous faisons une étude des ƒ-palindromes et de certaines équations qui en contiennent. Ensuite, nous introduisons les morphismes de classe P, P¹ et ƒ-P et nous démontrons notamment que l'ensemble des morphismes de classe P¹ est un monoïde. Nous rassemblons également les résultats d'un travail précédent sur les morphismes conjugués. Finalement, nous étudions les chevauchements de mots et nous construisons un graphe de chevauchements, assise de notre démonstration de la conjecture. Toutes ces recherches ont contribué au développement d'un outil informatique voué à l'étude de questions soulevées en combinatoire des mots. Ce dernier est constitué d'un ensemble de classes et de fonctions écrites en langage Python annexées à ce mémoire. Elles seront bientôt incluses dans un paquetage sur la combinatoire des mots associé au logiciel libre Sage. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, ƒ-palindrome, Complexité palindromique, Conjecture de Hof, Knill et Simon, Point fixe de morphisme, Chevauchement, Automates.

La combinatoire de Coxeter-Catalan est très jeune. Elle s'est développée dans les deux dernières décennies en lien avec des phénomènes combinatoires reliés aux nombres de Catalan. Entre autres, elle permet d'interpréter certains résultats de la théorie des algèbres amassées, une théorie très vivante ces dernières années. En 2007, N. Reading a donné une interprétation combinatoire des générateurs des algèbres amassées - les amas - à l'aide des groupes de Coxeter et certains éléments - appelés éléments triés - ayant des propriétés combinatoires particulières. Le présent texte rassemble les notions essentielles sur les groupes de Coxeter et la combinatoire sous-jacente, afin de démontrer l'interprétation de N. Reading et d'illustrer certaines conséquences de celle-ci. Tout en introduisant les notions, une attention particulière est accordée à la perspective actuelle des résultats et au cheminement de ceux-ci. Le texte est parsemé d'images pour un apport visuel accru. Celles-ci ont été réalisées à l'aide de la librairie TikZ de LATEX. ______________________________________________________________________________

Ce travail se consacre principalement à l'étude d'équations sur les mots ainsi qu'à leur application en géométrie discrète. Comme le rappelle Freeman en 1961, tout chemin dans le plan discret, que l'on peut voir comme une liste de déplacements parmi {→, ↑, ←, ↓}, peut être représenté par un mot pour lequel chaque lettre représente l'un des quatre déplacements élémentaires possibles. Ce point de vue offre entre autre la possibilité de décrire plusieurs objets de la géométrie discrète, tels les polyominos par exemple, en termes d'équations sur les mots. Dans cet ouvrage, nous utilisons cette correspondance pour étudier les pavages du plan par translation dont il est bien connu qu'il en existe deux réguliers : les pavages hexagonaux et les pavages carrés. Ce résultat important fut établi par Beauquier et Nivat et a permis d'étudier les pavages du point de vue algorithmique. Une classe importante est apparue naturellement, à savoir celle des polyominos qui pavent le plan par translation de plusieurs manières. Alors qu'il existe des polyominos pavants à la manière d'un hexagone d'un nombre arbitraire de façons, il en est tout autrement pour le cas des carrés: nous présentons et résolvons la conjecture selon laquelle un polyomino pave comme un carré d'au plus deux façons, puis nous étudions plus en détail la structure de ces derniers. Puisque les contours sont codés sur un alphabet fini, la combinatoire des mots s'impose comme l'outil principal pour traiter ces problèmes de nature géométrique. ______________________________________________________________________________