Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
Combinatoire et algorithmique dans les classes de permutations à motifs exclus.
Adeline Pierrot

14 March 2014, 10h30 - 14 March 2014, 11h30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Combinatoire

Résumé :
Cet exposé donnera un aperçu accessible du domaine de recherche dynamique des permutations à motifs exclus, tout en illustrant dans ce cadre les interactions fructueuses existantes entre combinatoire et algorithmique.
Un outil clé présenté sera la décomposition par substitution des permutations, qui est un exemple de décomposition récursive d'objets discrets utile tant sur le plan combinatoire qu'algorithmique, et qui fait partie du même cadre général que la décomposition modulaire des graphes. Une telle décomposition permet de mettre en évidence la structure des objets étudiés, et de l'exploiter afin d'obtenir entre autres des résultats de nature énumérative ou des algorithmes de génération aléatoire.
En particulier dans le cas des permutations à motifs exclus, on obtient un algorithme qui prend en entrée la base de motifs exclus et produit une spécification combinatoire, c'est-à-dire une description récursive de la classe de permutations qui peut être directement transcrite en générateur aléatoire et en un système d'équations satisfaites par la série génératrice.

Pour en savoir plus :
Séminaires
A Family of Tractable Graph Distances
Gestion de données du Web
Wednesday 04 July 2018 - 10h30
Salle : 465 - PCRI-N
Stratis Ioannidis .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 29 June 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Distributionally Robust Optimization with Principa
Optimisation combinatoire et stochastique
Friday 29 June 2018 - 11h00
Salle : 455 - PCRI-N
Dr. Jianqiang Cheng .............................................

Caractérisation de réseaux égocentrés par l'énumér
Friday 15 June 2018 - 14h30
Salle : 455 - PCRI-N
Raphaël Charbey .............................................

DATA VERACITY ASSESSMENT: HOW A-PRIORI KNOWLEDGE E
Intégration de données et de connaissances
Friday 15 June 2018 - 14h00
Salle : 445 - PCRI-N
Valentina Beretta .............................................