Thèse de doctorat : Informatique : Lyon, École normale supérieure (sciences) : 2004. / Bibliogr. p. 101-104.

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.

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

Etant donnée une substitution de dimension 1, notée $\sigma$, nous pouvons définir l'enveloppe $\Omega_\sigma$ formant un système dynamique $(\Omega_\sigma, \R)$ où l'action de $\R$ sur les pavages est donnée par les translations. Si la substitution est primitive alors nous pouvons construire un pavage $P$ du demi-plan de Poincaré $\mathbb H_2 $ muni de sa métrique $\frac{\mathrm d x + \mathrm d y}{y^2}$. De manière analogue nous pouvons construire des enveloppes pour les actions de $N= \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto z +t, t\in \R\}$ et $G = \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto a z +b,(a,b) \in \R_+ ^* \times \R\}$ que l'on notera respectivement $X_P ^N$ et $X_{P(c)}^G$ (où $P(c)$ est le pavage colorié ligne à ligne pour rendre l'action de $G$ libre).\par En utilisant la notion de $C^* $-algèbre de groupoïde ainsi que les résultats obtenus dans l'article de Ian Putnam et Jared Anderson et via l'isomorphisme issu de l'équivalence Morita entre $C((\Xi \times \R)/\As)$ et $C(\Xi) \rtimes \Z$, nous pouvons donner la description de la $C^*$-algèbre de l'enveloppe du pavage hyperbolique en termes de générateurs et relations. Nous terminons par la description des générateurs de la $K$-théorie de $C(X_{P(c)}^G) \rtimes G.$ pour les substitutions de Fibonacci, Thue-Morse et Tribonacci / Given a one dimensional substitution $\sigma$, one can define the continuous hull $\Omega_\sigma$ for the $\R$-action given by translations and so we obtain a dynamical system $(\Omega_\sigma,\sigma)$. If the substitution we choose is primitive, then we can construct an hyperbolic tiling on Poincaré's half-plane equiped with its standard metric $\frac{\mathrm d x +\mathrm d y}{y^2}$. By analogy of the standard case, we can define two continuous hulls, denoted $X_P ^ N $ and $X_{P(c)}^G$, where $P(c)$ is a colored tiling (in such fashion that the action of $G$ is free), and the groups are denoted respectively $N= \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto z +t, t\in \R\}$ and $G = \{ \mathbb{H}_2 \to \mathbb{H}_2, z \mapsto a z +b,(a,b) \in \R_+ ^* \times \R\}$.\par Using Jean Renault's construction of the reduced $C^*$-algebra of a groupoid , the results of Ian Putnam and Jared Anderson and the Morita equivalence between $C((\Xi\times \R)/\As)$ and $C(\Xi) \rtimes \Z$, we describe the $C^*$-algebra of the hyperbolic tiling using generators and relations. Finally we obtain for the Fibonacci, Thue-Morse and Tribonacci substitutions the full description of the generators of $K_* (C(X_{P(c)}^G ) \rtimes G)$

Cette thèse, constituée d'une série d'articles, considère des questions issues de la géométrie discrète en les traitant du point de vue de la combinatoire des mots qui s'avère un outil puissant et approprié pour les résoudre. Nous utilisons les mots soit pour représenter un chemin dans Z2 ou Z3, soit pour coder la suite des virages d'un chemin ou le contour d'une figure discrète fermée. Parmi les thèmes abordés, on compte les pavages du plan par polyominos, la notion de complexité en facteurs palindromes et la génération de droites discrètes 3D. La première partie concerne les pavages du plan où nous étudions le nombre de pavages réguliers du plan par une tuile carrée, c'est-à-dire une tuile ayant quatre tuiles adjacentes identiques. Il s'avère que certaines tuiles carrées pavent le plan de deux façons distinctes et elles sont appelées doubles carrées. Nous démontrons d'abord qu'il y a au plus deux tels pavages réguliers par une tuile carrée. Ensuite, nous considérons deux familles particulières de tuiles doubles carrées : les tuiles de Christoffel et les tuiles de Fibonacci. Ces deux familles décrivent les plus petits exemples de tuiles doubles carrées et peuvent être définies à partir des mots de Christoffel et du mot de Fibonacci par des règles de substitution et de concaténation. Les tuiles de Fibonacci définissent aussi une fractale, obtenue par un chemin auto-évitant, dont nous avons calculé plusieurs statistiques, comme le rapport de l'aire de la fractale sur l'aire de son enveloppe convexe. Dans l'article suivant, nous démontrons que tout double carré indécomposable est invariant sous une rotation de 180 degrés. Cette propriété géométrique est équivalente au fait que le mot de contour de la tuile se factorise en un produit de palindromes. Notre preuve repose sur une méthode de génération exhaustive des tuiles doubles carrées. La deuxième partie concerne la complexité palindromique - le nombre de facteurs palindromes distincts -, un sujet propre à la combinatoire des mots. Nous y considérons quatre classes de complexité palindromique qui découlent naturellement de la notion de défaut. Nous caractérisons notamment les mots de complexité palindromique minimale sur un alphabet à deux lettres et nous démontrons que les mots infinis obtenus par codage de rotations sur deux intervalles atteignent la complexité palindromique maximale. Dans une troisième partie, nous proposons une méthode basée sur des algorithmes de fractions continues multidimensionnelles pour la génération de droite discrètes 3D 6-connexes. Les expérimentations illustrent que la complexité en facteurs des mots ainsi générés serait linéaire. Cela se compare avantageusement aux autres définitions de droites discrètes 3D 6-connexes dont la complexité en facteurs est quadratique. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : combinatoire des mots, géométrie discrète, pavage, polyomino, complexité palindromique, droite discrète, algorithme de fractions continues multidimensionnelles.

Nous avons étudié la dynamique de Glauber sur les pavages de domaines finies du plan par des losanges ou par des dominos de taille 2 × 1. Ces pavages sont naturellement associés à des surfaces de R^3, qui peuvent être vues comme des interfaces dans des modèles de physique statistique. En particulier les pavages par des losanges correspondent au modèle d'Ising tridimensionnel à température nulle. Plus précisément les pavages d'un domaine sont en bijection avec les configurations d'Ising vérifiant certaines conditions au bord (dépendant du domaine pavé). Ces conditions forcent la coexistence des phases + et - ainsi que la position du bord de l'interface. Dans la limite thermodynamique où L, la longueur caractéristique du système, tend vers l'infini, ces interfaces obéissent à une loi des grand nombre et convergent vers une forme limite déterministe ne dépendant que des conditions aux bord. Dans le cas où la forme limite est planaire et pour les losanges, Caputo, Martinelli et Toninelli [CMT12] ont montré que le temps de mélange Tmix de la dynamique est d'ordre O(L^{2+o(1)}) (scaling diffusif). Nous avons généralisé ce résultat aux pavages par des dominos, toujours dans le cas d'une forme limite planaire. Nous avons aussi prouvé une borne inférieure Tmix ≥ cL^2 qui améliore d'un facteur log le résultat de [CMT12]. Dans le cas où la forme limite n'est pas planaire, elle peut être analytique ou bien contenir des parties "gelées" où elle est en un sens dégénérée. Dans le cas où elle n'a pas de telle partie gelée, et pour les pavages par des losanges, nous avons montré que la dynamique de Glauber devient "macroscopiquement proche" de l'équilibre en un temps L^{2+o(1)}

Nous avons étudié la dynamique de Glauber sur les pavages de domaines finies du plan par des losanges ou par des dominos de taille 2 × 1. Ces pavages sont naturellement associés à des surfaces de R^3, qui peuvent être vues comme des interfaces dans des modèles de physique statistique. En particulier les pavages par des losanges correspondent au modèle d'Ising tridimensionnel à température nulle. Plus précisément les pavages d'un domaine sont en bijection avec les configurations d'Ising vérifiant certaines conditions au bord (dépendant du domaine pavé). Ces conditions forcent la coexistence des phases + et - ainsi que la position du bord de l'interface. Dans la limite thermodynamique où L, la longueur caractéristique du système, tend vers l'infini, ces interfaces obéissent à une loi des grand nombre et convergent vers une forme limite déterministe ne dépendant que des conditions aux bord. Dans le cas où la forme limite est planaire et pour les losanges, Caputo, Martinelli et Toninelli [CMT12] ont montré que le temps de mélange Tmix de la dynamique est d'ordre O(L^{2+o(1)}) (scaling diffusif). Nous avons généralisé ce résultat aux pavages par des dominos, toujours dans le cas d'une forme limite planaire. Nous avons aussi prouvé une borne inférieure Tmix ≥ cL^2 qui améliore d'un facteur log le résultat de [CMT12]. Dans le cas où la forme limite n'est pas planaire, elle peut être analytique ou bien contenir des parties “gelées” où elle est en un sens dégénérée. Dans le cas où elle n'a pas de telle partie gelée, et pour les pavages par des losanges, nous avons montré que la dynamique de Glauber devient “macroscopiquement proche” de l'équilibre en un temps L^{2+o(1)} / We studied the Glauber dynamics on tilings of finite regions of the plane by lozenges or 2 × 1 dominoes. These tilings are naturally associated with surfaces of R^3, which can be seen as interfaces in statistical physics models. In particular, lozenge tilings correspond to three dimensional Ising model at zero temperature. More precisely, tilings of a finite regions are in bijection with Ising configurations with some boundary conditions (depending on the tiled domain). These boundary conditions impose the coexistence of the + and - phases, together with the position of the boundary of the interface. In the thermodynamic limit where L, the characteristic length of the system, tends toward infinity, these interface follow a law of large number and converge to a deterministic limit shape depending only on the boundary condition. When the limit shape is planar and for lozenge tilings, Caputo, Martinelli and Toninelli [CMT12] showed that the mixing time of the dynamics is of order (L^{2+o(1)}) (diffusive scaling). We generalized this result to domino tilings, always in the case of a planar limit shape. We also proved a lower bound Tmix ≥ cL^2 which improve on the result of [CMT12] by a log factor. When the limit shape is not planar, it can either be analytic or have some “frozen” domains where it is degenerated in a sense. When it does not have such frozen region, and for lozenge tilings, we showed that the Glauber dynamics becomes “macroscopically close” to equilibrium in a time L^{2+o(1)}

