00:00:00 / 00:00:00

Méthodes automatiques pour la génération aléatoire de structures combinatoires - cours 2/2

By Carine Pivoteau

Appears in collection : ALEA Days / Journées ALEA

La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d'être tirés). Ces deux techniques s'appuient fortement sur l'utilisation des séries génératrices afin de garantir l'uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s'appuie sur l'évaluation numérique de ces mêmes séries. Durant la séance d'exercices vous pourrez programmer vos propres générateurs suivant l'une ou l'autre de ces méthodes.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.20018503
  • Cite this video Pivoteau, Carine (13/03/2023). Méthodes automatiques pour la génération aléatoire de structures combinatoires - cours 2/2. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20018503
  • URL https://dx.doi.org/10.24350/CIRM.V.20018503

Domain(s)

Bibliography

  • FLAJOLET, Philippe, ZIMMERMANN, Paul, et VAN CUTSEM, Bernard. A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 1994, vol. 132, no 1-2, p. 1-35. - https://doi.org/10.1016/0304-3975(94)90226-7
  • A Calculus of Random Generation : Unlabelled Structures. P. Flajolet, P. Zimmermann, B. Van Cutsem. draft, 1997
  • DUCHON, Philippe, FLAJOLET, Philippe, LOUCHARD, Guy, et al. Boltzmann samplers for the random generation of combinatorial structures. Combinatorics, Probability and Computing, 2004, vol. 13, no 4-5, p. 577-625. - https://doi.org/10.1017/S0963548304006315
  • FLAJOLET, Philippe, FUSY, Éric, et PIVOTEAU, Carine. Boltzmann sampling of unlabelled structures. In : 2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Society for Industrial and Applied Mathematics, 2007. p. 201-211. - https://doi.org/10.1137/1.9781611972979.5

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback