Nous étudions la mesure spectrale des transformations stationnaires, puis nous l’utilisons pour étudier le théorème ergodique et le théorème limite central. Nous étudions également les martingales avec une nouvelle preuve du théorème central limite, sans analyse de Fourier. Pour le théorème limite central pour marches aléatoires dans un environnement aléatoire sur la dimension 1, on donne deux méthodes pour l’obtenir: approximation pour une martingale et méthode des moments. La méthode des martingales fait résoudre l’équation de Dirichlet (I - P)h = 0, alors que celle des moments résoudre l’équation de Poisson (I - P)h = f. Enfin, nous pouvons utiliser la deuxième méthode pour prouver la relation d’Einstein pour des diffusions réversibles dans un environnement aléatoire dans une dimension. / We study the spectral measure for stationary transformations, and then apply to Ergodic theorem and Central limit theorem. We study also martingale process with a new proof of the central limit theorem without Fourier analysis. For the central limit theorem for random walks in random environment, we give two methods to obtain it: martingale approximation and moments. The method of martingales solves Dirichlet’s equation (I - P)h = 0, and the method of moments solves Poisson’s equation (I - P)h = f. Finally, we can use the second method to prove the Einstein relation for reversible diffusions in random environment in one dimension.

Cette thèse s'organise en deux parties : une première partie s'intéresse aux mesures de similarité entre sommets d'un graphe, une seconde aux méthodes de clustering de graphe biparti. Une nouvelle mesure de similarité entre sommets basée sur des marches aléatoires en temps courts est introduite. Cette méthode a l'avantage, en particulier, d'être insensible à la densité du graphe. Il est ensuite proposé un large état de l'art des similarités entre sommets, ainsi qu'une comparaison expérimentale de ces différentes mesures. Cette première partie se poursuit par la proposition d'une méthode robuste de comparaison de graphes partageant le même ensemble de sommets. Cette mesure est mise en application pour comparer et fusionner des graphes de synonymie. Enfin une application d'aide à la construction de ressources lexicales est présentée. Elle consiste à proposer de nouvelles relations de synonymie à partir de l'ensemble des relations de synonymie déjà existantes. Dans une seconde partie, un parallèle entre l'analyse formelle de concepts et le clustering de graphe biparti est établi. Ce parallèle conduit à l'étude d'un cas particulier pour lequel une partition d’un des groupes de sommets d’un graphe biparti peut-être déterminée alors qu'il n'existe pas de partitionnement correspondant sur l’autre type de sommets. Une méthode simple qui répond à ce problème est proposée et évaluée. Enfin Kodex, un système de classification automatique des résultats d'une recherche d'information est présenté. Ce système est une application en RI des méthodes de clustering vues précédemment. Une évaluation sur une collection de deux millions de pages web montre les avantages de l'approche et permet en outre de mieux comprendre certaines différences entre méthodes de clustering. / This thesis is organized in two parts : the first part focuses on measures of similarity (or proximity) between vertices of a graph, the second part on clustering methods for bipartite graph. A new measure of similarity between vertices, based on short time random walks, is introduced. The main advantage of the method is that it is insensitive to the density of the graph. A broad state of the art of similarities between vertices is then proposed, as well as experimental comparisons of these measures. This is followed by the proposal of a robust method for comparing graphs sharing the same set of vertices. This measure is shown to be applicable to the comparison and merging of synonymy networks. Finally an application for the enrichment of lexical resources is presented. It consists in providing candidate synonyms on the basis of already existing links. In the second part, a parallel between formal concept analysis and clustering of bipartite graph is established. This parallel leads to the particular case where a partition of one of the vertex groups can be determined whereas there is no corresponding partition on the other group of vertices. A simple method that addresses this problem is proposed and evaluated. Finally, a system of automatic classification of search results (Kodex) is presented. This system is an application of previously seen clustering methods. An evaluation on a collection of two million web pages shows the benefits of the approach and also helps to understand some differences between clustering methods.

Les méthodes de Monte Carlo (MC) sont des méthodes numériques qui utilisent des nombres aléatoires pour résoudre avec des ordinateurs des problèmes des sciences appliquées et des techniques. On estime une quantité par des évaluations répétées utilisant N valeurs et l'erreur de la méthode est approchée par la variance de l'estimateur. Le présent travail analyse des méthodes de réduction de la variance et examine leur efficacité pour l'intégration numérique et la résolution d'équations différentielles et intégrales. Nous présentons d'abord les méthodes MC stratifiées et les méthodes d'échantillonnage par hypercube latin (LHS : Latin Hypercube Sampling). Parmi les méthodes de stratification, nous privilégions la méthode simple (MCS) : l'hypercube unité Is := [0; 1)s est divisé en N sous-cubes d'égale mesure, et un point aléatoire est choisi dans chacun des sous-cubes. Nous analysons la variance de ces méthodes pour le problème de la quadrature numérique. Nous étudions particulièrment le cas de l'estimation de la mesure d'un sous-ensemble de Is. La variance de la méthode MCS peut être majorée par O(1=N1+1=s). Les résultats d'expériences numériques en dimensions 2,3 et 4 montrent que les majorations obtenues sont précises. Nous proposons ensuite une méthode hybride entre MCS et LHS, qui possède les propriétés de ces deux techniques, avec un point aléatoire dans chaque sous-cube et les projections des points sur chacun des axes de coordonnées également réparties de manière régulière : une projection dans chacun des N sousintervalles qui divisent I := [0; 1) uniformément. Cette technique est appelée Stratification Sudoku (SS). Dans le même cadre d'analyse que précédemment, nous montrons que la variance de la méthode SS est majorée par O(1=N1+1=s) ; des expériences numériques en dimensions 2,3 et 4 valident les majorations démontrées. Nous présentons ensuite une approche de la méthode de marche aléatoire utilisant les techniques de réduction de variance précédentes. Nous proposons un algorithme de résolution de l'équation de diffusion, avec un coefficient de diffusion constant ou non-constant en espace. On utilise des particules échantillonnées suivant la distribution initiale, qui effectuent un déplacement gaussien à chaque pas de temps. On ordonne les particules suivant leur position à chaque étape et on remplace les nombres aléatoires qui permettent de calculer les déplacements par les points stratifiés utilisés précédemment. On évalue l'amélioration apportée par cette technique sur des exemples numériques Nous utilisons finalement une approche analogue pour la résolution numérique de l'équation de coagulation, qui modélise l'évolution de la taille de particules pouvant s'agglomérer. Les particules sont d'abord échantillonnées suivant la distribution initiale des tailles. On choisit un pas de temps et, à chaque étape et pour chaque particule, on choisit au hasard un partenaire de coalescence et un nombre aléatoire qui décide de cette coalescence. Si l'on classe les particules suivant leur taille à chaque pas de temps et si l'on remplace les nombres aléatoires par des points stratifiés, on observe une réduction de variance par rapport à l'algorithme MC usuel. / Monte Carlo (MC) methods are numerical methods using random numbers to solve on computers problems from applied sciences and techniques. One estimates a quantity by repeated evaluations using N values ; the error of the method is approximated through the variance of the estimator. In the present work, we analyze variance reduction methods and we test their efficiency for numerical integration and for solving differential or integral equations. First, we present stratified MC methods and Latin Hypercube Sampling (LHS) technique. Among stratification strategies, we focus on the simple approach (MCS) : the unit hypercube Is := [0; 1)s is divided into N subcubes having the same measure, and one random point is chosen in each subcube. We analyze the variance of the method for the problem of numerical quadrature. The case of the evaluation of the measure of a subset of Is is particularly detailed. The variance of the MCS method may be bounded by O(1=N1+1=s). The results of numerical experiments in dimensions 2,3, and 4 show that the upper bounds are tight. We next propose an hybrid method between MCS and LHS, that has properties of both approaches, with one random point in each subcube and such that the projections of the points on each coordinate axis are also evenly distributed : one projection in each of the N subintervals that uniformly divide the unit interval I := [0; 1). We call this technique Sudoku Sampling (SS). Conducting the same analysis as before, we show that the variance of the SS method is bounded by O(1=N1+1=s) ; the order of the bound is validated through the results of numerical experiments in dimensions 2,3, and 4. Next, we present an approach of the random walk method using the variance reduction techniques previously analyzed. We propose an algorithm for solving the diffusion equation with a constant or spatially-varying diffusion coefficient. One uses particles, that are sampled from the initial distribution ; they are subject to a Gaussian move in each time step. The particles are renumbered according to their positions in every step and the random numbers which give the displacements are replaced by the stratified points used above. The improvement brought by this technique is evaluated in numerical experiments. An analogous approach is finally used for numerically solving the coagulation equation ; this equation models the evolution of the sizes of particles that may agglomerate. The particles are first sampled from the initial size distribution. A time step is fixed and, in every step and for each particle, a coalescence partner is chosen and a random number decides if coalescence occurs. If the particles are ordered in every time step by increasing sizes an if the random numbers are replaced by statified points, a variance reduction is observed, when compared to the results of usual MC algorithm.

Le but de cette thèse est de modéliser la propagation d’un contaminant au sein d’un réseau d’eau potable muni de capteurs temps réel. Elle comporte les trois axes de développement suivant: la résolution des équations de transport, celle du problème d’identification des sources de contamination et le placement des capteurs.Le transport d’un produit chimique est modélisé dans un réseau d’eau potable par l’équation de transport réaction 1-D avec l’hypothèse de mélange parfait aux noeuds. Il est proposé d’améliorer sa prédiction par l’ajout d’un modèle de mélange imparfait aux jonctions double T et d’un modèle de dispersion prenant en compte un profil de vitesse 3-D et la diffusion radiale. Le premier modèle est créé à l’aide d’un plan d’expériences avec triangulation de Delaunay, de simulations CFD, et de la méthode d’interpolation krigeage. Le second utilise les équations adjointes du problème de transport avec l’ajout de particules évoluant à l’aide d’une marche aléatoire, cette dernière modélisant la diffusion radiale dans la surface droite du tuyau.Le problème d’identification des sources consiste, à l’aide de réponses positives ou négatives à la contamination des noeuds capteurs, à trouver l’origine, le temps d’injection et la durée de la contamination. La résolution de ce problème inverse est faite par la résolution des équations de transport adjointes par formulation backtracking. La méthode donne la liste des sources potentielles ainsi que le classement de celles-ci selon leur probabilité d’être la vraie source de contamination. Elle s’exprime en fonction de combien, en pourcentage, cette source potentielle peut expliquer les réponses positives aux capteurs.Le placement des capteurs est optimisé pour l’identification des sources. L’objectif est la maximisation du potentiel de détection de la véritable source de contamination. Deux résolutions sont testées. La première utilise un algorithme glouton combiné à une méthode de Monte Carlo.La seconde utilise une méthode de recherche locale sur graphe.Finalement les méthodes sont appliquées à un cas test réel avec dans l’ordre : le placement des capteurs, l’identification de la source de contamination et l’estimation de sa propagation. / The aim of this thesis is to model the propagation of a contaminant inside a water distribution network equipped with real time sensors. There are three research directions: the solving of the transport equations, the source identification and the sensor placement. Classical model for transport of a chemical product in a water distribution network isusing 1D-advection-reaction equations with the hypothesis of perfect mixing at junctions. It isproposed to improve the predictions by adding a model of imperfect mixing at double T-junctions and by considering dispersion effect in pipes which takes into account a 3-D velocity profile. The first enhancement is created with the help of a design of experiment based on the Delaunay triangulation, CFD simulations and the interpolation method Kriging. The second one uses the adjoint formulation of the transport equations applied with an algorithm of particle backtracking and a random walk, which models the radial diffusion in the cross-section of a pipe.The source identification problem consists in finding the contamination origin, itsinjection time and its duration from positive and negative responses given by the sensors. The solution to this inverse problem is computed by solving the adjoint transport equations with a backtracking formulation. The method gives a list of potential sources and the ranking of thosemore likely to be the real sources of contamination. It is function of how much, in percentage, they can explain the positive responses of the sensors.The sensor placement is chosen in order to maximize the ranking of the real source of contamination among the potential sources. Two solutions are proposed. The first one uses agreedy algorithm combined with a Monte Carlo method. The second one uses a local search method on graphs. Finally the methods are applied to a real test case in the following order: the sensor placement, the source identification and the estimation of the contamination propagation.

