Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés.

Nous étudions dans cette thèse la notion de quasipériodicité,introduite par Apostolico et Ehrenfeucht au début des années 1990,puis étendue aux mots infinis par Solomon Marcus au début des années2000. Un mot (fini ou infini) w est quasipériodique s'il peut êtrecouvert par des occurrences, éventuellement chevauchantes, d'un autremot, fini, appelé sa quasipériode. En 2006, Monteil etMarcus ont introduit la notion plus forte de quasipériodicitémulti-échelles : le fait d'avoir une infinité de quasipériodes.Dans un premier temps, nous étudions la quasipériodicité des motsinfinis bidimensionnels. Nous montrons que, contrairement au casunidimensionnel où la quasipériodicité ne force aucune propriété fortedes mots infinis, il existe des quasipériodes q qui forcent les mots2D q-quasipériodiques à être d'entropie nulle. Nous montrons égalementque la quasipériodicité multi-échelles en deux dimensions forcel'existence de fréquences uniformes pour les facteurs.Dans un deuxième temps, nous donnons des résultats sur les motsinfinis en une dimension. Nous donnons notament une approchepermettant de déterminer les quasipériodes d'un mot infini à partir deses facteurs carrés et de ses facteurs spéciaux. Nous montrons ensuiteque la famille des mots périodiques, ainsi que celle des mots standardsturmiens, peuvent être caractérisées en termes de quasipériodicitémulti-échelles. / We study the notion of quasiperiodicity, introduced by Apostolico and Ehrenfeucht at the beginning of the 1990's, then extended to infinite words by Solomon Marcus at the beginning of the 2000's. A (finite or infinite) word w is quasiperiodic if it can be covered by occurrences, possibly overlapping, of another finite word, call its quasiperiod. In 2006, Monteil and Marcus introduced a stronger notion: multi-scale quasiperiodicity, the property of having infinitely many quasiperiods.First we study quasiperiodicity of two-dimensional infinite words. We show that, by contrast with the one-dimensional case where quasiperiodicity do not force any property on infinite words, there exist quasiperiods q which force 2D q-quasiperiodic words to have zero entropy. We also show that multi-scale quasiperiodicity in two dimension force the existence of uniform frequencies for factors.Then we give results on infinite words in one dimension. Most notably we give a method to determine the quasiperiods of an infinite words from its square and special factors. We show that the family of periodic words and standard Sturmian words are characterizable in terms of multi-scale quasiperiodicity.

Dans cette thèse, nous construisons des pavages de la droite réelle et du demi-plan hyperbolique à l’aide de représentants efficaces d’automorphismes IWIP du groupe libre Fn. Dans un premier temps, nous utilisons la substitution définie par P. Arnoux, V. Berthé, A. Siegel, A. Hilion associée à un représentant efficace d’un automorphisme IWIP pour générer des espaces de pavages substitutifs apériodiques de la droite réelle. Nous montrons, en nous servant d’un théorème de connexité des représentants efficaces d’automorphismes IWIP dû à J. Los, que le type topologique de ces espaces de pavages est indépendant du choix du représentant. Nous associons ainsi, à homéomorphisme près, un espace de pavages de la droite réelle à une classe d’automorphisme externe IWIP de Fn, puis à une classe de conjugaison d’un élément IWIP dans Out(Fn). D’autre part, nous construisons à partir des éléments de l’espace de pavage de la droite réelle précédemment construits des pavages faiblement apériodiques pour le groupe des transformations affines du demi-plan hyperbolique. Nous étudions les propriétés topologiques et dynamiques de ces espaces de pavages du plan hyperbolique. Enfin, dans une dernière partie, nous montrons que les espaces de pavages précédemment construits peuvent être munis d’une structure lisse en se servant de leur structure de limite projective. / In this thesis, we construct tilings of the real line and the hyperbolic half-plane using train-track maps of IWIP free group automorphisms. One the one hand, we use a substitution defined by P. Arnoux, V. Berthé, A. Siegel, A. Hilion coming from a train-track map of a IWIP free group automorphism to generate substitutive aperiodic tilings of the real line. We show, thanks to a theorem of J. Los about connectivity of train-track representatives of an IWIP automorphism, that the topological type of those tiling spaces is the same up to a choice of train-track representative. Thus we associate, up to an homeomorphism, a tiling space of the real line to a class of an IWIP outer automorphism of Fn, then we extend this result to a conjugacy class of an IWIP element in Out(Fn). On the other hand, we construct from elements of tiling spaces of the real line previously defined, a set of weakly aperiodic for the affine group tilings of the hyperbolic half-plane. We study topological et dynamical properties of the tiling space generated by those hyperbolic tilings. Finally, in the last section we endow tiling spaces previously constructed with a smooth structure thanks to their inverse limit structure.

