Let (X,d) be a metric space, Y a set and f:X\to Y a function. Multifractal analysis consists in the general problem of computing the Hausdorff dimension of the, often fractal, level sets f^{-1}(\{y \}) (y\in Y) of f. We will start with some historical examples for which this problem naturally arose. Then we will describe some classes of functions for which it is completely solved. This will show that multifractal analysis provides refined geometric information on some natural objects and also that it is closely related to large deviations theory. Then, we will focus on the so- called "smoothing transformation" on probability distributions on \mathbb{R}_+, and we will see how its fixed points are naturally related to typical multifractal behaviors. This will lead us to present new results invoked in the study of L\'evy processes in multifractal time, especially concerning the asymptotic behavior of branching random walks.

Il s'agit de l'étude d'une représentation de séquence d'ADN dans un arbre quaternaire dont la construction permet de visualiser les répétitions de suffixes. À partir d'une séquence de lettres, on construit un arbre digital de recherche (\emph{Digital Search Tree}) sur l'ensemble des suffixes de la séquence inversée. Des résultats sur la hauteur et la profondeur d'insertion existent lorsque les séquences à placer dans l'arbre sont indépendantes les unes des autres. Ici les mots à insérer sont fortement dépendants. On donne des propriétés asymptotiques sur la profondeur d'insertion et les longueurs des branches, pour un arbre obtenu à partir des suffixes d'une séquence i.i.d. ou markovienne retournée. De plus, certains résultats peuvent aussi s'interpréter comme des résultats de convergence sur les longueurs de plus longues répétitions d'une lettre dans une séquence Markovienne.

Lorsque l'on s'intéresse aux algorithmes de recherche de motifs, on s'intéresse principalement à deux paramètres~: le nombre d'occurrence d'un motif dans un texte; et le nombre de positions dans le texte où une occurrence peut apparaître. Au regard de la complexité des algorithmes de recherche de motifs, le premier paramètre est lié à la complexité d'un algorithme qui énumère toutes les occurrences présentes dans le texte et le second est fortement associée à la complexité d'un algorithme (souvent dynamique) de comptage du nombre d'occurrences (la mise à jour ne pouvant se faire que lorsqu'une nouvelle occurrence a été trouvée). Nous étudions ces deux paramètres dans un cadre très général. Tout d'abord, le cadre probabiliste est celui de sources corrélées -- les sources dynamiques -- qui est un processus aléatoire qui permet de modéliser entre autre les modèles probabilistes classiques d'étude des chaînes de caractères (les sources de Bernoulli et les chaînes de Markov) et permet de modéliser des processus plus général en permettant d'avoir des interactions entre deux symboles du mot, quelle que soit leur distance. Le type de motif recherché est lui aussi assez général. Dans le cas où le motif est une expression régulière décrit par une expression régulière, nous étudions le nombre de positions d'occurrences de cette expression régulière dans un texte aléatoire. Ce paramètre est étudié par le biais de l'automate qui représente son langage. Ici, le nombre de composantes fortement connexes de l'automate induit par l'expression régulière joue un rôle très important. Le résultat présenté concerne les (graphes des) expressions régulières à une composante fortement connexe mais la méthode s'étend naturellement à un nombre quelconque de composantes fortement connexes. Dans le cas où le motif est un ensemble de mots finis, nous étudions le nombre d'occurrences. Le graphe de De Bruijn, pondéré par les nombre d'occurrences ajoutés par chaque transition joue un grand rôle dans l'étude. A chaque fois, le problème étudié peut s'exprimer sous la forme de graphes pondérés. La matrice de transition de ce graphe se traduit alors en une matrice d'opérateurs fonctionnels qui vont tenir compte de la dynamique de la source probabiliste. En quelque sorte, cet opérateur matriciel combine à la fois la structure algébrique du problème et la dynamique de la source. Enfin, sur un espace de fonction adapté et moyennant de bonnes conditions sur la source, un résultat de décomposition, à la Perron-Frobenius, de opérateur est obtenue. Avec des hypothèses naturelles sur l'expression régulière considérée, la moyenne et la variance du nombre de position où une occurrence d'une expression régulière peut apparaître dépendent linéairement de la taille du texte considéré lorsque le texte est produit par une ``bonne'' source dynamique. De plus, la variable aléatoire correspondante suit asymptotiquement une loi gaussienne. Le résultat est le même pour le nombre d'occurrences d'un ensemble de motif dans un texte. Ce travail a été réalisé en collaboration avec Brigitte Vallée (CNRS et Université de Caen).

Nous étudions les propriétés probabilistes des algorithmes euclidiens pour des coûts à croissance modérée. B. Vallée et V.B. avaient obtenu un théorème de la limite centrale avec vitesse optimale de convergence, et, sous une hypothèse de type réseau sur le coût, un théorème de la limite locale avec vitesse optimale. Plus récemment, A. Hachemi a montré un théorème de la limite locale (sans vitesse) pour tous les coûts. Une hypothèse de type diophantien (et générique) sur les coûts nous permet de contrôler la vitesse de convergence. Notre démonstration utilise certains résultats-clés du travail avec B. Vallée (basés sur les techniques de Dolgopyat) ainsi que d'autres méthodes dues a Dolgopyat.

En fouille de données, l'objectif est d'extraire des connaissances à partir de grandes bases de données. Une base de données est une suite d'objets (Personne1, Personne2,....) qui sont eux-mêmes une suite de descripteurs (grand, petit, blond, brun, etc). Dans ce type de bases, la connaissance se représente sous forme de motifs de descripteurs qui apparaissent un nombre de fois supérieur à un seuil fixé par l'utilisateur. On dira par exemple que le motif (petit,brun) est \gamma-fréquent s'il apparaît dans au moins \gamma objets. Plus un motif est fréquent, plus les descripteurs qu'il contient sont corrélés. Notre problème est de compter le nombre de motifs fréquents dans une base de données aléatoire pour un seuil \gamma fixé. Ce problème est doublement intéressant. Tout d'abord, il correspond à la quantité d'informations que les experts reçoivent après extraction des motifs. Selon que le seuil est petit ou grand, cette quantité explose ou reste accessible et jusqu'à aujourd'hui, le seul ordre de grandeur disponible est celui du pire des cas (2^m pour m descripteurs et pour tout seuil). Un ordre de grandeur plus réaliste provenant d'une analyse en moyenne est donc souhaitable. De plus, les bases considérées admettent un codage naturel sous forme d'une matrice binaire. En algorithmique, les matrices binaires (pas nécessairement carrées) codent aussi des objets combinatoires comme les graphes bipartites, co-bipartites ou les hypergraphes. Les motifs fréquents, ou des représentations plus compactes comme les motifs fermés et les bordures, ont alors une traduction en termes de matrices, de graphes ou d'hypergraphes. Par exemple, les motifs fréquents sont des sous-graphe bipartites complets particuliers, les motifs fermés sont des séparateurs minimaux dans le graphe co-bipartite et la bordure est en bijection avec les traverses minimales d'un hypergraphe (associé à la base complémentaire). Dénombrer les motifs fréquents, fermés ou la bordure revient donc à dénombrer ces objets combinatoires. Notre modèle aléatoire suppose que chaque ligne de la matrice (correspondant à chaque objet) est un mot produit par une source quelconque (sur l'alphabet \{0,1\}). Nous étudions trois types de seuils: les seuils constants, les seuils proportionnels au nombre d'objets et les seuils au moins logarithmiques en le nombre d'objets. A chacun de ces trois seuils, correspond une hypothèse qui induit un résultat. Nous exposerons ces résultats puis nous montrerons que les hypothèses sont suffisamment générales pour qu'un grand nombre de sources conviennent (sources de Bernoulli, chaînes de Markov, sources dynamiques,...).

Plusieurs modèles de graphes aléatoires ont été proposés pour tenter d'expliquer le phénomène petit-monde. Le plus célèbre est sans doute le concept de navigabilité introduit par J. Kleinberg en 2000. De nombreuses généralisations de ce modèle ont été proposées par la suite, démontrant sa généralité. Malheureusement les processus de construction sous-jacents à ces généralisations imposent la connaissance globale des individus du réseau, ce qui n'est pas raisonnable pour tenter d'expliquer ce phénomène sur le graphe des connaissances sociales par exemple. Nous proposons ici un premier modèle de construction aléatoire complètement distribué, très économique en mémoire, qui peut être considéré comme un premier pas vers une explication de l'émergence du phénomène petit-monde dans les réseaux d'interaction "réels". Notre approche consiste en la construction d'un réseau aléatoire approximant correctement les informations nécessaires à la construction.

On utilise un algorithme pour définir des bijections impliquant les chemins de Dyck. Cet algorithme est paramétré par des règles de réécriture et est proche de la dérivation d'un mot dans une grammaire algébrique. Les bijections sont des variations de la construction classique des chemins de Dyck par l'insertion d'un pic dans la dernière descente. Une étude systématique des algorithmes paramétrés par une seule règle de réécriture permet d'identifier 12 bijections et, compte-tenu des symétries, 5 paramètres classiques ou nouveaux dont la distribution est identique à la longueur de la dernière descente. On présente d'autres bijections définissables par des généralisations de cet algorithme et utilisées dans divers contextes combinatoires.

Dans cet exposé, nous présentons et étudions un algorithme de rendez-vous basé sur des délais aléatoires. Cet algorithme peut également être considéré comme un algorithme distribué probabiliste pour trouver le couplage maximal. Tout processus du réseau génère une variable aléatoire uniforme dans l'intervalle réel [0,1] pour chacun de ses processus voisins. Le nombre produit est censé être un temps possible pour avoir un rendez-vous, si les deux processus sont disponibles à ce moment-là. Initialement, le nombre des temps potentiellement possibles proposés par les processus est deux fois le nombre de liens entre eux. Toutes les fois que l'horloge atteint le plus petit temps généré, il y aura un rendez-vous entre le processus qui propose ce temps et le processus sollicité et tous les deux annulent toutes autres données de leurs agendas, informant leurs voisins. Ces derniers mettent à jour leurs agendas en suppriment les temps qu'ils ont proposé initialement à ces deux processus. L'algorithme continue pour les processus restants jusqu'à ce que le temps 1 ait expiré. Nous étudions l'espérance du nombre rendez-vous qui est la taille moyenne de couplage obtenu. Nous donnons une formule récursive qui pourrait être employée pour calculer, en général, ce nombre et nous donnons aussi les formes closes ou les valeurs asymptotiques pour quelques familles intéressantes des graphes (arbres, graphes aléatoires, mille-pattes,...). Notre algorithme est plus efficace que ceux que nous connaissons dans la mesure où le nombre prévu de rendez-vous par tour est plus grand.

L'algorithme d'élection de {\em leader} est un processus d'élimination qui divise récursivement en deux sous-groupes un groupe initial de taille n, en élimine un et continue la procédure jusqu'à obtenir un {\em leader}. De tels algorithmes de sélection aléatoire ont de nombreuses applications dans le cadre des systèmes distribués tels que pour synchroniser les réseaux de communication sans fil. On s'intéresse au coût de l'algorithme, i.e. le nombre d'opérations nécessaires à son exécution. Il est connu que le temps moyen pour traiter un groupe de taille n est asymptotiquement de l'ordre de \log n et qu'en outre, l'algorithme présente un comportement oscillatoire. Le but de ce travail est de proposer une représentation alternative de ce comportement asymptotique en utilisant des techniques probabilistes simples.