|
Combinatoire des mots M2 UE343
|
Département : Informatique
Projet : Arithmétique Informatique
Bureau : LIRMM E.3.06
Mél : berthe@lirmm.fr
Téléphone : +33 4 67 41 86 82
Télécopie : +33 4 67 41 85 00
LIRMM
161, rue Ada
34 392 Montpellier Cedex 5
La combinatoire des mots intervient dans de nombreux domaines
de l'informatique (compression, langages formles et automates)
et des mathématiques (théorie des nombres, probabilités, théorie des groupes).
Nous nous proposons de centrer ce cours autour de
deux familles de mots infinis de faible complexité mais au comportement combinatoire
très riche, à savoir, les mots sturmiens et les mots substitutifs. Les mots sturmiens entretiennent d'étroites relations avce la géométrie discrète
(ce sont des codages de droites discrètes).
Les mots substitutifs sont engendrés par un procédé algorithmique simple :
les morphismes de monoïde libre.