On s'intéresse à quatre familles de trajectoires formées de pas +1 et -1 commençant en 0: les marches de Bernoulli, les excursions (chemins de Dyck), les méandres (préfixes de chemin de Dyck), les ponts (chemins terminant en 0). On appelle pic, un maximum local. Le nombre standard de pics dans chacune de ces familles est n/4 (pour des trajectoires de longueur n): on a même un TCL avec variance lineaire. Du côté des trajectoires, on a également un comportement asymptotique: divisées par racine carrée de n en espace et par n en temps, elles convergent, selon la famille, vers le mouvement Brownien, le méandre Brownien, l'excursion Brownienne ou le pont Brownien. Le but de l'exposé est de répondre à la question suivante: quelle est l'influence du nombre de pics dans le comportement asymptotique des familles décrites plus haut? (c'est-à-dire, comment se comportent ces trajectoires si on les conditionne à avoir k=k(n) pics? et quel est, asymptotiquement, le lien entre "la répartition des pics" et les valeurs prises par les trajectoires?)

Dans cet exposé (qui est basé sur un travail en cours avec Bernhard Gittenberger, TU Wien), je montrerai comment notre bonne vieille ``méthode du noyau'' permet d'obtenir l'aire moyenne de chemins de Dyck généralisés, et notamment que tous les moments sont algébriques ! Dans le classique cas des chemins de Dyck, on se place sur le réseau \mathbb{N}\times\mathbb{N}, on part de l'origine, puis on fait des sauts (+1,-1) ou (+1,-1). On peut s'imposer (ou non) de revenir sur la ligne y=0, qui est donc une "barrière" de la marche. Les chemins de Dyck généralisés sont l'équivalent, avec un ensemble de sauts (+1,+y), où y appartient à un ensemble fini Y d'entiers positifs ou négatifs. Le cas Y=(-1,0,+1) correspond aux chemins de ``Motzkin'',\\ le cas Y=(-1,+1,+2) aux arbres binaires-ternaires,\\ le cas Y=(+2,-3) aux célèbres ``clubs de Duchon'',\\ le cas Y=(+13,+2,-3,-5) à une marche de dérive 7\dots Notre méthode de résolution consiste à annuler un "noyau", afin de résoudre une équation fonctionnelle qui a plus d'inconnues que d'équations... à priori ! Avec Ph. Flajolet, nous avons étudié via cette méthode différents paramètres (retours en zéro, altitude finale) de tels chemins ``dirigés'' : http://www-lipn.univ-paris13.fr/~banderier/Papers/tcs.ps Pour l'aire, cette méthode s'avère encore l'approche clef, non seulement pour l'énumération, mais surtout pour l'asymptotique. Couplée à l'analyse de singularité, elle nous permet en effet d'obtenir un développement asymptotique (à n'importe quel ordre) pour l'aire moyenne. Nous donnons des formules explicites pour l'im\-por\-tan\-te classe des chemins de ``{\L}ukasiewicz'' (juste -1 comme saut négatif, ce qui corres\-pond à la bijection classique entre arbre d'arité fixée et chemins aléatoires). Bien sûr, la ``dérive'' de la marche joue un rôle, et je vous laisse parier sur l'aire moyenne d'une marche à dérive négative, frustrée par la barrière y=0 (un méandre brownien réfléchi à dérive négative, donc on conditionne sur une probabilité nulle)~: aire en O(n^2), O(n^{3/2}), O(n), O(\sqrt n), O(1), \dots ?

Cet exposé concerne la compression sans perte de données d'un texte dont les symboles sont les entiers naturels et suivent une loi de distribution géométrique pour un paramètre q donné. Les codes préfixes optimaux pour cette classe de distributions sont nommés codes de Golomb et sont très utilisés en pratique. Dans le but d'améliorer le codage on peut considérer un code portant sur des blocs de symboles. On traitera le cas des blocs de deux symboles qui mène à des codes préfixes optimaux aux propriétés intéressantes.

Typiquement, les problèmes concernant la sortie d'une marche aléatoire bidimensionnelle d'un polyèdre n'admettent pas des solutions analytiques. On peut obtenir une certaine équation qui lie la transformée de Laplace bidimensionelle à ses restrictions sur les bords du domaine, mais on n'est pas capable en général d'obtenir sa solution; typiquement, seulement des approximations des grandes déviations logarithmiques (non-précises) sont disponibles. Nous obtenons ici un résultat exact pour la probabilité de ruine éventuelle dans le cas des sauts exponentiels, ainsi que des approximations des grandes déviations précises pour les cas des sauts de Cramer, pour un modèle multidimensionnel motivé par la réassurance. Nous supposons que deux ou plusieurs compagnies partagent les primes et les montants Z_i qu'elles paient pour chaque sinistre en proportions données p=(p_1,p_2) et \delta=( \delta_1, \delta_2) avec \delta_1+ \delta_2=1. Le résultat est un processus de Lévy bi-dimensionnel X_i(t):=p_i t+x_i-\delta_i S(t), i=1, 2 où le processus de Poisson composé S(t)= Z_1+\cdots+Z_{N(t)} représente le montant cumulé des sinistres, Z_i sont des variables aléatoires { i.i.d.} ( "les sinistres"), N_t est un processus de comptage de Poisson indépendant de Z_i, et x_i, p_i sont les réserves initiales et les taux de prime. Ce processus est dégénéré, dans le sens où il change seulement le long des directions p, \delta, et il s'avère que ses probabilités de ruine peuvent être exprimées comme fonction des probabilités de ruine de ses coordonnées.

La clusterisation des solutions dans certains problèmes de satisfaction de contraintes est prédite par les méthodes physiques comme celle de la cavité. Intuitivement, cette clusterisation correspond à la naissance de groupes de solutions proches les unes des autres, chaque groupe étant loin des autres. Cependant, d'un point de vue mathématique, la définition de la clusterisation n'est pas encore énoncé de manière satisfaisante. Un premier niveau, fort, de clusterisation, a été démontré par Cocco, Dubois et Monasson pour le problème 3-XORSAT. Nous montrons que cette clusterisation n'apparaît pas dans le problème 2-SAT. Nous montrons également qu'avant la moitié du seuil de satisfaisabilité, même une clusterisation de niveau plus faible ne peut avoir lieu. Cette notion de clusterisation faible est liée à la vitesse de convergence dans une dynamique de type recuit simulé.

Le problème considère ici est d'estimer le nombre d'éléments distincts n, ou cardinalité, de très grands multi-ensembles de taille N. Les algorithmes de comptage exact utilisent une mémoire en O(n) et ont un temps d'exécution en O(N \log n). Or notre motivation pour ce problème vient de l'analyse de très grandes bases de données ou du trafic internet. Dans ces domaines le volume gigantesque des données considérées rend impossible l'emploi d'algorithmes avec une mémoire linéaire. Les liens des réseaux internet ``backbone'', comme OC-192 des réseaux SONET, peuvent avoir une capacité de 10 Gbps. Les seuls algorithmes qui peuvent être utiles doivent avoir une mémoire constante et ne faire qu'une passe sur les données. L'idée principale est de transformer le problème en un problème probabiliste. Il ne s'agit plus de chercher le nombre exact de mots distincts, mais une estimée de ce nombre avec une précision donnée. On introduit ici plusieurs classes d'algorithmes pour répondre a ce problème. Elles atteignent une erreur standard de 1/\sqrt M en utilisant M unités de mémoire.