Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage. Les ACP sont utilisés en informatique comme modèle de calcul, ainsi qu'en biologie et en physique. Ils interviennent aussi dans différents contextes en probabilités et en combinatoire. Un ACP est ergodique s'il a une unique mesure invariante qui est attractive. Nous prouvons que pour les AC déterministes, l'ergodicité est équivalente à la nilpotence, ce qui fournit une nouvelle preuve de l'indécidabilité de l'ergodicité pour les ACP. Alors que la mesure invariante d'un AC ergodique est triviale, la mesure invariante d'un ACP ergodique peut être très complexe. Nous proposons un algorithme pour échantillonner parfaitement cette mesure. Nous nous intéressons à des familles spécifiques d'ACP, ayant des mesures de Bernoulli ou des mesures markoviennes invariantes, et étudions les propriétés de leurs diagrammes espace-temps. Nous résolvons le problème de classification de la densité sur les grilles de dimension supérieure ou égale à 2 et sur les arbres. Enfin, nous nous intéressons à d'autres types de problèmes. Nous donnons une caractérisation combinatoire des mesures limites pour des marches aléatoires sur des produits libres de groupes. Nous étudions les mesures d'entropie maximale de sous-décalages de type fini sur les réseaux et sur les arbres. Les ACP interviennent à nouveau dans ce dernier travail.

Cette thèse étudie les urnes de Pólya à travers le prisme de la combinatoire analytique. Les urnes sont des modèles, conceptuellement très simples, de dynamique de croissance ou d'extinction dont les comportements limites sont extrêmement variés. Ces modèles sont largement étudiés par des approches probabilistes mais la compréhension précise des diverses lois limites reste une question ouverte. Les travaux de Flajolet et al. en 2005 ont illustré que pour ces questions, une approche par combinatoire analytique peut se révéler très fructueuse: l'étude des propriétés (nature, singularités) des séries génératrices associées aux urnes donne accès à des lois limites avec grande précision. Cette thèse s'inscrit dans la continuité de ces travaux et commence par identifier les séries des urnes de nature algébrique, grâce à un algorithme sophistiqué issu du calcul formel (Divination/Preuve automatique). Pour les classes d'urnes algébriques, nous menons des analyses, exacte et asymptotique, afin de connaître avec précision les comportements limites (structures des moments, vitesse de convergence, aspects limites locaux). Puis, l'étude d'urnes non algébriques est faite au travers d'exemples concrets portant sur la modélisation de réseaux sociaux, ainsi que sur la combinatoire des formules booléennes. Enfin, à travers des modèles d'urnes plus généraux (absence d'équilibre, présence d'aléa au sein des règles de substitution), nous montrons que l'approche symbolique de la combinatoire analytique est robuste. En particulier, une étude combinatoire générale des urnes sans condition d'équilibre est réalisée pour la première fois, unissant toute urne à une équation aux dérivées partielles.

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.

Nous étudions les systèmes de véhicules en libre service en aller-simple : avec emprunt et restitution dans des lieux éventuellement différents. La publicité promeut l'image de flexibilité et d'accessibilité (tarifaire) de tels systèmes, mais en réalité il arrive qu'il n'y ait pas de véhicule disponible au départ, voire pire, pas de place à l'arrivée. Il est envisageable (et pratiqué pour Vélib' à Paris) de relocaliser les véhicules pour éviter que certaines stations soient vides ou pleines à cause des marées ou de la gravitation. Notre parti-pris est cependant de ne pas considérer de "relocalisation physique" (à base de tournées de camions) en raison du coût, du trafic et de la pollution occasionnées (surtout pour des systèmes de voitures, comme Autolib' à Paris). La question à laquelle nous désirons répondre dans cette thèse est la suivante : Une gestion via des tarifs incitatifs permet-elle d'améliorer significativement les performances des systèmes de véhicules en libre service ?

Ce document pr esente les travaux que j'ai r ealis es depuis ma th ese de doctorat. Outre la pr esentation de mes contributions, j'ai essay e de pr esenter des survols des domaines dans lesquels mes travaux s'inscrivent et d'indiquer les principales questions qui s'y posent. Mes travaux visent a r epondre aux nouveaux challenges algorithmiques que posent la croissance des r eseaux de telecommunications actuels ainsi que l'augmentation des donnees et du trafi c qui y circulent. Un moyen de faire face a la taille de ces probl emes est de s'aider de la structure particuliere des r eseaux. Pour cela, je m'attache a d e nir de nouvelles caract erisations des propri et es structurelles des graphes pour les calculer et les utiliser effi cacement a des fins algorithmiques. Autant que possible, je propose des algorithmes distribu es qui ne reposent que sur une connaissance locale/partielle des r eseaux. En particulier, j' etudie les jeux de poursuite - traitant de la capture d'une entit e mobile par une equipe d'autres agents - qui off rent un point de vue int eressant sur de nombreuses propri et es de graphes et, notamment, des d ecompositions de graphes. L'approche de ces jeux d'un point de vue agents mobiles permet aussi l' etude de mod eles de calcul distribu e. Le chapitre 1 est d edi e a l' etude de plusieurs variantes des jeux de gendarmes et voleur. Le chapitre 2 traite des decompositions de graphes et de leur relation avec les problemes d'encerclement dans les graphes. Le chapitre 3 se concentre sur les probl emes d'encerclement dans des contextes a la fois centralis e et distribu e. Finalement, le chapitre 4 traite de probl emes de routage dans diff erents contextes, ainsi que de mod eles de calcul distribu e.

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.