Sujet : Génération dirigée de mots d'un langage à motifs

Responsable : Jean-Guy PENAUD et Nasser SAHEB
Téléphone : 05 56 60 84 47 (JGP) et 05 56 60 84 93 (NS)
e-mail : {penaud,saheb}@labri.fr
Site Web : http://dept-info.labri.u-bordeaux.fr/
Equipe : Combinatoire et Algorithmique

Présentation du sujet :

Le but est d'engendrer des mots contenant des séquences particulières de lettres constituant des motifs, ces motifs ayant des probabilités
d'apparition spécifiques dans l'ensemble des mots d'une longueur donnée.
Une des applications de cette étude est, en bio-informatique, de fournir des méthodes pour engendrer des séquences génomiques.
Ce travail comporte une étude comparative des diverses méthodes publiées (récursives, à rejet, chaîne de Markov) afin de pouvoir
proposer dans des cas précis la solution la plus performante.

Mot-clés : génération aléatoire, théorie des langages, combinatoire, complexité.

Références :
A. Denise, O. Roques and M. Termier, Random generation of words of context-free languages according to the frequencies
of letters , in D. Gardy and A. Mokkadem editeurs, Mathematics and Computer Science: Algorithms, Trees, Combinatorics
and Probabilities; Trends in Mathematics, pp. 113-125, Birkhaüser, 2000.

A. Denise, M. Vasconcellos and D.J.A. Welsh, The random planar graph, in Congressus Numericatium , pp. 61-79, 1996.

J.-G. Penaud, Elisa Pergola, Renzo Pinzani, Olivier Roques, Chemins de Schröder et hiérarchies aléatoires , in Theoretical
Computer Science 255, pp. 345-361. 2001.

M. Mosbah and N. Saheb, Non uniform random spanning trees in weighted graphs, in Theoretical Computer Science 218,
pp. 263-271, 1999.