Ce manuscrit de thèse s’intéresse à l’étude théorique et à l’observation d’effets quantiques résultantde la manipulation de photons en fréquence. Ainsi nous rapportons une expérience d’interférenceà deux photons, pour laquelle l’intrication et la manipulation des photons survient dans le domainedes fréquences. Nous montrons que cette figure d’interférence est sensible à la dispersion des deuxphotons jumeaux et que ce phénomène peut être compensé de manière non-locale. D’un autre coté,nous étudions la réalisation d’une marche aléatoire quantique établie par la modulation de phase.Nous mettons en évidence un comportement intéressant de ces marches et suggérons un schémaexpérimental. / This manuscript deals with a theoretical and experimental study of quantum effects taking place inthe frequency domain. On one side, we report a two photons interference experiment, where both theentanglement of the photons and their manipulation take place in the frequency domain. We showthat this interference pattern is sensitive to the dispersion of both photons and allows us to perform anonlocal dispersion cancellation. On the other side we study the implementation of a quantum walkbased on the phase modulation. We predict an interesting behavior of these quantum walks andsuggest a physical implementation.

Nous présentons dans ce mémoire un nouvel algorithme de type Metropolis-Hastings dans lequel la distribution instrumentale a été conçue pour l'estimation de distributions cibles bimodales. En fait, cet algorithme peut être vu comme une modification de l'algorithme Metropolis de type marche aléatoire habituel auquel on ajoute quelques incréments de grande envergure à des moments aléatoires à travers la simulation. Le but de ces grands incréments est de quitter le mode de la distribution cible où l'on se trouve et de trouver l'autre mode. Par la suite, nous présentons puis démontrons un résultat de convergence faible qui nous assure que, lorsque la dimension de la distribution cible croît vers l'infini, la chaîne de Markov engendrée par l'algorithme converge vers un certain processus stochastique qui est continu presque partout. L'idée est similaire à ce qui a été fait par Roberts et al. (1997), mais la technique utilisée pour la démonstration des résultats est basée sur ce qui a été fait par Bédard (2006). Nous proposons enfin une stratégie pour trouver la paramétrisation optimale de notre nouvel algorithme afin de maximiser la vitesse d'exploration locale des modes d'une distribution cible donnée tout en estimant bien la pondération relative de chaque mode. Tel que dans l'approche traditionnellement utilisée pour ce genre d'analyse, notre stratégie passe par l'optimisation de la vitesse d'exploration du processus limite. Finalement, nous présentons des exemples numériques d'implémentation de l'algorithme sur certaines distributions cibles, dont une ne respecte pas les conditions du résultat théorique présenté. / In this thesis, we present a new Metropolis-Hastings algorithm whose proposal distribution has been designed to successfully estimate bimodal target distributions. This sampler may be seen as a variant of the usual random walk Metropolis sampler in which we propose large candidate steps at random times. The goal of these large candidate steps is to leave the actual mode of the target distribution in order to find the second one. We then state and prove a weak convergence result stipulating that if we let the dimension of the target distribution increase to infinity, the Markov chain yielded by the algorithm converges to a certain stochastic process that is almost everywhere continuous. The theoretical result is in the flavour of Roberts et al. (1997), while the method of proof is similar to that found in Bédard (2006). We propose a strategy for optimally parameterizing our new sampler. This strategy aims at optimizing local exploration of the target modes, while correctly estimating the relative weight of each mode. As is traditionally done in the statistical literature, our approach consists of optimizing the limiting process rather than the finite-dimensional Markov chain. Finally, we illustrate our method via numerical examples on some target distributions, one of which violates the regularity conditions of the theoretical result.

