L'ARN (acide ribonucléique) est une molécule ubiquitaire qui joueplusieurs rôles fondamentaux au sein de la cellule: synthèse desprotéines avec les ARN messagers, activité catalytique ou implicationdans la régulation, les ARN non-codants. Les nouvelles technologies deséquençage à haut- débit permettent de produire des milliards de séquences à moindre coût, posant de manière cruciale la question de l'analyse de ces données.L'objectif de cette thèse est de définir de nouvelles méthodescomputationnelles pour aider à l'analyse de ces séquences dans le casdes ARN non-codants. Dans cette perspective, la "structuresecondaire" d'un ARN, formée par l'ensemble des appariements entrebases, délivre des informations utiles pour étudier la fonction del'ARN. Notre travail se concentre plus particulièrement surl'ensemble des structures potentielles que peut adopter une séquenced'ARN donnée, ensemble que nous appelons "multi-structure". Nousapportons deux contributions: un algorithme pour générersystématiquement toutes les structures localement optimales composantune multi-structure, et un algorithme basé sur la recherche d'unemulti-structure pour identifier un ARN non-codant dans une séquencegénomique. Ces résultats ont été mis en oeuvre dans deux logiciels,Alterna et Regliss, appliqués avec succès à des ensembles de test. / RNA (ribonucleic acid) molecules have various functions in cells. Justas they can store and deliver the DNA message for the proteinsynthesis (messenger RNAs), they can also directly catalyze chemicalreactions or act as a regulator (functional RNAs, also callednon-coding RNAs). Nowadays, recent sequencing technologies yield billions of genomic sequences - DNA, RNA - at a very small cost. However, sequencing isonly the first step: The function of the sequence remains open forinvestigation. The objective of the thesis is to define newcomputational methods to help sequence and structure analysis ofnon-coding RNAs. In this perspective, the "secondary structure" of an RNA,made with base pairs, provides useful hints to further study itsfunction. Our work is focused on sets of all possible RNA structuresfor a given sequence, introducing the concept of "RNAmulti-structures". The thesis details how such sets can be constructed systematically to generate all locally optimal secondary structures, and how they can be used as a pattern to identify non-coding RNAs in genomic sequences.We provide efficient algorithms for these two problems. Thesealgorithms have been implementated in the software tools Alterna andRegliss and tested on real data, providing new insight into RNAstructures.

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.

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 de recherche a été mené dans l’équipe MODGEN du département GenPhySE, 1388 UMR de l’INRA. Il avait pour perspectives de modéliser les variabilités de la taille de portée des ovins pour une meilleure évaluation génétique et de proposer des modèles d’analyse adoptés à ce type de caractère.Les objectifs de l’étude étaient d'identifier, et d'analyser les facteurs environnementaux et génétiques des variabilités des tailles de portée des brebis et de proposer une méthode adaptée pour canaliser les caractères discrets qui prenne en compte conjointement des objectifs sur la moyenne et sur la variabilité du caractère. La thèse s’appuyait sur des données issues de la chaîne nationale de contrôle de performances en relation avec des organismes de sélection ovin qui sont particulièrement intéressés par les résultats de ces recherches (CORAM). Choix des races. Nous avons considéré trois races dont les fréquences de la taille de portée sont plus ou moins élevées. La race Romane connue par sa forte prolificité ainsi des effectifs contrôlés importants a permis des analyses précises. Les deux autres races choisies sont la race Suffolk et la race Rouge de l’Ouest qui ont servi à tester les modèles sur des populations comportant de moins en moins de portées multiples. La taille de portée des ovins considérée comme une variable continue. Au cours de l’étude, nous avons identifié et hiérarchisé les facteurs de variation environnementaux du niveau de prolificité et de de sa variance pour trois races ovines (Suffolk, Rouge de l’Ouest et Romane). Si les facteurs de variation environnementaux du niveau de prolificité étaient déjà bien connus, peu de données concernaient les facteurs de variation environnementaux de la variance. Nous avons également estimé les paramètres génétiques du niveau de prolificité et de sa variance, ils sont cohérents entre eux. Les héritabilités estimées sur la moyenne sont faibles, en cohérences entre les trois races et avec des études antérieures. La non homogénéité des corrélations estimées par le modèle à deux étapes peut s’expliquer par la relation structurelle entre la moyenne et la variance sur l’échelle observée qui n'est pas prise en compte dans ce type d'analyse. A l'échelle d'une race, cette relation dépend de l’écart spécifique entre les seuils; elle est différente de la relation moyenne – variance observée pour l’ensemble des races et qui est calculée sur des données brutes. La taille de portée des ovins considérée comme une variable discrète Nous avons montré l’existence d’une variabilité d’origine génétique dans les trois races étudiées et nous avons montré que le modèle à seuils homothétique [HTM] s’ajustait mieux aux données et qu'il permettait de calculer conjointement l’effet génétique sur la moyenne et sur la variance. Nous avons aussi montré les limites de ce modèle et nous avons proposé une solution afin de donner un cadre plus général à son utilisation et l’utiliser dans les évaluations génétiques. Nous avons également identifié un critère de sélection pertinent qui permet de sélectionner les individus de même moyenne ayant des variances différentes. Nous avons proposé le modèle à seuils indépendants [ITM] ou le modèle multi caractères avec contrainte, ce modèle considère que chaque réalisation est un caractère. Nous avons montré la faisabilité de ce modèle sur les trois races. Ceci nous a permis de mettre en évidence les problèmes liés à la convergence du programme utilisé, et nous avons proposé d’implémenter ce modèle en modifiant le programme TM.

Les travaux de ma thèse ont pour but la définition d’une démarche modulaire permettant le diagnostic des défauts liés conjointement aux dynamiques continue et discrète des systèmes dynamiques hybrides, en particulier les Systèmes Continus à Commande Discrète. L’objectif est de construire un modèle de diagnostic appelé, diagnostiqueur, permettant de diagnostiquer à la fois les défauts paramétriques et discrets des systèmes dynamiques hybrides de grande taille. Les défauts paramétriques sont caractérisés par un changement anormal de certains paramètres tandis que les défauts discrets sont caractérisés par un changement inattendu du mode discret du système. Cette démarche est basée sur une modélisation modulaire orientée composant permettant de tenir compte de la nature composite du système. Elle tient compte également des interactions entre les dynamiques discrètes et continue. Cette démarche est développée à travers deux approches. Une approche de diagnostique modulaire dont le diagnostiqueur est construite à partir du modèle global de système, et une approche de diagnostique décentralisé dont d’un ensemble des diagnostiqueurs locaux sont construits à partir des modèles locaux des composants système. Ces deux approches sont validées en utilisant un convertisseur à trois cellules. / This thesis aims at defining a diagnosis approach for hybrid dynamic systems in particular Discretely Controlled Continuous Systems. The goal is to build a diagnosis module called, diagnoser, able to diagnose parametric and discrete faults. Parametric faults affect the system continuous dynamics and are characterized by abnormal changes in some system parameters; whereas discrete faults affect the system discrete dynamics and are considered either as the occurrence of unobservable events and/or reaching discrete fault modes. This approach is based on modular modeling in order to take into account the interactions between continuous and discrete dynamics. This approach is developed through two approaches. A modular diagnosis approach in which the diagnoser is built based on the use of the global model and a decentralized approach in which a set of local diagnosers are built based on the local model of the system components. The three-cell converter is used to demonstrate the efficacy of these two approaches.

L'objectif de ce travail est d'établir un cadre théorique favorable à la détermination et au contrôle des efforts radiaux dans les moteurs électriques synchrones. Le besoin d'une modélisation susceptible d'être utilisée pour le contrôle en temps réels des efforts écarte naturellement les classiques méthodes numériques de calcul des champs. Aussi, notre volonté de représenter de façon la plus synthétique qui soit l'état magnétique de la machine nous conduit à proposer une modélisation qui intègre de façon intrinsèque un maximum d'informations concernant la machine comme le caractère localisé des courants dans les encoches et les nombreuses symétries liées au bobinage de la machine. Cette modélisation est basée sur une discrétisation du champ d'entrefer qui consiste à considérer le champ constant sous chaque dent statorique.

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

Dans ce mémoire, nous analysons la description de diagrammes structurés dans le domaine des mathématiques discrètes et de l'informatique théorique. Cette analyse s'effectue à partir de méthodes établies du génie logiciel. Nous trouvons un ensemble de propriétés que nous recherchons dans une solution informatique nous permettant de créer ces diagrammes. Nous analysons aussi les outils classiques à partir des propriétés précédentes qui nous permettent de réaliser ces diagrammes dans un environnement LATEX. Nous observons que ces outils ne sont pas aussi puissants qu'ils le pourraient en fonction des propriétés établies par notre analyse. Par la suite, en nous basant sur les méthodes de représentation graphique des courbes et sur la théorie des langages informatiques, nous jetons les bases d'un langage de description. Nous présentons aussi un outil, développé en Java qui nous permet de décrire aisément nos diagrammes d'informatique théorique et de mathématiques discrètes à partir d'une hiérarchie d'objets claire et extensible. Nous avons implémenté les éléments essentiels de notre langage en SDDL (Structured Diagram Description Language). Nous l'avons aussi validé à l'aide d'exemples représentatifs tirés de sources d'autorité. Nous avons finalement présenté notre solution dans le cadre de la conférence TUG 2010. Nous l'avons aussi présenté avec un article dans la revue du TeX Users Groups, TUG. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : diagrammes, informatique théorique, mathématiques discrètes, langage

