Cette thèse se décompose en deux parties indépendantes. Notre objectif dans la première partie est d'étudier le comportement asymptotique des $U$-statistiques, basées sur des noyaux d'ordre 2, échantillonnées par une marche aléatoire. Plus précisément, on se donne $(S_n)_(n \in \N)$ une marche aléatoire sur $\Z^d$, $d \geq 1$ et $(\xi_x)_(x \in \Z^(d))$ une collection de variables aléatoires indépendantes, identiquement distribuées, indépendante de $(S_n)_(n \in \N)$. On note $\mu$ la loi de $\xi_0$ et l'on désigne par $h : \R^2\ra \R$, une fonction mesurable, symétrique, telle que $h \in L^2(\mu\otimes\mu)$. On s'intéresse au comportement asymptotique de la suite de processus, $$ \cU_n(t)=\sum_(i,j=0)^([nt])h(\xi_(S_i), \xi_(S_j)), \quad t\in[0,1], \quad n=0,1,\ldots, $$ à valeurs dans $\cD([0,1])$, l'espace des fonctions c.à.l.à.g. définies sur $[0,1]$, muni de la topologie de Skorohod. Cabus et Guillotin ont obtenu la distribution asymptotique de ces objets, dans le cas où la marche aléatoire, $(S_n)_(n \in \N)$, est récurrente sur $\Z^2$, ainsi que dans le cas où elle est transiente sur $\Z^d$, pour $d\geq3$. Elles ont également conjecturé la forme de la distribution limite, dans le cas de la marche aléatoire simple, symétrique, sur $\Z$. Dans le cas où $\Sn$ appartient au domaine d'attraction d'une loi stable d'indice $1<\alpha\leq2$, nous prouvons deux théorèmes limites fonctionnels, décrivant le comportement asymptotique de $\(\cU_n, n=1,2,\ldots\)$. Nous démontrons ainsi, la conjecture de Cabus et Guillotin. Par ailleurs, nous donnons une nouvelle preuve de leurs résultats.\\ Dans une seconde partie, nous étudions le comportement asymptotique du temps d'atteinte de deux versions d'un algorithme d'évolution simplifié, modélisant le repliement d'une protéine : le $(1+1)$-EA sur le problème LeadingOnes. Pour chaque algorithme nous donnons une loi des grands nombres, un théorème central limite et nous comparons la performance des deux modèles.\\

La marche de Sinai est un modèle élémentaire de marches aléatoires en milieu aléatoire unidimensionnelle effectuant des sauts unités sur ses plus proches voisins. On impose trois conditions sur le milieu aléatoire : deux hypothèses nécessaires pour obtenir un processus récurrent non réduit à un marche aléatoire simple et une hypothèse de régularité qui nous permet un bon contrôle des fluctuations du milieu aléatoire. Le comportement asymptotique de ce processus a été découvert par Y. Sinai en 1982 : il montre qu'il est sous diffusif et que pour instant n donné il est localisé dans le voisinage d'un point déterminé du réseau. Ce point est une variable aléatoire dépendant uniquement du milieu aléatoire et de n dont la distribution limite a été déterminée par H. Kesten et A. O. Golosov (indépendamment) en 1986. Une partie de cette thèse (partie II) a eu pour but de donner une preuve alternative au résultat de Y. Sinai . L'étude détaillée des résultats sur la localisation nous a permis de découvrir un nouvel aspect du comportement de la marche de Sinai que nous avons appelé concentration (partie III de la thèse). Nous avons montré que celle-ci était concentrée dans un voisinage restreint du point de localisation, c'est-à-dire que pour un intervalle de temps de longueur n la marche de Sinai passe la quasi-totalité de ce temps n dans un voisinage du point de localisation dont la taille est négligeable devant la distance parcourue. Nous avons également montré que le temps local de la marche de Sinai au point de localisation normalisé par n converge en probabilité vers une variable aléatoire dépendant uniquement du milieu et de n. Cette variable aléatoire est l'inverse de la moyenne du temps local dans la vallée où la marche de Sinai reste prisonnière, en un temps de retour au point de localisation. Les résultats que nous avons obtenus sont de type « trempé », c'est-à-dire que l'on travaille avec un milieu aléatoire appartenant à un sous-espace de probabilité du milieu aléatoire et on montre que ce sous-espace à une probabilité qui tend vers 1. De ces résultats est apparu des conséquences naturelles sur le maximum des temps locaux et le lieu favori de la marche de Sinai, notamment nous avons montré que la marche de Sinai et les lieux favoris de cette marche, correctement normalisés, ont même distribution limite.

Les nids des insectes sociaux fascinent car, aussi complexes et structurés qu'ils puissent être, ils sont construits de façon auto-organisée par des insectes qui peuvent être de plusieurs ordres de grandeur plus petits que la structure. Nous abordons ici l'étude des mécanismes de comportement individuel impliqués dans ces processus de morphogenèse à travers l'exemple de l'agrégation de cadavres par une colonie de fourmis Messor Sancta. Nous proposons un modèle de marche aléatoire non réciproque faisant émerger un suivi des structures, appuyé sur des observations individuelles et dont nous étudions les propriétés statistiques. Nous modélisons également l'interaction entre les actes de construction et un écoulement d'air de faible vitesse comme un exemple des couplages écoulement-constructions supposés responsables de l'adaptation des nids aux conditions environnementales.

Dans cette thèse, nous nous intéressons à la caractérisation de grandes collections de documents (en utilisant les liens entre ces derniers) afin de faciliter leur utilisation et leur exploitation par des humains ou par des outils informatiques. Dans un premier temps, nous avons abordé la problématique du calcul de centralité dans les graphes de documents. Nous avons décrit les principaux algorithmes de calcul de centralité existants en mettant l'accent sur le problème TKC (Tightly Knit Community) dont souffre la plupart des mesures de centralité récentes. Ensuite, nous avons proposé trois nouveaux algorithmes de calcul de centralité (MHITS, NHITS et DocRank) permettant d'affronter le phénomène TKC. Les différents algorithmes proposés ont été évalués et comparés aux approches existantes. Des critères d'évaluation ont notamment été proposés pour mesurer l'effet TKC. Dans un deuxième temps, nous nous sommes intéressés au problème de la classification non supervisée de documents. Plus précisément, nous avons envisagé ce regroupement comme une tâche d'identification de structures de communautés (ISC) dans les graphes de documents. Nous avons décrit les principales approches d'ISC existantes en distinguant les approches basées sur un modèle génératif des approches algorithmiques ou classiques. Puis, nous avons proposé un modèle génératif (SPCE) basé sur le lissage et sur une initialisation appropriée pour l'ISC dans des graphes de faible densité. Le modèle SPCE a été évalué et validé en le comparant à d'autres approches d'ISC. Enfin, nous avons montré que le modèle SPCE pouvait être étendu pour prendre en compte simultanément les liens et les contenus des documents.

Cette thèse étudie la distribution limite de paramètres définis récursivement sur des arbres (graphes enracinés). Un premier paramètre étudié est le résultat d'expressions arithmétiques tirées aléatoirement. Une application est l'amélioration heuristique d'un algorithme de recherche de structures secondaires d'ARN. Un autre paramètre étudié est la taille d'expressions logiques ou arithmétiques réduites selon des lois idempotentes, nilpotentes ou d'absorption. J'étudie des fonctionnelles polynomiales du mouvement brownien standard, du pont, du méandre, et de l'excursion browniens en utilisant la méthode des moments à base de séries génératrices et d'analyse de singularité. J'obtiens la limite gaussienne de la loi jointe de la taille et de la longueur de cheminement interne des tries avec source de Bernoulli en utilisant des méthodes de point fixe.

En mécanique statistique quantique, un système quantique ouvert représente un petit système de degré fini de liberté en interaction avec un système extérieur très large (bain thermique, réservoir bosonique, environnement... ).<br /> <br /> Pour décrire cette interaction, les physiciens et les mathématiciens utilisent souvent deux approches: l'approche markovienne et l'approche hamiltonienne.<br /> <br /> Nous comparons systématiquement les approches hamiltonienne et markovienne dans les cas des modèles de spin-boson et de Pauli-Fierz. Ensuite, nous présentons un modèle lindbladien pour une chaîne de N spins couplée à des bains thermiques. Puis, nous étudions le lien entre les interactions quantiques répétées et la limite de densité faible. Finalement, nous étudions les propriétés des équations d'évolutions discrètes associées aux modèles d'interactions répétées, qui sont dirigées par des bruits discrets classiques.

La plupart des modèles mathématiques introduits dans la littérature biologique décrivant des phénomènes spatiaux de populations en interaction consistent en des systèmes d'équations différentielles ordinaires obtenues sous des hypothèses de dispersion globale, excluant par conséquent toute structure spatiale. Les systèmes de particules, au contraire, sont des processus de Markov d'espace d'états $F^S$ où $F$ est un ensemble fini de couleurs et $S$ est une structure spatiale, typiquement $\Z^d$. Ils sont en ce sens parfaitement adaptés à l'étude des conséquences de l'inclusion d'une structure spatiale sous forme d'interactions locales. Nous étudions les propriétés mathématiques (mesures stationnaires, géométrie des configurations, transitions de phases) de différents systèmes de particules multicolores définis sur $\Z^d$. Chacun de ces systèmes est déstiné à modéliser les interactions locales au sein d'une communauté de populations structurée spatialement. Plus précisément, les processus biologiques étudiés sont la succession écologique, l'allélopathie ou compétition entre une espèce inhibitrice et une espèce sensible, les interactions multispécifiques hôtes-symbiontes, et les migrations continues de gènes des cultures transgéniques par pollinisation en milieu hétérogène. Les techniques mathématiques sont purement probabilistes, incluant le couplage, la dualité, les arguments multi-échelle, la percolation orientée, les propriétés asymptôtiques des marches aléatoires, ou encore les estimations de grandes déviations.

