Abstract EN:

Dans le domaine de la combinatoire, la génération aléatoire d’objets est un problème central relié à de nombreux aspects de la science combinatoire, que ce soit à l’énumération exacte ou asymptotique, ou à la vérification de conjectures. De nombreuses méthodes ont été proposées afin de résoudre efficacement ce problème, dont le modèle de Boltzmann. Ce modèle, au prix d’un contrôle moindre sur la taille des objets générés, assure les propriétés de complexité linéaire dans beaucoup de cas réels, et de facilité d’automatisation pour de larges classes d’objets. Cette thèse vise à étendre encore les classes d’objets combinatoires sur lesquelles ce modèle de Boltzmann peut s’appliquer, tout en conservant les propriétés d’efficacité et d’automatisation. La première partie est une étude des algorithmes de générations de Boltzmann existants, ainsi que de leur propriétés et leurs fondations mathématiques sous-jacentes. Dans une seconde partie, nous présentons notre idée de biaiser ces algorithmes pour étendre leur domaine de validité. Nous proposons une extension très générale, avant de l’appliquer à plusieurs opérateurs combinatoires tels que la dérivation, le produit de shuffle et l’opération de dépointage. Enfin, nous présentons un algorithme de génération uniforme pour le produit de Hadamard. Nous appuyons nos algorithmes et résultats par des exemples et données expérimentales illustrant le bien fondé de nos méthodes.