Centrale Informatique MP 2008

Thème de l'épreuve Mots de Lukasiewicz, recherche de motifs
Principaux outils utilisés programmation récursive et itérative, dénombrement

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
              

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


- version du 7 mars 2008 12h26

INFORMATIQUE

i=1

Filière

MP

Soit u = (u1 , . . . , un ) un mot tel que

i=1

n
X

ui = -1. Demontrer qu'il existe

i=1

un unique entier i, 1 6 i 6 n, tel que (ui , ui+1 , . . . , un , u1 , . . . , 
ui-1 ) soit un mot de
Lukasiewicz. Ce mot est appele conjugue de u.
I.B.2) Ecrire une fonction conjugue qui calcule le conjugue d'un mot u = (u1 , 
. . . un )
n
X
verifiant
ui = -1.

I.B.1)

I.B - Denombrement

Cette derniere fonction adjonction realise l'adjonction d'une nouvelle cellule 
en tete
de liste (et retournant un pointeur sur ladite cellule). On ne demande pas de 
l'ecrire.

I.A.3) Montrer que si u et v sont des mots de Lukasiewicz, alors (+1) · u · v 
est un
mot de Lukasiewicz.
I.A.4) Reciproquement, montrer que tout mot de Lukasiewicz de longueur 
superieure
ou egale a 3 admet une decomposition unique de la forme (+1) · u · v, ou u et v 
sont
des mots de Lukasiewicz.
I.A.5) Ecrire une fonction decompose qui associe ce couple (u, v) a un mot de
Lukasiewicz de longueur superieure ou egale a 3. En Pascal, on pourra ecrire une
procedure qui modifie deux de ses parametres u et v passes par reference. On ne
demande pas de traiter les cas ou le mot fourni en entree ne serait pas de 
Lukasiewicz.
I.A.6) On souhaite calculer tous les mots de Lukasiewicz d'une longueur donnee.
Comparer les avantages d'une solution recursive appliquant le principe de la 
decomposition suggere par la question A.4), et celle d'une solution appliquant 
le meme
principe, mais pour laquelle on tabulerait les resultats intermediaires.
I.A.7) Ecrire une fonction obtenirLukasiewicz qui calcule la liste des mots de
Lukasiewicz de taille inferieure ou egale a un entier donne.
En Pascal, on dispose des types et fonction :
type
ptliste=^liste;
liste=record
valeur : string;
suivant:ptliste
end;
function adjonction(x:string; pt:ptliste):ptliste;

Page 1/3

I.A - Quelques proprietes
I.A.1) Donner tous les mots de Lukasiewicz de longueur 1, 2 et 3, puis tous ceux
de longueur paire.
I.A.2) Ecrire une fonction qui indique si un mot est de Lukasiewicz. Cette 
fonction
renverra une valeur booleenne. La fonction proposee devra imperativement avoir 
une
complexite (en termes d'operations elementaires) en O(n), avec n la longueur du 
mot
d'entree.

On note avec un point · la concatenation de deux mots, par exemple a · b.
- En Caml, un mot de Lukasiewicz sera represente par une liste d'entiers (int
list).
- En Pascal, un mot de Lukasiewicz sera represente par une chaine de caracteres
(string) composee de symboles '+' (pour +1) et '-' (pour -1). On rappelle
les operations suivantes :
· acceder au caractere numero i de la chaine c : c[i] (la numerotation commence 
a 1) ;
· obtenir la longueur d'une chaine c : length(c) ;
· extraire une chaine d'une sous-chaine : copy(cha^
ine, position, longueur).
Par exemple, copy('abcdef', 2, 3) retourne 'bcd' ;
· concatener deux chaines ou caracteres c1 et c2 pour obtenir une nouvelle
chaine : c1 + c2.
On demande d'indiquer le type de toutes les fonctions ecrites, que ce soit en 
Caml
ou en Pascal.

i=1

On appelle mots de Lukasiewicz les mots u = (u1 , u2 , . . . , un ) sur cet 
alphabet qui
verifient les deux proprietes suivantes :
n
k
X
X
ui = -1 et
ui > 0 pour 1 6 k 6 n - 1.

Dans cette partie, les mots consideres sont pris sur l'alphabet {-1, +1}.

Partie I - Mots de Lukasiewicz

Les deux parties sont independantes. Le candidat indiquera en tete de sa copie 
le
langage choisi : Caml ou Pascal.

Épreuve :

Concours Centrale - Supélec 2008

