E3A Informatique MP 2008

Thème de l'épreuve Six exercices d'informatique
Principaux outils utilisés programmation impérative et récursive, langages, fonctions booléennes

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


12AN

9238

CONCOURS ENSAM - ESTP - ARCHIMEDE

É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'unepart 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.

Indiquer en tête de copie ou de chaque exercice le langage utilisé

Quel que soit le langage utilisé, le candidat pourra supposer qu'il dispose 
d'une fonction test_liste_vide
qui prend en entrée une liste et renvoie le booléen 1 si la liste est vide et 0 
sinon.

Le candidat pourra, s'il le juge utile, supposer que chaque liste se termine 
par un élément de marquage
de fin de liste appelé N I L.

Exercice 1

a) Ecrire la fonction :

Tri_denombrement
données N : entier naturel
L : liste d'entiers tous compris entre 1 et N

résultat M : tableau de longueur N

qui prend en entrée un entier naturel non nul N et une liste L d'entiers tous 
compris entre 1 et N et
renvoie le tableau de longueur N, dans lequel la k--ième case contient le 
nombre d'éléments égaux à le
dans la liste L, pour tout entier k compris entre 1 et N.

I)) Calculer en fonction de n, n étant la longueur de la liste L, et de N, le 
coût de ce tri dans le
meilleur des cas, dans le pire des cas et en moyenne. On supposera que le temps 
d'accès à la k--ième
case du tableau est linéaire en le, le reste des opérations ayant un coût 
négligeable.

Exercice 2
(les questions a et b sont indépendantes.)

a) Ecrire la fonction :

Matrice
données L : liste
77. : entier
résultat M : tableau à deux entrées de taille n,n

qui prend en entrée une liste L et l'entier n et renvoie le tableau des 
coefficients d'une matrice carrée
de taille n remplie ligne par ligne de gauche à drOite par les coefficients de 
la liste L. La liste contient
des entiers relatifs. Si la liste L n'est pas suffisamment longue, la matrice 
est complétée par des 0. Si
la liste L est trop longue, le programme s'arrête lorsque la matrice est 
remplie.

b) Soit T un tableau rempli avec des entiers naturels. Un plateau de T de 
valeur le et de longueur .
l est une suite de 1 indices consécutifs z',z° + 1, ...,i + Z ---- 1 sur 
lesquels T prend la valeur k: (T[7Ç] :
T[z° + 1] == --- : T[i +l --- 1] = le). Par exemple, le tableau [1, 2, 3, 3, 3, 
1, 2, 6, 6] posséde un plateau de
valeur 3 et de longueur 3, un plateau de valeur 6 et de longueur 2, deux 
plateaux de valeur 1 et de
longueur 1 et deux plateaux de valeur 2 et de longueur 1.

Ecrire la fonction :

LongueurMaxPlateau
données T : tableau
N : entier naturel

résultat 1 : entier naturel

qui prend en entrée un tableau d'entiers naturels et sa longueur N et renvoie 
la plus grande longueur
de ses plateaux.

Exercice 3
(les questions a, b et c sont indépendantes.)

@) Qu'efiectue le programme ci--dessous :

PROG(L : liste d'entiers )

L2 <-- liste_vide
E' <-- premier_element(L)
tant que (E <> NIL) faire
Eg <-- premier_element(L2)
SW <-- 0
tant que(E2 <> NIL et SW : 0) faire
si(E : E2) alors SW <-- 1

sinon E2 <-- element_suivant(L2)

fin si
fin faire
si (SW : 0) alors L2 <-- aj outer_element(E)
fin si

E <-- element_suivant(L)
fin faire
retournerL2

On remarquera que les listes considérées par ce programme se terminent par un 
élément de marquage
de fin de liste appelé N I L.

b) Décrire l'exécution du programme N BS ci-dessous sur l'entrée (7, 3) :

