Ce mémoire est une synthèse de plusieurs études à l'intersection des systèmes dynamiques dans l'analyse statistique de séquences, de l'analyse d'algorithmes dans des arbres aléatoires et des processus stochastiques discrets. Les résultats établis ont des applications dans des domaines variés allant des séquences biologiques aux modèles de régression linéaire, processus de branchement, en passant par la statistique fonctionnelle et les estimations d'indicateurs de risque appliqués à l'assurance. Tous les résultats établis utilisent d'une façon ou d'une autre le caractère récursif de la structure étudiée, en faisant apparaître des invariants comme des martingales. Elles sont au coeur de ce mémoire, utilisées comme outils dans les preuves ou comme objets d'étude.

Cette thèse traite de la résolution numérique de problèmes de contrôle stochastique, illustrée d'applications sur les marchés d'électricité. Tout d'abord, nous proposons un modèle structurel pour le prix d'électricité, autorisant des pics de prix bien au delà du coût marginal de production lorsque le marché est tendu. Ce modèle permet de valoriser et couvrir partiellement des produits dérivés sur l'électricité, avec pour actifs de couverture des contrats à terme sur combustibles. Nous étudions ensuite un algorithme, à base de simulations de Monte-Carlo et régressions à base locale, pour résoudre des problèmes généraux de commutation optimale. Nous établissons un taux de convergence complet de la méthode. De plus, nous rendons l'algorithme parcimonieux en usage mémoire en permettant d'éviter le stockage du faisceau de trajectoires. Nous l'illustrons sur le problème d'investissements en centrales électriques (lesquelles se répercutent sur le prix d'électricité grâce à notre modèle structurel). Enfin, nous étudions des problèmes de contrôle stochastique plus généraux (où le contrôle peut être continu et modifier la dynamique du processus d'état), dont la solution peut être étudiée via des Équations Différentielles Stochastiques Rétrogrades contraintes, pour lesquelles nous développons un algorithme, qui combine randomisation du contrôle et optimisation paramétrique. Un taux de convergence entre l'EDSR contrainte et sa version discrète est fourni, ainsi qu'un estimateur du contrôle optimal. Nous appliquons ensuite cet algorithme au problème de sur-réplication d'option sous volatilité incertaine.

Cette thèse porte principalement sur l'équilibrage de charge dans de grands graphes aléatoires. En informatique, un problème d'équilibrage de charge survient lorsque différentes tâches ont besoin d'accéder à un même ensemble de points de ressources. Il faut alors décider quelles ressources spécifiques seront allouées à quelles tâches. Suivant le contexte, les notions de "tâche" et de "ressource" peuvent avoir différentes interprétations. Afin de prendre des exemples concrets, on se concentrera sur deux applications en particulier: - un système de hachage à choix multiples (plus précisément, le "cuckoo hashing"). L'objectif est ici d'allouer des cellules d'un tableau à des objets, afin de pouvoir ensuite vérifier facilement la présence d'un objet et récupérer les données associées. Les tâches sont liées aux objets à stocker, et les ressources sont les cellules du tableau. - un réseau de distribution de contenu distribué, au sens où les contenus peuvent être stockés sur une multitude de petits serveurs aux capacités individuelles très limitées. Ici, les tâches sont des demandes de téléchargement (ou requêtes) pour un contenu et les ressources sont liées aux serveurs et à la façon dont leurs espaces de stockage sont utilisés. Le problème d'équilibrage de charge consiste à décider quel serveur va servir quelle requête. Les contraintes locales portant sur chaque ressource (en quelle quantité est-elle disponible et pour quelles tâches est-elle convenable?) ainsi que la charge de travail associée avec chaque tâche peuvent être représentées efficacement sur un graphe biparti, avec des contraintes de capacité sur ses sommets et ses arêtes. De plus, en pratique, les systèmes considérés sont souvent de très grande taille (avec parfois des milliers de tâches et de points de ressources différents) et relativement aléatoires (que ce soit par choix ou une conséquence de leur grande taille). Une modélisation à l'aide de grands graphes aléatoires est donc souvent pertinente. L'ensemble des solutions envisageables pour un problème d'équilibrage de charge donné étant vaste, il est primordial de commencer par déterminer des bornes sur les performances que l'on peut espérer. Ainsi, on considérera dans un premier temps une solution optimale du problème (même si elle ne serait pas réalisable avec des contraintes pratiques). Les performances d'une telle solution peuvent être obtenues en étudiant les appariements de taille maximum dans un grand graphe aléatoire, ce que l'on réalisera à l'aide de la méthode de la cavité. Cette méthode vient de l'étude des systèmes désordonnés en physique statistique, et on s'attachera ici à l'appliquer de manière rigoureuse dans le cadre que l'on considère. Dans le contexte du cuckoo hashing, les résultats obtenus permettent de calculer le seuil sur la charge du système (le nombre d'objets à insérer par rapport à la taille du tableau) en-dessous duquel on peut construire une table de hachage correcte avec grande probabilité dans un grand système, et également de traiter de manière similaire de variantes de la méthode de hachage basique qui tentent de diminuer la quantité d'aléa nécessaire au système. Au-delà du problème d'équilibrage de charge, dans le cadre des réseaux de distributions de contenu distribués, un second problème se pose: comment décider quel contenu stocker et en quelle quantité, autrement dit comment répliquer les contenus? On appelle ce second problème un problème d'allocation de ressources. A nouveau, l'étude déjà réalisée permet de quantifier l'efficacité d'une politique de réplication fixée en supposant que la politique d'équilibrage de charge fonctionne de manière optimale. Il reste cependant à optimiser la politique de réplication de contenus utilisée, ce que l'on effectue dans un régime où l'espace de stockage disponible au niveau de chaque serveur est important par rapport à la taille d'un contenu. Finalement, afin de quantifier maintenant les performances minimales atteignables en pratique, on s'intéressera aux mêmes questions lorsque la politique d'équilibrage de charge utilisée est un simple algorithme glouton. Cette étude est réalisée à l'aide d'approximations de champs moyen. On utilisera également les résultats obtenus afin de concevoir des politiques de réplication de contenus adaptatives.

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.

