9h15-9h30
Introduction par Philippe Flajolet
9h30-10h45
Philippe
Duchon,
Labri, Université de Bordeaux
I
Cours: Chaînes de Markov et génération
aléatoire
11h15-12h30
Michel
Bauer,
SPhT, CEA Saclay
Cours: Quelques modèles combinatoires et analytiques de la
physique
15h30-16h30
Mireille
Bousquet-Melou,
CNRS, LaBRI, Univ. Bordeaux I
Séries rationnelles et algébriques en combinatoire
énumérative
Soit A une classe d'objets
munis d'une taille entière telle que
pour tout n le nombre a_n d'objets de taille n est fini.
On s'intéresse aux cas où la série
génératrice \sum_n a_n t^n est
rationnelle, ou plus généralement algébrique. Ces
propriétés présentent un intérêt
pratique, car on sait en général
dire beaucoup de choses sur les nombres a_n, mais aussi un
intérêt
plus spécifiquement combinatoire : la nature rationnelle ou
algébrique
de la série suggère que les objets possèdent une
structure (peut-être
bien cachée) semblable, en gros, à la structure
linéaire des mots dans le cas
rationnel, et à la structure branchante des arbres dans le cas
algébrique. En termes plus informatiques, les objets
comptés par une
série rationnelle seraient apparentés aux mots de
langages éguliers,
tandis que les objets comptés par des séries
algébriques seraient
apparentés aux mots des langages algébriques
(non-ambigus).
On discutera cette intuition combinatoire, en l'illustrant par des
exemples. L'impression finale devrait être que, si cette
intuition
paraît satisfaisante dans le cas rationnel, elle est probablement
incomplète dans le cas algébrique.
17h00-17h30
Elahe Zohoorianazad,
Institut Elie Cartan,
Université Henri Poincaré
Asymptotique du déplacement total dans un modèle de
parking avec la stratégie de marche aléatoire
Considérons n-1 voitures
et n places disponibles. Nous allons étudier un modèle de
parking où chaque voiture, a son arrivée, choisit de
manière aléatoire, uniformément, une
place où se garer. Si la place choisie est occupée, la
voiture se déplace suivant une
marche aléatoire symétrique jusqu'à ce qu'elle
trouve une place vide. Dans ce travail nous
étudions le comportement asymptotique du déplacement
total des n-1 voitures. Notre étude
fait apparaître certains processus de Marcus-Lushnikov
apparaissant déjà dans l'étude des
algorithmes Union-Find par Knuth \& Schonhage (1987), Chassaing
\& Marchand (2004).
17h30-18h00
Carine Pivoteau,
ALGO, INRIA-Rocquencourt
Génération aléatoire sous modèle de
Boltzmann : le cas non étiqueté
On s'intéresse à
la génération aléatoire d'objets appartenant
à des classes combinatoires
non étiquetées spécifiables à partir de
constructions telles que l'union, le produit, la
séquence, l'ensemble, le multi-ensemble et le cycle. Dans le
modèle de Boltzmann, on
relâche légèrement la contrainte sur la taille des
objets que l'on engendre tout en
gardant une distribution uniforme sur les objets de même taille.
Nous proposons, pour
chacune des constructions évoquées, un
générateur conforme à ce modèle. Des
réglages
appropriés permettent, le plus souvent, d'obtenir des
algorithmes qui opèrent en temps
linéaire en moyenne. [Travail en commun avec Philippe Flajolet
et Eric Fusy].
18h15-18h45
Éric Fusy,
ALGO, INRIA-Rocquencourt
Pointage et génération de Boltzmann sous le modèle
de Polya
Les opérateurs de Polya
constituent une extension intéressante des séries
génératrices
car ils permettent d'encoder les automorphismes (symétries) des
objets d'une classe
combinatoire non étiquetée. La présence de
symétries implique que le pointage des objets
est "biaisé". Par exemple, un arbre donnera naissance à
peu d'arbres enracinés différents
s'il a beaucoup de symétries. Nous définissons dans cet
exposé un opérateur de pointage
non biaisé : au lieu de pointer un atome de l'objet, on
s'autorise à pointer un cycle
d'atomes induisant une symétrie de l'objet. Avec cet
opérateur, chaque objet de taille n
donne naissance à exactement n objets pointés. On peut
ensuite combiner notre opérateur de
pointage non biaisé avec les générateurs de
Boltzmann, développés cette fois dans le cadre
des opérateurs de Polya. On obtient ainsi un
procédé permettant d'engendrer en temps
linéaire de nombreuses structures non étiquetées:
arbres, graphes outerplanaires...
18h45-19h15
Charles Bordenave,
INRIA-Rocquencourt/TREC-ENS
Navigation sur un processus ponctuel de Poisson
Sur un ensemble de points
localement fini, une navigation construit itérativement un
chemin sur cet ensemble qui relie un point à un autre.
L'ensemble des chemins aboutissant
à un point donné définit un arbre : l'arbre de
navigation. Dans cette présentation, on
analysera les propriétés de l'arbre de navigation lorsque
l'ensemble de points est un
processus ponctuel de Poisson sur \R^d. On examinera la distribution de
fonctionnelles
stables et la convergence faible locale de l'arbre de navigation. On
s'intéressera
également à des propriétés plus globales
comme la moyenne asymptotique d'une fonctionnelle
le long d'un chemin, la forme de l'arbre de navigation et ses fins
topologiques. On
illustrera notre travail sur l'arbre couvrant radial et sur les graphes
de type "small
world". Nous y établissons de nouveaux résultats.