- version du 7 mars 2008 12h26

INFORMATIQUE

i=1

Filière

MP

Soit u = (u1 , . . . , un ) un mot tel que

i=1

n
X

ui = -1. Demontrer qu'il existe

i=1

un unique entier i, 1 6 i 6 n, tel que (ui , ui+1 , . . . , un , u1 , . . . , 
ui-1 ) soit un mot de
Lukasiewicz. Ce mot est appele conjugue de u.
I.B.2) Ecrire une fonction conjugue qui calcule le conjugue d'un mot u = (u1 , 
. . . un )
n
X
verifiant
ui = -1.

I.B.1)

I.B - Denombrement

Cette derniere fonction adjonction realise l'adjonction d'une nouvelle cellule 
en tete
de liste (et retournant un pointeur sur ladite cellule). On ne demande pas de 
l'ecrire.

I.A.3) Montrer que si u et v sont des mots de Lukasiewicz, alors (+1) · u · v 
est un
mot de Lukasiewicz.
I.A.4) Reciproquement, montrer que tout mot de Lukasiewicz de longueur 
superieure
ou egale a 3 admet une decomposition unique de la forme (+1) · u · v, ou u et v 
sont
des mots de Lukasiewicz.
I.A.5) Ecrire une fonction decompose qui associe ce couple (u, v) a un mot de
Lukasiewicz de longueur superieure ou egale a 3. En Pascal, on pourra ecrire une
procedure qui modifie deux de ses parametres u et v passes par reference. On ne
demande pas de traiter les cas ou le mot fourni en entree ne serait pas de 
Lukasiewicz.
I.A.6) On souhaite calculer tous les mots de Lukasiewicz d'une longueur donnee.
Comparer les avantages d'une solution recursive appliquant le principe de la 
decomposition suggere par la question A.4), et celle d'une solution appliquant 
le meme
principe, mais pour laquelle on tabulerait les resultats intermediaires.
I.A.7) Ecrire une fonction obtenirLukasiewicz qui calcule la liste des mots de
Lukasiewicz de taille inferieure ou egale a un entier donne.
En Pascal, on dispose des types et fonction :
type
ptliste=^liste;
liste=record
valeur : string;
suivant:ptliste
end;
function adjonction(x:string; pt:ptliste):ptliste;

Page 1/3

I.A - Quelques proprietes
I.A.1) Donner tous les mots de Lukasiewicz de longueur 1, 2 et 3, puis tous ceux
de longueur paire.
I.A.2) Ecrire une fonction qui indique si un mot est de Lukasiewicz. Cette 
fonction
renverra une valeur booleenne. La fonction proposee devra imperativement avoir 
une
complexite (en termes d'operations elementaires) en O(n), avec n la longueur du 
mot
d'entree.

On note avec un point · la concatenation de deux mots, par exemple a · b.
- En Caml, un mot de Lukasiewicz sera represente par une liste d'entiers (int
list).
- En Pascal, un mot de Lukasiewicz sera represente par une chaine de caracteres
(string) composee de symboles '+' (pour +1) et '-' (pour -1). On rappelle
les operations suivantes :
· acceder au caractere numero i de la chaine c : c[i] (la numerotation commence 
a 1) ;
· obtenir la longueur d'une chaine c : length(c) ;
· extraire une chaine d'une sous-chaine : copy(cha^
ine, position, longueur).
Par exemple, copy('abcdef', 2, 3) retourne 'bcd' ;
· concatener deux chaines ou caracteres c1 et c2 pour obtenir une nouvelle
chaine : c1 + c2.
On demande d'indiquer le type de toutes les fonctions ecrites, que ce soit en 
Caml
ou en Pascal.

i=1

On appelle mots de Lukasiewicz les mots u = (u1 , u2 , . . . , un ) sur cet 
alphabet qui
verifient les deux proprietes suivantes :
n
k
X
X
ui = -1 et
ui > 0 pour 1 6 k 6 n - 1.

Dans cette partie, les mots consideres sont pris sur l'alphabet {-1, +1}.

Partie I - Mots de Lukasiewicz

Les deux parties sont independantes. Le candidat indiquera en tete de sa copie 
le
langage choisi : Caml ou Pascal.

Épreuve :

Concours Centrale - Supélec 2008

- version du 7 mars 2008 12h26

INFORMATIQUE

i=1

Filière

MP

Soit u = (u1 , . . . , un ) un mot tel que

i=1

n
X

ui = -1. Demontrer qu'il existe

i=1

un unique entier i, 1 6 i 6 n, tel que (ui , ui+1 , . . . , un , u1 , . . . , 
ui-1 ) soit un mot de
Lukasiewicz. Ce mot est appele conjugue de u.
I.B.2) Ecrire une fonction conjugue qui calcule le conjugue d'un mot u = (u1 , 
. . . un )
n
X
verifiant
ui = -1.

I.B.1)

I.B - Denombrement

Cette derniere fonction adjonction realise l'adjonction d'une nouvelle cellule 
en tete
de liste (et retournant un pointeur sur ladite cellule). On ne demande pas de 
l'ecrire.

I.A.3) Montrer que si u et v sont des mots de Lukasiewicz, alors (+1) · u · v 
est un
mot de Lukasiewicz.
I.A.4) Reciproquement, montrer que tout mot de Lukasiewicz de longueur 
superieure
ou egale a 3 admet une decomposition unique de la forme (+1) · u · v, ou u et v 
sont
des mots de Lukasiewicz.
I.A.5) Ecrire une fonction decompose qui associe ce couple (u, v) a un mot de
Lukasiewicz de longueur superieure ou egale a 3. En Pascal, on pourra ecrire une
procedure qui modifie deux de ses parametres u et v passes par reference. On ne
demande pas de traiter les cas ou le mot fourni en entree ne serait pas de 
Lukasiewicz.
I.A.6) On souhaite calculer tous les mots de Lukasiewicz d'une longueur donnee.
Comparer les avantages d'une solution recursive appliquant le principe de la 
decomposition suggere par la question A.4), et celle d'une solution appliquant 
le meme
principe, mais pour laquelle on tabulerait les resultats intermediaires.
I.A.7) Ecrire une fonction obtenirLukasiewicz qui calcule la liste des mots de
Lukasiewicz de taille inferieure ou egale a un entier donne.
En Pascal, on dispose des types et fonction :
type
ptliste=^liste;
liste=record
valeur : string;
suivant:ptliste
end;
function adjonction(x:string; pt:ptliste):ptliste;

Page 1/3

I.A - Quelques proprietes
I.A.1) Donner tous les mots de Lukasiewicz de longueur 1, 2 et 3, puis tous ceux
de longueur paire.
I.A.2) Ecrire une fonction qui indique si un mot est de Lukasiewicz. Cette 
fonction
renverra une valeur booleenne. La fonction proposee devra imperativement avoir 
une
complexite (en termes d'operations elementaires) en O(n), avec n la longueur du 
mot
d'entree.

On note avec un point · la concatenation de deux mots, par exemple a · b.
- En Caml, un mot de Lukasiewicz sera represente par une liste d'entiers (int
list).
- En Pascal, un mot de Lukasiewicz sera represente par une chaine de caracteres
(string) composee de symboles '+' (pour +1) et '-' (pour -1). On rappelle
les operations suivantes :
· acceder au caractere numero i de la chaine c : c[i] (la numerotation commence 
a 1) ;
· obtenir la longueur d'une chaine c : length(c) ;
· extraire une chaine d'une sous-chaine : copy(cha^
ine, position, longueur).
Par exemple, copy('abcdef', 2, 3) retourne 'bcd' ;
· concatener deux chaines ou caracteres c1 et c2 pour obtenir une nouvelle
chaine : c1 + c2.
On demande d'indiquer le type de toutes les fonctions ecrites, que ce soit en 
Caml
ou en Pascal.

i=1

On appelle mots de Lukasiewicz les mots u = (u1 , u2 , . . . , un ) sur cet 
alphabet qui
verifient les deux proprietes suivantes :
n
k
X
X
ui = -1 et
ui > 0 pour 1 6 k 6 n - 1.

Dans cette partie, les mots consideres sont pris sur l'alphabet {-1, +1}.

Partie I - Mots de Lukasiewicz

Les deux parties sont independantes. Le candidat indiquera en tete de sa copie 
le
langage choisi : Caml ou Pascal.

Épreuve :

Concours Centrale - Supélec 2008

Demontrer que u est un mot de Lukasiewicz si et seulement si  (u) = (-1).

I.D.4)

Filière MP

II.B - Algorithme de Rabin-Karp
La presentation de l'algorithme de Rabin-Karp est faite dans le cas de 
l'alphabet
A0 = {0, 1, ..., 9}.
Un mot m  A0 peut etre vu naturellement comme un entier (m = 366 est dans
A0 ... mais aussi dans N).
II.B.1) La premiere idee de l'algorithme de Rabin-Karp est que si on cherche
p = 366 dans m = 97463667305, on va regarder les lettres de m par groupes de 3,
en initialisant un compteur a c = 974, et en « avancant » dans m en ajoutant a
chaque fois une nouvelle lettre, et en effacant la premiere de c. Dans notre 
exemple,
c passe d'abord a 746 puis 463. Plus formellement, lire la lettre  = mi+|p| 
dans m
en effacant mi change c en 10c +  - 10|p| mi . Si c = p, cela signifie que le 
motif p est
present en position i dans m.
On suppose dans cette premiere version de l'algorithme de Rabin-Karp que p est 
de
tres petite longueur, de sorte que le compteur c ne depassera jamais la valeur 
du
plus grand entier autorise par Caml ou Pascal.
On considere definie une fonction appelee numeral prenant comme entree un 
caractere de l'alphabet A0 et retournant la valeur entiere correspondante (par 
exemple
on associe l'entier 0 au caractere '0') :
· En Caml,
numeral : char -> int = 
· En Pascal, function numeral(a : char) : integer ;

II.A - Algorithme naif
II.A.1) Ecrire une fonction coincide prenant en entree deux chaines de 
caracteres
p et m, une position pos, et retournant true si p apparait en position pos dans
m (et false sinon). Cette fonction devra uniquement utiliser des comparaisons de
caracteres, sans utiliser sub_string (Caml) ou copy (Pascal). De plus, en cas de
reponse false, elle devra arreter les tests des que possible.
II.A.2) Ecrire une fonction recherche prenant en entree deux chaines de 
caracteres
p et m, et retournant la liste (dans n'importe quel ordre, et eventuellement 
vide) des
positions de p dans m.
En Pascal, on dispose comme dans la premiere partie des types ptliste,liste et
de la fonction adjonction, avec cette fois le champ valeur de type integer.
II.A.3) Evaluer la complexite (en termes de comparaisons de caracteres, et en
fonction de |p| et |m|) de la fonction precedente dans le pire des cas. On 
exhibera
un cas defavorable (en terme de complexite), avec p et m arbitrairement grands.

m = m1 ...mn , on dit que p apparait en position i dans m lorsque p = mi 
...mi+|p|-1 ,
avec |p| la longueur de p.

Dans ce probleme, nous allons etudier deux algorithmes de recherche de motif (en
general note p) dans un mot (en general note m). Par exemple, le motif p0=bra 
apparait deux fois dans le mot m0=abracadabra. Les programmes de recherche de
motif devront retourner la liste (eventuellement vide) des positions (au sens de
Caml/Pascal) du motif dans le mot. Dans l'exemple precedent, les programmes 
devront retourner une liste contenant les positions 1 et 8 en Caml ; 2 et 9 en 
Pascal.
C'est la position de la premiere lettre qui est prise en compte. Plus 
formellement, si
Page 2/3

Partie II - Recherche de motif

Ecrire une fonction rho qui calcule (u).
Ecrire une fonction rhoLim qui calcule  (u).

I.D.2)
I.D.3)

I.D.1) Justifier le fait que la suite (n (u))nN est constante au dela d'un 
certain
rang. La valeur limite de la suite (n (u))nN est notee  (u).

 (u) = u, si u ne contient pas de capsule
(u) = (u1 , . . . , ui-1 , ui+2 , . . . un ),

si (ui , ui+1 , ui+2 ) = (+1, -1, -1) est la premiere capsule de u

I.D - Capsules
On appelle capsule d'un mot u tout facteur de u de la forme (+1, -1, -1).
On definit sur {-1, 1} une fonction  dite de decapsulage :

I.C - Regularite

I.C.1) Montrer que le langage L = (+1)n (-1)n+1 , n  N n'est pas reconnaissable 
(implicitement dans la suite : « par un automate fini »).
I.C.2) Montrer que l'intersection de deux langages reconnaissables est un 
langage
reconnaissable.
I.C.3) Prouver le caractere reconnaissable ou non du langage constitue des mots
de Lukasiewicz.

I.B.3) En utilisant les resultats precedents, determiner le nombre de mots de 
Lukasiewicz de longueur 2n + 1.
On pourra utiliser ce resultat admis : « Si u et v sont deux mots non vides, 
les deux
propositions suivantes sont equivalentes :
· uv = vu
· il existe un mot w non vide et deux entiers k,  > 1 tels que u = wk et v = w »

INFORMATIQUE

Demontrer que u est un mot de Lukasiewicz si et seulement si  (u) = (-1).

I.D.4)

Filière MP

II.B - Algorithme de Rabin-Karp
La presentation de l'algorithme de Rabin-Karp est faite dans le cas de 
l'alphabet
A0 = {0, 1, ..., 9}.
Un mot m  A0 peut etre vu naturellement comme un entier (m = 366 est dans
A0 ... mais aussi dans N).
II.B.1) La premiere idee de l'algorithme de Rabin-Karp est que si on cherche
p = 366 dans m = 97463667305, on va regarder les lettres de m par groupes de 3,
en initialisant un compteur a c = 974, et en « avancant » dans m en ajoutant a
chaque fois une nouvelle lettre, et en effacant la premiere de c. Dans notre 
exemple,
c passe d'abord a 746 puis 463. Plus formellement, lire la lettre  = mi+|p| 
dans m
en effacant mi change c en 10c +  - 10|p| mi . Si c = p, cela signifie que le 
motif p est
present en position i dans m.
On suppose dans cette premiere version de l'algorithme de Rabin-Karp que p est 
de
tres petite longueur, de sorte que le compteur c ne depassera jamais la valeur 
du
plus grand entier autorise par Caml ou Pascal.
On considere definie une fonction appelee numeral prenant comme entree un 
caractere de l'alphabet A0 et retournant la valeur entiere correspondante (par 
exemple
on associe l'entier 0 au caractere '0') :
· En Caml,
numeral : char -> int = 
· En Pascal, function numeral(a : char) : integer ;

II.A - Algorithme naif
II.A.1) Ecrire une fonction coincide prenant en entree deux chaines de 
caracteres
p et m, une position pos, et retournant true si p apparait en position pos dans
m (et false sinon). Cette fonction devra uniquement utiliser des comparaisons de
caracteres, sans utiliser sub_string (Caml) ou copy (Pascal). De plus, en cas de
reponse false, elle devra arreter les tests des que possible.
II.A.2) Ecrire une fonction recherche prenant en entree deux chaines de 
caracteres
p et m, et retournant la liste (dans n'importe quel ordre, et eventuellement 
vide) des
positions de p dans m.
En Pascal, on dispose comme dans la premiere partie des types ptliste,liste et
de la fonction adjonction, avec cette fois le champ valeur de type integer.
II.A.3) Evaluer la complexite (en termes de comparaisons de caracteres, et en
fonction de |p| et |m|) de la fonction precedente dans le pire des cas. On 
exhibera
un cas defavorable (en terme de complexite), avec p et m arbitrairement grands.

m = m1 ...mn , on dit que p apparait en position i dans m lorsque p = mi 
...mi+|p|-1 ,
avec |p| la longueur de p.

Dans ce probleme, nous allons etudier deux algorithmes de recherche de motif (en
general note p) dans un mot (en general note m). Par exemple, le motif p0=bra 
apparait deux fois dans le mot m0=abracadabra. Les programmes de recherche de
motif devront retourner la liste (eventuellement vide) des positions (au sens de
Caml/Pascal) du motif dans le mot. Dans l'exemple precedent, les programmes 
devront retourner une liste contenant les positions 1 et 8 en Caml ; 2 et 9 en 
Pascal.
C'est la position de la premiere lettre qui est prise en compte. Plus 
formellement, si
Page 2/3

Partie II - Recherche de motif

Ecrire une fonction rho qui calcule (u).
Ecrire une fonction rhoLim qui calcule  (u).

I.D.2)
I.D.3)

I.D.1) Justifier le fait que la suite (n (u))nN est constante au dela d'un 
certain
rang. La valeur limite de la suite (n (u))nN est notee  (u).

 (u) = u, si u ne contient pas de capsule
(u) = (u1 , . . . , ui-1 , ui+2 , . . . un ),

si (ui , ui+1 , ui+2 ) = (+1, -1, -1) est la premiere capsule de u

I.D - Capsules
On appelle capsule d'un mot u tout facteur de u de la forme (+1, -1, -1).
On definit sur {-1, 1} une fonction  dite de decapsulage :

I.C - Regularite

I.C.1) Montrer que le langage L = (+1)n (-1)n+1 , n  N n'est pas reconnaissable 
(implicitement dans la suite : « par un automate fini »).
I.C.2) Montrer que l'intersection de deux langages reconnaissables est un 
langage
reconnaissable.
I.C.3) Prouver le caractere reconnaissable ou non du langage constitue des mots
de Lukasiewicz.

I.B.3) En utilisant les resultats precedents, determiner le nombre de mots de 
Lukasiewicz de longueur 2n + 1.
On pourra utiliser ce resultat admis : « Si u et v sont deux mots non vides, 
les deux
propositions suivantes sont equivalentes :
· uv = vu
· il existe un mot w non vide et deux entiers k,  > 1 tels que u = wk et v = w »

INFORMATIQUE

· · · FIN · · ·

Page 3/3

e) Comparer les complexites dans le pire des cas de l'algorithme de Rabin-Karp 
et
de l'algorithme naif.
f) En pratique, aura-t-on interet a prendre q plutot petit ou plutot grand ? Que
peut-on alors esperer pour le temps de calcul de la recherche des occurrences 
de p
dans m ?
On demande une justification informelle, le choix de l'entier q et l'evaluation 
de
temps moyen de calcul etant deux choses tres delicates . . .

q est suppose tel que les calculs arithmetiques modulo q sont d'un cout 
constant.
Le temps de calcul pendra donc en compte ces operations arithmetiques, et les
comparaisons de caracteres, du type mi = pj .

Lorsque c = p, on a c  p [q]. Mais reciproquement, lorsque c  p [q], on n'est
pas assure d'avoir c = p. On regarde alors (avec l'algorithme naif) si le 
facteur de m
correspondant au compteur c calcule est egal a p. Si c  p [q] mais c 6= p, on 
parle
de « fausse-position ».
a) Donner les valeurs successives de c lors de la recherche de p = 366 dans
m = 97463667305, avec q = 9.
b) Ecrire une fonction recherchant les positions d'un motif dans un mot, en 
appliquant l'algorithme de Rabin-Karp, avec un entier q donne en parametre.
c) Lors de la recherche de p = 0001000 dans m = 000000000 avec q = 1000, combien
de cas de fausse-position va-t-on rencontrer ?
d) Majorer le temps de calcul de la liste des positions de p dans m, en 
fonction de
|p| et |m| avec l'algorithme de Rabin-Karp.

a) Ecrire une fonction prenant en entree un mot m, une longueur , et retournant
la valeur initiale du compteur, calculee en lisant les  = |p| premieres lettres 
de m.
Dans l'exemple donne plus haut, sur l'entree (m, 3), la fonction doit retourner 
974.
b) Ecrire enfin une fonction prenant en entree un motif, un mot (suppose de 
taille
superieure au motif), et calculant la liste des positions dans m ou le motif p 
est
present.
II.B.2) L'hypothese quant a la longueur « faible » de p etant tres restrictive, 
on
modifie l'algorithme precedent en choisissant un entier q modulo lequel on 
calculera
c. En lisant la lettre  = mi+| p| et en effacant mi , le nouveau compteur 
devient donc

c  10c +  - 10|p| mi [q].

INFORMATIQUE

Filière MP

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique MP 2008 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par
Vincent Danjean (Enseignant-chercheur en école d'ingénieur) et Vincent 
Puyhaubert
(Professeur en CPGE).

Ce sujet comporte deux problèmes indépendants.
· Le premier problème, assez long, introduit la notion de mots de Lukasiewicz.
Il s'agit de mots u sur l'alphabet {-1, +1} dont la somme des caractères vaut -1
et dont la somme partielle des k premiers caractères est positive ou nulle pour
tout k de 1 à |u|-1. Ces mots servent entre autres à représenter le comportement
d'une pile, dans laquelle on peut empiler et dépiler un caractère. Les sommes
partielles représentent alors la hauteur de pile à un moment donné. Le fait
que celles-ci doivent rester positives ou nulles signifie qu'on ne peut retirer 
un
élément à une pile vide. Une somme totale égale à -1 indique que l'on a dépilé
le « fond de pile » et que le calcul est terminé.
Dans ce problème, on s'intéresse à des propriétés internes des mots de 
Lukasiewicz, à leur dénombrement, à la reconnaissabilité de l'ensemble des mots 
de
Lukasiewicz ainsi qu'à une caractérisation fonctionnelle de ces mots. C'est un
problème assez technique avec de nombreux programmes, essentiellement des
fonctions récursives qui utilisent des listes d'entiers. Des questions 
délicates se
concentrent dans la partie B. Les preuves nécessitent alors de l'habileté dans
les manipulations de mots sur un alphabet, telles que le découpage ou la 
concaténation. Les parties B, C et D sont indépendantes et seule la partie C 
donne
l'occasion de travailler avec des automates.
· Le deuxième problème, plus court, s'intéresse au thème classique de la 
recherche
de motif dans un mot. Après l'écriture de l'algorithme naïf, le sujet étudie 
l'algorithme de Rabin-Karp, qui utilise des opérations arithmétiques sur les 
lettres.
C'est une partie facile demandant des programmes simples en style impératif.
Quelques questions qualitatives, sans doute discriminantes, permettaient de
détecter les candidats comprenant bien les idées du problème.
Pour conclure, il s'agit d'un sujet qui permet de bien réviser l'intégralité des
notions du programme, même si pour la plupart elles ne font l'objet que de 
quelques
questions.

Les conseils du jury
Le rapport du jury souligne que « le niveau moyen des candidats a semblé en
baisse ». Il cite deux raisons principales récurrentes. La première concerne la
programmation : ils rappellent ainsi quelques conseils à suivre dont « indenter
correctement ; ne pas commencer un programme en bas de page ; donner
des noms expressifs aux variables et fonctions annexes ». La deuxième est
relative aux automates, dont ils relèvent « une très forte incompréhension
pour la grande majorité des candidats » : le jury attend par exemple que
« les futurs candidats comprennent qu'un automate fini est autre chose qu'un
quintuplet » et relève la mauvaise connaissance du lemme de l'étoile.

Indications
I.A.2 Utiliser une fonction récursive et un filtrage afin de parcourir la liste 
tout
en calculant la somme de ses termes.
I.A.3 Noter u = (u1 , . . . , un ) et v = (v1 , . . . , vm ) les deux mots de 
Lukasiewicz et
déterminer la somme des lettres de chaque sous-mot de w = (+1) · u · v en
distinguant trois cas.
I.A.4 Démontrer ce résultat en deux temps : d'abord l'existence, ensuite 
l'unicité.
Il faut avant tout trouver où réaliser la coupure entre le sous-mot u et le 
sousmot v tels que x = (+1) · u · v : une idée pourrait être d'utiliser 
l'indice i
i
P
minimal vérifiant
xk = 0.
k=1

I.A.5 Utiliser une fonction récursive parcourant la liste en mémorisant dans une
autre liste les premiers termes déjà lus.
I.A.6 Réfléchir aux appels récursifs nécessaires dans une méthode récursive.
I.A.7 C'est évidemment la méthode itérative qu'il faut choisir, comme vous avez
dû le constater dans la question précédente. Construire progressivement un
tableau contenant tous les mots de Lukasiewicz de taille inférieure à n :
il suffira de fusionner certaines cases du tableau pour en remplir d'autres...
I.B.1 Il s'agit du même type de preuve qu'à la question I.A.4.
I.B.3 Il faut dans un premier temps bien comprendre le lien qui existe entre
les mots de Lukasiewicz et l'ensemble des mots dont la somme des lettres
vaut -1. Par l'opération de conjugaison, on a un lien très précis que l'on
peut exploiter ici.
I.C.1 Il s'agit d'une application directe du lemme de l'étoile (également appelé
lemme de pompage).
I.C.2 À l'aide d'un automate reconnaissant un langage L1 et d'un automate 
reconnaissant un langage L2 , il faut construire un automate reconnaissant
L1  L2 .
I.C.3 Appliquer les deux questions précédentes en essayant d'écrire le langage L
comme intersection du langage contenant les mots de Lukasiewicz et d'un
langage reconnaissable à déterminer.
I.D.1 Considérer la suite des longueurs de n (u).
I.D.2 Il s'agit d'une recherche de motifs : une fonction récursive fait ici 
l'affaire si
on l'écrit convenablement.
I.D.4 Commencer par démontrer les deux lemmes suivants
· u est un mot de Lukasiewicz  (u) est un mot de Lukasiewicz
· le seul mot de Lukasiewicz sans capsule est (-1)
et conclure.
II.A.1 On dispose en Caml de la fonction string_length pour obtenir la longueur
d'une chaîne de caractères. Il suffit de vérifier caractère par caractère s'il y
a égalité des chaînes.
II.A.3 Calculer d'abord la complexité de la fonction coincide.
II.B.2.d Attention ! Les opérations élémentaires à considérer ici sont les 
comparaisons
de caractères et les calculs modulo q.

I. Mots de Lukasiewicz
I.A

Quelques propriétés

I.A.1 Le seul mot de Lukasiewicz de longueur 1 est évidemment (-1). Si (u1 , u2 
)
est un mot de Lukasiewicz alors nécessairement u1 > 0 donc u1 = 1 et ainsi
u2 = -1 - u1 = -2, ce qui est impossible. Donc il n'y a pas de mot de 
Lukasiewicz de longueur 2. De même, si (u1 , u2 , u3 ) est un mot de 
Lukasiewicz, u1 = 1 ;
u2 = 1 impliquerait u3 = -3 ce qui est impossible donc u2 = -1 et alors u3 = -1.
Par conséquent le seul mot de Lukasiewicz de longueur 3 est (1, -1, -1).
n
P
Si (u1 , . . . , un ) est un mot de Lukasiewicz avec n pair, alors
ui est une somme
i=1

d'un nombre pair d'entiers impairs : elle est donc paire et ne peut être égale 
à -1.
Il n'y a aucun mot de Lukasiewicz de longueur paire.

Pour mieux comprendre la notion de mot de Lukasiewicz, on peut essayer
de lui donner une interprétation graphique. À tout mot u = (u1 , . . . , un ),
on associe une ligne polygonale dans le demi-plan des abscisses positives.
Cette ligne polygonale démarre en l'origine : à chaque caractère lu, la ligne
passe à l'unité suivante en abscisse et elle le fait en montant d'une unité s'il
s'agit du caractère (+1), en descendant sinon. Comme un bon dessin vaut
mieux qu'un long discours, voilà cette représentation graphique pour le mot
(1, -1, 1, 1, -1, 1, -1, -1, -1).

On voit alors qu'être un mot de Lukasiewicz est équivalent à avoir une
ligne polygonale allant de l'origine à un point d'ordonnée -1, en restant
constamment au-dessus de la droite des abscisses, sauf au dernier caractère.
Dans la littérature liée à la combinatoire, on parle souvent de chemins à pas
(1, 1) et (1, -1).

I.A.2 Appliquons directement la définition pour créer cette fonction de test de
type int list -> bool. L'idée est de parcourir le mot en entrée avec une 
fonction
récursive auxiliaire qui stocke le reste du mot encore à lire et la somme des 
premiers
éléments déjà lus. Si à un moment, cette somme devient négative, le programme
renvoie faux. À la fin, on teste simplement si la somme totale vaut -1. Cette 
fonction
est bien de complexité linéaire en la longueur du mot d'entrée.

let test_Lukasiewicz u =
let rec test_positif v somme =
match v with
[] -> (somme = -1);
|v1::v' -> if (somme >= 0)
then test_positif v' (somme+v1)
else false
in test_positif u 0 ;;
I.A.3 Soient u = (u1 , . . . , un ) et v = (v1 , . . . , vm ) deux mots de 
Lukasiewicz.
Notons w = (+1) · u · v. Pour simplifier, notons w = (w1 , . . . , wn+m+1 ) 
avec w1 = +1,
puis (w2 , . . . , wn+1 ) = u, (wn+2 , . . . , wn+m+1 ) = v. On vérifie, en 
suivant la définition, que w est un mot de Lukasiewicz.
·
·

n+m+1
P

n
P

i=1

i=1

wi = w1 +

ui +

m
P

vi = +1 - 1 - 1 = -1

i=1

 w1 = +1 > 0
 pour tout k compris entre 2 et n,

k
P

wi = +1 +

i=1

n+1
P

n
P

i=1

i=1

wi = +1 +

k-1
P

ui > 0

i=1

ui = +1 - 1 = 0 > 0

 pour tout k compris entre n + 2 et n + m,

k
P

wi = +1 - 1 +

i=1

k-n-1
P

vi > 0

i=1

Si u et v sont deux mots de Lukasiewicz, (+1) · u · v est un mot de Lukasiewicz.
La propriété établie se vérifie aisément graphiquement. Considérons par
exemple les deux mots u = (1, -1, 1, -1, -1) et v = (1, 1, -1, -1, -1) 
représentés par les chemins suivants
u

v

Alors (+1) · u · v se représente par
u
v

k
P
On voit que le mot v commence lorsque la somme partielle
wi s'annule
pour la deuxième fois, la première fois se trouvant à l'origine. i=1