Dans cette thèse nous étudions le comportement asymptotique de systèmes de particules en interaction de type champ moyen en espace discret, systèmes pour lesquels l'interaction a lieu par l'intermédiaire de la mesure empirique. Dans la première partie de ce mémoire, nous nous intéressons aux systèmes de particules de type Fleming-Viot: les particules se déplacent indépendamment suivant une dynamique markovienne jusqu'au moment où l'une d'entre elles touche un état absorbant. A cet instant, la particule absorbée choisit uniformément une autre particule et saute sur sa position. L'ergodicité du processus est établie dans le cadre de marches aléatoires sur N avec dérive vers l'origine et pour une dynamique proche de celle du graphe complet. Pour ce dernier, nous obtenons une estimation quantitative de la convergence en temps long à l'aide de la courbure de Wasserstein. Nous montrons de plus la convergence de la distribution empirique stationnaire vers une unique distribution quasi-stationnaire, quand le nombre de particules tend vers l'infini. Dans la deuxième partie de ce mémoire, nous nous intéressons au comportement en temps long et quand le nombre de particules devient grand, d'un système de processus de naissance et mort pour lequel les particules interagissent à chaque instant par le biais de la moyenne de leurs positions. Nous établissons l'existence d'une limite macroscopique, solution d'une équation non linéaire ainsi que le phénomène de propagation du chaos avec une estimation quantitative et uniforme en temps / In this thesis we study the asymptotic behavior of particle systems in mean field type interaction in discrete space, where the system acts over one fixed particle through the empirical measure of the system. In the first part of this thesis, we are interested in Fleming-Viot particle systems: the particles move independently of each other until one of them reaches an absorbing state. At this time, the absorbed particle jumps instantly to the position of one of the other particles, chosen uniformly at random. The ergodicity of the process is established in the case of random walks on N with a dirft towards the origin and on complete graph dynamics. For the latter, we obtain a quantitative estimate of the convergence described by the Wasserstein curvature. Moreover, under the invariant measure, we show the convergence of the empirical measure towards the unique quasi-stationary distribution as the size of the system tends to infinity. In the second part of this thesis, we study the behavior in large time and when the number of particles is large of a system of birth and death processes where at each time a particle interacts with the others through the mean of theirs positions. We establish the existence of a macroscopic limit, solution of a non linear equation and the propagation of chaos phenomenon with quantitative and uniform in time estimate

L'objet de cette thèse est l'étude de l'auto-organisation dans les automates cellulaires unidimensionnels.Les automates cellulaires sont un système dynamique discret ainsi qu'un modèle de calcul massivement parallèle, ces deux aspects s'influençant mutuellement. L'auto-organisation est un phénomène où un comportement organisé est observé asymptotiquement, indépendamment de la configuration initiale. Typiquement, nous considérons que le point initial est tiré aléatoirement: étant donnée une mesure de probabilité décrivant une distribution de configurations initiales, nous étudions son évolution sous l'action de l'automate, le comportement asymptotique étant décrit par la(les) mesure(s) limite(s).Notre étude présente deux aspects. D'abord, nous caractérisons les mesures qui peuvent être atteintes à la limite par les automates cellulaires; ceci correspond aux différents comportements asymptotiques pouvant apparaître en simulation. Cette approche rejoint divers résultats récents caractérisant des paramètres de systèmes dynamiques par des conditions de calculabilité, utilisant des outils d'analyse calculable. Il s'agit également d'une description de la puissance de calcul des automates cellulaires sur les mesures.Ensuite, nous proposons des outils pour létude de l'auto-organisation dans des classes restreintes. Nous introduisons un cadre d'étude d'automates pouvant être vus comme un ensemble de particules en interaction, afin d'en déduire des propriétés sur leur comportement asymptotique. Une dernière direction de recherche concerne les automates convergeant vers la mesure uniforme sur une large classe de mesures initiales (phénomène de randomisation). / The subject of this thesis is the study of self-organization in one-dimensional cellular automata.Cellular automata are a discrete dynamical system as well as a massively parallel model of computation, both theseaspects influencing each other. Self-organisation is a phenomenon where an organised behaviour is observed asymptotically, regardless of the initial configuration. Typically, we consider that the initial point is sampled at random; that is, we consider a probability measure describing the distribution of theinitial configurations, and we study its evolution under the action of the automaton, the asymptoticbehaviour being described by the limit measure(s).Our work is two-sided. On the one hand, we characterise measures that can bereached as limit measures by cellular automata; this corresponds to the possible kinds of asymptoticbehaviours that can arise in simulations. This approach is similar to several recent results characterising someparameters of dynamical systems by computability conditions, using tools from computable analysis. Thisresult is also a description of the measure-theoretical computational power of cellular automata.On the other hand, we provided tools for the practical study of self-organization in restricted classes of cellularautomata. We introduced a frameworkfor cellular automata that can be seen as a set of interacting particles, in order todeduce properties concerning their asymptotic behaviour. Another ongoing research direction focus on cellular automata that converge to the uniform measurefor a wide class of initial measures (randomization phenomenon).

