Génération aléatoire de structures combinatoires par principes de Boltzmann

Cet exposé décrit une approche très simple à la génération aléatoire de configurations combinatoires tels les mots, arbres, permutations, et graphes de divers types.

Cette approche est fondée sur les modèles de Boltzmann connus par ailleurs en thermodynamique et utilisés dans diverses méthodes d’optimisation tant heuristiques que rigoureuses. L’idée consiste ici à effectuer la génération aléatoire selon une mesure répartie sur toute une classe combinatoire et définie au moyen de ``poids exponentiels’’, à ajuster le paramètre du modèle, puis à filtrer le résultat selon des critères de taille. Les algorithmes résultants opérent en général en temps subquadratique, voire linéaire. Ils peuvent être implantés aisément, analysés mathématiquement avec une grande précision, et s’avèrent souvent compétitifs en pratique. (Travail en commun avec P. Duchon, G. Louchard, G. Schaeffer, 2003; texte disponible sous http://algo.inria.fr/flajolet/Publications/)