Spelling suggestions: "subject:"palindromic"" "subject:"palindrome""
1 |
Structure des pavages, droites discrètes 3D et combinatoire des motsLabbé, Sébastien 05 1900 (has links) (PDF)
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.
|
2 |
Contribution à l'étude de la dynamique d'un automate à mémoireMoumida, Driss 27 October 1989 (has links) (PDF)
Dans cette thèse, nous étudions la dynamique d'un automate a mémoire dont la fonction de transition est une fonction a seuil. Au chapitre 1, on présente différentes propriétés qui permettent de reconnaitre ou de réaliser une fonction a seuil donnée. Au chapitre 2 nous rappelons les résultats essentiels concernant la dynamique des automates a mémoire linéaires. Le chapitre 3 est consacre a l'étude de deux familles d'automates: automates a mémoire palindromiques et automates réversibles. Aux chapitres 4 et 5, on s'intéresse a la dynamique des automates a mémoire géométriques. Au chapitre 6, on ramène l'étude de la dynamique d'un automate a mémoire a seuil a la résolution d'un programme linéaire. On présente un algorithme qui pour un couple (k,p) permet de construire, s'il en existe, un automate a mémoire a seuil de taille de mémoire k admettant un cycle de longueur p. Cet algorithme nous a permis de construire des familles d'automates admettant des cycles de longueurs supérieures au double de la taille de la mémoire
|
Page generated in 0.0411 seconds