Supervision : Michèle SORIA

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

Uniform random generation is a central issue in combinatorics. Indeed, random sampling is virtually connected to all parts of combinatorics, whether to exact or asymptotic enumeration, or to the experimental verification of conjectures. Various methods have been developed in order to efficiently solve that issue. Boltzmann model is among them. This method, relaxing some constraints about the size of the object being currently generated, ensures a linear complexity in many actual cases, and can easily be automatized for various combinatorial classes. This thesis aims at enlarging the set of such admissible classes, while keeping the nice properties of linear complexity and ease of automation. The first part is devoted to the presentation of the Boltzmann model and existing Boltzmann samplers, and the study of their properties and mathematical foundations. In the second part, we introduce our idea of biasing those samplers in order to enlarge their range of validity. Firstly, we present a general extension, and then specialize it to several combinatorial operations such as the derivation, the shuffle product or the unpointing operation. Finally, we present a uniform random sampler for the Hadamard product. We highlight our algorithms through this thesis with examples and experimental results, illustrating the efficiency of our methods.

Phd defence : 09/25/2012

Jury members :

Philippe Duchon
Conrado Martínez
Olivier Bodini
Christoph Dürr
Cyril Nicaud
Konstantinos Panagiotou
Bruno Salvy
Michèle Soria

2009-2022 Publications

• 2022
  • C. 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), Post-actes des Journées Francophones sur les Systèmes Multi-Agents, 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”, thesis, phd defence 09/25/2012, supervision 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, 23^rd 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”, 7^th 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 - 5^th Latin-American Algorithms, Graphs and Optimization Symposium, vol. 35, Electronic Notes in Discrete Mathematics, Rio Grande do Sul, Brazil, pp. 305-310, (Elsevier) (2009)