Mines Informatique optionnelle MP 2017

Thème de l'épreuve Langages unaires. Exponentiation rapide.
Principaux outils utilisés récursivité, automates, langages
Mots clefs exponentiation rapide, puissance, langage unaire, écriture binaire inverse

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


A2017 ­ INFO MP

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT Atlantique (ex Télécom Bretagne),
ENSAE PARISTECH.
Concours Centrale-Supelec (Cycle International),
Concours Mines-Télécom, Concours Commun TPE/EIVP.
CONCOURS 2017
ÉPREUVE D'INFORMATIQUE MP
Durée de l'épreuve : 3 heures
L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement les candidats de la filière MP.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

INFORMATIQUE - MP
L'énoncé de cette épreuve comporte 7 pages de texte.

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

Épreuve d'informatique 2017

Première partie : langages et automates
On s'intéresse aux langages sur l'alphabet S = {a} ; un tel langage est dit 
unaire. Un automate
reconnaissant un langage unaire sera dit unaire. Lorsqu'on dessinera un 
automate unaire, il ne
sera pas utile de faire figurer les étiquettes des transitions, toutes ces 
étiquettes étant
l'étiquette a. C'est ce qui est fait dans cet énoncé.
Dans un automate unaire, on appelle chemin une suite q1, ..., qp d'états telle 
que, pour i
compris entre 1 et p, il existe une transition de qi ­ 1 vers qi ; on dit qu'il 
s'agit d'un chemin de
q1 à qp. On appelle circuit un chemin q1, ..., qp tel qu'il existe une 
transition de qp vers q1.
Dans cet exercice, tous les automates considérés seront finis et auront un et 
un seul état initial.
On dit qu'un automate est émondé si, pour tout état q, il existe d'une part un 
chemin de l'état
initial à q et d'autre part un chemin de q à un état final.
On rappelle qu'un langage non vide est rationnel si et seulement s'il est 
reconnu par un
automate ou encore si et seulement s'il est reconnu par un automate 
déterministe émondé.
Soient a et b deux entiers positifs ou nuls. On note L(a, b ) le langage unaire 
défini par :
L(a, b ) = {aak + b | k entier positif ou nul}.
r 1 ­ Donner sans justification une condition nécessaire et suffisante pour que 
L(a, b)
soit fini. Dans le cas où cette condition est satisfaite, donner sans 
justification le
cardinal de L(a, b ).
r 2 ­ On considère l'automate A1 ci-dessous. Indiquer sans justification deux 
entiers
a1, b 1 tels que A1 reconnaisse le langage L(a1, b 1).
0

1

4

3

2

Automate A1
r 3 ­ On considère l'automate A2 ci-dessous :

1

2

3

4

5

6

0

Automate A2
On note L2 le langage reconnu par A2. Indiquer sans justification quatre 
entiers a2, b 2, a3,
b3 tels que A2 reconnaisse le langage L2 = L(a2, b 2) È L(a3, b 3).

Page 1 sur 7

Épreuve d'informatique 2017
r 4 ­ Construire un automate déterministe émondé A3 en appliquant la procédure 
de
déterminisation à l'automate A2.!
r 5 ­ En s'appuyant sur l'automate A3, indiquer sans justification cinq entiers 
a4, b 4,
b5, b 6, b 7, tels que A3 reconnaisse le langage L3 = L(a4, b 4) È L(a4, b 5) È 
L(a4, b 6) È
L(a4, b 7) (remarque : le langage L3 est égal par ailleurs au langage L2).
On dit ci-dessous qu'un automate est de la forme F si, en omettant les états 
finals, il peut se
tracer selon le schéma ci-dessous :

q0

...

qr­1

qr

...

qs

Le chemin q0, ..., qr ­ 1 peut être vide, auquel cas on a r = 0. Le circuit qr 
, ..., qs ne doit pas
être vide mais on peut avoir r = s avec une transition de l'état qr vers 
lui-même (un tel circuit
s'appelle aussi une boucle). On constate que les automates A1 et A3 sont de la 
forme F, mais
non A2.
r 6 ­ Dessiner sans justification un automate de la forme F qui reconnaît le 
langage
L(1, 2). On fera figurer le ou les état(s) final(s).
ATTENTION : on ne demande aucune justification mais uniquement de tracer un
automate de la forme F en choisissant correctement les longueurs du chemin et du
circuit et en ajoutant le ou les état(s) final(s).
r 7 ­ Dessiner un automate de la forme F qui reconnaît le langage L(2, 3) È 
L(5, 2).
On fera figurer le ou les état(s) final(s). Comme à la question précédente, on 
ne
demande aucune justification.
r 8 ­ En s'inspirant de la réponse à la question précédente, décrire sans 
justification
un automate de la forme F qui reconnaît le langage L(2, 3) Ç L(5, 2). Indiquer 
deux
entiers a et b tels qu'on ait la relation : L(2, 3) Ç L(5, 2) = L(a, b ).
r 9 ­ Montrer qu'un automate déterministe émondé qui reconnaît un langage unaire
rationnel infini est de la forme F. Donner une condition nécessaire et 
suffisante portant
sur les états finals pour qu'un automate de la forme F reconnaisse un langage 
infini.
r 10 ­ Soit L un langage rationnel unaire infini. En s'appuyant sur la question
précédente, montrer qu'il existe deux entiers a   et b   tels que L contient
L(a, b ).
r 11 ­ On considère une suite (un)n ³ 0 de nombres entiers positifs ou nuls. On
suppose que la suite (un + 1 ­ un)n ³ 0 est positive et strictement croissante. 
Soit L le
langage défini par : L = {aun | n ³ 0}. En utilisant la question précédente, 
montrer que
L n'est pas rationnel.
r 12 ­ Montrer que le langage L défini par L = {an2 | n ³ 0} n'est pas 
rationnel.
Page 2 sur 7

Épreuve d'informatique 2017

Seconde partie : algorithmique et programmation
Préliminaire concernant la programmation
Il faudra coder des fonctions à l'aide du langage de programmation Caml, tout 
autre langage
étant exclu. Lorsque le candidat écrira une fonction, il pourra faire appel à 
d'autres fonctions
définies dans les questions précédentes ; il pourra aussi définir des fonctions 
auxiliaires.
Quand l'énoncé demande de coder une fonction, il n'est pas nécessaire de 
justifier que celle-ci
est correcte, sauf si l'énoncé le demande explicitement. Enfin, si les 
paramètres d'une
fonction à coder sont supposés vérifier certaines hypothèses, il ne sera pas 
utile dans l'écriture
de cette fonction de tester si les hypothèses sont bien vérifiées.
Dans les énoncés de l'exercice, un même identificateur écrit dans deux polices 
de caractères
différentes désignera la même entité, mais du point de vue mathématique pour la 
police en
italique (par exemple n) et du point de vue informatique pour celle en romain 
(par
exemple !).
On ne se préoccupera pas d'un éventuel dépassement du plus grand entier 
représentable.
On pourra utiliser les fonctions suivantes.
· La fonction "#$%&"' ajoute une valeur en début d'une liste dont la référence 
est
passée en paramètre ; par exemple si on a :
&"()&%*(")+)'",)-./)0/)12//)
après l'instruction :)"#$%&"')&%*(")3//)
4&%*(" vaut -3/)./)0/)125)
· La fonction 6"$%&"' retire la valeur du début d'une liste dont la référence 
est passée
en paramètre et renvoie la valeur retirée ; par exemple si on a :
&"()&%*(")+)'",)-./)0/)12//)
après l'instruction :)&"()78&)+)6"$%&"')&%*("//)
4&%*(" vaut [0/)12 et 78& vaut .5)
Cette fonction ne doit être utilisée que si la liste dont la référence est 
passée en
paramètre n'est pas vide.
· La fonction &9!:;";' renvoie la longueur d'une liste passée en paramètre.
· La fonction %!7"'*" reçoit en paramètre une liste et renvoie une nouvelle 
liste qui
est l'inverse de la première. Par exemple, si on a :
&"()&%*(")+)-./)0/)12//
l'instruction %!7"'*")&%*("//)renvoie la liste -1/)0/).2.
On considère un ensemble U muni d'une loi de composition interne associative 
appelée
multiplication et possédant un élément neutre pour cette loi noté e. Cette 
multiplication est
notée avec le signe ×.
Par exemple, U peut être l'ensemble des entiers ou des réels munis de la 
multiplication
usuelle, l'élément neutre étant 1. L'ensemble U peut aussi être l'ensemble des 
matrices
carrées booléennes (respectivement d'entiers, de réels) d'une même dimension d 
avec le
produit usuel comme multiplication, l'élément neutre étant la matrice identité 
booléenne
(respectivement entière, réelle) de dimension d.
Soit a un élément de U et soit n un entier positif ou nul. On définit an de la 
façon suivante :
· a0 = e,
· si n  1, an = an ­ 1 × a.
La multiplication étant associative, si i et j sont deux entiers positifs ou 
nuls de somme égale à
n, on a : an = ai × aj.

Page 3 sur 7

Épreuve d'informatique 2017
Un élément a de U et un entier n supérieur ou égal à 1 étant donnés, on cherche 
à calculer an
en s'intéressant au nombre de multiplications effectuées.
Dans toute la suite, a et n désignent respectivement un élément quelconque de U 
et un entier
strictement positif.
Exemple 1 : n = 14. On peut calculer a14 en multipliant 13 fois l'élément a par 
lui-même. On
effectue ainsi 13 multiplications.
Exemple 2 : n = 14. On peut calculer a14 en calculant a2 par a2 = a × a, puis 
a3 par a3 = a2 × a
puis a6 par a6 = a3 × a3, puis a7 par a7 = a6 × a, puis enfin a14 = a7 × a7. On 
a ainsi obtenu le
résultat en effectuant 5 multiplications.
Exemple 3 : n = 14. On peut aussi calculer a14 en calculant a2 par a2 = a × a, 
puis a4 par
a4 = a2 × a2, puis a6 par a6 = a2 × a4 puis a8 par a8 = a4 × a4, puis a14 par 
a14 = a6 × a8. On a
ainsi obtenu le résultat en effectuant encore 5 multiplications.
L'objectif est de déterminer des algorithmes qui effectuent peu de 
multiplications. Soit x un
nombre réel positif ; on note ëx û la partie entière par défaut de x et éx ù sa 
partie entière par
excès.
On appelle suite pour l'obtention de la puissance n toute suite non vide 
croissante d'entiers
distincts (n0, n1, ..., nr) telle que :
· n0 = 1,
· nr = n,
· pour tout indice k vérifiant 1  k  r, il existe deux entiers i et j distincts 
ou non vérifiant
0  i  k ­ 1, 0  j  k ­ 1 et nk = ni + nj (la paire {i, j} n'est pas 
nécessairement unique).
À une suite pour l'obtention de la puissance n correspond une suite de 
multiplications
conduisant au calcul de an. Par exemple, la suite (1, 2, 4, 6, 7, 12, 19) 
correspond au calcul de
a19 en faisant les 6 multiplications suivantes : a2 = a × a, a4 = a2 × a2, a6 = 
a2 × a4,
a7 = a × a6, a12 = a6 × a6, a19 = a7 × a12.
Réciproquement, considérons un calcul de an dans lequel on fait en sorte 
d'ordonner les
multiplications pour que les puissances calculées soient d'exposants croissants 
; on peut
associer à ce calcul une suite pour l'obtention de la puissance n.
À l'exemple 1 est associée la suite (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 
14), de longueur 14.
À l'exemple 2 est associée la suite (1, 2, 3, 6, 7, 14), de longueur 6.
À l'exemple 3 est associée la suite (1, 2, 4, 6, 8, 14), de longueur 6.
Le nombre de multiplications correspondant à une suite pour l'obtention de la 
puissance n est
égal à la longueur de la suite diminuée de 1.
r 13 ­ Montrer que tout calcul de an qui n'utilise que des multiplications 
nécessite un
nombre de multiplications au moins égal à élog 2 nù . Donner une famille 
infinie de
valeurs de n qui peuvent être calculées en effectuant exactement ce nombre de
multiplications ; justifier la réponse.
On considère un algorithme appelé par_division ayant pour objectif le calcul de 
an. Cet
algorithme s'appuie sur le principe récursif suivant :

Page 4 sur 7

Épreuve d'informatique 2017
si n vaut 1, alors an vaut a,
sinon
· on calcule la partie entière par défaut, notée q, de n / 2 ,
· on calcule par l'algorithme par_division la valeur de b = aq,
· si n est pair, alors an = b × b,
sinon an = (b × b) × a.
Ainsi, pour obtenir a14, l'algorithme par_division fait appel au calcul de a7 
qui fait appel au
calcul de a3 (pour obtenir a6 en multipliant a3 par a3 puis a7 en multipliant 
a6 par a) qui fait
appel au calcul de a1 (pour obtenir a2 puis a3). Les différentes puissances 
calculées sont les
puissances 1, 2, 3, 6, 7 et 14. On constate ainsi que la suite pour l'obtention 
de la puissance 14
correspondant à l'algorithme par_division est la suite (1, 2, 3, 6, 7, 14), de 
longueur 6. De
même, la suite pour l'obtention de la puissance 19 correspondant à l'algorithme 
par_division
est la suite (1, 2, 4, 8, 9, 18, 19) de longueur 7.
r 14 ­ Calculer (sans justification) la suite correspondant à l'algorithme 
par_division
successivement :
· pour l'obtention de la puissance 15 ;
· pour l'obtention de la puissance 16 ;
· pour l'obtention de la puissance 27 ;
· pour l'obtention de la puissance 125.
Dans chaque cas, indiquer la longueur de la suite obtenue.
r 15 ­ Écrire en Caml la fonction nommée $8'<6%7%*%9! qui calcule la suite pour
l'obtention de la puissance n correspondant à l'algorithme par_division. Si ! 
est une
valeur entière strictement positive, $8'<6%7%*%9!)!)renvoie une liste contenant 
la
suite pour l'obtention de la puissance n.
r 16 ­ Montrer que l'algorithme par_division pour l'obtention de la puissance n
effectue au plus 2 ´ ëlog 2 nû multiplications. Montrer que ce nombre est 
atteint pour
un nombre infini de valeurs de n.
On considère maintenant un algorithme appelé par_decomposition_binaire dont 
l'objectif est
aussi le calcul de an. Cet algorithme utilise la décomposition d'un entier 
suivant les
puissances de 2. L'algorithme est expliqué ci-dessous à l'aide d'exemples.
· Soit n = 14. On décompose 14 selon les puissances de 2 : 14 = 2 + 4 + 8. On a 
donc :
a14 = (a2 × a4) × a8, ce qui conduit à calculer les puissances de a d'exposants 
2, 4, 8
mais aussi 6 et 14 ; la suite pour l'obtention de la puissance 14 correspondant 
à cet
algorithme est la suite (1, 2, 4, 6, 8, 14).
·
Soit n = 18. On a : 18 = 2 + 16, ce qui implique : a18 = a2 × a16. L'algorithme 
calcule
les puissances d'exposants 2, 4, 8, 16 puis 18 ; la suite pour l'obtention de 
la puissance
18 correspondant à cet algorithme est : (1, 2, 4, 8, 16, 18).
·
Soit n = 101. On a : 101 = 1 + 4 + 32 + 64. L'algorithme calcule a101 en 
utilisant les
multiplications impliquées par la formule : a101 = ((a × a4) × a32) × a64 ; on 
calcule les
puissances 2, 4, 5 (pour a × a4 = a5), 8, 16, 32, 37 (pour a5 × a32 = a37), 64 
et 101
(pour a37 × a64 = a101) ; la suite pour l'obtention de la puissance 101 
correspondant à
cet algorithme est : (1, 2, 4, 5, 8, 16, 32, 37, 64, 101).

Page 5 sur 7

Épreuve d'informatique 2017
De manière générale, l'algorithme procède en écrivant la décomposition unique 
de n comme
une somme de puissances croissantes du nombre 2, et calcule la valeur cible de 
an en
effectuant les produits correspondant aux sommes partielles de cette somme.
r 17 ­ Calculer (sans justification) la suite correspondant
par_decomposition_binaire successivement :
· pour l'obtention de la puissance 15 ;
· pour l'obtention de la puissance 16 ;
· pour l'obtention de la puissance 27 ;
· pour l'obtention de la puissance 125.
Dans chaque cas, indiquer la longueur de la suite obtenue.

à

l'algorithme

On considère la décomposition de n suivant les puissances croissantes du nombre 
2 :
n = c0 + c1 × 2 + ... + ci × 2i + ... + ck × 2k,
où, pour i vérifiant 0  i < k, le coefficient ci vaut 0 ou 1 et ck vaut 1.
On appelle écriture binaire inverse de n la suite (c0, c1, ..., ci, ..., ck).
Par exemple, l'écriture binaire inverse de l'entier 14 est (0, 1, 1, 1), celle 
de l'entier 18 est
(0, 1, 0, 0, 1) et celle de l'entier 101 est (1, 0, 1, 0, 0, 1, 1).
r 18 ­ Écrire en Caml une fonction nommée =%!8%'"<%!7"'*" qui calcule
l'écriture binaire inverse d'un nombre donné. Si ! est une valeur entière 
strictement
positive, alors =%!8%'"<%!7"'*") ! renvoie une liste contenant l'écriture 
binaire
inverse de n.
r 19 ­ Écrire en Caml la fonction $8'<6">9#$9*%(%9!<=%!8%'" qui calcule la
suite pour l'obtention de la puissance n correspondant à l'algorithme
par_decomposition_binaire. Si ! est une valeur entière strictement positive,
$8'<6">9#$9*%(%9!<=%!8%'")! renvoie une liste contenant la suite cherchée.
r 20 ­ On suppose que l'on a n = 3k, où k est un entier positif ou nul. En 
utilisant la
formule : 3k = 3k ­ 1 + 2 ´ 3k ­ 1, montrer qu'il existe une suite pour 
l'obtention de la
puissance n de longueur 2k + 1. Indiquer une telle suite correspondant à n = 27 
;
comparer la longueur de cette suite à la longueur de la suite correspondant à
l'algorithme par_division.
r 21 ­ Soit k un entier positif ou nul. Écrire en Caml une fonction *;%("<1
calculant une suite de longueur 2k + 1 pour l'obtention de la puissance 3k. On
s'appuiera pour cela sur la question précédente. Si ? est une valeur entière 
positive ou
nulle, *;%("<1)?)renvoie une liste contenant la suite cherchée.
r 22 ­ On suppose que l'on a n = 5k, où k est un entier positif ou nul 
quelconque.
Montrer qu'il existe une suite pour l'obtention de la puissance n de longueur 
3k + 1.
Indiquer la suite correspondant à n = 125 ; comparer la longueur de cette suite 
à la
longueur de la suite correspondant à l'algorithme par_division.
r 23 ­ Donner une suite de longueur 6 pour l'obtention de la puissance 15. Qu'en
déduire quant aux algorithmes par_division et par_decomposition_binaire étudiés
précédemment ?
Page 6 sur 7

Épreuve d'informatique 2017
r 24 ­ On considère un tableau (ou vecteur) T, indicé à partir de 0, contenant 
une
suite pour l'obtention d'une certaine puissance positive n. Soit k un entier 
compris
entre 1 et la longueur de T diminuée de 1. Soit val la valeur contenue dans T à 
l'indice
k. On sait que val est la somme de deux valeurs du tableau T situées à des 
indices
(éventuellement confondus, éventuellement non uniques) strictement inférieurs à 
k. Il
s'agit de programmer une fonction nommée >@"'>@"'<%!6%>" qui détermine ces
deux indices. Par exemple, si tableau T contient les valeurs 1, 2, 3, 4, 7, 14, 
17, 31, la
longueur du tableau vaut 8, et, si k vaut 6, alors val vaut 17 et la fonction
>@"'>@"'<%!6%>" doit renvoyer les indices 2 et 5 correspondant aux valeurs 3 et
14 du tableau ; si, avec ce même tableau, k vaut 1, la fonction doit renvoyer 0 
et 0.
Écrire en Caml la fonction >@"'>@"'<%!6%>" telle que, si :
· A code un vecteur contenant une suite pour l'obtention d'une certaine
puissance positive n (la valeur de n est inutile pour l'écriture de la 
fonction),
· ? code un entier compris entre 1 et la longueur de A diminuée de 1,
alors >@"'>@"'<%!6%>" A ? renvoie une liste de deux entiers contenant les deux
indices cherchés, par ordre croissant. Indiquer (sans justification) la 
complexité C(k)
de cette fonction.
r 25 ­ Dans cette question, U est l'ensemble des réels. Soit x un nombre réel
quelconque et soit un tableau (ou vecteur) T contenant une suite pour 
l'obtention d'une
certaine puissance positive n. Écrire en Caml une fonction $;%**8!>" qui 
calcule la
valeur de xn en utilisant le tableau T. Si B est une valeur de type ,&98( et A 
code un
vecteur contenant une suite pour l'obtention d'une certaine puissance positive 
n, alors
$;%**8!>")B)A)renvoie la valeur de xn en effectuant des multiplications suivant 
la
suite représentée par T.
Indications :
· on utilisera la fonction >@"'>@"'<%!6%>" de la question précédente); en
appelant h la longueur de T, la complexité de la fonction $;%**8!>" devra
nécessairement être en O(h ´ C(h)) (il n'est pas demandé de justifier cette
complexité) ;
· si A est un vecteur, 7">(<&"!:(@)A)donne la longueur de A ;
· l'opérateur)C5)permet de faire le produit de deux valeurs de type ,&98(.
r 26 ­ Décrire le principe d'une fonction nommée suite_optimale permettant
d'exhiber une suite de longueur minimale pour l'obtention de la puissance n, en
effectuant une énumération exhaustive des suites possibles. Cette fonction devra
utiliser une fonction récursive nommée suite_optimale_rec dont on donnera aussi 
le
principe.
r 27 ­ Écrire en Caml les fonctions *;%("<9$(%#8&"<'"> et
*;%("<9$(%#8&")correspondant aux fonctions de la question précédente. Si ! est
une valeur de type %!(, alors *;%("<9$(%#8&"<'">) !) renvoie une liste
contenant une suite de longueur minimale pour l'obtention de la puissance n.

Page 7 sur 7

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



Mines Informatique optionnelle MP 2017 -- Corrigé
Ce corrigé est proposé par Martin Guy (ENS Lyon) ; il a été relu par William
Aufort (ENS Lyon) et Benjamin Monmege (enseignant-chercheur à l'université).

L'épreuve se compose de deux problèmes indépendants. Le premier porte sur les
langages et les automates ; le second est consacré à l'algorithmique.
· Le premier problème se concentre sur les langages sur un alphabet unaire et
sur les automates finis. Après l'observation et la construction de différents 
automates, on prouve
que les langages rationnels unaires infinis contiennent né
cessairement ak+ | k  N pour un certain  et un certain . On en dérive
enfin une propriété permettant de prouver que certains langages unaires ne sont
pas rationnels. Ce premier problème permet de vérifier la maîtrise des bases sur
les automates ainsi que de prouver des propriétés sur certains langages.
· Le second problème, plus conséquent, présente deux algorithmes permettant de
calculer la puissance n d'un élément a (pouvant être un entier, un réel ou une
matrice) avec le moins de multiplications possible. Il peut se séparer en 
plusieurs parties. Tout d'abord, les premières questions permettent de 
s'approprier
la notion de suite pour l'obtention de la puissance n à partir d'exemples, puis 
se
concentrent sur l'algorithme d'exponentiation rapide. Les questions suivantes
présentent un second algorithme basé sur la décomposition binaire de la 
puissance n. Au passage, on montre qu'un algorithme optimal d'élévation à la 
puissance n effectue nécessairement entre log(n) et 2 × log(n) multiplications.
On constate ensuite que les deux algorithmes étudiés ne sont pas optimaux
puisqu'il existe des exemples pour lesquels ils ne renvoient pas la suite 
optimale
de multiplications à effectuer. Les dernières questions se consacrent donc à la
recherche d'une suite optimale via l'exploration exhaustive de l'ensemble des
suites. Ce problème permet de vérifier les acquis en algorithmique mais aussi
en programmation car tous les algorithmes étudiés doivent être implémentés.
Ce sujet comporte quelques questions pointues et il est assez long, mais 
plusieurs
questions peuvent se faire rapidement, notamment celles qui demandent d'omettre
la justification.

Indications
Partie I
1 Se concentrer sur les conditions pour que {k +  | k  N} soit fini.
2 Trouver « à la main » quelques mots reconnus par l'automate A1 et observer
un motif.
3 Séparer l'automate en deux parties.
7 Commencer par trouver un automate non déterministe semblable à celui de la
question 3 reconnaissant L(2, 3)  L(5, 2).
8 Observer qu'il suffit de supprimer des états finals à l'automate déterministe 
obtenu
à la question 7.
9 Utiliser le déterminisme de l'automate pour construire le chemin q0 , . . . , 
qs puis
le fait que L est infini pour justifier la transition entre qs et qr .
10 Utiliser l'hypothèse que L est un langage rationnel pour en tirer un 
automate qui
le reconnaît puis utiliser la question 9 pour affirmer qu'il existe un état 
final dans
le circuit qr , . . . , qs .
11 Prouver par l'absurde. Se ramener à la question précédente en commençant par
montrer que L est infini.
Partie II
13 Montrer ce résultat par une récurrence forte sur n. Pour la seconde partie 
de la
question, considérer n de la forme 2k .
16 Prouver le résultat par récurrence forte sur n. Pour la seconde partie, 
considérer n
de la forme 2k - 1.
18 Remarquer que la décomposition en binaire de n/2 se déduit aisément de celle
de n pour en déduire un algorithme récursif.
19 Utiliser l'écriture binaire inverse (c0 , . . . , ck ) de n. Utiliser une 
fonction auxiliaire
récursive qui va traiter la décomposition binaire inverse de la puissance, en 
distinguant deux cas selon la valeur du coefficient courant de la décomposition.
20 Prouver par récurrence sur k en utilisant la formule donnée et en observant 
que
pour obtenir la puissance 2 × 3k il suffit de calculer 3k + 3k . Pour la 
seconde partie
de la question, décomposer 27 avec la formule à la manière de la preuve.
21 Se servir de l'exemple précédent (n = 27) pour trouver l'algorithme.
22 Utiliser l'identité 5k = 2 × 2 × 5k-1 + 5k-1 .
23 S'inspirer de la suite obtenue à la question précédente pour n = 125.
24 Il faut tester toutes les paires d'indices.
25 Utiliser un tableau pour stocker les puissances intermédiaires calculées.
26 Il faut réussir à énumérer toutes les listes en respectant deux conditions : 
la liste
doit être triée par ordre croissant et chaque élément est somme d'exactement 
deux
éléments d'indice plus petit. Visualiser l'énumération exhaustive comme un 
arbre.
27 Séparer en plusieurs fonctions auxiliaires codant différentes étapes de 
l'algorithme.

I. Langages et automates
1 Soit (, )  N fixé. Distinguons deux cas. Si  6= 0, la suite (k + )kN est 
strictement croissante (et donc non majorée car c'est une suite d'entiers). 
Parconséquent,
L(, ) contient une infinité d'éléments. Sinon,  = 0 et on a L(0, ) = a . Ainsi,
2

L(, ) est fini si et seulement si  = 0. Dans ce cas, on a Card L(0, ) = 1.
2 En déroulant les étapes de l'automate, on s'intéresse aux 3 premiers mots 
reconnus
par l'automate pour découvrir le motif :
Mot
aa
aaaaaa
aaaaaaaaaa

Longueur
2
6
10

Décomposition
2=2+0×4
6=2+1×4
10 = 2 + 2 × 4

En décomposant la longueur de chaque mot sous la forme 1 + k1 on trouve les
valeurs recherchées. Ainsi,
L'automate A1 reconnaît le langage L(4, 2).
Pour aller plus vite, il suffit de regarder le nombre minimum de a à lire pour
aller de l'état initial jusqu'à l'état final, ici 2, ce qui donne la valeur de 
1 .
Pour 1 , la longueur du circuit depuis l'état final donne la valeur recherchée.
Cette approche est motivée par la forme k +  de l'ensemble des exposants.
3 L'automate A2 est composé de deux automates de la forme de A1 : la partie
haute (composée des états {0, 1, 2, 3}) et la partie basse (composée de {0, 4, 
5, 6}).
On raisonne alors comme précédemment sur chacune des parties.
L'automate A2 est un automate non déterministe. La lecture de la première
lettre permet soit d'aller à l'état 1, soit d'aller à l'état 4. Il suffit alors 
de
raisonner séparément sur chaque partie.
Ainsi, la partie haute reconnaît le langage L(3, 2) et la partie basse 
reconnaît le
langage L(2, 3). Le langage L2 reconnu par A2 est l'union de ces deux langages 
donc
L2 = L(3, 2)  L(2, 3)
État Successeurs
4 Pour déterminiser, on construit successivement un au0
{1, 4}
tomate en partant de l'état initial et en créant des nou{1, 4}
{2, 5}
veaux états suivant l'ensemble des états accessibles via
{2, 5}
{3, 6}
une transition de l'automate depuis l'état en cours (au{3, 6}
{1, 5}
trement dit, les successeurs de l'état courant en lisant a).
{1, 5}
{2, 6}
Par exemple, les successeurs de l'état 0 sont les états 1
{2, 6}
{3, 5}
et 4. On crée donc un état {1, 4}. Ensuite, on fait de même
{3, 5}
{1, 6}
avec l'état {1, 4} : on regarde les successeurs à partir de
{1, 6}
{2, 5}
ces états. On s'arrête lorsqu'on ne crée pas de nouvel état.
Les états finals de A3 sont les parties d'états de A2 qui contiennent un état 
final
de A2 . On obtient alors l'automate déterministe émondé A3 suivant :

{0}

{1,4} {2,5} {3,6} {1,5} {2,6} {3,5} {1,6}

5 On remarque que la forme de l'automate A3 est similaire à celle de A1 à ceci 
près
qu'il y a 4 états finals, chacun étant associé à un i différent. Comme 
précédemment,
on compte la longueur du chemin depuis l'état initial jusqu'à chacun des états 
finals
pour trouver la valeur i associée. Enfin, 4 est encore une fois la longueur du 
circuit
en partant d'un état final (elle est la même quel que soit l'état final).
Le langage reconnu par A3 est L3 = L(6, 2)  L(6, 3)  L(6, 5)  L(6, 7).
6 Un exemple d'automate de la forme F reconnaissant L(1, 2) est

0

1

2

7 En combinant un automate pour L(2, 3) en partie haute et un automate pour
L(5, 2) en partie basse, on obtient l'automate suivant pour le langage L(2, 
3)L(5, 2) :
1

2

3

4

5

6

0
7

8

Suivant le cheminement de la question 4, déterminisons cet automate pour en
déduire l'automate suivant de la forme F :

{0} {1,4} {2,5} {3,6} {2,7} {3,8} {2,4} {3,5} {2,6} {3,7} {2,8} {3,4}

Afin de gagner du temps lors de l'épreuve et déterminiser rapidement le premier 
automate, il n'est pas la peine de faire le tableau. Il suffit de remarquer
que l'on ne crée à chaque fois qu'un seul état et lire parallèlement la partie
haute et la partie basse de l'automate.
8 L'automate A4 suivant est un automate de la forme F reconnaissant le langage
L(2, 3)  L(5, 2) :

{0} {1,4} {2,5} {3,6} {2,7} {3,8} {2,4} {3,5} {2,6} {3,7} {2,8} {3,4}