Mines Informatique MP 2004

J. 0794

A 2004 -- INF -- MP

- ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES,
ECOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE,
DES TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT--ÉTIENNE, DES MINES DE NANCY
DES TÉLÉCOMMUNICATIONS DE BRETAGNE,
ÉCOLE POLYTECHNIQUE
(Filière T.S.I.)

CONCOURS D'ADMISSION 2004

ÉPREUVE D'INFORMATIQUE

Filière MP
(Durée de l'épreuve : 3 heures)

Sujet mis à la disposition des concours Cycle International, ENSTIM et TPE-EIVP.

Les candidats et les candidates sont priés de mentionner de façon

apparente sur la première page de la copie :
« INFORMATIQUE -- Filière MP »

RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES

. L'énoncé de cette épreuve, y compris cette page de garde, comporte 10 pages.

0 Si, au cours de l'épreuve, un candidat ou une candidate repère ce qui lui 
semble être une erreur
d'énoncé, il ou elle le signale sur sa copie et poursuit sa composition en 
expliquant les raisons des
initiatives qu'il ou elle a décidé de prendre.

- Tout résultat fourni dans l'énoncé peut être utilisé pour les questions 
ultérieures même s'il n'a pas
été démontré.

. Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents 
même lorsque l'énoncé

ne le demande pas explicitement.
- L'utilisation d'une calculatrice ou d'un ordinateur est interdite.

COMPOSITION DE L'ÉPREUVE

L'épreuve comporte deux parties indépendantes :

0 un problème d'algorithmique et de programmation, page 2 à 7, à résoudre en 1 
h 45 mn environ ;
0 un problème sur les automates, pages 8 à 10, à résoudre en 1 h 15 mn environ.

Tournez la page S.V.P.

Épreuve d'informatique

]. Problème d'algorithmique et de programmation -- 1 h 45 mn environ

Le tri par baquets

Préliminaire concernant la programmation: il faudra écrire des fonctions ou des 
procédures à l'aide d'un
langage de programmation qui pourra être soit Caml, soit Pascal, tout autre 
langage étant exclu. Indiquer en
début de problème le langage de programmation choisi ; il est interdit de 
modifier ce choix au cours de
l'épreuve. Certaines questions du problème sont formulées différemment selon le 
langage de programmation ;
cela est indiqué chaque fois que cela est nécessaire. Par ailleurs, lorsqu'un 
candidat ou une candidate écrira une
fonction ou une procédure en langage de programmation, il ou elle précisera si 
nécessaire le rôle des variables
locales et pourra définir des fonctions ou procédures auxiliaires qu'il ou elle 
explicitera. Enfin, lorsque le
candidat ou la candidate écrira une fonction ou une procédure, il ou elle 
pourra, lorsque cela s'y prête, faire appel
à une autre fonction ou procédure définie dans les questions précédentes.

Terminologie, notations et indications

a) Dans l'énoncé, les identificateurs sont écrits en police de caractères 
Courier New dans le contexte du
langage de programmation et en italique sinon.

b) Un tableau est constitué de cases pouvant contenir des valeurs d'un type 
donné. Le nombre total de cases du
tableau s'appelle ici sa dimension. La case d'indice i d'un tableau T sera 
notée T[i] dans l'énoncé du problème.

