Partenaires


Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Actualités > Conférence - Génération exhaustive par la méthode ECO

Conférence - Génération exhaustive par la méthode ECO

par Antoine Trapet - 7 avril 2011

Elena Barcucci, Professeur de l’Université de Florence, Italie donnera une conférence le lundi 11 avril à 10h salle DR 16 B (salle M2-STIC) sur Génération exhaustive par la méthode ECO (Exhaustive generation by the ECO method, Generazione esaustiva per il metodo eco)

La méthode ECO fut introduite comme outil d’énumération de diverses classes d’objets combinatoires. Procédé essentiellement constructif, il permet au moyen d’insertions appropriées d’éléments de base dans un objet (pas sur des chemins, cellules de polyominos, nœud des arbres, entiers dans les permutations), d’obtenir les objets d’une dimension donnée (selon le paramètre utilisé pour l’énumération) à partir de ceux de dimension immédiatement inférieure, de telle sorte que chaque objet est obtenu une et une seule fois.

Cette construction incrémentale, lorsque définie de manière appropriée, produit une description synthétique du processus de croissance d’un arbre de génération qui contient sur chaque niveau tous les objets de dimension égale. En outre, dans de nombreuses situations il est possible d’obtenir la fonction génératrice qui énumère les objets de la classe selon un ou plusieurs paramètres. La méthode ECO se prête de manière inhérente à la génération exhaustive.

Aussi, seront illustrées ses applications à la génération exhaustive en général, avec les algorithmes en CAT, et aussi à la définition de codes de Gray en présentant de nombreux résultats de plusieurs chercheurs travaillant dans le domaine.


LE2I - Laboratoire Electronique, Informatique et Image | webmestre : Antoine Trapet | info légales | logo SPIP 2