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.

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).

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].

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...

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.