N B S (N : entier strictement positif, p : entier strictement positif))
si (N  U) alors faire
CÎ+--.9
nz+--i
7L+--j
fin faire
fin si
fin faire
retourner(£fi7n,n)
Exercice 4

Un nombre d'Armstrong est un nombre qui est égal à la somme des cubes des 
chiffres de son écriture
en base 10 ; par exemple 153 est un nombre d'Armstrong puisque 153 = 13 + 53 + 
33. Ecrire un
programme qui calcule tous les nombres d'Armstrong à trois ou quatre ehiflres.

Exercice 5

Une liste d'entiers est dite convenable si elle se compose d'un nombre pair 
d'éléments ..., b1, (Lg, b2, ...,
ak,bk tels que 611 < b1 < a2 < ----bk_1 < ak < b;,. On représente une réunion 
finie de k intervalles
fermés disjoints dont les extrémités sont des entiers relatifs par la liste 
ordonnée de leurs extrémités,
selon l'ordre croissant. On admet que cette liste est alors convenable. Par 
exemple, [--1, 2] U [4, 7] U
]--3, ----2] U [8, 8] est représentée par la liste --3, --2, --1, 2, 4, 7, 8, 
8. L'ensemble vide est représenté par
la liste vide.

&) Ecrire la procédure :

Convenable
données L : liste d'entiers
résultat b : booléen

qui prend en entrée une liste d'entiers L et retourne la valeur 1 si elle est 
convenable et 0 sinon.

b) On admet que l'intersection de deux réunions finies d'intervalles fermés 
disjoints dont les extrémités
sont des entiers relatifs est aussi une réunion finie d'intervalles fermés 
disjoints dont les extrémités
sont des entiers relatifs. Par exemple, l'intersection de [1, 2] U [4, 5], 
représenté par la liste convenable
1, 2, 4, 5 et de [--1, 3] U [5,7] U [8, 9], représenté par la liste convenable 
----1, 3, 5, 7, 8, 9, est [1,2] U [5, 5]
représenté par la liste convenable 1, 2, 5, 5. Ecrire la procédure :

Intersection
données L1 : liste convenable d'entiers
L2 : liste convenable d'entiers
résultat L' : liste convenable d' entiers

qui prend en entrée deux listes convenables d'entiers représentant chacune une 
réunion finie d'intervalles

fermés dis'oints res ectivement F1 et F2 et retourne la liste convenable 
d'entiers re résentant la dé--
...] 7 P 7 P

composition en réunion finie d'intervalles fermés disjoints de l'ensemble F1 0 
F2.

c) On admet que la réunion de deux réunions finies d'intervalles fermés 
disjoints dont les extrémités
sont des entiers relatifs est aussi une réunion finie d'intervalles fermés 
disjoints dont les extrémités sont
des entiers relatifs. Par exemple, la réunion de [l, 2] U [4, 5], représenté 
par la liste convenable 1, 2, 4, 5
et de [----1, 3] U [5,7] U [8, 9], représenté par la liste convenable --1, 3, 
5, 7, 8, 9, est [----1, 3] U [4, 7] U [8, 9]
représenté par la liste convenable --1, 3, 4, 7, 8, 9. Ecrire la procédure :

Reunion
données L1:liste convenable d'entiers
L2 : liste convenable d'entiers
résultat L' : liste convenable d'entiers

qui prend en entrée deux listes convenables d'entiers représentant chacune une 
réunion finie d'intervalles

fermés dis'oints res ectivement F et F2 et retourne la liste convenable 
d'entiers re résentant la dé--
7 1 )

composition en réunion finie d'intervalles fermés disjoints de l'ensemble F1 U 
F2.

Exercice 6

Si C est un langage sur un alphabet fini 2 et si n est un entier naturel non 
nul, on note £(n) le
langage formé par les mots de E qui sont de longueur n.

1. Justifier que le langage £(n) est de cardinal fini.
Dans la suite, on note uf,' le cardinal du langage En.

2. Dans cette question, l'alphabet E désigne l'alphabet a trois lettres 2 = {a, 
19,0} et E est le
langage des mots finis sur E qui contiennent au moins un c. Oe langage est 
donné par l'expression
rationnelle :

E = {a, b}*c{a, b, c}*.

a) Dessiner un automate déterministe a deux états qui reconnait exactement le 
langage £.
b) Soit n un entier naturel non nul.

i) Dessiner un automate qui reconnait exactement le langage £(n).
ii) On suppose n > 2. Soit Un_1 le langage {a,b,c}*(n --- 1). Démontrer que 
£(n) est
la réunion disjointe des langages {a, b}£(n -- 1) et cUn_1. En déduire la 
relation de

récurrence :
£ __ £ n--1

£

,, en fonction de n.

iii) Exprimer u

3. Dans cette question, on suppose que C est le langage reconnu par un automate 
déterministe

.À= (Q,E,1,f,ô) où:

0 Q est l'ensemble fini des états de A. On note m son cardinal et on suppose 
que m est un
entier naturel 2 2. Les états dans Q sont numérotés de 1 a m.

o 1 est le numéro de l'état initial de A,
0 f est le numéro de l'unique état final de A,

0 5 est la fonction de transition de A définie d'une partie de Q >< E dans Q.

On considère la matrice (m, m) M = (m...-) définie par : m,,j est le nombre de 
transitions de
source l'état z' et de but l'état j dans l'automate A. On note XM(X ) = X "" -- 
Ë__Ë (?......ka

le polynôme caractéristique de la matrice M.

Pour tout état j de Q, on note £j le langage reconnu par l'automate (Q, 2, j, 
f, 5) ; ainsi défini,
£1 : .C. Pour tout entier n > 1, soit V(n) le vecteur de coordonnées @, ...,oem 
où a:,-- est le
cardinal du langage [i,--(n), pour tout j dans Q.

a) Expliciter les coordonnées du vecteur V(1) en fonction de 5 .

b) Démontrer que, pour tout entier n > 2 et pour tout j dans Q, £j(n) est la 
réunion disjointe
des langages a/Ç;,,(n -- 1) pour tout (j, a, 143) dans Q >< 2 >< Q tel que ô(j, 
&) = k.

c) En déduire, pour tout entier n > 2, l'égalité V(n) : M "_1V(1).
£

,,) vérifie la relation

d) En utilisant le théorème de Cayley--Hamilton, démontrer que la suite (u

de récurrence :

.C _ .C C [.
un+m "" alun+m--l + a2un+m--2 + ' ° ' + amun '

Dans le cas où XM a m racines distinctes 011, ..., a..., que peut--on en 
déduire pour la suite
£ ?
(un) -

4. Soit E le langage sur l'alphabet E = {a, b} reconnu par l'automate B = (Q, 
2, 1, 2, 5) ci--dessous :

Figure 1: Automate B

a) Donner une expression rationnelle de £.

b) Expliciter la suite (uâ)n>1.

Exercice 7

Soit n un entier naturel ; 2. Soit f une fonction booléenne à n variables. On 
dit que f définit
implicitement sa n--ième variable si pour tout n--uplet (au, ..., oen_1) de {O, 
1}"_1, il existe un unique
fin dans {D, 1} tel que f(oe1,...,æn) : O.

1. Dans cette question, n = 2. Soit f1 la fonction boolénne définie par ses 
valeurs présentées dans
la table ci--dessous :

Démontrer que f1 définit implicitement sa seconde variable. Expliciter toutes 
les fonctions
booléennes sur {O, 1}2 qui définissent implicitement leur seconde variable.

Soit f une fonction booléenne a n variables.

2. Démontrer que f définit implicitement sa n--ième variable si et seulement si 
f vérifie la propriété
suivante :

V(oe1,...,oen_1,oen) EUR {07 1}n,f(OE1, ...,OEn_1,--În) : f(OE'1, °°°) fin)-

3. Soit f la fonction booléenne définie par :

n----l
V(oe1,...,oen_1,oen) EUR {0,1}",f(æ1,...,oen) : æ1oe2...oen + Zîfifin.
z'=1

Démontrer que f définit implicitement sa n-ième variable. Démontrer plus 
précisément qu'il
existe une fonction booléenne 9 sur {D,1}""', telle que

V(æ1,...,æn_1,oen) EUR {0,1}n, ( f(OE1,...,£En) : () <=> £En = g(æ1, ...,OEn_1) 
).

Préciser g.

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



E3A Informatique MP 2008 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par
Vincent Puyhaubert (Professeur en CPGE) et Guillaume Batog (ENS Cachan).

Le sujet comporte sept exercices indépendants. Ils se répartissent entre trois
grandes thématiques :
· Programmation :
 L'exercice 1 propose de trier une liste par dénombrement et de calculer
la complexité d'un tel algorithme, dans le pire ou le meilleur des cas
ainsi qu'en moyenne. Une bonne maîtrise du calcul de complexité est
donc nécessaire.
 L'exercice 2 est composé de deux questions indépendantes. La première
construit un programme pour remplir une matrice à partir des coefficients
d'une liste donnée ; la seconde calcule le plus grand nombre de valeurs
identiques consécutives dans un tableau donné.
 L'exercice 3 propose de trouver ce que calculent trois programmes écrits
en pseudo-code. Il s'agit d'un exercice difficile dans lequel il faut avoir une
bonne intuition, comprendre le but de chacune des variables utilisées et
savoir rédiger une réponse satisfaisant le correcteur.
 L'exercice 4 demande d'écrire un programme restituant une liste d'entiers
vérifiant une condition particulière visible sur leur écriture en base 10.
 L'exercice 5, nettement plus difficile d'un point de vue algorithmique,
propose de représenter une union finie d'intervalles fermés disjoints à l'aide
de la liste ordonnée de leurs extrémités. Il faut alors réaliser une fonction
qui décide si une liste ordonnée correspond à une telle réunion, puis écrire
deux fonctions qui réalisent respectivement les opérations d'intersection
et d'union.
· Automates : l'exercice 6 propose de calculer le cardinal de l'ensemble des 
mots
de longueur n d'un langage rationnel. Il nécessite une bonne aptitude à 
manipuler les langages et les automates finis, et utilise le formalisme 
mathématique
de l'algèbre linéaire (en particulier le théorème de Cayley-Hamilton).
· Logique : l'exercice 7 étudie une classe particulière de fonctions booléennes
pour lesquelles il est possible d'appliquer un théorème des fonctions 
implicites,
en détaillant deux exemples. Pour le résoudre, il faut avoir bien compris la
différence entre une fonction booléenne et son évaluation en une valeur de 
vérité.
Il s'agit d'un sujet typique du concours E3A : une longue suite d'exercices 
très éloignés les uns des autres, de difficultés différentes. On a tout intérêt 
à le lire en entier
au début de l'épreuve afin de sélectionner l'ordre dans lequel traiter les 
exercices.
Il n'est pas nécessaire de faire l'ensemble du sujet pour avoir une note 
correcte :
il vaut mieux explorer en détail quelques exercices plutôt qu'aborder 
superficiellement
chacun d'entre eux.

Indications
1.a Faire attention à la convention Caml qui numérote les tableaux à partir de 
0.
Un seul passage sur la liste suffit à résoudre le problème.
1.b Pour la complexité en moyenne, supposer que les entiers N et n sont fixés.
Combien y a-t-il alors de listes L possibles ? Quel est le coût d'une exécution
de l'algorithme sur une liste fixée, en fonction de ses coefficients ? En 
déduire
une majoration la plus simple possible de la complexité en moyenne.
2.a Initialiser la matrice M avec la matrice nulle puis remplacer ses 
coefficients
par ceux de la liste L tant que c'est possible.
2.b Parcourir le tableau T en mémorisant la longueur du plus grand plateau
rencontré et la longueur du plateau courant (remarquer qu'un tableau se
décompose en plateaux, éventuellement réduits à un seul élément).
3.a Commencer, au brouillon, par décrire l'exécution du programme sur l'entrée
[1, 2, 2, 3, 1], puis essayer de trouver le rôle de chacune des variables.
3.b Écrire proprement les appels récursifs sur l'exemple (N = 7, p = 3) et 
relier
ce calcul au nombre de manières de décomposer N en une somme de p entiers
strictement positifs.
3.c Les deux premiers tests inclus dans la boucle pour sont à comprendre comme
des cas disjoints. En particulier, ne pas rentrer dans le second test lorsque
le premier a été positif. Corriger cette erreur puis essayer de faire tourner
l'algorithme sur le tableau [5, -1, 1, 2, -3, -2, 1, 3, 2].
4 Décomposer le problème en commençant par écrire une fonction qui teste
si un entier à trois ou quatre chiffres est un nombre d'Armstrong.
5.a Écrire une fonction auxiliaire récursive prenant en entrée une liste L et un
entier i et vérifiant que L est une liste convenable, dont le premier élément
est strictement supérieur à i.
5.b, 5.c Il est possible d'écrire ces fonctions de manières récursives, à 
condition de
bien penser aux cas de base.
6.2.b.i Préférer écrire un automate déterministe reconnaissant le langage L(n).
Commencer par les petites valeurs de n.
6.2.b.iii Conjecturer au brouillon la valeur de la suite récurrente linéaire, 
puis prouver
le résultat par récurrence.
6.3.b Raisonner par double inclusion, en utilisant la définition du langage Lj 
(n).
6.3.c Montrer que, pour tout n > 2, V(n) = M V(n-1) en exprimant les différentes
coordonnées des deux vecteurs, puis conclure par récurrence.
6.4.b Utiliser l'idée développée à la question 6.3.d pour exprimer le terme uL
n dans
ce cas particulier.
7.2 Pour le sens direct, ne pas oublier qu'une fonction booléenne ne peut 
prendre
que deux valeurs (0 ou 1).
7.3 Pour exhiber la fonction g, distinguer le cas du (n - 1)-uplet (x1 , . . . 
, xn-1 )
dont toutes les composantes valent 1, des autres.

Rappelons ici quelques conseils que le jury livre chaque année dans ses
rapports. L'épreuve étant essentiellement tournée vers la programmation,
il est primordial que les candidats se préparent à cette épreuve : il est en 
effet
plus délicat de proposer un programme correct sans pouvoir le tester sur
machine. Même si le jury est clément sur les petites erreurs de syntaxe,
le candidat doit s'efforcer de produire un code clair, indenté et largement
commenté. Il peut aussi être intéressant de décrire rapidement le rôle d'une
variable introduite dans un programme en expliquant son initialisation, ou de
découper un programme long en plusieurs sous-programmes dont on décrit la
finalité. Les exercices plus théoriques doivent être résolus comme s'ils 
faisaient
partie d'une épreuve de mathématiques : les réponses doivent être concises,
mais argumentées précisément.

Exercice 1
1.a Afin d'écrire un programme correct en Caml, dans lequel un tableau de 
taille N
est numéroté de 0 à N - 1, on choisit de modifier légèrement le résultat 
demandé par
l'énoncé. Ainsi la fonction tri_denombrement prend en entrée un entier N et une
liste L d'entiers compris entre 1 et N et renvoie un tableau M de taille N + 1 
dont
la case d'indice 0 contient 0 et dont la case d'indice k  [[ 1 ; N ]] contient 
le nombre
d'éléments égaux à k dans la liste L.
Le programme écrit ci-dessous utilise une fonction auxiliaire passage, 
récursive,
qui prend en entrée une liste et remplit convenablement le tableau M, élément 
après
élément : à chaque fois que la valeur k est rencontrée dans la liste L, on 
incrémente
la case d'indice k du tableau M.
let tri_denombrement N L =
let M = make_vect (N+1) 0 in
let rec passage liste =
match liste with
| [] -> M
| k::reste -> M.(k)<-M.(k)+1; passage reste
in passage L;;
Cette fonction n'est pas un algorithme de tri : pour faire cela, il faut 
reconstituer la liste triée des éléments de L à partir du tableau M. Présentons 
un
exemple de fonction implémentant cette amélioration. Le programme récursif
auxiliaire permet de limiter le nombre d'accès à une case du tableau M,
puisque cette opération est supposée coûteuse dans cet exercice.
let tri N L =
let M = tri_denombrement N L in
let rec range i k =
(* renvoie la liste triée comprenant *)
(* tous les éléments de L inférieurs à i *)
if (i=N)&&(k=0) then []
else if k=0 then range (i+1) M.(i+1)
else i::(range i (k-1))
in range 0 M.(0);;

1.b La seule opération élémentaire considérée ici est l'accès à une case de 
tableau :
on suppose ici que cette opération a un coût linéaire en l'indice de la case 
voulue.
Cette hypothèse, imposée par l'énoncé, est assez étrange puisque, contrairement 
à une liste, on a coutume de considérer que l'accès à un élément donné
d'un tableau se fait en temps constant en Caml.
Appelons n la longueur de la suite L. Remarquons que la seule opération coûteuse
est l'accès à la case d'indice x du tableau M : cela coûte O(x).
· Complexité dans le meilleur des cas : tous les éléments de la liste L sont
égaux à 1 et donc chaque accès à une case a une complexité en O(1).
La complexité dans le meilleur des cas est en O(n).
· Complexité dans le pire des cas : tous les éléments de la liste L sont égaux
à N et donc chaque accès à une case a une complexité en O(N).
La complexité dans le pire des cas est majorée par C n N,
où C est une constante indépendante de n et N.
Mieux vaut éviter la notation O(nN) puisque les notations de Landau
ne sont traditionnellement définies que pour une suite dépendant d'un
unique paramètre.
· Complexité en moyenne : précisons ici l'énoncé. On suppose que N et n sont
des entiers fixés et on fait varier la liste L donnée en entrée de l'algorithme.
L'ensemble des listes L possibles est un ensemble fini. Chaque élément de la
liste peut prendre une valeur entre 1 et N. Comme elle est de taille n, 
l'ensemble
des listes est de cardinal Nn . On considère donc que chaque liste a une chance
sur Nn d'apparaître.
Afin de calculer la complexité en moyenne, il faut donc trouver le coût de 
calcul
sur chacune des listes. Considérons une liste fixée L : elle contient les 
éléments
1 , . . . , n . La complexité totale de l'exécution de l'algorithme sur la 
liste L est
majorée par C (i +· · ·+n ) où C est une constante indépendante de la liste L et
des entiers n et N. Ainsi, en sommant sur l'ensemble des listes L, la complexité
en moyenne est majorée par
N
N
P
C P
···
(1 + · · · + n )
n
N 1 =1 n =1

Quitte à réordonner la somme, il suffit de compter le nombre de fois qu'apparaît
chaque valeur k  [[ 1 ; N ]] parmi les termes i . Le nombre total de termes
étant n Nn , et chaque valeur apparaissant un nombre identique de fois pour
des raisons de symétrie, on en déduit que chaque valeur k  [[ 1 ; N ]] apparaît
n Nn-1 fois. Ainsi, la complexité en moyenne est majorée par
N
N
C P
Cn P
C n N (N + 1)
C n (N + 1)
k n Nn-1 =
k=
=
n
N k=1
N k=1
N
2
2

Le tri par dénombrement a une complexité
C n (N + 1)
en moyenne majorée par
.
2