En vue de contrôler les émissions de gaz à effet de serre, il est envisagé d’injecter du CO2 dans des réservoirs géologiques. Or le CO2 n'est pas un gaz inerte. En modifiant la composition chimique de l'eau in situ, il est à l'origine d'interactions roche/fluide. Ces réactions géochimiques impactent les propriétés d'écoulement. Aussi, pour s'assurer de la viabilité et de la pérennité du stockage, les opérateurs ont besoin de simulations tenant compte de ces écoulements réactifs. Cependant les paramètres de l'équation macroscopique de transport utilisée sont affectés par les réactions surfaciques. Or, ces spécificités dues au transfert de masse ne sont pas prises en compte actuellement. De même, la loi perméabilité-porosité (K-F) n’est estimée que semi-empiriquement. Le but de cette thèse a été de développer une méthode pour obtenir les coefficients macroscopiques précédents et les relations K-F, en résolvant les équations gouvernant les phénomènes à l'échelle du pore. Pour ce faire, nous avons utilisé l'approche réseau de pores. L'avantage du modèle réseau est qu'il prend en compte explicitement la structure tout en conceptualisant cette dernière à un ensemble de pores et de canaux à la morphologie simplifiée (sphères, cylindres). L'étude est basée sur deux changements d'échelles successifs : du local au pore, puis du pore à la carotte. Le problème de transport réactif est résolu pour des éléments basiques, analytiquement ou numériquement. Puis, en faisant appel aux solutions précédemment trouvées, le transport réactif est traité sur l'ensemble du réseau. Notre model fut validé par des observations sur micromodèles, puis à l'aide d'une expérience d'altération acide / The geological storage of CO2 is considered as an attractive option to reduce the greenhouse gas emissions in the atmosphere. CO2 is not an inert gas, however. Its dissolution in brine forms a weak acid that has the potential to react with the host rock formation. The induced pores structure modification impacts the flow properties. Thus, to ensure the viability and sustainability of CO2 storage, operators need simulations that take into account the specificities of reactive transport. However, the macroscopic coefficients of the reactive transport equation are modified from the values of an inert tracer by surface reactions. These specificities due to mass transfer are currently not considered. Similarly, the permeability-porosity (K-F) relationship is only estimated semi-empirically. The aim of this thesis was to develop a method to obtain the macroscopic coefficients and the K-F laws, by solving the equations governing the pore-scale phenomena. To do this, we used the Pore Network Modelling approach (PNM). The advantage of the PNM is that it explicitly takes into account the pore structure, while conceptualizing the latter to a set of pores and throats whose morphology is simplified into spheres or cylinders for instance. The study is based into two successive upscalings: from local-scale to pore-scale, then from pore-scale to core-scale. The reactive transport problem is solved for basic elements, analytically or numerically. Then, using the solutions previously found at the pore scale, the reactive transport phenomena are treated throughout the network. Our model was validated by observations on micromodels and by a comparison with an acid-induced alteration experiment

Cette thèse a été réalisée au sein de l’entreprise Invivoo. L’objectif principal était de trouver des stratégies d’investissement : avoir un gain important et un risque faible. Les travaux de recherche ont été principalement portés par ce dernier point. Dans ce sens, nous avons voulu généraliser un modèle fidèle à la réalité des marchés financiers, que ce soit pour des données à basse comme à haute fréquence et, à très haute fréquence, variation par variation. / No English summary available.