Ce travail présente des contributions théoriques et pratiques à la théorie des codages symboliques de systèmes dynamiques. Les applications concernent différents champs mathématiques et la modélisation en biologie moléculaire. Le but est d'illustrer comment des méthodes de discrétisation de systèmes dynamiques et une approche algorithmique permettent d'exploiter au mieux les connaissances disponibles sur le système, même partielles. Un premier objectif est d'exhiber des informations au sujet d'une dynamique que l'on connaît explicitement et les traduire en propriétés concrètes. Un deuxième objectif est de produire de la connaissance sur une dynamique ou un modèle lorsqu'on ne le connaît pas explicitement.Dans ce document, ces deux questions sont abordées sur deux grandes classes de systèmes dynamiques. <br /><br />Les premiers systèmes considérés sont des automorphismes et des translations sur un tore. Inspirés par les cas unidimensionnels (beta-numération, étude des suites sturmiennes), la question principale qui se pose est de trouver un domaine fondamental pour le tore dans lequel les trajectoires de la dynamique considérée se codent par des systèmes symboliques simples. Dans le cas où l'automorphisme du tore considéré admet une unique direction dilatante (le cas Pisot), un bon candidat pour ces partitions est donné par un domaine dont la base est fractale, introduit par G. Rauzy dans les années 1980. Nous décrivons comment une approche décidable pour décrire le bord fractal du domaine et ses propriétés de pavage, permet de s'assurer qu'il s'agit d'un domaine adéquat pour un codage du l'automorphisme. La description du bord du domaine permet de décrire ses propriétés topologiques, et de les exploiter dans les différents domaines d'informatique théorique où les automorphismes et les additions sur un tore apparaissent. Ainsi, en théorie des nombres, nous nous appuyons sur la topologie du domaine pour caractériser les propriétés des développements finis ou purement périodiques de rationnels en base non entière. En géométrie discrète, ces propriétés s'interprètent en termes de conditions pour l'engendrement de plans discrets par des méthodes itératives. <br /><br />La deuxième classe de systèmes concerne les systèmes dynamiques de grande échelle en biologie moléculaire. Il s'avère que les données et les connaissances sur les modèles de régulations transcriptionnelles dans une cellule sont souvent trop partielles pour leur appliquer les méthodes usuellement utilisées pour la modélisation de systèmes expérimentaux. Dans ce document, nous discutons d'un formalisme (inspiré par la dynamique) qui permet d'interpréter les observations en biologie moléculaire, pour aider à la correction de modèles, et, dans le futur, à la mise en place de plans expérimentaux. Au vu de la qualité des données, les aspects dynamiques sont alors remplacés par des considérations sur les déplacements d'états stationnaires, et analyser les données revient à formaliser puis résoudre des contraintes portant sur des ensembles discrets. Nous montrons ainsi comment aborder les notions de corrections de modèles et de diagnostic de réseaux grande échelle.

Les automates cellulaires forment une famille bien connue de modèles dynamiques discrets, introduits par S.Ulam et J. von Neumann dans les années 40. Ils ont été étudiés avec succès sous différents points de vue: modélisation, dynamique, ou encore complexité algorithmique. Dans ce travail, nous adoptons ce dernier point de vue pour étudier la famille des automates cellulaires coagulants, ceux dont l’état d’une cellule nepeut évoluer qu’en suivant une relation d’ordre prédéfinie sur l’ensemble de ses états. Nous étudions la complexité algorithmique de ces automates cellulaires de deux points de vue : la capacité de certains automates coagulants à simuler tous les autres automates cellulaires coagulants, appelée universalité intrinsèque, et la complexité temporelle de prédiction de l’évolution d’une cellule à partir d’une configuration finie, appelée complexité de prédiction. Nous montrons que malgré les sévères restrictions apportées par l’ordre sur les états,les automates cellulaires coagulants peuvent toujours exhiber des comportements de grande complexité.D’une part, nous démontrons qu’en dimension deux et supérieure il existe un automate cellulaire coagulants intrinsèquement universel pour les automates cellulaires coagulants en codant leurs états par des blocs de cellules ; cet automate cellulaire effectue au plus deux changements d’états par cellule. Ce résultat est minimal en dimension deux et peut être amélioré en passant à au plus un changement en dimensions supérieures.D’autre part, nous étudions la complexité algorithmique du problème de prédiction pour la famille des automates cellulaires totalistiques à deux états et voisinage de von Neumann en dimension deux. Dans cette famille de 32 automates, nous exhibons deux automates de complexité maximale dans le cas d’une mise à jour synchrone des cellules et nous montrons que dans le cas asynchrone cette complexité n’est atteinte qu’à partir de la dimension trois. Pour presque tous les autres automates de cette famille, nous montrons que leur complexité de prédiction est plus faible (sous l’hypothèse P 6≠NP). / Cellular automata are a well know family of discrete dynamic systems, defined by S. Ulam and J. von Neumannin the 40s. The have been successfully studied from the point of view of modeling, dynamics and computational complexity. In this work, we adopt this last point of view to study the family of freezing cellular automata, those where the state of a cell can only evolve following an order relation on the set of states. We study the complexity of these cellular automata from two points of view, the ability of some freezing cellular automata to simulate every other freezing cellular automata, called intrinsic universality, and the time complexity to predict the evolution of a cell starting from a given finite configuration, called prediction complexity. We show that despite the severe restriction of the ordering of states, freezing cellular automata can still exhibit highly complex behaviors.On the one hand, we show that in two or more dimensions there exists an intrinsically universal freezing cellular automaton, able to simulate any other freezing cellular automaton by encoding its states into blocks of cells, where each cell can change at most twice. This result is minimal in dimension two and can be even simplified to one change per cell in higher dimensions.On the other hand, we extensively study the computational complexity of the prediction problem for totalistic freezing cellular automata with two states and von Neumann neighborhood in dimension two. In this family of 32 cellular automata, we find two automata with the maximum complexity for classical synchronous cellular automata, while in the case of asynchronous evolution, the maximum complexity can only be achived in dimension three. For most of the other automata of this family, we show that they have a lower complexity (assuming P 6≠NP).

Dans cette thèse nous étudions différents systèmes dynamiques discrets permettant de simuler la formation des piles de sable. Le comportement des modèles de base SPM ou IPM(k) est bien connu dans des conditions initiales spécifiques. Nous étendons ces résultats à des conditions initiales plus générales, et nous introduisons le modèle SSPM qui ajoute de la symétrie à ces modèles et améliore leur réalisme. Dans un second temps, nous étudions un autre système dynamique, les automates de sable. Ils sont définis de manière analogue aux automates cellulaires, avec la contrainte supplémentaire qu'uneconfiguration n'admet pas de « trous ». Ces automates peuvent simuler tous les modèles de piles de sable définis localement, et à l'aide d'un cadre mathématique solide, ils permettent d'obtenir des résultats plus généraux. Nous nous intéressons à la dynamique des automates de sable, plus précisément aux propriétés de réversibilité d'un automate, et nous étudions la décidabilité de propriétés caractérisant les piles de sable classiques : conservation des grains et périodicité ultime.

Dans cette thèse, une nouvelle manière de générer des nombres pseudo-aléatoires est présentée.La proposition consiste à mixer deux générateurs exitants avec des itérations chaotiquesdiscrètes, qui satisfont à la définition de chaos proposée par Devaney. Un cadre rigoureux estintroduit, dans lequel les propriétés topologiques du générateur résultant sont données. Deuxréalisations pratiques d’un tel générateur sont ensuite présentées et évaluées. On montre que lespropriétés statistiques des générateurs fournis en entrée peuvent être grandement améliorées enprocédant ainsi. Ces deux propositions sont alors comparées, en profondeur, entre elles et avecun certain nombre de générateurs préexistants. On montre entre autres que la seconde manièrede mixer deux générateurs est largement meilleure que la première, à la fois en terme de vitesseet de performances.Dans la première partie de ce manuscrit, la fonction d’itérations considérée est la négation vectorielle.Dans la deuxième partie, nous proposons d’utiliser des graphes fortement connexescomme critère de sélection de bonnes fonctions d’itérations. Nous montrons que nous pouvonschanger de fonction sans perte de propriétés pour le générateur obtenu. Finalement, une illustrationdans le domaine de l’information dissimulée est présentée, et la robustesse de l’algorithmede tatouage numérique proposé est évalué. / In this thesis, a new way to generate pseudorandom numbers is presented. The propositionis to mix two exiting generators with discrete chaotic iterations that satisfy the Devaney’sdefinition of chaos. A rigorous framework is introduced, where topological properties of theresulting generator are given, and two practical designs are presented and evaluated. It is shownthat the statistical quality of the inputted generators can be greatly improved by this way, thusfulfilling the up-to-date standards. Comparison between these two designs and existing generatorsare investigated in details. Among other things, it is established that the second designedtechnique outperforms the first one, both in terms of performance and speed.In the first part of this manuscript, the iteration function embedded into chaotic iterations isthe vectorial Boolean negation. In the second part, we propose a method using graphs havingstrongly connected components as a selection criterion.We are thus able to modify the iterationfunction without deflating the good properties of the associated generator. Simulation resultsand basic security analysis are then presented to evaluate the randomness of this new family ofpseudorandom generators. Finally, an illustration in the field of information hiding is presented,and the robustness of the obtained data hiding algorithm against attacks is evaluated.