Au Québec, des milliers de tonnes de résidus de béton sont issus de la démolition des infrastructures et des milliers de tonnes de verre sont récupérés annuellement. Seulement près de la moitié de ces résidus sont réutilisés. La pression pour trouver des applications potentielles permettant une réutilisation optimale de ces résidus de démolition est grandissante. Dans un contexte de développement durable, la ville de Montréal a comme défi de réutiliser tous les matériaux de démolition qu’elle génère et tout le verre qu’elle récupère. Ce projet de recherche, financé par la ville de Montréal, s’inscrit donc dans une perspective de valorisation des matériaux recyclés et de développement de matériaux innovants et durables. L’objectif de cette étude de recherche est d’étudier et d’évaluer les divers potentiels d’application des granulats de béton recyclé et des granulats de verre recyclé dans les bétons compactés au rouleau. Le programme d’essais réalisé dans le cadre de cette étude comporte quatre phases. Dans un premier temps, des essais réalisés sur les matériaux recyclés ont permis de mieux les caractériser afin de formuler des mélanges de BCR optimaux. Par la suite, les propriétés à l’état frais et les propriétés mécaniques des BCR ont été réalisées en laboratoire. L’analyse de ces propriétés a permis de déterminer un taux de remplacement optimal. Ce taux de remplacement a été utilisé afin d’évaluer l’impact sur la durabilité des mélanges. Finalement, des analyses sommaires ont été réalisées afin de démontrer l’impact économique et environnemental d’un remplacement granulaire par des MR-2 dans les BCR. Les travaux de recherches ont montré qu’un remplacement granulaire par des matériaux recyclés affecte les propriétés à l’état frais, les propriétés mécaniques et la durabilité des BCR. Il a été montré qu’un taux de remplacement de ± 40 % dans le cas des granulats de béton recyclé et de ± 25 % dans le cas des granulats de verre recyclés permet d’obtenir un BCR présentant des propriétés satisfaisantes. Finalement, des analyses sommaires démontrent que l’utilisation de matériaux recyclés dans les BCR est profitable tant en matière économique et qu’en matière environnementale.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Alors que l'on observe une disponibilité croissante de données décrivant des objets 3D, il semble essentiel de disposer de moyens de traitement efficaces de ces derniers. Ainsi, nous présentons dans ce mémoire un ensemble d'outils de manipulation de surfaces, qui exploitent à la fois leurs propriétés géométriques et topologiques. Après avoir décrit différents résultats classiques de topologie, et les structures et résultats fondamentaux de la topologie algorithmique, nous présentons les concepts de M-tuiles et M-pavages, offrant notamment une grande souplesse combinatoire, et permettant de décrire finement le résultat d'algorithmes de découpage topologique. En s'appuyant sur les possibilités de description de ce formalisme, nous présentons différents algorithmes de découpage de surface, prenant en compte non seulement la topologie et la géométrie des surfaces, mais également les propriétés des M-tuiles issues de ces découpages. Nous présentons également dans ce mémoire une généralisation des lacets par les n-cets, permettant notamment de décrire une approche originale de pavage de surfaces en cylindres puis en quadrangles. Enfin, deux applications de ces outils de découpage sont présentées. Dans un premier temps, nous déclinons ces algorithmes de découpage dans le contexte de l'infographie, en proposant un ensemble d'outils d'aide à la manipulation de surfaces. Puis nous présentons dans un second temps une chaîne complète de traitement de données issues de l'imagerie médicale, permettant la visualisation dynamique de données complexes sur des cartes planes de la surface du cerveau, en illustrant sa pertinence dans le contexte de la stimulation corticale. En conclusion de ces travaux, nous présentons les perspectives que laissent entrevoir ces développements originaux, notamment en exploitant les possibilités offertes par les n-cets et les M-pavages, qui semblent multiples. Nous soulignons également la richesse qu'assure une exploration des domaines applicatifs par des outils issus de la géométrie algorithmique.