ROUSSEL Olivier
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
Membres du jury :
Philippe Duchon
Conrado Martínez
Olivier Bodini
Christoph Dürr
Cyril Nicaud
Konstantinos Panagiotou
Bruno Salvy
Michèle Soria
Publications 2009-2022
-
2022
- Cédric L.R. Buron, Z. Guessoum, S. Ductor, O. Roussel : “MoCaNA, un agent de négociation automatique utilisant la recherche arborescente de Monte-Carlo”, Revue Ouverte d'Intelligence Artificielle, vol. 3 (5-6), pp. 645-669, (Association pour la diffusion de la recherche francophone en intelligence artificielle) (2022)
-
2018
- C. Buron, Z. Guessoum, S. Ductor, O. Roussel : “MoCaNA, un agent de négociation automatique utilisant la recherche arborescente de Monte-Carlo”, Vingt-sixièmes Journées Francophones sur les Systèmes Multi-Agents, Métabief, France (2018)
-
2012
- O. Roussel : “Générateur aléatoire de strutures ordonnées par le modèle de Boltzmann”, thèse, soutenance 25/09/2012, direction de recherche Soria, Michèle (2012)
- O. Bodini, O. Roussel, M. Soria : “Boltzmann samplers for first-order differential specifications”, Discrete Applied Mathematics, vol. 160 (18), pp. 2563-2572, (Elsevier) (2012)
- A. Darrasse, K. Panagiotou, O. Roussel, M. Soria : “Biased Boltzmann samplers and generation of extended linear languages with shuffle”, Discrete Mathematics and Theoretical Computer Science, vol. DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings, Montreal, Canada, pp. 125-140, (Discrete Mathematics and Theoretical Computer Science) (2012)
-
2011
- O. Bodini, D. Gardy, O. Roussel : “Boys-and-girls birthdays and Hadamard products”, 7th International Conference on Lattice Path Combinatorics and Applications, vol. 117 (1-4), Fundamenta Informaticae, Siena, Italy, pp. 85-101, (IOS Press) (2011)
-
2010
- A. Darrasse, K. Panagiotou, O. Roussel, M. Soria : “Boltzmann generation for regular languages with shuffle”, GASCOM 2010 - Conference on random generation of combinatorial structures, Montréal, Canada (2010)
-
2009
- O. Roussel, M. Soria : “Boltzmann sampling of ordered structures”, LAGOS 2009 - 5th Latin-American Algorithms, Graphs and Optimization Symposium, vol. 35, Electronic Notes in Discrete Mathematics, Rio Grande do Sul, Brazil, pp. 305-310, (Elsevier) (2009)