La première partie a pour sujet le comportement à l'équilibre du modèle d'Ising pour d>4. Dans un premier temps, nous étudions le comportement thermique dans le cadre du comportement d'échelle étendu. Par interpolation de données numériques en dimensions cinq à huit, nous obtenons un développement décrivant la susceptibilité dans toute la phase haute température. Dans un second temps, nous étudions les effets de taille finie. Les résultats numériques obtenus pour le modèle d'Ising 5d sont compatibles avec une croissance anormale de la longueur de corrélation pour des conditions de bords libres. La seconde partie a pour sujet le vieillissement dans les systèmes de spins 2d complètement frustrés. Dans un premier temps, nous étudions le vieillissement du modèle d'Ising complètement frustré 2d lors d'une trempe depuis la phase haute température jusqu'à la température critique. La présence de défauts topologiques, comme pour le modèle XY, se manifeste par des corrections logarithmiques lors de la croissance de la longueur caractéristique. Dans un second temps, nous étudions le vieillissement du modèle XY complètement frustré 2d. Lors d'une trempe depuis l'état fondamental jusque dans la ligne critique, le vieillissement des spins est bien décrit par les ondes de spins. Lors d'une trempe depuis la phase haute température jusqu'à la température BKT pour les spins et jusqu'à la température de brisure de symétrie de la chiralité, nous estimons les grandeurs universelles des deux variables. Les résultats pour la chiralité sont incompatibles avec la classe d'universalité du modèle d'Ising 2d. Des corrections logarithmiques sont également présentes.