Cette thèse est dédiée à l'étude des pavages : des ensembles de coloriages du plan discret respectant des contraintes locales données par un jeu de tuiles. Nous nous penchons en particulier sur les liens qui unissent les pavages et la calculabilité. Les pavages étant des ensembles effectivement clos particuliers, nous étudions dans un premier temps la structure des ensembles de degrés Turing des pavages, la comparant à celle des ensembles effectivement clos en général : pour tout ensemble effectivement clos il existe un pavage qui a les même degrés Turing à 0 près, le degré des ensembles récursifs. De plus les pavages ne contenant pas de membre récursif ont une structure particulière : ils contiennent toujours un cône de degrés Turing, un degré Turing et tous les degrés qui lui sont supérieurs. Dans un second temps, nous étudions les ensembles de périodes des pavages, pour diverses notions de périodicité, parvenant à des caractérisations à l'aide de classes de complexité ou de calculabilité pour chaque notion étudiée. Enfin nous nous intéressons à la difficulté calculatoire des problèmes de la factorisation et de la conjugaison, des notions de simulation et d'équivalence adaptées aux spécificités des pavages. / This thesis is dedicated to the study of subshifts of finite type (SFTs) : sets of colorings of the discrete plane which respect some local constraints given by a set of forbidden patterns. We study the links between SFTs and computation. SFTs being specific effectively closed classes, we fist study their Turing degree structure, comparing it to the one of effectively closed classes in general: for any effectively closed class, there exist an SFT having the same Turing degrees except maybe 0, the degree of recursive sets. Furthermore, SFTs containing no recursive member have a particular structure: they always contain a cone of Turing degrees, ie. a Turing degree and all degrees above it. We then study the sets of periods of SFTs, for different notions of periodicity, reaching characterizations by means of computational complexity classes or computability classes for each notion introduced. Finally we look at the computable hardness of the factorization and conjugacy problems, the right notions of simulation and equivalence for SFTs.

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés. / In this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in codings of rotations, a family of words including the famous Sturmian words and Rote sequences. In particular, we show that these words are full, i.e. they realize the maximal palindromic complexity. Next, we consider a new family of words called generalized pseudostandard words, which are generated by an operator called iterated pseudopalindromic closure. We present a generalization of a formula described by Justin which allows one to generate in linear (thus optimal) time a generalized pseudostandard word. The central object, the f-palindrome or pseudopalindrome, is an indicator of the symmetries in geometric objects. In the last chapters, we focus on geometric problems. More precisely, we solve two conjectures of Provençal about tilings by translation, by exploiting the presence of palindromes and local periodicity in boundary words. At the end of many chapters, different open problems and conjectures are briefly presented.

Les travaux présentés ici s'intéressent aux coloriages du plan discret. Ce modèle d'inspiration géométrique est intrinsèquement lié aux modèles de calcul, et son étude se décline ici suivant deux axes complémentaires: calculabilité et combinatoire. Nous montrons en particulier ici comment de nombreux résultats récents s'expriment naturellement à travers le concept de bases, propriétés vérifiées par au moins un point de tout ensemble de coloriages, et d'antibases, contre-exemples à ce concept. Nous examinons ensuite les différents codages du calcul par des jeux de tuiles et exhibons en particulier un nouveau codage épars, permettant de caractériser les degrés Turing des ensembles de coloriages. Enfin nous revenons aux origines en étudiant les pavages du point de vue de la logique. Nous caractérisons ainsi les grandes familles d'ensembles de coloriages par des fragments de la logique monadique du second ordre.

Nous considérons le problème d’un électron sur des pavages quasipériodiques en une et deux dimensions. Nous introduisons tout d’abord les pavages quasipériodiques d’un point de vue géométrique, et défendons en particulier l’idée que ces pavages sont les pavages apériodiques les plus proches de la périodicité. Nous concentrant plus particulièrement sur l’un des pavages quasipériodiques les plus simples, la chaîne de Fibonacci, nous montrons à l’aide d’un groupe de renormalisation que la multifractalité des états électroniques découle directement de l’invariance d’échelle de la chaîne. Élargissant ensuite notre champ d’étude à un ensemble de chaînes quasipériodiques, nous nous intéressons au théorème de label des gaps, qui décrit comment la géométrie d’une chaîne donnée contraint les valeurs que peut prendre la densité d’états intégrée dans les gaps du spectre électronique. Plus précisément, nous nous intéressons à la façon dont l’énoncé de ce théorème est modifié lorsque l’on considère une séquence d’approximants périodiques approchant une chaîne quasipériodique. Enfin, nous montrons comment des champs de hauteurs géométriques peuvent être utilisés pour construire des états électroniques exacts sur des pavages en une et deux dimensions. Ces états sont robustes aux perturbations du hamiltonien, sous réserve que ces dernières respectent les symétries du pavage sous-jacent. Nous relions les dimensions fractales de ces états à la distribution de probabilités des hauteurs, que nous calculons de façon exacte. Dans le cas des chaînes quasipériodiques, nous montrons que la conductivité suit une loi d’échelle de la taille de l’échantillon, dont l’exposant est relié à cette même distribution de probabilités. / We consider the problem of a single electron on one and two-dimensional quasiperiodic tilings. We first introduce quasiperiodic tilings from a geometrical point of view, and point out that among aperiodic tilings, they are the closest to being periodic. Focusing on one of the simplest one-dimensional quasiperiodic tilings, the Fibonacci chain, we show, with the help of a renormalization group analysis, that the multifractality of the electronic states is a direct consequence of the scale invariance of the chain. Considering now a broader class of quasiperiodic chains, we study the gap labeling theorem, which relates the geometry of a given chain to the set of values the integrated density of states can take in the gaps of the electronic spectrum. More precisely, we study how this theorem is modified when considering a sequence of approximant chains approaching a quasiperiodic one. Finally, we show how geometrical height fields can be used to construct exact eigenstates on one and two-dimensional quasiperiodic tilings. These states are robust to perturbations of the Hamiltonian, provided that they respect the symmetries of the underlying tiling. These states are critical, and we relate their fractal dimensions to the probability distribution of the height field, which we compute exactly. In the case of quasiperiodic chains, we show that the conductivity follows a scaling law, with an exponent given by the same probability distribution.