La première partie de cette thèse est consacrée à l'étude des convexes dans le plan discret Z2 ou plus généralement Zn. Il existe en fait plusieurs notions de convexité discrète : la convexité simple selon certaines directions, la convexité totale (la convexité usuelle du continu), etc. La Q-convexité est encore une nouvelle classe qui généralise à la fois les totalement convexes et les polyominos HV-convexes. On étudie les liens entre toutes ces différentes notions, et on donne des propriétés des points particuliers de ces ensembles comme les points médians et les points saillants.<br /><br />Toute la deuxième partie est dédiée au problème de la tomographie dans le plan discret Z2. Il s'agit simplement de reconstruire un ensemble à partir du nombre de points dans les droites parallèles à des directions données. L'algorithme polynomial, déjà connu pour les polyominos HV-convexes avec les directions horizontales et verticales, se généralise aux Q-convexes pour des directions quelconques. D'autre part, le théorème d'unicité qui montre en particulier que sept directions suffisent pour déterminer un totalement convexe se généralise aussi aux Q-convexes. On en déduit que lorsque l'on a assez de directions pour avoir unicité de la solution, la reconstruction des totalement convexes peut se faire en temps polynomial. On a aussi un algorithme polynomial de reconstruction approchée des Q-convexes.

Les comportements dynamiques d’une famille de structures réticulées, c’est-à-dire constituées d’un réseau de poutres, sont étudiés à l’aide de la méthode d’homogénéisation des milieux périodiques discrets. Cette dernière permet de construire, de façon rigoureuse et en lien avec la microstructure, un milieu continu équivalent à l’échelle macroscopique lorsque la taille de la cellule de base est très petite par rapport à la longueur d’onde. Le domaine d’application de cetteméthode est également étendu à des fréquences plus élevées pour lesquelles les éléments de la cellule peuvent entrer en résonance en flexion. Cela se traduit à l’échelle macroscopique par des propriétés apparentes qui dépendent de la fréquence et par des bandes de fréquences interdites associées aux modes de flexion des éléments. Les structures considérées sont constituées par la répétition périodique de portiques non contreventés. Contrairement aux milieux massifs, ces structures présentent une déformabilité beaucoup plus grande en cisaillement qu’en tractioncompressionet leur cinématique locale est très riche. Ainsi, il est possible de générer une grande variété de comportements en jouant sur les ordres de grandeur des propriétés des éléments et celui de la fréquence. Cette approche permet de construire différents modèles de milieux continus (ou poutres) généralisé(e)s. Ce travail apporte un cadre d’analyse pour l’étude de milieux tels que les mousses, les matières végétales, les os. . . mais aussi pour concevoir de nouveaux matériaux avec des propriétés atypiques. Ici, les modèles de poutres généralisées servent à comprendre le fonctionnement des bâtiments. Dans ce cas, la difficulté réside dans la prise en compte du cisaillement dans les murs voiles. / The dynamic behaviours of a class of reticulated structures - that is to say made up of interconnected beams - are studied with the homogenization method of periodic discrete media. It enables to derive, rigorously and in relation with the microstructure, an equivalent continuous medium at the macroscopic scale when the cell size is much smaller than the wavelength. The scope of application of the method is also extended to higher frequencies for which cell elements can be in resonance for bending. Consequently, at the macroscopic scale, the effective properties can depend on the frequency and there are frequency band gaps associated with the bending modes of the elements. Studied structures are made up of the periodic repetition of unbraced frames. Contrary to massive media, those structures have a shear deformability muchhigher than traction-compression deformability and their local kinematics is very rich. Thus, it is possible to generate a large diversity of behaviours by changing the orders of magnitude of the element properties and of the frequency. This approach enables to build several generalized continuous media (or beams). This work brings a framework for the study of media such as foams, vegetable tissue, bones... but also for the design of new materials with atypical properties. Here, generalized beam models are used to understand the behaviour of buildings. In that case, the difficulty consists in taking into account the shear mechanism in the shear walls.