Dans cette thèse, nous traitons deux problèmes de contrôle optimal stochastique. Chaque problème correspond à une Partie de ce document. Le premier problème traité est très précis, il s'agit de la valorisation des contrats optionnels de vente de type Américain (dit Put Américain) en présence de dividendes discrets (Partie I). Le deuxième est plus général, puisqu'il s'agit dans un cadre discret en temps de prouver l'existence d'un principe de programmation dynamique sous des contraintes en probabilités (Partie II). Bien que les deux problèmes soient assez distincts, le principe de programmation dynamique est au coeur de ces deux problèmes. La relation entre la valorisation d'un Put Américain et un problème de frontière libre a été prouvée par McKean. La frontière de ce problème a une signification économique claire puisqu'elle correspond à tout instant à la borne supérieure de l'ensemble des prix d'actifs pour lesquels il est préférable d'exercer tout de suite son droit de vente. La forme de cette frontière en présence de dividendes discrets n'avait pas été résolue à notre connaissance. Sous l'hypothèse que le dividende est une fonction déterministe du prix de l'actif à l'instant précédant son versement, nous étudions donc comment la frontière est modifiée. Au voisinage des dates de dividende, et dans le modèle du Chapitre 3, nous savons qualifier la monotonie de la frontière, et dans certains cas quantifier son comportement local. Dans le Chapitre 3, nous montrons que la propriété du smooth-fit est satisfaite à toute date sauf celles de versement des dividendes. Dans les deux Chapitres 3 et 4, nous donnons des conditions pour garantir la continuité de cette frontière en dehors des dates de dividende. La Partie II est originellement motivée par la gestion optimale de la production d'une centrale hydro-electrique avec une contrainte en probabilité sur le niveau d'eau du barrage à certaines dates. En utilisant les travaux de Balder sur la relaxation de Young des problèmes de commande optimale, nous nous intéressons plus spécifiquement à leur résolution par programmation dynamique. Dans le Chapitre 5, nous étendons au cadre des mesures de Young des résultats dûs à Evstigneev. Nous établissons alors qu'il est possible de résoudre par programmation dynamique certains problèmes avec des contraintes en espérances conditionnelles. Grâce aux travaux de Bouchard, Elie, Soner et Touzi sur les problèmes de cible stochastique avec perte contrôlée, nous montrons dans le Chapitre 6 qu'un problème avec contrainte en espérance peut se ramener à un problème avec des contraintes en espérances conditionnelles. Comme cas particulier, nous prouvons ainsi que le problème initial de la gestion du barrage peut se résoudre par programmation dynamique.

En raison de la gravité des accidents liés au phénomène de fatigue-propagation de fissure, les préoccupations de l'industrie aéronautique à assurer l'intégrité des structures soumises à ce mode de sollicitation revêtent un caractère tout à fait essentiel. Les travaux de thèse présentés dans ce mémoire visent à appréhender le problème de sûreté des structures aéronautiques dimensionnées en tolérance aux dommages sous l'angle probabiliste. La formulation et l'application d'une approche fiabiliste menant à des processus de conception et de maintenance fiables des structures aéronautiques en contexte industriel nécessitent cependant de lever un nombre important de verrous scientifiques. Les efforts ont été concentrés au niveau de trois domaines dans ce travail. Une méthodologie a tout d'abord été développée afin de capturer et de retranscrire fidèlement l'aléa du chargement de fatigue à partir de séquences de chargement observées sur des structures en service et monitorées, ce qui constitue une réelle avancée scientifique. Un deuxième axe de recherche a porté sur la sélection d'un modèle mécanique apte à prédire l'évolution de fissure sous chargement d'amplitude variable à coût de calcul modéré. Les travaux se sont ainsi appuyés sur le modèle PREFFAS pour lequel des évolutions ont également été proposées afin de lever l'hypothèse restrictive de périodicité de chargement. Enfin, les analyses probabilistes, produits du couplage entre le modèle mécanique et les modélisations stochastiques préalablement établies, ont entre autre permis de conclure que le chargement est un paramètre qui influe notablement sur la dispersion du phénomène de propagation de fissure. Le dernier objectif de ces travaux a ainsi porté sur la formulation et la résolution du problème de fiabilité en tolérance aux dommages à partir des modèles stochastiques retenus pour le chargement, constituant un réel enjeu scientifique. Une méthode de résolution spécifique du problème de fiabilité a été mise en place afin de répondre aux objectifs fixés et appliquée à des structures jugées représentatives de problèmes réels.

Ce mémoire présente une nouvelle approche pour le calcul de temps d'exécution au pire (WCET) de tâche temps-réel critique, en particulier en ce qui concerne les aléas dus aux caches mémoire. Le point général est fait sur la problématique et l'état de l'art en la matière, mais l'accent est mis sur la théorie elle-même et son formalisme, d'abord dans le cadre monotâche puis dans le cadre multitâche. La méthode utilisée repose sur une technique d'interprétation abstraite, comme la plupart des autres méthodes de calcul de WCET, mais le formalisme est dans une approche probabiliste (bien que déterministe dans le cadre monotâche) de par l'utilisation de chaînes de Markov. La généralisation au cadre multitâche utilise les propriétés proba- bilistes pour faire une évaluation pessimiste d'un WCET et d'un écart type au pire, grâce à une modification astucieuse du propagateur dans ce cadre. Des premières évaluations du modèle, codées à la main à partir des résultats de compilation d'applications assez simples montrent des résultats promet- teurs quant à l'application du modèle sur des programmes réels en vraie grandeur.

Les travaux présentés dans ce mémoire ont été réalisés à l'Institut d'Optique Théorique et Appliquée d'Orsay dans le groupe "couches minces" dirigé par J.P. Chauvineau dont le thème fédérateur des activités est la réalisation et la caractérisation de couches ultra minces de quelques fractions à quelques nanomètres d'épaisseur. Ces systèmes physiques, dont les épaisseurs sont de l'ordre de quelques distances inter-atomiques, présentent souvent des propriétés différentes de celles des matériaux massifs : celles-ci s'expliquent par des effets dimensionnels et/ou d'effets de structure cristalline qui modifient la structure électronique, les propriétés optiques, électriques, magnétiques... Il est ainsi possible d'étudier des problèmes de physique fondamentale originaux et captivants qui peuvent déboucher à court terme sur des réalisations technologiques nouvelles que ce soit dans le domaine des couches minces magnétiques (celui dans lequel j'ai été essentiellement actif) ou dans celui des réflectomètres et/ou monochromateurs X-UV, autre branche d'activité très importante du groupe "couches minces". Il est essentiel de noter que ces propriétés nouvelles ne peuvent s'interpréter correctement que par une connaissance fine des mécanismes de croissance ainsi que des structures cristallographiques et géométriques des échantillons réalisés. C'est ce but que nous avons constamment poursuivi en multipliant les méthodes d'analyse qu'elles soient in-situ et fonctionnant pendant les dépôts ou bien encore ex-situ après la réalisation des échantillons.<br />Mon travail a d'abord consisté à étudier le système de bicouches or et indium par des mesures fines, non destructives et fonctionnant pendant les dépôts de ces matériaux, telles que la mesure de la résistance électrique, du travail de sortie puis par diffraction d'électrons rapides rasants et finalement en utilisant des expériences d'absorption d'électrons de faible énergie. Les expériences de mesure de la résistance électrique nous ont permis de mettre en évidence, suivant les épaisseurs d'indium et les températures de dépôts, des modifications irréversibles que nous avons pu localiser à l'interface or/indium. Il a été possible également d'étudier leur rôle sur les effets de taille quantiques (ETQ) qui avaient été mis en évidence, pour la première fois, sur le même système par des mesures de résistance électrique par C. Pariset et J.P. Chauvineau[1, 2]. Ce phénomène d'ETQ a été ensuite décelé, d'une part par des mesures de travail de sortie en utilisant deux méthodes, celle dite de Kelvin, utilisant un pendule vibrant, et celle de la diode, et d'autre part par la diffraction d'électrons rapides rasants (RHEED). Pour pouvoir interpréter la valeur anormalement élevée de la période de ces oscillations d'ETQ détectées par les méthodes précédentes nous avons monté une expérience d'absorption d'électrons de faible énergie au travers de ces bicouches or/indium qui ont confirmé nos premières hypothèses. Le développement de ces différents résultats constituera la première partie de mon exposé.<br />Puis, dans une deuxième partie, j'exposerai les expériences de caractérisation fine des interfaces de système constitués par la superposition de couches nanométriques de métaux nobles et de métaux de transition magnétiques. Je détaillerai les résultats obtenus par RHEED, réflectométrie de rayons X mous, par diffraction de rayons X et des mesures d'EXAFS ainsi que les propriétés magnétiques nouvelles découvertes sur ces échantillons par les équipes avec qui nous avons mené, et menons encore, des collaborations étroites.<br />Pour finir je présenterai la nouvelle expérience que nous mettons en ce moment au point en collaboration avec l'équipe dirigée par G. Lampel du Laboratoire de la Physique de la Matière Condensée de l'Ecole Polytechnique à Palaiseau ainsi que les premiers résultats obtenus. Il s'agit d'étudier l'interaction d'électrons de faible énergie et polarisés en spin avec des couches minces magnétiques pour pouvoir comprendre plus finement l'origine des phénomènes de magnétorésistance géante découverts sur les échantillons évoqués dans la deuxième partie et de mesurer de manière directe les libres parcours moyens des électrons quand ceci ont des énergies faibles (quelques eV tout au plus).

Dans cette thèse, nous proposons et développons de nouvelles méthodes en statistiques et en traitement du signal et des images basées sur la théorie des possibilités. Ces nouvelles méthodes sont des adaptations d'outils usuels de traitement d'information dont le but est de prendre en compte les défauts dus à la méconnaissance de l'utilisateur sur la modélisation du phénomène observé. Par cette adaptation, on passe de méthodes dont les sorties sont précises, ponctuelles, à des méthodes dont les sorties sont intervallistes et donc imprécises. Les intervalles produits reflètent, de façon cohérente, l'arbitraire dans le choix des paramètres lorsqu'une méthode classique est utilisée.<br />Beaucoup d'algorithmes en traitement du signal ou en statistiques utilisent, de façon plus ou moins explicite, la notion d'espérance mathématique associée à une représentation probabiliste du voisinage d'un point, que nous appelons noyau sommatif. Nous regroupons ainsi, sous la dénomination d'extraction sommative d'informations, des méthodes aussi diverses que la modélisation de la mesure, le filtrage linéaire, les processus d'échantillonnage, de reconstruction et de dérivation d'un signal numérique, l'estimation de densité de probabilité et de fonction de répartition par noyau ou par histogramme,...<br />Comme alternative à l'extraction sommative d'informations, nous présentons la méthode d'extraction maxitive d'informations qui utilise l'intégrale de Choquet associée à une représentation possibiliste du voisinage d'un point, que nous appelons noyau maxitif. La méconnaissance sur le noyau sommatif est prise en compte par le fait qu'un noyau maxitif représente une famille de noyaux sommatifs. De plus, le résultat intervalliste de l'extraction maxitive d'informations est l'ensemble des résultats ponctuels des extractions sommatives d'informations obtenues avec les noyaux sommatifs de la famille représentée par le noyau maxitif utilisé. En plus de cette justification théorique, nous présentons une série d'applications de l'extraction maxitive d'informations en statistiques et en traitement du signal qui constitue une boîte à outils à enrichir et à utiliser sur des cas réels.