Cette thèse porte sur une étude<br />analytique et probabiliste des théories de Heckman--Opdam et des<br />immeubles affines de type $\tilde{A}_r$. On étudie aussi la<br />frontière de Poisson des matrices triangulaires inversibles<br />rationnelles.<br /><br />Un de nos principaux résultats est l'obtention de nouvelles<br />estimations des fonctions hypergéométriques de Heckman--Opdam. Nos<br />preuves sont relativement plus simples que dans le cas particulier<br />des espaces symétriques $G/K$. Par exemple pour les estimations de<br />base des fonctions sphériques, obtenues par Harish-Chandra, ou<br />Gangolli et Varadarajan, ainsi que pour les estimations récentes<br />de la fonction sphérique élémentaire $\phi_0$ par Anker, Bougerol<br />et Jeulin.<br /><br />Un des autres principaux résultats est l'estimation du noyau de la<br />chaleur associé à un certain laplacien combinatoire sur un<br />immeuble affine de type $\tilde{A}_r$.

La théorie de la complexité distingue les problèmes que l'on sait résoudre en un temps polynomial en la taille des données (que l'on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l'état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l'on peut qualifier de déraisonnable). C'est pour cette raison que la communauté scientifique s'est tournée vers les algorithmes (polynomiaux) d'approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d'approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d'approximation de k si la taille de toute solution pouvant être retournée par l'algorithme est inférieure ou égale à k fois la taille de la solution optimale). Dans la littérature, on en vient à considérer qu'un algorithme est plus performant qu'un autre lorsqu'il possède un plus petit rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Mes travaux de thèse ont pour objet de mieux "capturer" le comportement des algorithmes d'approximation en allant plus loin que le simple rapport d'approximation en pire cas, et ce sur deux problèmes distincts : I. Le problème du Vertex Cover En montrant que les performances moyennes d'un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l'algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l'optimum lorsque n tend vers l'infini. En évaluant les performances moyennes d'un algorithme. Nous avons prouvé que l'algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d'approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n'importe quel graphe. Ce résultat, combiné à d'autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d'approximation en pire cas . En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies. On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation (fonction du degré max. du graphe). Tous ces résultats montrent que le rapport d'approximation en pire cas n'est pas toujours suffisant pour caractériser l'intégralité de la qualité d'un algorithme et que d'autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour. II. Le problème de la connexion de groupes dynamiques dans les réseaux Nous avons analysé un processus de mise-à-jour d'un arbre connectant dans un réseau un groupe que les membres peuvent rejoindre ou quitter à tout moment. Notre processus possède de bonnes propriétés : il est simple à implémenter et il garantit, après chaque opération d'ajout ou de retrait, que le diamètre de l'arbre est au plus 2 fois l'optimal. Cependant, pour obtenir cette garantie, nous devons autoriser la reconstruction totale de l'arbre lorsque le membre identifié comme sa racine quitte le groupe. Ces étapes de reconstruction sont très coûteuses et nous cherchons donc à en évaluer le nombre. Des travaux précédents montraient que dans le pire cas, il faut reconstruire (quasiment) à chaque étape pour conserver la garantie sur le diamètre. Nous montrons dans cette thèse (en utilisant les marches aléatoires, etc.) que, en fonction de certains paramètres du problèmes (comme les probabilités associées aux opérations d'ajout et de retrait), l'espérance du nombre de reconstructions est soit logarithmique en le nombre d'évènements (ajout ou retrait), soit constant. Ce résultat montre que le comportement moyen est très bon (malgré un pire cas très défavorable) et que notre processus de mise-à-jour peut être une solution viable en pratique.

L'étude des marches aléatoires fait apparaître des connexions entre leurs propriétés algébriques, géométriques ou encore combinatoires et leurs propriétés stochastiques. Si les marches aléatoires sur les groupes - ou sur des espaces homogènes - fournissent beaucoup d'exemples, il serait appréciable d'obtenir de tels résultats de rigidité sur des structures algébriques plus faibles telles celles de semi-groupoide ou de groupoide. Dans cette thèse il est considéré un exemple de semi-groupoide et un exemple de groupoide, tous les deux sont définis a partir de sous-graphes contraints du graphe de Cayley d'un groupe - le premier graphe est dirige alors que le second ne l'est pas. Pour ce premier exemple, on précise un résultat de Campanino et Petritis (ils ont montre que la marche aléatoire simple était transiente pour cet exemple de graphe dirigé) en déterminant la frontière de Martin associée à cette marche et établissant sa trivialité Dans le second exemple apparaissant dans ce manuscrit, on considère des pavages quasi-périodiques de l'espace euclidien obtenus à l'aide de la méthode de coupe et projection. Nous considérons la marche aléatoire simple le long des arêtes des polytopes constituant le pavage, et nous répondons a la question du type de celle-ci, c'est-à-dire nous déterminons si elle est récurrente ou transiente. Nous montrons ce résultat en établissant des inégalités isopérimétriques Cette stratégie permet d'obtenir des estimées de la vitesse de décroissance du noyau de la chaleur, ce que n'aurait pas permis l'utilisation d'un critère de type Nash-Williams.