00:00:00 / 00:00:00

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

De Carine Pivoteau

Apparaît dans la collection : ALEA Days 2023 / Journées ALEA 2023

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.

Informations sur la vidéo

Données de citation

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

Domaine(s)

Bibliographie

  • 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

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis
Loading…
Loading the web debug toolbar…
Attempt #