Institut Gaspard Monge Laboratoire d'informatique

De
Publié par

Institut Gaspard-Monge Laboratoire d'informatique UMR 8049 Universite de Marne-la-Vallee E.S.I.E.E. C.N.R.S. Rapport scientifique 2001 — 2004 (novembre 2004)

  • informatique linguistique

  • algebres de hopf combinatoires

  • polynomes de jack et de macdonald

  • generalisations du monoıde plaxique et de robinson-schensted

  • calculs dans le centre de l'algebre du groupe symetrique


Publié le : mardi 19 juin 2012
Lecture(s) : 14
Tags :
Source : igm.univ-mlv.fr
Nombre de pages : 190
Voir plus Voir moins

Institut Gaspard-Monge
Laboratoire d’informatique
UMR 8049
Universit¶e de Marne-la-Vall¶ee
E.S.I.E.E.
C.N.R.S.
Rapport scientiflque
2001 | 2004
(novembre 2004)Table des mati?eres
1 Pr¶esentation du laboratoire 7
1.1 Politique scientiflque . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Activit¶es communes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Formation doctorale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Recrutements et perspectives de croissance . . . . . . . . . . . . . . . . 10
1.5 Conseil du laboratoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Liste des membres permanents du laboratoire . . . . . . . . . . . . . . 13
2 Algorithmique 15
2.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Th?emes de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 R¶esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Algorithmique du texte . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Automates, codage et dynamique symbolique . . . . . . . . . . 22
2.3.3 g¶enomique . . . . . . . . . . . . . . . . . . . . . 32
2.3.4 Programmation g¶en¶erique et r¶eseaux . . . . . . . . . . . . . . . 40
2.4 Activit¶es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.1 Contrats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.2 Difiusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.4.3 Travaux ¶editoriaux et organisation de colloques . . . . . . . . . 48
2.4.4 Collaborations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.5 Visiteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.4.6 Activit¶es doctorales . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.4.7 Th?eses et habilitations . . . . . . . . . . . . . . . . . . . . . . . 50
2.5 Responsabilit¶es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6 R¶ef¶erences bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Combinatoire alg¶ebrique et calcul symbolique 65
3.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2 Th?emes de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664 Table des mati?eres
3.3 R¶esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3.1 Fonctions sym¶etriques non commutatives, fonctions
quasi-sym¶etriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3.2 Alg?ebres de Hopf combinatoires . . . . . . . . . . . . . . . . . . 68
3.3.3 G¶en¶eralisations du mono˜‡de plaxique et de
Robinson-SchenstedKnuth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3.4 Polyn^ omes de Jack et de Macdonald . . . . . . . . . . . . . . . 69
3.3.5 Alg?ebres de Hecke a–nes . . . . . . . . . . . . . . . . . . . . . . 70
3.3.6 Tableaux de rubans . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.7 Th¶eorie des invariants et information quantique . . . . . . . . . 70
3.3.8 Polyn^ omes de Schubert et de Grothendieck . . . . . . . . . . . . 71
3.3.9 Alg?ebres de Lie libres . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3.10 Th¶eorie des automates . . . . . . . . . . . . . . . . . . . . . . . 71
3.3.11 Combinatoire classique . . . . . . . . . . . . . . . . . . . . . . . 71
3.3.12 Calculs dans le centre de l’alg?ebre du groupe sym¶etrique . . . . 72
3.3.13 Combinatoire ¶enum¶erative . . . . . . . . . . . . . . . . . . . . . 73
3.3.14 Hyperd¶eterminants, hyperpfa–ens et int¶egrales multiples . . . . 73
3.3.15 Applications diverses . . . . . . . . . . . . . . . . . . . . . . . . 74
3.3.16 Logiciels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.4 Activit¶es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4.1 Contrats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4.2 Difiusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4.3 Collaborations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.4.4 Activit¶es doctorales . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.4.5 Th?eses et habilitations . . . . . . . . . . . . . . . . . . . . . . . 77
3.5 R¶ef¶erences bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . 78
4 Informatique linguistique 85
4.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2 Th?emes de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3 R¶esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.3.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.3.2 Biblioth?eques de ressources linguistiques . . . . . . . . . . . . . 89
4.3.3 Extension des . . . . . . . . . . . . . . . . . . . . . . 91
4.4 Activit¶es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.4.1 Contrats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.4.2 Difiusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.4.3 Collaborations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.4.4 Activit¶es doctorales . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.4.5 Th?eses et habilitations . . . . . . . . . . . . . . . . . . . . . . . 93
4.5 R¶ef¶erences bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . 94Table des mati?eres 5
5 G¶eom¶etrie discr?ete et imagerie 105
5.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 Th?emes de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.3 R¶esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.3.1 Topologie discr?ete . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.3.2 Op¶erateurs topologiques et traitement d’images . . . . . . . . . 114
5.3.3 Morphologie math¶ematique et applications du traitement
d’images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.3.4 G¶eom¶etrie algorithmique et g¶eom¶etrie discr?ete . . . . . . . . . . 129
5.3.5 Compression d’image . . . . . . . . . . . . . . . . . . . . . . . . 132
5.4 Activit¶es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.4.1 Formation doctorale . . . . . . . . . . . . . . . . . . . . . . . . 135
5.4.2 Participation a? la vie scientiflque . . . . . . . . . . . . . . . . . 136
5.4.3 Coop¶erations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.4.4 Contrat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.5 R¶ef¶erences bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . 138
6 Signal et communications 145
6.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.2 Th?emes de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.3 R¶esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.3.1 Communications num¶eriques . . . . . . . . . . . . . . . . . . . . 147
6.3.2 S¶eparation de sources . . . . . . . . . . . . . . . . . . . . . . . . 152
6.3.3 Th¶eorie de l’information . . . . . . . . . . . . . . . . . . . . . . 156
6.3.4 Analyse en ondelettes 2D . . . . . . . . . . . . . . . . . . . . . . 158
6.4 Activit¶es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.4.1 Contrats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.4.2 Difiusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.4.3 Collaborations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6.4.4 Activit¶es doctorales . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.4.5 Th?eses et habilitations . . . . . . . . . . . . . . . . . . . . . . . 165
6.4.6 Rayonnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
6.5 R¶ef¶erences bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . 166
Donn¶ees compl¶ementaires 175
Th?eses et habilitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Rapports internes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
S¶eminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Moyens et environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1886 Table des mati?eresChapitre Premier
Pr¶esentation du laboratoire
e laboratoire d’informatique de l’Institut Gaspard-Monge (IGM) a ¶et¶e cr¶e¶e en
1992. Il d¶eveloppe des recherches en informatique fondamentale et ses applica-L tions. Il a pu devenir productif tr?es rapidement et m^eme essaimer vers d’autres
laboratoires d’informatique gr^ ace a? des transferts de travaux et de chercheurs op¶er¶es
notamment a? partir de l’universit¶e Paris 7. Les th?emes de d¶epart incluent
l’informa?tique th¶eorique et le traitement de la langue naturelle. A ces th?emes originaux se sont
ajout¶es l’imagerie, la g¶eom¶etrie discr?ete et, plus r¶ecemment, le traitement du signal.
Le lien commun entre tous ces th?emes est l’utilisation de m¶ethodes formalis¶ees pour
atteindre un objectif de description exacte des ph¶enom?enes.
Du point de vue administratif, le laboratoire a ¶et¶e cr¶e¶e en 1992 comme ¶equipe
d’ac¶cueil de doctorants par la Direction de la Recherche et des Etudes Doctorales. Il a
ensuite ¶et¶e ¶equipe postulante du CNRS en 1994, renouvel¶ee en 1996, puis conflrm¶ee
comme UPRES-A en 1998. Depuis 2002, le laboratoire a le statut d’UMR.
Le laboratoire est constitu¶e de cinq ¶equipes identifl¶ees par des th?emes de recherche
qui sont a? la base des projets d¶ecrits plus loin. Ces ¶equipes sont les suivantes :
{ Algorithmique ;
{ Combinatoire alg¶ebrique et calcul symbolique ;
{ Informatique linguistique ;
{ G¶eom¶etrie discr?ete et imagerie ;
{ Signal et communications.
?A celles-ci s’ajoute l’¶equipe < Simulacres, images, sons et arts relais > qui fait
actuellement partie du laboratoire mais qui doit le quitter a? la fln du contrat quadriennal
actuel (d¶ecembre 2005).
Les activit¶es, projets, collaborations, et la production de chacune de ces ¶equipes sont
d¶ecrits dans les chapitres suivants du rapport.8 Chapitre Premier. Pr¶esentation du laboratoire
1.1 Politique scientiflque
Pendant la derni?ere p¶eriode les th¶ematiques de recherche du laboratoire se sont
a–rm¶ees pour donner la conflguration actuelle en ¶equipes. Hormis l’accueil r¶ecent d’une
¶equipe en traitement du signal, les th?emes des autres ¶equipes ¶etaient pr¶esents au d¶ebut
du contrat pr¶ec¶edent et la politique scientiflque a eu pour but de les renforcer, sans
chercher a? en ajouter de nouveaux.
L’orientation scientiflque pour la nouvelle p¶eriode confortera l’orientation retenue
et se traduira par un ¶elargissement de la surface des th?emes de recherche des ¶equipes
existantes. Le potentiel de croissance du laboratoire, du^ en particulier a? son pouvoir
d’attraction, au d¶eflcit en enseignants-chercheurs en informatique a? l’universit¶e et a?
la politique de recrutement a? l’ESIEE, sera utilis¶e pour des recrutements de qualit¶e
capables de s’int¶egrer dans les ¶equipes et de les enrichir. Une attention particuli?ere sera
port¶ee aux chercheurs susceptibles d’impulser des recherches de nature appliqu¶ee.
?A titre d’exemple, les postes universitaires en informatique qui sont destin¶es au
laboratoire ont pour profll les th?emes de recherche des ¶equipes. Un ?¶echage sur
l’informatique linguistique a aussi ¶et¶e d¶ecid¶e pour aider au renforcement d’une ¶equipe
poss¶edant peu de permanents.
Par ailleurs, la politique de campus favoris¶ee par le Polytechnicum de
Marne-laVall¶ee encourage les discussions avec des ¶etablissements comme l’ENPC et pourrait ^etre
?profltable au laboratoire. A terme on peut envisager un regroupement de la plupart des
chercheurs du campus ayant une activit¶e dans le domaine des sciences et technologies
de l’information et de la communication.
La recherche du laboratoire comporte globalement deux grandes orientations dans
lesquelles s’inscrivent les travaux de toutes les ¶equipes. La premi?ere est celle de
l’informatique th¶eorique et de la combinatoire. Elle comprend l’activit¶e ancienne sur la
combinatoire des mots et le codage qui alimente des travaux algorithmiques, la
combinatoire alg¶ebrique en liaison avec des questions de calcul formel sp¶ecialis¶e, et la
g¶eom¶etrie discr?ete qui est utilis¶ee en analyse d’images.
La seconde orientation porte sur le traitement symbolique et statistique de signaux.
En partant des signaux ¶el¶ementaires jusqu’ a des ¶el¶ements plus complexes, elle comprend
l’algorithmique du texte avec ses aspects combinatoires, le traitement statistique du
signal et ses liens avec le codage de source ou de canal, le traitement d’images, l’analyse
algorithmique des s¶equences mol¶eculaires et le traitement de la langue naturelle.
La volont¶e de combiner une recherche de nature fondamentale avec le d¶eveloppement
de logiciels prototypes trouve une traduction dans les activit¶es des ¶equipes.
L’algorithmique de texte est ¶etroitement associ¶ee a? des ¶etudes sur le traitement des s¶equences
biologiques mol¶eculaires en amont de la bioinformatique (il n’y a pas d’exploitation
massive des donn¶ees). L’activit¶e en algorithmique est aussi associ¶ee a? des travaux
sur la programmation g¶en¶erique. L’¶equipe de combinatoire alg¶ebrique est fortement
impliqu¶ee dans l’¶ecriture de biblioth?eques sp¶ecialis¶ees de calcul formel pour le logi-1.2. Activit¶es communes 9
ciel mupad. Le logiciel unitex inclut un vaste ensemble de connaissances pr¶ecises sur
le lexique et la syntaxe de plusieurs langues naturelles. Les recherches en g¶eom¶etrie
discr?ete sont utilis¶ees en traitement d’images. Enfln, le traitement du signal conduit
au d¶eveloppement de difi¶erents algorithmes d’estimation en vue d’am¶eliorer les
performances des syst?emes de communication et de r¶esoudre e–cacement des probl?emes de
s¶eparation et de restauration de signaux.
1.2 Activit¶es communes
La f¶ed¶eration des ¶equipes se r¶ealise dans plusieurs activit¶es et moyens communs :
{ le s¶eminaire hebdomadaire du laboratoire (actuellement le mardi apr?es-midi) qui
est l’occasion d’accueillir des chercheurs ext¶erieurs au laboratoire ;
{ le service de pr¶e-publications qui sert pour la difiusion rapide des r¶esultats des
chercheurs sous la forme de rapports de recherche ;
{ la politique d’¶equipement informatique du laboratoire concert¶ee et commune aux
¶equipes, et qui s’appuie sur le r¶eseau de l’universit¶e ;
{ le serveur informatique de courrier monge.univ-mlv.fr qui a pour r^ole principal
la communication entre chercheurs et accueille le serveur Web du laboratoire :
http://igm.univ-mlv.fr/LabInfo/.
1.3 Formation doctorale
¶Le laboratoire est une des ¶equipes d’accueil principales du DEA < Informatique
Fondamentale et Applications >. Celui-ci constituera a? partir de 2005 la deuxi?eme
ann¶ee du master recherche < Informatique >.
Pendant la p¶eriode consid¶er¶ee 25 membres du laboratoire ont obtenu leur doctorat,
et 5 autres ont ¶et¶e habilit¶es a? diriger des recherches.
¶ ¶Le DEA fait partie de l’Ecole doctorale< Information, Communication, Mod¶elisation,
Simulation > (ICMS). Il accueille en moyenne une vingtaine d’¶etudiants chaque ann¶ee.
Ceux-ci proviennent, pour plus de la moiti¶e, de formations ext¶erieures au campus.
Les ¶etablissements co-habilit¶es a? d¶elivrer le dipl^ ome sont :
¶1. Ecole Nationale des Ponts et Chauss¶ees (ENPC) (correspondant : Renaud K¶eriven) ;
¶ ¶ ¶2. Ecole Sup¶erieure d’Ing¶enieurs en Electrotechnique et Electronique (ESIEE)
(correspondant : Gilles Bertrand) ;
¶3. Universit¶e de Marne-la-Vall¶ee (Marie-Pierre B¶eal, directrice du DEA).10 Chapitre Premier. Pr¶esentation du laboratoire
¶Le DEA est compos¶e d’un tronc commun qui se d¶ecline ensuite en six flli?eres. Ces
flli?eres sont les suivantes :
{ Images et cin¶ema
Cette flli?ere est orient¶ee vers la synth?ese d’images. Ses objectifs sont d’une part
la cr¶eation d’images r¶ealistes de grande qualit¶e, et d’autre part la r¶ealisation
d’images de synth?ese en mouvement. La nouvelle orientation de cette flli?ere en
fait une formation unique en r¶egion parisienne.
{ Imagerie 3D et environnements virtuels
Cette flli?ere traite de l’ensemble des probl?emes intervenant dans l’analyse et le
traitement informatique des images r¶eelles. Une attention particuli?ere est port¶ee
aux mod?eles, aux algorithmes et aux architectures mat¶erielles sp¶ecialis¶ees.
{ Logiciels des r¶eseaux
Cette flli?ere embrasse l’ensemble des aspects logiciels, et notamment les
applications r¶eparties, la transmission multi-m¶edia, le routage, la conception de moteurs
de recherche ou la s¶ecurit¶e.
{ Traitement des g¶enomes
Cette flli?ere forme des chercheurs pour le traitement informatique des g¶enomes, en
liaison avec des organismes de recherche des sciences de la vie. L’informatique, et
en particulier l’algorithmique est indispensable a? l’analyse des g¶enomes complets
qui sont en cours de s¶equen» cage. Notre ¶equipe d’algorithmique est a? la pointe de
ces d¶eveloppements.
{ Langue naturelle et repr¶esentation des connaissances
Cette flli?ere forme des chercheurs dans le domaine de la documentation
automatique, du traitement de corpus et dans les applications vers le multim¶edia. Les
aspects linguistiques du Web, notamment pour les moteurs de recherche, sont
consid¶er¶es. Le laboratoire a une position en pointe dans ces domaines.
{ Automates et combinatoire
Cette flli?ere est a? la poursuite de la formation dans le domaine fondamental qui
a fait le succ?es de l’¶ecole fran» caise d’informatique th¶eorique. Elle traite des
algorithmes et syst?emes formels, des automates, qui sont li¶es au traitement de la
langue naturelle, des donn¶ees textuelles, ainsi que le traitement du g¶enome. La
formation dans le calcul symbolique est orient¶ee vers les applications dans des
domaines vari¶es comprenant le calcul scientiflque.
Nous formons dans ces domaines des ¶etudiants participant aux recherches conduites
dans le domaine fondamental et aussi dans le domaine industriel.
1.4 Recrutements et perspectives de croissance
Le laboratoire compte environ cent chercheurs dont a? peu pr?es la moiti¶e sont des
membres permanents. Apr?es une croissance initiale assez forte (le nombre de cher-

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.