Philippe Flajolet (INRIA Rocquencourt)

Quelques mots, des arbres et des cartes planaires me permettront d’illustrer le lien entre énumeration, codage compact et géneration aléatoire uniforme. Après avoir defini les cartes combinatoires (ou plongements de graphes dans le plan) et en particulier les triangulations et autres graphes de polyedres convexes, je presenterai deux algorithmes pour construire des triangulations aléatoires. * Le premier algorithme repose sur une construction élémentaire de certaines cartes, à partir de mots et d’arbres “conjugués”. On illustrera ainsi l’approche bijective : des objets comptes par une jolie formule doivent (devraient ?) être simples à construire. * Le second algorithme, l’extraction- rejet, est probabiliste et utilise quelques notions de théorie des graphes (composantes k-connexes). Cependant l’analyse de sa complexite se ramène à l’analyse de la distribution d’un paramètre dans un nouveau schéma de composition de séries génératrices. Ce sera l’occasion d’entrevoir une analyse de cols coalescents et la fonction d’Airy, chère a Ph. Flajolet. Enfin, sur l’exemple du diamètre des polyedres convexes, je montrerai comment ces algorithmes permettent de conjecturer des propriétés statistiques. (Voir aussi sur ma page, le résume étendu Random Sampling of Large Planar Maps and Convex Polyhedra STOC’99, Atlanta.)

Une nouvelle célèbre de Jorge-Luis Borges décrit la bibliothèque de Babylone, si incroyablement grande qu’elle contient les oeuvres de Shakespeare dans l’ordre et a l’envers, son propre catalogue et de multiples versions légèrement fausses de son catalogue, etc. Par ailleurs, des numérologues observent que la suite 314159 apparaît en position 176451 dans le développement décimal du nombre pi.

Une classe d’objets combinatoire sera dite “vérifiant le théorème de Borges” (mots, arbres, graphes, permutations, etc) si toute famille finie de motifs apparaît avec probabilité tendant vers 1 dans un objet de grande taille. Les nombres réels, les mots, les arbres binaires de recherche, les arbres digitaux, par exemple satisfont a diverses versions quantifiables du théorème de Borges. Les méthodes de preuve sont du ressort de la combinatoire analytique.

Dans cet expose correspondant à des travaux inachevés, on tentera de montrer l’intérêt de ces phénomènes dans des contextes informatiques variés:

  • analyse statistique de séquences biologiques,
  • partage de sous-expressions en calcul formel,
  • pagination d’index pour de grands volumes de données,
  • représentation compacte de dictionnaires,
  • compression de données,
  • diagrammes de décision binaires lies a la complexité des fonctions booléennes.

De nombreux problèmes ouverts subsistent …