Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 22 mars 2011 à 10h30 en B311, Julien David nous parlera de : Génération exhaustive de multiensembles de sous-mots fréquents

Résumé : On étudie le problème suivant: partant d'un mot w et d'un entier q, on souhaite engendrer toutes les façons possibles de partitionner w en ensemble de sous-mots fréquents. Un sous-mot est fréquent s'il possède au moins q occurrences dans la partition. Chaque mot étant associé à un nombre d'occurrences, on s'intéresse à des multiensembles de mots plutôt qu'à des ensembles de mots. Par exemple, partant du mot w=cabcba et d'un entier q=2, le multiensemble {(cb,2),(a,2)} est une solution. On présentera un algorithme qui engendre l'ensemble des solutions sans redondance et on montrera que, sauf si P=NP, la complexité de ce problème est exponentiel dans la taille de la sortie. On donnera un exemple d'une des applications possibles pour cet algorithme.

 [Slides.pdf]


Dernière modification : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr