La combinatoire analytique

Table des matières

Introduction
I Préliminaires
1 Classes combinatoires et spécifications
1.1 Classe combinatoire non-étiquetée
1.2 Séries génératrices ordinaires
1.3 Constructeurs
1.4 Classes étiquetées et séries exponentielles
1.5 Classes Multivariées
1.6 Dérivée combinatoire
1.7 Analogie avec la théorie des espèces
2 Arbres
2.1 Arbres enracinés planaires
2.2 Arbres de Catalan
2.3 Arbres de Motzkin
2.4 Autres types d’arbres enracinés
3 Génération aléatoire
3.1 Introduction à la génération aléatoire
3.2 Méthodes ad-hoc et méthode récursive
3.3 Générateur de Boltzmann
3.4 Applications de la génération aléatoire
II Algorithmes de Rémy
4 L’algorithme original de Rémy
4.1 Introduction
4.2 L’algorithme de Rémy
4.3 Spécification holonome
5 Amélioration de l’algorithme de Rémy
5.1 Spécification des arbres de Catalan
5.2 Génération aléatoire
6 Extension aux arbres de Motzkin
6.1 Spécification holonome des arbres de Motzkin
6.2 Génération aléatoire
6.3 Conclusion et perspectives
Conclusion