Centrale Informatique MP 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

- 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