Journées ALÉA 2012

Emploi du temps Prévisionnel

Lundi 5 MarsMardi 6 MarsMercredi 7 MarsJeudi 8 MarsVendredi 9 Mars
9h
Fermer [x]
Lundi 05 Mars 9hpar Les responsables du GT Alea,
Rôle et histoire des journées ALEA, grandes thématiques scientifiques ...
9h
Calcul Formel pour la combinatoire II
Fermer [x]
Mardi 06 mars 09:00par Alin Bostan et Bruno Salvy, INRIA, Rocquencourt
Le calcul formel étudie la manipulation informatique d'objets mathématiques exacts. Dans ce cours, les objets mathématiques de prédilection seront les fonctions génératrices d'énumération en combinatoire. Le point de vue promu sera l'utilisation d'approximations à grande précision (séries formelles tronquées) comme structure de données intermédiaire pour représenter des objets exacts (fonctions génératrices). Nous présenterons les principaux outils permettant de passer d'équations, sommes ou intégrales à de bonnes approximations (des centaines, voire des milliers, de coefficients), principalement grâce à l'itération de Newton symbolique. À l'inverse, à partir d'approximations, nous expliquerons comment reconstruire des équations qu'elles résolvent de manière approchée ou des ``formules exactes'' qu'elles approchent. L'outil de base est l'approximation de Padé et de Padé-Hermite. Les approximations à grande précision sont souvent suffisantes pour que les expressions reconstruites soient exactes. Nous exposerons pour conclure des algorithmes permettant de prouver des identités entre séries hypergéométriques ou plus généralement D-finies. Au delà de la présentation des outils algorithmiques théoriques, le cours mettra l'accent sur leur pratique, et c'est pourquoi il se déroulera en partie sur machine.
9h
Pseudo-aléa: objets et génération I
Fermer [x]
Mercredi 07 marspar David XiaoCNRS, LIAFA
Pseudo-aléa: objets et génération
RESUME
9h
Pseudo-aléa: objets et génération II
Fermer [x]
Jeudi 08 marspar David XiaoCNRS, LIAFA
Pseudo-aléa: objets et génération
RESUME
 
 
9h15
Calcul Formel pour la combinatoire I
Fermer [x]
Lundi 05 mars 09:15par Alin Bostan et Bruno Salvy, INRIA, Rocquencourt
Calcul Formel pour la combinatoire
Le calcul formel étudie la manipulation informatique d'objets mathématiques exacts. Dans ce cours, les objets mathématiques de prédilection seront les fonctions génératrices d'énumération en combinatoire. Le point de vue promu sera l'utilisation d'approximations à grande précision (séries formelles tronquées) comme structure de données intermédiaire pour représenter des objets exacts (fonctions génératrices). Nous présenterons les principaux outils permettant de passer d'équations, sommes ou intégrales à de bonnes approximations (des centaines, voire des milliers, de coefficients), principalement grâce à l'itération de Newton symbolique. À l'inverse, à partir d'approximations, nous expliquerons comment reconstruire des équations qu'elles résolvent de manière approchée ou des ``formules exactes'' qu'elles approchent. L'outil de base est l'approximation de Padé et de Padé-Hermite. Les approximations à grande précision sont souvent suffisantes pour que les expressions reconstruites soient exactes. Nous exposerons pour conclure des algorithmes permettant de prouver des identités entre séries hypergéométriques ou plus généralement D-finies. Au delà de la présentation des outils algorithmiques théoriques, le cours mettra l'accent sur leur pratique, et c'est pourquoi il se déroulera en partie sur machine.
 
 
 
9h15
Hauteur maximale de ponts Browniens et d'excursions Browniennes conditionnés à ne pas se croiser
Fermer [x]
Vendredi 09 mars 09:15par Gregory SchehrCNRS-Univ. Paris XI
Hauteur maximale de ponts Browniens et d'excursions Browniennes conditionnés à ne pas se croiser
Les marcheurs Browniens conditionnés à ne pas se croiser ont suscité beaucoup d'intérêt ces dernières années, tant en mathématique (pour leurs aspects probabilistes et combinatoires) qu'en physique (comme des modèles de polymères ou de transition de mouillage ou de fusion). Dans cet exposé je présenterai un calcul exact de la distribution de la hauteur maximale d'une collection de N ponts Browniens (appelés 'watermelons without wall') et de N excursions Browniennes (appelées 'watermelons with a wall') conditionnés à ne pas se croiser. Je montrerai que dans la limite asymptotique où N tend vers l'infini cette distribution converge vers la distribution de Tracy-Widom qui décrit les fluctuations de la plus grande valeur propre de matrices aléatoires de l'ensemble gaussien orthogonal (GOE pour 'Gaussian Orthogonal Ensemble'). Je discuterai enfin une application de ces résultats asymptotiques à des modèles de croissance stochastique.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
10h15
 
Comment calculer 3000 termes d'une marche dans le quart de plan
Fermer [x]
Mardi 06 mars 10:15par Stephen Melczer , INRIA Rocquencourt
Comment calculer 3000 termes d'une marche dans le quart de plan
Les marches à pas unitaires dans le quart de plan peuvent être classées en deux familles, selon les propriétés de leur série génératrice : les séries de la première famille vérifient des équations différentielles à coefficients polynomiaux, celles de la seconde famille ne vérifient aucune équation de ce type. Bostan et Kauers ont utilisé des méthodes de calcul formel afin de "deviner" des équations différentielles pour les marches appartenant à la première famille, et ont exploité ces équations pour déduire des résultats asymptotiques. L'étape la plus coûteuse de cette approche de type "deviner-pour-régner" est le calcul des premiers termes d'une suite énumérant des marches. Dans cet exposé, nous présenterons des procédures efficaces permettant d'engendrer un grand nombre de termes d'une telle suite. Ces améliorations comprennent le passage à une méthode modulaire et l'utilisation de structures de données efficaces.
10h15
Tableaux escaliers et Tree-like tableaux
Fermer [x]
Mercredi 07 mars 10:15par Sandrine Dasse-Hartaut, LIAFA
Tableaux escaliers et Tree-like tableaux
Les tableaux escaliers ont été créés par S. Corteel et L. Williams. Une première approche consistait à les générer récursivement par ajouts de colonnes. Le lien existant entre tableaux escaliers et Tree-like tableaux a permis de comprendre une nouvelle manière de générer les tableaux récursivement, plus simple.
 
Une construction combinatoire d'ensembles régénératifs
Fermer [x]
Jeudi 08 mars 10:15par Philippe Marchal , CNRS - Paris 13
Une construction combinatoire d'ensembles régénératifs
Un ensemble régénératif est un sous ensemble de R+ tel que si on regarde R à droite de t (t réél), on voit un ensemble qui a même loi que R. Nous donnons une construction combinatoire de tels ensembles, indexés par les fonctions mesurables de [0,1] dans [0,1], et qui ont des propriétés d'emboitement.
10h15
Asymptotique de certains nombres de marches confinées dans un quart de plan
Fermer [x]
Vendredi 09 mars 10:15par Kilian Raschel, CNRS et Université de Tours
Asymptotique de certains nombres de marches confinées dans un quart de plan
L'énumération des marches à petits sauts confinées dans un quart de plan est maintenant un sujet classique en combinatoire. Des quantité particulièrement importantes sont les nombres de chemins partant de l'origine, ayant une longueur fixée, et arrivant en des points particuliers (par exemple l'origine, ou bien un des axes, ou encore n'importe où). Si des expressions pour ces nombres de chemins sont disponibles dans la littérature récente (via la connaissance de leur série génératrice), très peu de résultats existent sur leur asymptotique, lorsque la longueur tend vers l'infini. L'objet de cet exposé est précisément de présenter une méthode permettant de trouver l'asymptotique de ces nombres de chemins. Il s'agit d'un travail en commun avec Guy Fayolle.
10h30
Urnes de Polya équilibrées
Fermer [x]
Lundi 05 mars 10:30par Basile Morcrette, Univ. Paris 6, Inria Rocquencourt
Urnes de Polya équilibrées
Parmi toutes les urnes de Polya équilibrées, on cherche à démasquer celles qui ont une série génératrice algébrique. Pour cette investigation, les méthodes automatiques de Guess'n'Prove ont mis en lumière de nombreux exemples témoins. On peut a posteriori les classifier grâce à des conditions arithmétiques sur les coefficients des règles de l'urne. Cela conduit à des preuves élémentaires d'algébricité et à une description précise des polynômes annulateurs. Il s'agit d'un travail en cours avec A. Bostan, F. Chyzak et Ph. Dumas.
 
 
 
 
 
 
 
 
 
 
 
 
 
10h45
Chemins de Dyck généralisés
Fermer [x]
Vendredi 09 mars 10:45par Axel Bacher, École polytechnique
Chemins de Dyck généralisés
Un chemin de Dyck généralisé (ou excursion discrète) est un chemin unidimensionnel faisant des pas dans un ensemble fini S donné, qui commence et termine à hauteur 0, et qui reste à une hauteur positive. Bousquet-Mélou a montré que la série génératrice Ek des excursions de hauteur au plus k est de la forme Fk/Fk+1, où les Fk sont des polynômes obéissant à une relation de récurrence linéaire. Nous donnons une interprétation combinatoire aux polynômes Fk et à leur relation de récurrence en utilisant une méthode par matrice de transfert (ou automate fini). Nous étendons notre méthode aux méandres discrets (chemins qui commencent en 0, restent à une hauteur positive, mais peuvent finir n'importe où). Enfin, nous étudions le cas particulier où l'ensemble S est symétrique et nous montrons que plusieurs simplifications se produisent.
 
 
 
 
 
 
11h00
Construction de peignes, mélange de peignes et marches aléatoires
Fermer [x]
Jeudi 08 mars 11:00par Peggy Cénac-Guesdon, Institut de Mathématiques de Bourgogne
Construction de peignes, mélange de peignes et marches aléatoires
Les séquences aléatoires de lettres peuvent être vues comme des chaînes au sens probabiliste ou comme des sources au sens de la théorie de l’information. La manière dont les mots sont produits a une grande influence sur le comportement probabiliste des algorithmes ou des principales structures de données associées (arbre binaire de recherche, arbre digital, arbre des suffixes, pour la compression). Les chaînes de Markov à mémoire de longueur variable (en anglais VLMC) constituent une classe de sources probabilistes, suffisamment générale pour pouvoir représenter des sources diverses, et unifier le traitement de sources naturelles (sources sans mémoire et chaînes de Markov), suffisamment structurée pour pouvoir être précisément étudiée. Il sera question dans cet exposé d'une construction explicite d'une VLMC en tant que source dynamique, puis d'existence et de convergence vers la mesure stationnaire pour des exemples, dont le "peigne". Nous verrons ensuite que le peigne peut plus ou moins bien mélanger et être à l'origine de la construction d'arbres de suffixes dont les paramètres ne convergent pas à vitesse logarithmique. Enfin, nous regarderons quelques propriétés de marches aléatoires construites à partir du peigne.
 
11h15
Probabilités libres
Fermer [x]
Lundi 05 mars 11:15par Philippe Biane, Université Paris-Est
Probabilités libres
Les probabilités libres permettent de modéliser le comportement des matrices aléatoires de grandes tailles, en particulier leurs propriétés spectrales. J'expliquerai les bases de la théorie et de ses applications aux matrices aléatoires, ainsi que les outils combinatoires qui ont été développés à cet effet.
 
Probabilités libres
Fermer [x]
Mardi 06 mars 11:15par Philippe Biane, Université Paris-Est
Probabilités libres
Les probabilités libres permettent de modéliser le comportement des matrices aléatoires de grandes tailles, en particulier leurs propriétés spectrales. J'expliquerai les bases de la théorie et de ses applications aux matrices aléatoires, ainsi que les outils combinatoires qui ont été développés à cet effet.
11h15
Enumération et génération aléatoire d'exécutions concurrentes.
Fermer [x]
Mercredi 07 mars 11:15par Antoine Génitrini, LPMA-UPMC
Enumération et génération aléatoire d'exécutions concurrentes.
Une partie fondamentale en théorie de la concurrence repose sur l'opérateur d'entrelacement de processus. Le principe de base est tel que deux processus s'exécutant en parallèle, noté P ||| Q, peut être obtenu en mélangeant leurs exécutions. L'opérateur d'entrelacement satisfait a.P' ||| b.Q' = a.(P' ||| b.Q') + b.(a.P' ||| Q') où l'opérateur + est un opérateur de branchement. Le but de notre étude est l'obtention de l'arbre résultant de l'entrelacement de grands processus typiques. L'explosion combinatoire entre la taille des processus et son arbre d'entrelacement est connue, mais à travers cet exposé nous allons présenter de manière bien plus fine les mesures et formes moyennes de l'arbre typique d'entrelacements de grands processus. Cette étude nous permettra d'ailleurs de quantifier le taux de partage des branches de cet arbre moyen. Nous terminerons la présentation avec la présentation de deux algorithmes efficaces permettant pour l'un de compter le nombre d'exécutions différentes induites par l'entrelacement des processus et pour l'autre d'en tirer une uniformément au hasard.
 
 
 
 
 
 
 
 
 
 
 
 
Arbres généraux pour la représentation de fonctions booléennes aléatoires.
Fermer [x]
Mercredi 07 mars 11:45par Cécile Mailler, Univ. de Versailles-St-Quentin
Arbres généraux pour la représentation de fonctions booléennes aléatoires.
Une expression logique représentant une fonction booléenne peut être représentée par un arbre dont les n{\oe}uds internes sont étiquetés par un connecteur et les feuilles par un littéral. En choisissant la manière d'étiqueter (i.e. le système logique), la structure d'arbres (planaire ou non, binaire ou d'arité quelconque, équilibré ou non) ainsi que sa distribution (uniforme suivant la taille, processus de Galton-Watson), on induit une distribution différente sur les fonctions booléennes. Dans cet exposé, je présenterai les résultats principaux, ainsi que les idées clé sous-jacentes, de travaux réalisés en collaboration avec A. Genitrini, B. Gittenberger et V. Kraus. Ces travaux se concentrent sur des distributions uniformes selon la taille, mais explorent différentes structures d'arbres (non-planaires et/ou non-binaires), ainsi que deux systèmes logiques distincts (et/ou et implication). Enfin, je soulèverai des interrogations sur les différentes notions de taille d'un arbre (notamment dans le cas d'arbres non-binaires) et donc sur les différentes notions de complexité d'une fonction booléenne. J'introduirai un nouveau modèle, à l'étude actuellement, fondamentalement différent des autres et dont les premiers résultats laissent envisager un comportement distinct de la distribution induite sur les fonctions booléennes.
 
11h45
Classification de la densité sur des graphes infinis
Fermer [x]
vendredi 09 mars 11:45par Irène Marcovici, Univ. Paris 7
Classification de la densité sur des graphes infinis
Un automate cellulaire (AC) est un réseau régulier de cellules, chacune contenant un état (simplement 0 ou 1 en général). Les contenus de toutes les cellules évoluent de manière synchrone, en fonction des états d'un nombre fini de leurs voisines. Le problème de "classification de la densité" consiste à chercher un AC capable de déterminer si une configuration initiale définie sur un anneau contient une majorité de 0 ou de 1. Nous nous intéressons ici à l'extension de ce problème à un réseau infini. Chaque cellule est initialisée indépendamment à l'état 1 avec probabilité p ou à l'état 0 avec probabilité 1-p, et la question est alors de construire un AC qui converge vers la configuration "tout 0" lorsque p< 1/2, et vers la configuration "tout 1" quand p> 1/2 (synchronisation de toutes les cellules sur l'état majoritaire). On dira qu'un tel AC classifie la densité. Nous montrons que sur la grille Z2, l'AC de Toom (règle majorité sur le voisinage nord-est-centre) classifie la densité. Sur les arbres homogènes de degré supérieur ou égal à 3, nous savons aussi exhiber des AC qui classifient la densité. Sur Z, il existe des AC et des ACP (automates cellulaires probabilistes) candidats, mais la question reste ouverte. Travail en collaboration avec Ana Busic, Nazim Fatès et Jean Mairesse.
 
 
 
12h00
Loi limite des grands arbres m-aires de recherche et équations de point fixe
Fermer [x]
Jeudi 08 mars 12:00par Brigitte Chauvin, Univ. Versailles Saint Quentin
Loi limite des grands arbres m-aires de recherche et équations de point fixe
Pour m>26, l'asymptotique du vecteur composition d'un arbre m-aire de recherche fait apparaî tre au second ordre une variable aléatoire à valeurs complexes WDT. Lorsqu'on plonge en temps continu, le processus de branchement multitype obtenu a également un second terme asymptotique en WCT, une (autre) variable aléatoire à valeurs complexes. Chacune de ces variables aléatoires est solution d'une équation de point fixe en distribution. Dans cet exposé, on rappellera les résultats obtenus par la méthode de contraction puis on se concentrera sur l'existence d'une densité pour WDT et WCT et sur leur support, qui s'avère être tout le plan complexe. En outre ces variables admettent des moments exponentiels. Les méthodes utilisées sont de l'analyse fine des transformées de Fourier et la mise en évidence de martingales ``cascades'' de Mandelbrot.
 
 
 
12h15
Etude d'une marche aléatoire sur un arbre muni de résistances aléatoires
Fermer [x]
Mercredi 07 mars 12:15par Efdoevi Koudou, Institut Elie Cartan, Nancy
Etude d'une marche aléatoire sur un arbre muni de résistances aléatoires
Ce travail en cours étudie une marche particulière en milieu aléatoire. Le milieu est un arbre déterministe constituant un réseau électrique dont les résistances sont aléatoires et suivent des lois gaussiennes inverses pour les sommets internes et des lois gaussiennes inverses réciproques pour les sommets externes. Les paramètres sont choisis de sorte que la résistance équivalente du réseau (au sens des lois d'Ohm-Kirchoff) suive une loi gaussienne inverse réciproque. La marche aléatoire considérée ici est celle que l'on peut naturellement définir sur tout réseau électrique selon le livre de Doyle et Snell Random walks and Electrical networks. Nous nous intéressons notamment à la probabilité qu'une particule, partant de la racine de l'arbre, atteigne une feuille avant de revenir à la racine.
 
12h15
Comportement asymptotique d'un automate cellulaire simple : utilisation de l'invariance d'echelle
Fermer [x]
Vendredi 09 mars 12:15par Benjamin Hellouin,
Comportement asymptotique d'un automate cellulaire simple : utilisation de l'invariance d'echelle
On considère un automate cellulaire simple représentant deux particules de vitesses différentes qui s'annihilent quand elles se rencontrent. En traçant un parallèle entre le comportement de cet automate sur une configuration initiale aléatoire et celui d'une certaine marche aléatoire, l'approximation par un mouvement brownien permet d'obtenir des informations sur son comportement asymptotique. En utilisant cette approche, nous pouvons calculer des temps d'entrée asymptotiques, généralisant un résultat de Kurka et al., et une approximation plus fine permet de donner des bornes polynomiales sur la densité de particules et la vitesse de convergence vers la mesure limite.
12h30
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
15h00
Techniques probabilistes et combinatoires pour l'analyse des flux de données.
Fermer [x]
Lundi 05 mars 15:00par Conrado Martinez, UNIV. POLITECNICA CATALUNYA
Techniques probabilistes et combinatoires pour l'analyse des flux de données
Il y a près de 30 ans, Philippe Flajolet, dans un de ses papiers les plus cités, a montré que l'on pouvait concevoir des algorithmes pour estimer extrêmement précisément le nombre d'éléments différents dans un multi-ensemble, en utilisant peu de mémoire auxiliaire, en un seul passage sur les données et avec une simplicité et une élégance extraordinaires. C'est un cas particulier, mais assez important, de ce que l'on appelle "streaming analysis". Mais pour que les algorithmes d'estimation fonctionnent, on a besoin d'une analyse très précise de ses propriétés probabilistes : il faut trouver des paramètres qui sont au coeur de ce type d'algorithmes, et c'est l'analyse qui les fournit. À la suite de ce travail, beaucoup de chercheurs, Philippe lui-même avec autres coauteurs, ont proposé de nouveaux algorithmes et ont étudié leurs performances. Les outils mathématiques (combinatoire, proba, ...) qu'il faut mettre en jeu sont très intéressants et nous trouvons dans ce domaine des défis mathématiques et informatiques très attrayants. Sans doute, le domaine des algorithmes de streaming est l'un des meilleurs exemples d'interaction parfaite entre mathématiques et informatique.
 
Comportement transitoire des processus d'Ehrenfest et d'Engset.
Fermer [x]
Mardi 06 mars 15:00par Mathieu Feuillet, Inria Rocquencourt
Comportement transitoire des processus d'Ehrenfest et d'Engset.
Nous considérons deux processus stochastiques classiques : les urnes d'Ehrenfest, introduites en 1907 pour la théorie cinétique des gaz pour décrire les échanges de chaleur entre deux corps et le modèle d'Engset introduit en 1918 et qui est, avec le modèle d'Erlang, un des tous premiers modèles stochastiques de réseaux de communication. Nous proposons d'étudier le comportement asymptotique de la distribution des temps d'atteinte de ces deux processus lorsque le nombre de particules ou d'utilisateurs croît vers l'infini. En particulier, nous obtenons des résultats sur les temps d'atteinte de frontière. Cette étude repose sur des techniques de martingales et notamment sur une famille de martingales positives qui est l'équivalent pour le processus d'Ehrenfest des martingales exponentielles utilisées pour l'étude des marches aléatoires et du mouvement brownien.
 
 
 
Dynamique des vues ego-centrées de la topologie de l'internet : analyse et modélisation
Fermer [x]
Jeudi 08 mars 15:00par Clémence Magnien, CNRS
Dynamique des vues ego-centrées de la topologie de l'internet : analyse et modélisation
Dans de nombreux contextes, les objets étudiés peuvent être modélisés par des graphes, appelés graphes de terrain : topologie de l'internet, graphes du web, réseaux sociaux, réseaux biologiques, ... La plupart de ces graphes sont dynamiques, c'est-à-dire qu'ils évoluent au fil du temps par l'apparition et la disparition de nœuds et de liens. L'étude de cette dynamique soulève de nombreuses questions importantes. Je m'intéresserai dans cet exposé à un cas particulier : la topologie de l'internet (constituée de routeurs et de liens de communication au niveau IP). On peut capturer une partie de sa dynamique en s'intéressant à ce qu'une machine donnée peut voir de cette topologie, qu'on appelle vue ego-centrée, et en répétant périodiquement la mesure de ces vues ego-centrées. Je présenterai une analyse de la dynamique observée sur de telles mesures. On verra en particulier que ces vues ego-centrées évoluent à un rythme beaucoup plus élevé que ce à quoi on aurait pu s'attendre. On verra également que deux phénomènes jouent un rôle clé dans la dynamique observée : le load-balancing ou équilibrage de charge, et l'évolution du routage. Enfin, je présenterai des pistes pour la modélisation de la topologie de l'internet et sa dynamique. On verra que des approches basées sur des graphes aléatoires permettent de reproduire fidèlement les observations. Ces approches ont le double avantage de permettre d'expliquer les comportements observés, et de permettre, par une étude détaillée de l'impact des différents paramètres, d'espérer quantifier de manière rigoureuse la dynamique réelle de la topologie.
 
 
 
 
 
 
 
 
 
 
15h30
Comportement asymptotique de statistiques dans des permutations aléatoires
Fermer [x]
Mardi 06 mars 15:30par Valentin Féray, Université Bordeaux 1
Comportement asymptotique de statistiques dans des permutations aléatoires
L'objectif de cet exposé est de présenter une nouvelle méthode pour déterminer des lois limites dans des permutations aléatoires (uniformes). La méthode fonctionne pour de nombreuses statisques renormalisées: nombre d'excédences, d'adjacences, de motifs généralisés. Elle se base sur la méthode des moments et formalise l'intuition que les images de deux entiers différents sont "quasi-indépendantes".
 
 
 
 
 
15h45
Analyse de flux de données: tendances récentes et nouveaux défis pour ALEA.
Fermer [x]
Lundi 05 mars 15:45par Jérémie Lumbroso, INRIA Rocquencourt
Voir les grands flux de données comme des permutations aléatoires
L'exposé de Conrado Martínez présente un panorama de la richesse de l'algorithmique probabiliste développée pour le traitement quantitatif de grandes masses de données. Cette algorithmique repose essentiellement sur des observations probabilistes et pour les évolutions les plus récentes, d'algèbre et d'algèbre linéaire. Nous considérons un point de vue différent. Il s'avère que les flux de données peuvent être considérés comme des permutations aléatoires : ainsi, on peut concevoir et analyser ces algorithmes de manière complètement combinatoire, et notamment se baser sur des statistiques bien connues sur les permutations pour en déduire des estimateurs. C'est ce que nous illustrerons principalement au travers de RECORDINALITÉ, un estimateur du nombre d'éléments distincts qui se base sur le nombre de records observés dans une permutation, dont tout bon combinatoricien sait qu'il est de l'ordre de ln(n), où n est le nombre d'éléments de la permutation. Avec cette approche originale, nous espérons intéresser les nombreux combinatoriciens d'exception qui fréquentent les journées Aléa !
 
 
 
 
 
 
 
16h00
Énumération d'intervalles dans le treillis de Tamari.
Fermer [x]
Mardi 06 mars 16:00par Guillaume Chapuy, CNRS - Univ. Paris 7
Énumération d'intervalles dans le treillis de Tamari.
L'ensemble des arbres binaires de taille n est naturellement muni d'une structure d'ordre partiel, le "Treillis de Tamari". Lors de son exposé à l'IHP de Décembre 2010, François Bergeron a présenté (entre autres!) une conjecture pour le nombre d'intervalles "étiquetés" dans ce treillis. Les nombres en question sont particulièrement simples, et sont reliés aux nombres de fonctions de parking, et (conjecturalement) à la théorie des polynômes harmoniques diagonaux. Dans ce travail nous résolvons cette conjecture (y compris une généralisation aux arbres m-aires, plus difficile). Le gros du travail est la résolution d'une équation fonctionnelle "difféo-catalytique". J'essaierai d'expliquer pourquoi cette équation est intéressante (liens avec ce que l'on sait / ne sait pas faire, théorie des équations catalytiques standard), et comment nous l'avons résolue. La méthode s'adapte pour démontrer des conjectures plus générales de Bergeron et Préville-Ratelle, puisque l'on calcule explicitement le caractère de la "parking Tamari representation" de Sn, obtenue par action de Sn sur ces objets.
(Travail en commun avec Mireille Bousquet-Mélou et Louis-François Préville-Ratelle)
 
 
 
Epidemies sur des graphes aleatoires avec clustering
Fermer [x]
Jeudi 08 mars 16:00par Emilie Coupechoux, INRIA-ENS
Epidemies sur des graphes aleatoires avec clustering
Motives par l'analyse des reseaux sociaux, nous considerons un modele de graphe aleatoire dont la distribution des degres est fixee, et le clustering (probabilite pour que deux sommets soient connectes entre eux, sachant qu'ils ont un voisin commun) varie. Sur ce graphe aleatoire, nous etudions un processus de diffusion dont le modele provient de la theorie des jeux. Alors que des resultats ont deja ete obtenus pour des graphes aleatoires sans clustering, le but ici est de souligner l'impact du clustering sur la propagation du processus (plus precisement, nous etudions le nombre de sommets infectes a la fin de la propagation, lorsque l'epidemie part initialement d'un seul individu). Lorsque la distribution des degres suit une loi de puissance, l'impact du clustering sur ce type d'epidemie depend du degre moyen du graphe: a faible degre, le clustering limite la propagation, alors que le contraire se produit a fort degre.
 
 
16h15
L'Asymptotique des nombres de Stirling de deuxième espèce revisitée: une approche par la méthode du "point de Selle"
Fermer [x]
Lundi 05 mars 16:15par Guy Louchard, Université Libre de Bruxelles
L'Asymptotique des nombres de Stirling de deuxième espèce revisitée: une approche par la méthode du "point de Selle"
Utilisant la méthode du "point de Selle" et des développements en multiséries, nous obtenons, a partir de la fonction génératrice des nombres de Stirling de deuxième espèce S(n,j) et de l'intégrale de Cauchy, des résultats asymptotiques dans les régions centrale et non-centrale. Dans la région centrale, nous revisitons la célèbre approximation Gaussienne avec plus de précision. Dans la région j=n-n^α, α < 1/2, nous analysons la dépendance de S(n,j) en α.
 
 
 
 
 
 
16h30
 
 
Cartes planaires équipées d'une forêt couvrante
Fermer [x]
Mardi 06 mars 16:30par Julien Courtiel, Univ. Bordeaux I
Cartes planaires équipées d'une forêt couvrante
Dans un travail récent, Olivier Bernardi et Mireille Bousquet-Mélou ont prouvé que la série génératrice des cartes planaires pondérées par leur polynôme de Tutte (un polynôme bivarié qui généralise le polynôme chromatique) satisfait une équation différentielle algébrique (énorme).
Ce résultat repose sur une approche récursive, et la preuve est extrêmement lourde et technique. Il semble robuste, puisqu'il subsiste lorsqu'on remplace les cartes planaires générales par les triangulations.
On se concentre ici sur une spécialisation à une variable du polynôme de Tutte, qui compte les forêts couvrantes selon le nombre de composantes connexes.
Partant d'une construction de Bouttier, Di Francesco et Guitter (2007), nous établissons, de manière combinatoire, des équations fonctionnelles pour la série étudiée, dont découlent ensuite les équations différentielles cherchées. Cette approche s'applique à des familles variées de cartes..
Les équations fonctionnelles permettent de mener à bien l'étude asymptotique des séries obtenues, et d'analyser la nature des transitions de phase.
 
 
 
Calcul de la taille maximale d'un b-matching dans des graphes aléatoires par la méthode de la cavité.
Fermer [x]
Jeudi 08 mars 16:30par Matthieu Leconte, INRIA - Technicolor
Calcul de la taille maximale d'un b-matching dans des graphes aléatoires par la méthode de la cavité.
Motivés par une modélisation de réseau de distribution de contenus et par un problème d'orientation d'hypergraphes aléatoires, on s'intéresse au calcul de la taille maximale d'un b-matching dans une suite de graphes aléatoires qui convergent localement faiblement vers un arbre de Galton-Watson. On utilise un algorithme de message passing appelé Belief Propagation (BP) à température positive pour approximer la distribution marginale de cette quantité à chaque sommet du graphe. On établit d'une part des propriétés de convergence de l'algorithme utilisé et d'autre part on vérifie que le calcul effectué est asymptotiquement correct. Comme le graphe limite que l'on considère est un arbre de Galton-Watson, on obtient des équations récursives en distribution sur les messages de BP, ce qui conduit à une formule analytique pour la quantité recherchée.
 
 
 
 
 
 
 
 
 
 
17h00
L'algorithme d'Euclide est ''totalement'' gaussien,
Fermer [x]
Lundi 05 mars 17:00par Brigitte Vallée, Université de Caen
L'algorithme d'Euclide est ''totalement'' gaussien
Le calcul du pgcd peut être considéré comme la cinquième opération élémentaire. Son analyse probabiliste s'avère donc naturelle, utile, et pourtant non triviale. Je ferai une petite synthèse sur ce qui est désormais connu sur l'analyse de la complexité de cet algorithme, en mettant l'accent sur l'analyse en distribution, et en insistant sur les dernières nouveautés. Cet algorithme du pgcd peut être aussi vu comme la restriction aux nombres rationnels de l'algorithme des fractions continues, et il est naturel de se demander si ces deux algorithmes partagent beaucoup de propriétés probabilistes. Les données du monde ''discret'' se comportent-elles comme les données du monde ''continu'' ?
 
 
17h00
Modèles de surfaces aléatoires
Fermer [x]
Mercredi 07 mars 17:00par Gilles Schaeffer, Ecole Polytechnique Palaiseau
Modèles de surfaces aléatoires
Les cartes combinatoires permettent de décrire naturellement des surfaces aléatoires discrètes. En particulier la distribution uniforme sur les quadrangulations planaires formées par recollement de n quadrangles a été étudiée très en détail ces dernières années: loi de paramètres (degré max des sommets, diamètre) lorsque n tends l'infini, limite infinie discrète, limite d'échelle et carte Brownienne à la Le Gall et Miermont... Je m'intéresserai dans cet exposé à des définitions alternatives de surfaces aléatoires à base de cartes (décorées, étiquetées, coloriées ou pondérées) pour tenter de tracer une frontière entre celles qui ressemblent aux quadrangulations, et les autres.
 
 
 
 
 
 
 
 
 
 
 
 
17h30
Comportement asymtotique des modèles fluides stochastiques.
Fermer [x]
Lundi 05 mars 17:30par Hedi Nabli, Fac. des Sciences de Sfax
Comportement asymtotique des modèles fluides stochastiques.
Le modèle fluide stochastique est souvent utilisé dans les réseaux de communication à haut débit.
En réalité, l'information qui circule dans un réseau est toujours discrète, on parle de nombre de tâches à exécuter et non de quantité.
À l'échelle d'une rafale, l'information est supposée arriver selon un flux liquide avec des débits aléatoires.
Plus précisément, le débit d'entrée fluide est supposé être régi par un processus de Markov à espace d'états fini. Lorsque ce liquide dépasse la capacité du serveur, traitant cette information, il est stocké dans un buffer afin d'être servi ultérieurement..
On s'intéresse alors à la distribution de probabilité de la quantité du liquide dans le buffer en régime asymptotique. Les deux cas d'un buffer à capacité infinie et l'autre à capacité finie sont traités et analysés. Les deux méthodes proposées sont à la fois précises et numériquement stables. Un exemple de trafic vidéo MPEG sera modélisé et étudié.
 
Séance de TP
Fermer [x]
Mardi 06 mars 17:30par Alin Bostan et Bruno Salvy , INRIA Rocquencourt
Séance de TP
 
 
Recherche des noyaux d'un graphe aléatoire
Fermer [x]
Jeudi 08 mars 17:30par Jean-Marie Lebars, Université de Caen
Recherche des noyaux d'un graphe aléatoire
Le fait que le problème de décider si un graphe possède un noyau est NP-complet ne garantit pas qu'il est facile d'obtenir des distributions naturelles produisant des instances difficiles (les algorithmes connus sont de complexité exponentielle). Nous montrerons qu'il existe une connexion entre la complexité de trouver un noyau et les tailles possibles des noyaux. Cependant, la taille des noyaux d'un graphe de G(n,p) varie fortement selon la valeur de p. Nous verrons pourquoi le cas p = c/n fournit les instances les plus difficiles.
 
 
 
 
 
 
 
 
18h00
Exercice de TD
Fermer [x]
Lundi 05 mars 18:00par Philippe Biane , Université Paris-Est
Exercice de TD
Les probabilités libres permettent de modéliser le comportement des matrices aléatoires de grandes tailles, en particulier leurs propriétés spectrales. J'expliquerai les bases de la théorie et de ses applications aux matrices aléatoires, ainsi que les outils combinatoires qui ont été développés à cet effet.
 
18h00
Énumération de constellations et fractions multicontinues.
Fermer [x]
Mercredi 07 mars 18:00par Marie Albenque, Ecole Polytechnique
Énumération de constellations et fractions multicontinues.
Les constellations sont des cartes planaires dont les faces sont coloriées en noir ou blanc, de telle sorte que : - deux faces adjacentes sont de couleurs opposées - toute face noire a degré p - toute face blanche a un degré multiple de p (p étant un entier fixé ≥ 2). On s'intéresse ici à la « fonction à deux points » : série génératrice des constellations avec deux sommets marqués à distance fixée. Nous montrerons comment la fonction à deux points des constellations est naturellement encodée par une fraction multicontinue et comment on peut utiliser cette correspondance pour obtenir la fonction à deux points grâce à une généralisation des déterminants de Hankel. Travail en commun avec Jérémie Bouttier.
 
Fermer [x]
Jeudi 08 Mars 18:00par David Xiao, CNRS
Exercice de TD
RESUME
 
 
 
 
 
 
 
 
 
 
 
Distances en percolation et TASEP
Fermer [x]
Mercredi 07 mars 18:30par Lucas Gérin, Univ. Paris 10
Distances en percolation et TASEP
La percolation de paramètre p, c'est ce qui reste dans Z² quand on efface chaque arête indépendamment avec probabilité 1-p.
Quand p est proche de un, il y a une composante connexe infinie. Le TASEP, ce sont des voitures qui avancent de façon aléatoire sur une seule voie, sans se doubler et sans se rentrer dedans.
A priori, ça n'a rien à voir.
Le but de cet exposé est de montrer que des estimées sur le TASEP permettent d'obtenir des estimées sur certaines distances dans la composante infinie de percolation, quand p est très proche de un. (Travail avec A.-L. Basdevant et N. Enriquez).
 
 
 
 
 
 
 
 
 
19h
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
19h30
Repas
Fermer [x]
19:30par Les participants
Le repas
On y mange et on y boit
 
Repas
Fermer [x]
19:30par Les participants
Le repas
On y mange et on y boit
 
Repas
Fermer [x]
19:30par Les participants
Le repas
On y mange et on y boit
 
Bouillabaisse
Fermer [x]
19:30par Les participants
Le repas
On y mange et on y boit
 
Repas
Fermer [x]
19:30par Les participants
Le repas
On y mange et on y boit
 
 
 
 
 
21h00
 
 
GT ALEA : journées ALEA, projets ...
Fermer [x]
Mercredi 04 mars 18:30par Les participants
Comportement asymtotique des modèles fluides stochastiques.