Ce mémoire de thèse est une contribution à l'étude des canons modulo p. De nombreux outils mathématiques et informatiques ont été employés pour l'étude des canons rythmiques mosaïques. La recherche récente s'est particulièrement attachée à trouver les canons sans périodicité interne, dits de Vuza. Ces canons ont la particularité d'être une base pour la construction de tous les canons rythmiques mosaïques, cependant ils sont très difficiles à obtenir. La meilleure méthode actuellement est un algorithme exhaustif de recherche, qui malgré de récentes améliorations reste exponentiel. Plusieurs techniques ont été utilisées dans l'espoir de mieux les comprendre ou de les générer plus rapidement. Ce mémoire présente donc un nouveau sujet d'étude pour mieux comprendre le pavage apériodique. / This thesis is a contribution to the study of modulo p tiling. Many mathematical and computational tools were used for the study of rhythmic tiling canons. Recent research has mainly focused in finding tiling without inner periodicity, being called Vuza canons. Those canons are a constructive basis for all rhythmic tiling canons, however, they are really difficult to obtain. Best current method is a brut force exploration that, despite a few recent enhancements, is exponential. Many technics have been used, hoping to understand Vuza canons better or to generate them faster. Hence, this thesis presents a completely new way to study aperiodic tiling.

Dans la tradition occidentale, mathématiques et musique ont été étroitement liées depuis plus de 2000 ans. Nonobstant cette longue histoire concernant les relations entre mathématiques et musique, l'intérêt professionnel des mathématiciens dans ce domaine est un phénomène assez récent. Alors que la puissance d'application des mathématiques dans la description de la musique a été reconnue depuis longtemps, c'est seulement grâce a des développements plus récents que la musique commence à occuper également une place stratégique au sein des mathématiques. Ce fait est confirmé par l'émergence d'un nombre croissant de problèmes «~mathémusicaux~». Ces problèmes sont caractérisés par le fait qu'en positionnant un problème à l'origine musical dans un contexte mathématique approprié non seulement on obtient des résultats mathématiques nouveaux mais cela ouvre la voie également à des constructions musicales nouvelles. C'est ce double mouvement, de la musique aux mathématiques et vice-versa, qui suscite l'intérêt de plus en plus de chercheurs dans les deux domaines et qui est au c\oe ur d'une croissante activité de recherche internationale accompagnée de la création de revues internationales à comité de lecture et collections d'ouvrages consacrés à la matière ainsi que d'une prolifération de conférences, séminaires d'études et projets collaboratifs dans le domaine. Dans la première partie de ce mémoire, nous présentons tout d'abord une sélection de problèmes «~mathémusicaux~» sur lesquels nous avons travaillé en montrant les résultats obtenus et les questions qui restent ouvertes. Dans la deuxième partie, nous détaillons trois types d'interactions entre recherche mathémusicale et trois autre disciplines, à savoir les sciences cognitives, l'informatique et la philosophie.

"Dynamics" is very roughly the study of how objects change in time; for instance whether an electrical circuit goes to equilibrium, due to thermal dissipation. By "information", we mean how helpful it is to observe an object in order to know it better, for instance how many binary digits we can acquire on the value of a voltage by an appropriate measure. A "computation" is a physical process, e.g. the flow of current into a complex set of transistors, that after some time eventually gives us the solution of a mathematical problem (such as "Is 13 prime?"). We are interested to various relations between these concepts. In a first chapter, we unify some arguments in the literature to show that a whole class of quantities of dynamical systems are uncomputable. For instance the topological entropy of tilings and Turing machines. Then we propose a precise meaning to the statement "This dynamical system is a computer", at least for symbolic systems, such as cellular automata. We also show, for instance, that a "computer" must be dynamically unstable, and can even be chaotic. In a third chapter, we compare how complicated it is to control a system according whether we can acquire information on it ("feedback") or not ("open loop"). We are specifically interested in finite-state systems. In last chapter we show how to control a scalar linear system when only a finite amount of information can be acquired at every step of time.