Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 4 Mars 2003

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

par Philippe Flajolet (INRIA, Rocquencourt)

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

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr