En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

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

Sélection Signaler une erreur
Multi angle
Auteurs : Pivoteau, Carine (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...

Résumé : 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.

Keywords : génération aléatoire; méthode récursive; méthode de Boltzmann; combinatoire analytique

Codes MSC :
05A15 - Exact enumeration problems, generating functions
05A16 - Asymptotic enumeration
60C05 - Combinatorial probability
68W20 - randomized algorithms

    Informations sur la Vidéo

    Réalisateur : Petit, Jean
    Langue : Anglais
    Date de publication : 28/03/2023
    Date de captation : 13/03/2023
    Sous collection : Research School
    arXiv category : Combinatorics ; Logic
    Domaine : Combinatorics
    Format : MP4 (.mp4) - HD
    Durée : 01:16:43
    Audience : Researchers ; Graduate Students ; Doctoral Students, Post-Doctoral Students
    Download : https://videos.cirm-math.fr/2023-03-14_Pivoteau.mp4

Informations sur la Rencontre

Nom de la rencontre : ALEA Days / Journées ALEA
Organisateurs de la rencontre : Elvey Price, Andrew ; Lecouvey, Cédric ; Mailler, Cécile ; Raschel, Kilian
Dates : 13/03/2023 - 15/03/2023
Année de la rencontre : 2023
URL Congrès : https://conferences.cirm-math.fr/2887.html

Données de citation

DOI : 10.24350/CIRM.V.20018503
Citer cette vidéo: Pivoteau, Carine (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
URI : http://dx.doi.org/10.24350/CIRM.V.20018503

Voir aussi

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



Imagette Video

Sélection Signaler une erreur