On s’intéresse à la dynamique dans un voisinage d’un point fixe d’une fonction antiholomorphe d’une variable. Dans un premier temps, on cherche à décrire et à comprendre l’espace des orbites dans un voisinage d’un point fixe multiple, appelé point parabolique, et à explorer les propriétés géométriques préservées par les changements de coordonnée. En particulier, on résout le problème de classification analytique des points paraboliques. Résoudre ce problème consiste à définir un module de classification complet qui permet de déterminer si deux germes de difféomorphismes antiholomorphes sont analytiquement conjugués dans un voisinage de leur point fixe parabolique. On examine également les applications du module à différents problèmes : i) extraction d’une racine n-ième antiholomorphe, ii) existence d’une courbe analytique invariante sous la dynamique d’un germe antiholomorphe parabolique et iii) centralisateur d’un germe antiholomorphe parabolique. Dans un second temps, on étudie les déploiements génériques d’un point fixe double, soit un point parabolique de codimension 1. Les questions sont de nature similaire, à savoir comprendre l’espace des orbites et les propriétés géométriques des déploiements. Afin de classifier les déploiements génériques, on déploie le module de classification pour les points paraboliques, ce qui permet d’obtenir des conditions nécessaires et suffisantes pour déterminer lorsque deux déploiements génériques sont équivalents. / We are interested in the dynamics in a neighbourhood of a fixed point of an antiholomorphic function of one variable. First, we want to describe and understand the space of orbits in a neighbourhood of a multiple fixed point, called a parabolic point, and to explore the geometric properties preserved by changes of coordinate. In particular, we solve the problem of analytical classification of parabolic fixed points. To solve this problem, we define a complete modulus of classification that allows to determine whether two germs of antiholomorphic diffeomorphisms are analytically conjugate in a neighbourhood of their parabolic fixed point. We also consider the applications of the modulus to different problems: i) extraction of an n-th antiholomorphic root, ii) existence of an invariant real analytical curve under the dynamics of a parabolic antiholomorphic germ, and iii) centraliser of a parabolic antiholomorphic germ. In the second part, we study generic unfoldings of a double fixed point, i.e. a parabolic point of codimension 1. The questions are similar in nature, namely to understand the space of orbits and the geometric properties of unfoldings. In order to classify generic unfoldings, the modulus of classification of the parabolic point is unfolded, thus providing the necessary and sufficient conditions to determine when two generic unfoldings are equivalent.

La sécurité et la cryptographie sont des éléments clés pour les dispositifs soumis à des contraintes comme l’IOT, Carte à Puce, Systèm Embarqué, etc. Leur implémentation matérielle constitue un défi en termes de limitation en ressources physiques, vitesse de fonctionnement, capacité de mémoire, etc. Dans ce contexte, comme la plupart des protocoles s’appuient sur la sécurité d’un bon générateur de nombres aléatoires, considéré comme un élément indispensable dans le noyau de sécurité. Par conséquent, le présent travail propose des nouveaux générateurs pseudo-aléatoires basés sur des itérations chaotiques, et conçus pour être déployés sur des supports matériels, à savoir sur du FPGA ou du ASIC. Ces implémentations matérielles peuvent être décrites comme des post-traitements sur des générateurs existants. Elles transforment donc une suite de nombres non-uniformes en une autre suite de nombres uniformes. La dépendance entre l’entrée et la sortie a été prouvée chaotique selon les définitions mathématiques du chaos fournies notamment par Devaney et Li-Yorke. Suite à cela, nous effectuant tout d’abord un état de l’art complet sur les mises en œuvre matérielles et physiques des générateurs de nombres pseudo-aléatoires (PRNG, pour pseudorandom number generators). Nous proposons ensuite de nouveaux générateurs à base d’itérations chaotiques (IC) qui seront testés sur notre plate-forme matérielle. L’idée de départ était de partir du n-cube (ou, de manière équivalente, de la négation vectorielle dans les IC), puis d’enlever un cycle Hamiltonien suffisamment équilibré pour produire de nouvelles fonctions à itérer, à laquelle s’ajoute une permutation en sortie. Les méthodes préconisées pour trouver de bonnes fonctions serons détaillées, et le tout sera implanté sur notre plate-forme FPGA. Les générateurs obtenus disposent généralement d’un meilleur profil statistique que leur entrée, tout en fonctionnant à une grande vitesse. Finalement, nous les implémenterons sur de nombreux supports matériels (65-nm ASIC circuit and Zynq FPGA platform). / Security and cryptography are key elements in constrained devices such as IoT, smart card, embedded system, etc. Their hardware implementations represent a challenge in terms of limitations in physical resources, operating speed, memory capacity, etc. In this context, as most protocols rely on the security of a good random number generator, considered an indispensable element in lightweight security core. Therefore, this work proposes new pseudo-random generators based on chaotic iterations, and designed to be deployed on hardware support, namely FPGA or ASIC. These hardware implementations can be described as post-processing on existing generators. They transform a sequence of numbers not uniform into another sequence of numbers uniform. The dependency between input and output has been proven chaotic, according notably to the mathematical definitions of chaos provided by Devaney and Li-Yorke. Following that, we firstly elaborate or develop out a complete state of the art of the material and physical implementations of pseudo-random number generators (PRNG, for pseudorandom number generators). We then propose new generators based on chaotic iterations (IC) which will be tested on our hardware platform. The initial idea was to start from the n-cube (or, in an equivalent way, the vectorial negation in CIs), then remove a Hamiltonian cycle balanced enough to produce new functions to be iterated, for which is added permutation on output . The methods recommended to find good functions, will be detailed, and the whole will be implemented on our FPGA platform. The resulting generators generally have a better statistical profiles than its inputs, while operating at a high speed. Finally, we will implement them on many hardware support (65-nm ASIC circuit and Zynq FPGA platform).

Ce travail présente des contributions théoriques et appliquées dans le contexte des systèmes dynamiques discrets vus comme modèles des réseaux de régulation biologique. En mettant en avant le fait qu'accroître les connaissances du vivant nécessite aujourd'hui de mieux comprendre les propriétés mathématiques qui le régissent, il développe diverses réflexions menées en bio-informatique théorique en se fondant sur le formalisme des réseaux d'automates, notamment booléens. Les trois principaux thèmes abordés sur ces réseaux sont la robustesse environnementale, la combinatoire comportementale et la robustesse structurelle. La robustesse environnementale est notamment évoquée à travers une étude de la manière dont les réseaux d'automates réagissent face à l'influence de conditions de bord fixées (on y retrouve une généralisation au cas non-linéaire d'un résultat connu dans le domaine des automates cellulaires). La combinatoire comportementale est quant à elle abordée par les cycles d'interaction dont on connaît l'importance sur la dynamique des réseaux. Pour ces motifs particuliers et leurs intersections sont présentées des caractérisations combinatoires de leur comportement asymptotique en parallèle, qui font ensuite l'objet de comparaisons. Enfin, le thème de la robustesse structurelle est traité au travers du concept de graphe de transition général, qui a mené à mettre en évidence tous les comportements possibles des cycles d'interaction, à donner une classification de la robustesse des réseaux vis-à-vis de leur asynchronisme/synchronisme, de laquelle se sont imposées des études plus précises sur le rôle de la non-monotonie dans ces réseaux.

Les itérations chaotiques, un outil issu des mathématiques discrètes, sont pour la première fois étudiées pour obtenir de la divergence et du désordre. Après avoir utilisé les mathématiques discrètes pour en déduire des situations de non convergence, ces itérations sont modélisées sous la forme d'un système dynamique et sont étudiées topologiquement dans le cadre de la théorie mathématique du chaos. Nous prouvons que leur adjectif " chaotique " a été bien choisi: ces itérations sont du chaos aux sens de Devaney, Li-Yorke, l'expansivité, l'entropie topologique et l'exposant de Lyapunov, etc. Ces propriétés ayant été établies pour une topologie autre que la topologie de l'ordre, les conséquences de ce choix sont discutées. Nous montrons alors que ces itérations chaotiques peuvent être portées telles quelles sur ordinateur, sans perte de propriétés, et qu'il est possible de contourner le problème de la finitude des ordinateurs pour obtenir des programmes aux comportements prouvés chaotiques selon Devaney, etc. Cette manière de faire est respectée pour générer un algorithme de tatouage numérique et une fonction de hachage chaotiques au sens le plus fort qui soit. A chaque fois, l'intérêt d'être dans le cadre de la théorie mathématique du chaos est justifié, les propriétés à respecter sont choisies suivant les objectifs visés, et l'objet ainsi construit est évalué. Une notion de sécurité pour la stéganographie est introduite, pour combler l'absence d'outil permettant d'estimer la résistance d'un schéma de dissimulation d'information face à certaines catégories d'attaques. Enfin, deux solutions au problème de l'agrégation sécurisée des données dans les réseaux de capteurs sans fil sont proposées.