c) Dans ce problème, nous appelons opérations élémentaires :
0 un accès en mémoire pour lire ou écrire la valeur d'une variable ou d'une 
case d'un tableau ;
0 une opération arithmétique entre entiers : addition, soustraction, 
multiplication, division entière, calcul
du reste dans une division entière ;
o une comparaison (>, <, 2, S, =, #) entre deux entiers. Soient f et g deux fonctions d'une même variable entière n (resp. de deux mêmes variables entières n et m). On dit que la fonction f a un ordre de grandeur au plus égal à celui de la fonction g s'il existe un entier strictement positif k et un entier N (resp. deux entiers N et M) tels qu'on ait, pour tout n ?. N (resp. n 2 N et m 2 M), f(n) .<. k g(n) (resp. f(n, m) S k g(n, m)). On dit que les deux fonctions ont même ordre de grandeur si l'ordre de grandeur de l'une est au moins égal à l'ordre de grandeur de l'autre, et réciproquement. Par exemple, les fonctions f(n) : 3 n2 -- 5 n + 4 et g(n) : n2 ont même ordre de grandeur. On pourra aussi dire que g est un ordre de grandeur de f. Quand on calculera la complexité d'un algorithme 54, on l'exprimera sous la forme d'un ordre de grandeur du nombre d'opérations élémentaires effectuées pendant le déroulement de %; cette complexité sera exprimée à l'aide de paramètres caractéristiques du problème à traiter. d) Si l'on se préoccupe de trier une liste de n données, on sait alors que les algorithmes de tri opérant par comparaisons et échanges des données de la liste ont une complexité dans le cas le plus défavorable au moins de l'ordre de grandeur de nln(n). On étudie dans ce problème des algorithmes de tri d'entiers qui n'opèrent pas par comparaisons entre les données à trier. e) Tout au long du problème, on fera l'hypothèse qu'il n'y a pas de limitation sur la taille de la mémoire disponible et qu'on peut donc manipuler des tableaux de dimensions quelconques. On ne se préoccupera pas non plus du fait que les entiers codés sur un ordinateur sont bornés et on fera comme s'ils ne l'étaient pas. 0 Indications pour la programmation Caml: Ce qui est appelé tableau dans l'énoncé correspond à ce qui est appelé vecteur en Caml. En Caml, T . (i ) représente la case T[i] d'un tableau T. Page 2 sur 10 Épreuve commune 2004 Pascal : Dans tout le problème, on supposera qu'on écrit les différentes fonctions dans un fichier contenant les définitions suivantes : const MAX_DIM = 100; MAX_VAL = lOQD: type TABLE : array[0..MAX_DIM] of INTEGER; BACS = array[0..9] of TABLE; PREMIÈRE PARTIE Tri d'entiers compris entre 0 et MAX_VAL Cette partie est consacrée à un algorithme qui peut être considéré comme la version la plus simple du tri par baquets étudié dans la seconde partie. On suppose dans cette première partie qu'on veut trier par ordre croissant un ensemble de n entiers dont les valeurs sont toutes comprises entre 0 et une valeur maximum notée MAX_VAL. Certaines valeurs peuvent figurer plusieurs fois dans l'ensemble des données à trier; ces valeurs figureront alors avec le même nombre d'occurrences après le tri. Exemple : Pour MAX_VAL : 10 et n = 9, avec les données à trier suivantes : 6, 4, 2, 8, 4, 2, 3, 6, 4, les données triées sont alors : 2, 2, 3, 4, 4, 4, 6, 6, 8. Cl 1 -- Expliciter un algorithme de tri, de complexité MAX_VAL + n, fondé sur le principe suivant: on compte, pour chaque entier compris entre 0 à MAX_VAL, son nombre d'occurrences parmi les entiers à trier, puis on en déduit la liste triée. On justifiera sommairement la complexité de l'algorithme proposé. D 2 -- Il s'agit de programmer l'algorithme de la question Cl 1. Les données à trier se trouvent initialement dans un tableau ; après le tri, les données doivent occuper globalement les mêmes cases du tableau mais en étant cette fois-ci ordonnées par ordre croissant. ' Caml : Écrire en Caml une fonction tri_simple telle que, si 0 tableau est un vecteur de dimension suffisante, . tableau . ( 0 ) contient le nombre de données à trier, . les données à trier, de valeurs comprises entre 0 et MAX_VAL, se trouvent dans tableau consécutivement à partir de l'indice 1, alors tri_simple tableau ordonne les données du vecteur tableau par ordre croissant. La constante entière MAX_VAL est supposée déjà définie. Pascal : Écrire en Pascal une procédure tri_s imple telle que si 0 tableau est de type TABLE, 0 tableau [ 0] contient le nombre de données à trier, nombre qui ne dépasse pas la constante MAX_DIM, . les données à trier, de valeurs comprises entre 0 et MAX_VAL, se trouvent dans tableau consécutivement à partir de l'indice 1, alors tri_simple (tableau) ordonne par ordre croissant les données contenues dans tableau. Page 3 sur 10 Tournez la page S.V.P. Épreuve d'informatique DEUXIÈME PARTIE Gestion de tables Dans toute cette partie, on considérera des tableaux dont le plus petit indice vaut 0 et tels que les données du problème n'occupent pas nécessairement toutes les cases. Plus précisément, pour un tableau T contenant n données significatives du problème (typiquement, des données à trier) : 0 la case T[O] contiendra le nombre n ; o les données significatives occuperont les cases T[l], T[2], T[n]. Par exemple, on pourrait, pour trier les entiers 6, l et 7, disposer d'un tableau T dont les indices varient de 0 à 8, mettre la valeur 3 (nombre de données à trier) dans T[O], dans T[l] la valeur 6, dans T[2] la valeur 1, dans T[3] la valeur 7 et ne pas se préoccuper des contenus des cases d'indice 4 à 8. Ce tableau peut être représenté ainsi : T= ---fl----- On appellera table un tableau conçu selon ce modèle. Une table contiendra toujours des entiers positifs ou nuls. Ainsi, pour l'exemple précédent, la table Tcontient les données 6, l et 7. Une table Test dite vide si T[O] vaut 0. Une table sera dite triée si les entiers contenus dans les cases d'indices compris entre 1 et T[O] sont croissants au sens large. Les questions Cl 3 à D 10 préparent la programmation du tri par baquets dont le principe sera indiqué après la question D 10. D 3 -- Vider une table consiste à la transformer en une table vide. Caml : Écrire en Caml une fonction vider telle que, si T est un vecteur contenant une table, vider T vide la table T. Pascal : Écrire en Pascal une procédure vider telle que, si T est de type TABLE, vider (T) vide la table T. D 4 --- Ajouter un entier p a une table consiste à ajouter p a la suite des données figurant déjà dans la table et à actualiser le nombre des données de la table. Par exemple, si la table T est réprésentée ci-dessous (les cases non remplies contiennent des valeurs non significatives) : Tr ---fl---- ajouter à la table T la valeur 5 consiste à transformer Ten : Tr ___-"__- Caml : Écrire en Caml une fonction ajouter telle que, si T est un vecteur contenant une table et p un entier, ajouter T p transforme T pour ajouter p a la table T. On supposera que la dimension de la table Tpermet cet ajout. Pascal: Écrire en Pascal une procédure ajouter telle que, si T est de type TABLE et p un entier, ajouter (T, p) ajoute l'entier p a la table T. On supposera que la dimension de la table T permet cet ajout. DS ---- Concatêner une table T 1 et une table T2 consiste à ajouter successivement dans TI toutes les données de T2. Par exemple, si les tables TI et T2 sont réprésentées ci--dessous : TI : ___--___- T2: --------- la table T] devient après concaténation : TI : --...-- La table T2 est inchangée. Page 4 sur 10 Épreuve commune 2004 Caml : Écrire en Caml une fonction concatener telle que, si T1 et T2 sont deux vecteurs contenant des tables, concatener T1 T2 concatène les tables T1 et T2. On supposera que la dimension de T1 est suffisante pour cette concaténation. Pascal: Écrire en Pascal une procédure concatener telle que, si T1 et T2 sont de type TABLE, concatener (T1, T2) concatène les tables T1 et T2. On supposera que la dimension de T1 est suffisante pour cette concaténation. Cl 6 -- Indiquer la complexité de la fonction ou de la procédure concatener en l'exprimant à l'aide des nombres de données contenues par les tables T1 et T2. On justifiera sommairement le résultat. E] 7 --- Il s'agit ici de définir une fonction max_valeurs qui détermine la plus grande valeur d'une table T (c'est--à-dire le plus grand des entiers qui se trouvent entre les indices 1 et T[O]). Caml : Écrire en Caml une fonction max_valeurs telle que, si T est un vecteur contenant une table, max_valeurs T renvoie la valeur du plus grand entier de T. La fonction max_valeurs renverra la valeur --1 si la table est vide. Pascal : Écrire en Pascal une fonction max_valeurs telle que, si T est de type TABLE, max_valeurs (T) renvoie la valeur du plus grand entier de T. La fonction max_valeurs renverra la valeur --1 si la table est vide. D 8 --- Il s'agit de déterminer le nombre de chiffres d'un entier positif ou nul donné écrit dans la base 10 ; par exemple, le nombre de chiffres de 5973 vaut 4. Caml: Écrire en Caml une fonction nombre_chiffires telle que, si p est un entier positif ou nul, nombre_chi f fres p renvoie le nombre de chiffres de l'entier p. Pascal : Écrire en Pascal une fonction nombre_chiffres telle que, si p est un entier positif ou nul, nombre_chi f f res ( p) renvoie le nombre de chiffres de l'entier p. Cl 9 ---- Il s'agit de définir une fonction max_chszres qui calcule le nombre maximum de chiffres dans une écriture décimale des entiers contenus dans une table. Par exemple, si la table est : Tr ___-___- le résultat doit valoir 4. Caml : Écrire en Caml une fonction max_chiff res telle que, si T est un vecteur contenant une table, max_chiffres T renvoie le nombre maximum de chiffres des données de la table T. La fonction renverra la valeur 0 si la table est vide. Pascal : Écrire en Pascal une fonction max_chiffres telle que, si T est de type TABLE, max_chiff res (T) renvoie le nombre maximum de chiffres des données de la table T. La fonction renverra la valeur 0 si la table est vide. CI 10 -- Exprimer la complexité de la fonction max_chiflres appliquée à une table T à l'aide : 0 du nombre n de données de la table T 0 du nombre maximum maxc de chiffres des données de la table T. On justifiera sommairement le résultat. Page 5 sur 10 Tournez la page S.V.P. Épreuve d'informatique TROISIÈME PARTIE Tri d'entiers écrits en base 10 à l'aide de baquets Dans la description de l'algorithme du tri par baquets, on appelle chiflre de rang r (r 2 1) d'un entier positif ou nul p le r--ième chiffre en partant de la droite de l'entier p écrit dans la base 10 ; par définition, si r est supérieur au nombre total de chiffres de p, le chiffre de rang r vaut alors 0. Par exemple, pour l'entier p = 597, le chiffre de rang 1 est 7, celui de rang 2 est 9, celui de rang 3 est 5, et le chiffre de rang i pour i 2 4 est 0. Les données sont dans une table T. L'objectif de l'algorithme est de transformer la table T en une table triée de manière croissante contenant les mêmes données. On dispose par ailleurs d'un tableau appelé baquets, dont les indices varient de 0 à 9, de 10 tables ; ces 10 tables peuvent contenir chacune au moins autant de données que le nombre de données contenues par la table T. L'algorithme est le suivant : 0 Calculer le nombre maximum de chiffres des données de la table T; le noter maxc. . Pour r qui varie de 1 à maxc, faire : a) Vider les dix baquets, c'est-à-- dire vider baquets... pour tout i appartenant à {O, 1, 9.,}, b) considérer successivement, de l'indice là l' indice T[O], les entiers de la table T: en notant p l' entier considéré, déterminer le chiffre de rang r de l'entier p , en notant k ce chiffre, ajouter p à la table baquets[k] ; c) vider T; d) pour i variant de 0 à 9, concaténer T et baquets[i] (le résultat de la concaténation se trouve dans 7). Indications : on pourra utiliser dans la suite du problème une fonction nommée puiss]0, supposée déjà définie, qui calcule pour un entier p positif ou nul la valeur de 10" . Dans les calculs de complexité, on considérera que les appels à cette fonction sont négligeables, ce qui signifie qu'on ne comptabilisera pas les opérations correspondantes. Lors de l'écriture d'une fonction ou d'une procédure en langage de programmation, si p est une variable entière positive ou nulle, on pourra obtenir 10p par puiss l 0 (p) . D 11 --- On applique l'algorithme du tri par baquets à la table T ci-dessous, qui contient 8 données à trier. T= "___--___-- Le nombre maximum de chiffres des données de la table vaut 3. Pendant l'itération correspondant à la valeur 1 de r: . àl' issue du point b), les baquets d'indices 1, 2, 4, 5, 6, 8, 9 sont restes vides, baquets[0], baquets[3] et baquets[7] sont représentés ci- -:dessous ""WOE= ----::: '"'f"EUR"...= ...: baquetsl7lr ÏZÇ-ÏÏÇ . à l'issue du point d), la table Test : T= ... ÏÏ-ËÊÏ Détailler de même les itérations correspondant aux valeurs 2 et 3 de r. D 12 -- Montrer qu'après l'exécution de l'algorithme du tri par baquets, la table T est triée. CI 13 --- Il s'agit d'écrire en langage de programmation une fonction ou une procédure nommée distribuer qui effectue le point b) de l'algorithme du tri par baquets. Caml : écrire en Caml une fonction distribuer telle que si : 0 T est un vecteur contenant une table, 0 r est un entier au moins égal à 1, . baquets est un vecteur de dimension 10 de vecteurs d'entiers ; chacun de ces 10 vecteurs contient une table vide et est supposé de dimension suffisante pour contenir les données qu'on voudra y mettre, alors distribuer T r baquets effectue les opérations indiquées dans le point b) de l'algorithme du tri par baquets. Page 6 sur 10 Épreuve commune 2004 Pascal : écrire en Pascal une procédure distribuer telle que si : 0 T, de type Table, contient une table, 0 r est un entier au moins égal à l, . baquets est de type BACS (voir au début du problème) ; chacune des dix tables (de type TABLE) de baquets contient une table vide supposée de dimension suffisante pour contenir les données qu'on voudra y mettre, alors distribuer(T, r, baquets) effectue les opérations indiquées dans le point b) de l'algorithme du tri par baquets. D 14-- Il s'agit d'écrire en langage de programmation une fonction ou une procédure nommée tri_baquets qui effectue le tri par baquets. Caml : écrire en Caml une fonction tri_baquets telle que si T est un vecteur contenant une table, tri_baquets T transforme la table Ten une table triée en utilisant l'algorithme du tri par baquets. Pascal : écrire en Pascal une procédure tri_baquets telle que si T, de type Table, contient une table, tri_baquets (T) transforme la table Ten une table triée en utilisant l'algorithme du tri par baquets. CJ 15 --- On note n le nombre de données à trier et maxc le nombre maximum de chiffres des données de la table. Montrer que la complexité de l'algorithme du tri par baquets est de l'ordre de maxc x n. [3 16 --- En supposant les données à trier toutes distinctes, donner une fonction exprimée uniquement à l'aide du nombre n de données à trier telle que : 0 son ordre de grandeur minore la complexité du tri par baquets ; 0 son ordre de grandeur peut être atteint. E] 17 -- Il s'agit dans cette question de modifier le tri par baquets pour que la complexité devienne de l'ordre de la somme du nombre des chiffres des données de la table. Cette nouvelle version du tri par baquets devra commencer directement par la mise dans les baquets sans nécessiter le calcul préalable du nombre maximum de chiffres des données ni l'utilisation d'un autre algorithme préparatoire. Pour définir un tel algorithme, donner son principe, justifier rapidement son exactitude et sa complexité, puis écrire ou réécrire en langage de programmation les fonctions ou procédures ajoutées ou modifiées ; on sera sans doute conduit à récrire distribuer et tri_baquet en les nommant distribuer_bis et tri_baquet_bis. FIN DU PROBLÈME D'ALGORITHMIQUE ET DE PROGRAMMATION Page 7 sur 10 Tournez la page S.V.P. Épreuve d'informatique 12. Problème sur les automates -- 1 h 15 mn environ Longueur discriminante de deux automates Deux automates 2 et fll'sont équivalents s'ils reconnaissent le même langage. S'ils ne sont pas équivalents, alors il existe des mots qui sont reconnus par l'un et pas par l'autre. La longueur minimum des mots qui ont cette propriété est dite discriminante. L'objet de ce problème est d'évaluer, par deux méthodes, un majorant de la longueur discriminante de 54 et ñ'en fonction des nombres d'états de 54 et fll'. Notations et terminologie Un alphabet 27 est un ensemble fini d'éléments appelés lettres. Un mot sur 27 est une suite finie de lettres de Z ; le mot vide est noté 8. On désigne par 27* l'ensemble des mots sur 2, y compris le mot vide. La longueur d'un mot m, notée Iml, est le nombre de lettres qui le composent. Un langage est une partie de Z*. Un automate flest décrit par une structure , où :

0 2 est un alphabet ;
0 Q est un ensemble fini et non vide appelé ensemble des états de fll ;

0 T ç; Q >< 2 >< Q est appelé l'ensemble des transitions ; étant donnée une transition (p, a, q) EUR T, on dit qu'elle va de l'état p à l'état q et qu'elle est d'étiquette a ; on pourra la noter p L q ; 0 I g Q est appelé ensemble des états initiaux de R; 0 F g Q est appelé ensemble des états finals de 2. On représente graphiquement l'automate fll ainsi : 0 un état p est figuré par un cercle marqué en son centre par p ; si p appartient à I, cela est figuré par une flèche entrante sans origine ; si un état q appartient à F, cela est figuré par une flèche sortante sans but ; 0 une transition (p, a, q) EUR T est figurée par une flèche allant de l'état p vers l'état q et étiquetée par la lettre a. Un calculcdeñest un chemin dela formepo --£-1----+pl _?!qu _a_L.pk, avecp,-l ip,--EUR Tpour 1 SiSk; po est l'origine du calcul, pk son extrémité. L'étiquette de c est le mot formé par la suite des étiquettes des transitions successives du chemin. Un calcul de % d'origine p, d'extrémité q et d'étiquette m est dit réussi si on a p EUR I et q EUR F. Un mot m EUR 2?" est reconnu par 2 s'il est l'étiquette d'un calcul réussi. Le langage reconnu par fil, noté L(fl), est l'ensemble des mots reconnus par 51 Deux automates % et ñ'sont dits équivalents si on a L(fll) : L(fl). L'automate 54 est dit déterministe si 1 ne contient qu'un élément et si, pour tout (p, a) EUR Q >< 2, il existe au plus un état q EUR Q avec (p, a, q) EUR T. L'automate Hest dit complet si et seulement si, pour tout p EUR Q et tout a EUR 2, il existe q EUR Q avec (p, a, q) EUR T. On rappelle que tout automate ayant n états est équivalent à un automate déterministe complet ayant au plus 2" états. PREMIÈRE PARTIE Approche naïve D 18 -- Soit 54 un automate, déterministe ou non déterministe, avec n états. Montrer que L(fi) est vide si et seulement s'il ne contient aucun mot de longueur inférieure ou égale à n -- 1. Cl 19 -- Soit fit un automate déterministe complet ayant n états. Donner un automate ayant aussi n états qui reconnaît L(fll) , le complémentaire dans 2* de L(fl). Justifier votre réponse. Page 8 sur 10 Épreuve commune 2004 D 20 -- Soient % et 2' deux automates utilisant le même alphabet 2 avec respectivement n et n' états. Donner un automate ayant n x n' états qui reconnaît L(fl) n L(fl'). Justifier votre réponse. D 21 --- Soient 54 et fll' deux aùtomates déterministes complets utilisant le même alphabet ): avec respectivement n et n' états. Montrer que si 2 et 54' ne sont pas équivalents, il existe un mot de longueur au plus n X n' -- 1 qui est reconnu par l'un et non par l'autre, i. e. la longueur discriminante de 2 et R' est inférieure ou égale à n >< n' -- l. [322 -- En déduire un majorant pour la longueur discriminante de deux automates non équivalents quelconques avec n et n' états respectivement. SECONDE PARTIE Approche plus fine L'objectif de cette partie est de démontrer que la longueur discriminante de deux automates déterministes non équivalents, avec n et n' états respectivement, est inférieure ou égale à n + n' -- l. D23 -- Montrer sur un exemple, avec un alphabet à une seule lettre, qu'il existe des automates déterministes H et 2' non équivalents et qui reconnaissent les mêmes mots de longueur strictement inférieure à n + n' -- 1, où n (resp. n') désigne le nombre d'états de 54 (resp. de R'). On introduit un ensemble de définitions et de notations. Soit fll : <2, Q, T, [, F> un automate déterministe avec n états. On identifie 
l'ensemble Q des états de 54 avec

l'ensemble {1, 2, , n} des n premiers entiers naturels non nuls de sorte que 
chaque état est identifié par un
entier compris entre l et n. On suppose que l'on a I = { 1}.
On note { el, ez, en} la base canonique de l'espace vectoriel R". Pour un 
entier i compris entre 1 et n, le

vecteur e,- est donc le vecteur de R" dont toutes les composantes sont nulles 
sauf la i -ième qui vaut 1. On note 0
le vecteur nul de R".

Pour chaque lettre a de l'alphabet S, on définit une application linéaire (pa 
de R" dans R" par :
pour tout i avec 1 S i S n : 0 s'il existej, 1 .<.j _