Algorithmique et Programmation TD n? 1 : Recherche de motif Morphismes sur le monoıde libre Ecole normale superieure Departement d'informatique 2011-2012 1 Petits Rappels Mots x et z sont, respectivement, un prefixe et un suffixe d'une chaıne de caracteres ? si on peut ecrire ? = x.z. De meme, y est un facteur de ? si on peut ecrire ? = x.y.z, ou x et z sont eventuellement vides. On dit aussi que x est un sous-mot de y si on peut obtenir x en effac¸ant des lettres de y. Monoıde libre Etant donne un alphabet fini A, l'ensemble des mots (finis) formes de lettres de A, note A?, muni de l'operateur de concatenation, forme le monoıde libre (il est dit “libre” car ses elements ne satisfont aucune equation non-triviale). Morphisme Un morphisme du monoıde libre est une fonction ? : A? ? A? telle que ?(x.y) = ?(x).?(y). Il en decoule qu'un morphisme est entierement determine par les images des lettres de A. 2 Echauffement Exercice 1 (?) : Sous-mot. Donnez un algorithme qui determine si un mot x est un sous-mot d'un autre mot y.
- lettres ? ?
- paire de mots distincts
- entier de la question precedente
- ?n
- croıt de fac¸on polynomiale
- matrice-matrice
- morphismes uniformes
- monoıde libre