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

Nous présentons un cadre nouveau à la génération aléatoire de configurations combinatoires fondé sur ce que nous appelons des modèles de Boltzmann. L'idée consiste à effectuer la génération aléatoire d'objets structurellement complexes de taille fixée en plaçant une distribution de probabilités appropriée sur l'ensemble d'une classe combinatoire infinie. Les algorithmes obtenus opèrent usuellement en temps moyen linéaire.

Ils peuvent être implantés aisément au sein d'un système de calcul formel, être analysés mathématiquement avec une grande précision, et, après réglages adéquats, se montrer très efficaces en pratique.

(Il s'agit d'un travail en cours avec P. Duchon, G. Louchard, G. Schaeffer.)