e3a 2015

CONCOURS ARTS ET MÉTIERS ParisTech -ESTP -POLYTECH

Épreuve d’Informatique MP
Durée 3 h

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

L’usage de calculatrices est interdit.

AVERTISSEMENT

La présentation, la lisibilité, l’orthographe, la qualité de la rédaction, la clarté et la précision des

raisonnements entreront pour une part importante dans l’appréciation des copies. En particulier, les résultats
non justifiés ne seront pas pris en compte. Les candidats sont invités à encadrer les résultats de leurs calculs.

Les différents exercices sont indépendants.

Lorsqu’on demande d’évaluer une complexité, on attend un ordre de grandeur, par exemple O(n).

Pour un nombre réel x, on note bxc sa partie entière.

Il est interdit aux candidats de signer leur composition ou d’y mettre un signe quelconque pouvant
indiquer sa provenance.

Exercice 1
On admettra que la multiplication de deux entiers naturels se fait en temps constant.
1. On s’intéresse dans cette partie au calcul de la puissance k-ième d’un entier naturel n, pour un
entier naturel k ≥ 1.
(a) Dans un premier temps, on utilise un algorithme naı̈f :
let rec puissance n k =
if k= 1 then n
else n * (puissance n (k-1));;
val puissance : int -> int -> int

Quelle est la complexité de cet algorithme ? Le justifier précisément.

(b) On utilise ensuite l’algorithme suivant :
let rec puissance2 n k =
if k >1 then
let x = puissance2 n (k/2) in
if k mod2 =0 then
x * x
else
else x * x * n;;
val puissance2 : int -> int -> int
i. Décrire l’exécution du programme puissance2 sur l’entrée (2,7).
ii. Décrire l’exécution du programme puissance2 sur l’entrée (2,8).
iii. Démontrer que le nombre d’appels récursifs à l’intérieur du programme puissance2 sur
l’entrée (n, k) est au plus de log2 k + 1. En déduire que le programme termine.
iv. Justifier que ce programme est correct.
v. Évaluer la complexité de ce programme.

1
 2. On s’intéresse ici au problème de déterminer si un entier naturel est une puissance non triviale
d’un nombre entier ou non : on dit qu’un nombre entier naturel n est une puissance entière s’il
existe deux entiers naturels k et m tous deux > 1 tels que n = mk .
(a) Écrire la fonction :
test_puissance : int -> int -> bool
qui prend en entrée les entiers naturels n > 1 et k > 1 et renvoie le booléen true s’il existe un
entier naturel m tel que n = mk et false sinon.
Note : l’énoncé original mentionne un N qui n’est pas défini.
(b) i. Soit n un entier naturel. On suppose que n est une puissance entière : Soient k et m deux
entiers naturels > 1 tels que n = mk . Justifier que k 6 log2 (n).
ii. Écrire la fonction :
test_puissance_entiere : int -> bool
qui prend en entrée l’entier naturel n > 1 et renvoie le booléen true s’il existe deux entiers
naturels k et m tous deux > 1 tels que n = mk et false sinon.
iii. Démontrer que la complexité de ce programme est au plus O(n log2 (n) log2 (k)).
iv. En déduire la fonction :
liste1_puissances_entieres : int -> int list

qui prend en entrée l’entier naturel n > 1 et renvoie la liste des entiers naturels compris
entre 2 et n qui sont des puissances entières.
(c) En vous inspirant du crible d’Erathosthène, écrire la fonction :
liste2_puissances_entieres : int -> int list

qui prend en entrée l’entier naturel n > 1 et renvoie la liste des entiers naturels compris entre
2 et n qui sont des puissances entières.

Exercice 2
Soit Σ l’alphabet des chiffres : Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Un nombre entier naturel non nul n est considéré à l’aide de son écriture en base 10 comme un mot
sur l’alphabet Σ :

n s’écrit al al−1 . . . a0 ⇐⇒ n = al 10l + al−1 10l−1 + . . . + a0 , avec al 6= 0.

Un mot sur Σ sera considéré comme un tableau de type int vect dont les éléments sont compris
entre 0 et 9. Par exemple le nombre 2015 sera représenté par [|2; 0; 1; 5|] .
On dit qu’un entier naturel non nul a la propriété P2015 si son écriture en base 10 comprend le motif
2015. On cherche à reconnaı̂tre les entiers naturels non nuls ayant cette propriété.
1. Dessiner un automate déterministe complet qui reconnait exactement les entiers naturels non nuls
ayant la propriété P2015 .
2. On considère la fonction G qui envoie un mot abcd dans Σ4 sur l’entier naturel a ∗ 1000 + b ∗ 100 +
c ∗ 10 + d.
(a) Combien de valeurs distinctes la fonction G peut-elle prendre ?
(b) Étant donné un mot abcde dans Σ5 , expliciter comment calculer G(bcde) en fonction de G(abcd)
et e.
(c) Écrire la fonction :
decalG : int -> int -> int

qui prend en entrée l’entier naturel G(abcd) et le chiffre e dans Σ et renvoie la valeur G(bcde),
pour abcde un mot dans Σ5 .

2
 (d) On utilise la fonction G pour résoudre le problème. Étant donné un entier naturel non nul
n s’écrivant al al−1 . . . a0 en base 10, on calcule la valeur prise par G sur chaque facteur
ai ai−1 ai−2 ai−3 . Écrire la fonction :
testG_motif : int vect -> bool

qui prend en entrée le tableau défini par l’écriture en base 10 d’un entier naturel non nul n et
renvoie le booléen true si l’entier naturel n a la propriété P2015 et false sinon. Cette fonction
ne lira qu’une fois au plus chacun des caractères de l’écriture en base 10 de n.
(e) Évaluer la complexité de votre algorithme.
(f) Écrire la fonction :
nbG_motif : int vect -> int

qui prend en entrée le tableau défini par l’écriture en base 10 d’un entier naturel non nul n et
renvoie le nombre d’occurrences du motif 2015 dans l’écriture en base 10 de n.
3. On considère la fonction H qui envoie un mot abcd dans Σ4 sur l’entier naturel compris entre 0 et
10 égal à a ∗ 1000 + b ∗ 100 + e ∗ 10 + d modulo 11.
(a) Combien de valeurs distinctes la fonction H peut-elle prendre ?
(b) Écrire la fonction :
calculH : int vect -> int

qui prend en entrée un mot abcd dans Σ4 et renvoie la valeur de H prise sur ce mot.
(c) Étant donné un mot abcde dans Σ5 , expliciter comment calculer H(bcde) en fonction de H(abcd),
a et e.
(d) En utilisant la fonction H, écrire la fonction :
testH_motif : int vect -> int

qui prend en entrée le tableau défini par l’écriture en base 10 d’un entier naturel non nul n et
renvoie renvoie le booléen true si l’entier naturel n a la propriété P2015 et 0 (ou false) sinon.
Cette fonction ne lira que trois fois au plus chacun des caractères de l’écriture en base 10 de n.
(e) Évaluer la complexité de votre algorithme.

Exercice 3
On souhaite analyser les résultats de sondages concernant une élection. Les candidats à l’élection sont
numérotés de 0 à k −1. Les résultats de chaque sondage sont stockés dans un tableau : si le sondage a recueilli
N réponses, le tableau comporte N cases, une pour chaque réponse : la i-ème case du tableau contient le
numéro du candidat proposé par la i-ème personne sondée. On a ainsi un tableau T de longueur N qui
contient des entiers naturels entre 0 et k − 1.
Le sondage donne le candidat numéroté i élu si le nombre i est dans strictement plus de N/2 cases
de T . Par exemple, un sondage correspondant au tableau [2, 4, 5, 0, 4, 4, 4] donne le candidat 4 élu. Mais un
tableau ne donne pas toujours un élu, par exemple le tableau [1, 2, 3, 4, 6, 2, 3, 3].
On suppose qu’un entier k est défini.
1. (a) Écrire une fonction nb de type int vect -> int -> int telle que si a est un entier naturel et
tab un tableau de taille N issu d’un tel sondage, nb tab a est le nombre de cases du tableau
tab qui contiennent a.
(b) Évaluer la complexité de l’appel de nb en fonction de N et de k.
(c) En déduire une fonction elu1 de type int vect -> int telle que elu1 tab est l’entier donné
élu par le tableau tab si celui-ci existe et −1 sinon.
(d) Évaluer la complexité de votre algorithme en fonction de N et de k.
2. On se propose d’utiliser la stratégie diviser pour régner pour déterminer l’éventuel élu donné par
un tableau. On dispose de deux fonctions, qu’on ne cherchera pas à décrire :

3
 • miGauche : int vect -> int vect qui prend en argument un tableau tab de longueur N > 2
et retourne le tableau de longueur bN/2c formé par les bN/2c premières cases de tab,
• miDroite : int vect -> int vect qui prend en argument un tableau tab de longueur N > 2
et retourne le tableau de longueur N − bN/2c formé par les N − bN/2c dernières cases de tab.
(a) Soit tab un tableau de longueur N > 2. Démontrer que si tab donne a comme élu alors celui-ci
est aussi donné élu par le tableau miGauche tab ou par le tableau miDroite tab.
(b) Proposer une fonction elu2, utilisant la stratégie diviser pour régner, de type
int vect -> int * int ; si tab est un tableau, elu2 tab est le couple (a,n) si l’entier a est
donné élu par tab et apparait dans n cases exactement de tab, et (-1,0) si tab ne donne pas
d’élu. On pourra utiliser la fonction nb définie en l(a).
(c) Évaluer la complexité de cette fonction en fonction de N .
3. Soit T un tableau de longueur N . On dit que le nombre entier a est un postulant pour la valeur n
du tableau T si : n est un entier strictement supérieur à N/2 tel que a apparait au plus (au sens
large) n fois dans T et tout entier b distinct de a, apparait au plus (au sens large) N − n fois dans
T . Par exemple, 3 est un postulant pour n = 5 du tableau [1, 2, 3, 4, 3, 2, 3, 3].
On dit que le nombre entier a est un postulant du tableau T s’il existe un nombre entier n > N/2
tel que a est un postulant pour la valeur n du tableau T
(a) Démontrer que si le tableau T donne a élu alors a est un postulant de T .
(b) Démontrer que si a est un postulant de T , alors aucun autre élément de T ne pourrait être
donné comme élu.
(c) Donner un exemple de tableau qui contient un postulant mais ne donne aucun élu et un exemple
de tableau n’ayant aucun postulant.
(d) Soit T un tableau de longueur un entier pair N . On note T G le tableau de longueur N/2 formé
par les N/2 premières cases de T et T D le tableau de longueur N/2 formé par les N/2 dernières
cases de T .
i. On suppose que le tableau T D ne donne pas d’élu. Soit a un postulant pour la valeur l du
tableau T G. Démontrer que a est un postulant de T . On exprimera la valeur d’un entier n
tel que n > N/2 et a est un postulant pour la valeur n du tableau T en fonction de l et N .
ii. Soient a un postulant pour la valeur l du tableau T G et b un postulant pour la valeur m
du tableau T D.
A. On suppose que a = b. Démontrer que a est un postulant de T . On exprimera la valeur
d’un entier n tel que n > N/2 et a est un postulant pour la valeur n du tableau T en
fonction de l et m.
B. On suppose que a 6= b et m > l. Démontrer que b est un postulant pour la valeur
N/2 + m − l de T .
C. On suppose que a 6= b et m = l. Démontrer que T ne donne pas d’élu.
4. Écrire une fonction postulant : int vect -> int * int telle que, si tab est un tableau d’entiers
naturels de longueur N , postulant tab est un couple (a,n) tel que
- lorsque postulant tab renvoie le couple (-1,0), le tableau tab n’a pas d’élu,
- lorsque postulant tab renvoie le couple (a,n) avec n > N/2, a est un postulant pour la valeur
n du tableau tab. On supposera pour simplifier que la taille du tableau est une puissance de 2,
La procédure utilisera la stratégie diviser pour régner et aura une complexité linéaire, ce qu’on
justifiera précisément.
5. En déduire une fonction elu3, de type int vect -> int qui prend en argument un tableau tab
et retourne l’entier élu de tab si celui-ci existe et −1 sinon, de complexité linéaire.