ROUSSEL Olivier

Docteur
Équipe : APR
Date de départ : 30/09/2012
Direction de recherche : Michèle SORIA

Générateur aléatoire de strutures ordonnées par le modèle de Boltzmann

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.
Soutenance : 25/09/2012 - 14h - Site Jussieu 25-26/105
Membres du jury :
Philippe Duchon
Conrado Martínez
Olivier Bodini
Christoph Dürr
Cyril Nicaud
Konstantinos Panagiotou
Bruno Salvy
Michèle Soria

1 Docteur 2018

Publications 2009-2018

 Mentions légales
Carte du site |