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 17 Juin 2008

Comptage de mots et de paquets de mots dans des textes aléatoires

par Pierre Nicodème (LIX, Polytechnique Palaiseau)

Le comptage de mots dans des textes aléatoires fait apparaître des phénomènes qui sont à première vue contreintuitifs et qui dépendent de la manière dont les mots sont auto-corrélés. Nous ferons un peu de mathématiques expérimentales en tirant des chaînes binaires aléatoires pour aborder cette question. Nous présenterons ensuite la décomposition formelle sur les langages de Régnier et Szpankowski (1998) et sa traduction en séries génératrices qui résolvent le problème du comptage de mots. Ceci nous aménera, par une extension de cette méthode au comptage des paquets (clumps en anglais) d’un ensemble de mots dans le cas où cet ensemble est réduit. Enfin nous donnerons une construction par automate qui résout le cas général (non-réduit).

Travail en commun avec Frédérique Bassino, Julien Clément et Julien Fayolle.

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