Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 15 Novembre 2011

Une méthode algorithmique pour le calcul des séries génératrices des classes de permutations, et pour la génération aléatoire dans ces classes

par Mathilde Bouvel (LaBRI, Bordeaux)

L'objectif de l'exposé est de présenter un cheminement algorithmique qui, partant d'une classe de permutations C donnée par sa base (supposée finie), permet d'obtenir automatiquement des résultats énumératifs sur la classe C, et un générateur aléatoire de permutations de C.

Je commencerai par définir les classes de permutations, et expliquerai comment le point de vue de la décomposition par substitution peut être efficacement utilisé pour décrire les permutations de toute classe donnée dans le formalisme des structures combinatoires. Une fois dans ce cadre classique, il devient aisé d'obtenir des résultats d'énumération et des générateurs aléatoires. La difficulté principale est de passer *algorithmiquement* de la description d'une classe par sa base à un système d'équations la décrivant comme une structure combinatoire. Je montrerai les principales étapes de ce cheminement, et esquisserai une explication plus détaillée de certaines d'entre elles.

Il s'agit d'un travail en commun avec Frédérique Bassino, Adeline Pierrot, Carine Pivoteau et Dominique Rossin.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr