E3A Informatique MP 2007

Thème de l'épreuve Six exercices d'informatique
Principaux outils utilisés programmation impérative et récursive, langage d'un automate, formules logiques

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


Z12L

e 3 a
CONCOURS ENSAM - ESTP - ARCHIMEDE

Épreuve d'Informatique MP

durée 3 heures

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 la calculatrice est interdit

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

Exercice 1

&) Ecrire la fonction

Sym données M : tableau à deux dimensions
n : entier
résultat 56 : boolêen

qui prend en entrée le tableau des coefficients d'une matrice carrée de taille 
n et renvoie la valeur
1 si la matrice est symétrique et 0 sinon.

(9) Ecrire la fonction
Egalite--listes données L : liste
L' : liste
résultat b : booléen

qui prend en entrée deux listes et renvoie la valeur 1 si les deux listes sont 
égales et 0 sinon. Ces
listes contiennent des entiers positifs ou nuls et se terminent par la valeur 
--1.

c) Un tableau d'entiers T est dit trié par ordre croissant si ses entrées sont 
triées par ordre
croissant : si l est la longueur du tableau, Vi,j EUR {1, ..., l},i < j => T[i] 
{ T[j]. Il est dit trié par
ordre décroissant si ses entrées sont triées par ordre décroissant : si l est 
la longueur du tableau,
Vi, j EUR {1, ..., l},i < j => T [2] > T ... Dans les deux cas, il est dit 
trié. Remarquons qu'un tableau
T peut être à la fois trié dans l'ordre croissant et dans l'ordre décroissant, 
s'il vérifie : si l est la
longueur du tableau, Vi, j EUR {1, ..., I}, T [i] = T [3] Il alors est dit 
constant.

Ecrire la fonction

Test--tri données T : tableau d'entiers
l : entier
résultat a: : entier

qui prend en entrée un tableau T de longueur 1 et retourne la valeur 1 si le 
tableau T est trié par
ordre croissant et non constant, --1 si T est trié par ordre décroissant et non 
constant, 0 si T est
constant et 2 si T n'est pas trié.

Ecrire la procédure

Fusion données T : tableau d'entiers
l : entier
U : tableau d'entiers
m : entier
résultat W : tableau d'entiers trié

qui fusionne deux tableaux triés tous deux par ordre croissant (respectivement 
tous deux triés par
ordre décroissant), de longueurs respectives l, m ; le résultat est un tableau 
trié par ordre croissant
(respectivement par ordre décroissant) de longueur 1 + m. Dans le cas où les 
deux tableaux ne
sont pas tous deux triés dans un même ordre, la procédure Fusion renverra un 
tableau vide et un
message d'avertissement.

Exercice 2

a) Que retourne le programme suivant :

S <-- 2007

i <-- 1

tant que (i2 < S) faire i<---- @ + 1
fin tant que

afficher(i)

b) Que calculent les procédures suivantes :

TR(N : entier, T : tableau d'entiers de longueur N, 1 : entier, m : entier)

si (1 5 l) et (l 5 m) et (m S N) faire
pour (2°: 1) â(i=m--l+l) faireTR[i] <--T[l--1+i]
retourner TR

fin si

Valeur(N : entier, T : tableau d'entiers de longueur N, l : entier)

si (1 5 l) et (l 5 N) faire
a: <-- T...
9 <-- 0
d +-- N + 1
j <-- 1
tant que (j 5 N) faire
si (T... <æ) faire g+--g+1
Ulÿl <-- TÜl
si (T... >:13) faire d<--d--1
Uldl *-- TU]
fin si
j <-- j + 1
fin tant que
si (9 < 1 < d) afficher :1:
sinon si (1 _<_ 9) faire Valeur(g,TR(N, U, 1,9), !)
si (l 2 d) faire Valeur(N ---- d + 1, TR(N, U, d, N),l -- d + 1)
fin si
sinon retourner "! NON VALIDE"

fin si

Exercice 3

Soit n un entier naturel. On dit que n est un nombre parfait si 277. est la 
somme des entiers naturels
diviseurs de n. Par exemple, l'entier 6 est un nombre parfait puisque 2 >< 6 = 
12 = 6 + 3 + 2 + 1.
Ecrire un programme qui détermine la liste des nombres parfaits n tels que n 
_<_ 9999.

Exercice 4

Un entier naturel 77. étant donné, on calcule le produit prod(n) de ses 
chiffres dans son écriture en
base 10, puis le produit des chiffres de prod(n) dans son écriture en base 10, 
et on recommence
ainsi l'application de prod jusqu'à obtenir un chiffre entre 0 et 9. Le nombre 
minimal de fois
où on applique prod pour transformer n en un chiffre entre 0 et 9 est appelé la 
persistance de
n. Par exemple, la persistance de 9 est égale à. O, celle de 97 est égale à 3, 
car prod(97) =
9 >< 7 = 63,prod(ô3) = 6 >< 3 = 18,prod(18) = 1 >< 8 = 8, et celle de 9575 est 
égale à 5, car
prod(9575) = 1575,pr0d(1575) = 175,prod(175) = 35,prod(35) = 15,prod(15) = 5. 
Ecrire un
programme qui calcule le plus petit entier naturel de persistance 5.

Exercice 5

On considère l'alphabet à deux lettres: 2 = {a, à}.

Soit n un entier naturel non nul. Un buffer de taille n est modélisé par un 
automate A,, =
(Q... A... 0,Fn) sur l'alphabet E défini par ;

0 Q... l'ensemble des états de A,, est l'ensemble {O, 1, 2, ..., n}. L'état i 
représente la présence
de exactement z' bits dans le buffer.

. La lettre & représente l'arrivée d'un bit dans le buffer. La lettre â 
représente la sortie d'un

bit du buffer.

. A... est l'ensemble des transitions de An :

-- % EUR {O, ...n -- 1}, (i,a,z' + 1),
---- Vz' EUR {1,...,n}, (i,â,z' - 1),

o 0 est l'état initial de A...
. F,, = {O, ...,n} est l'ensemble des états finaux.

On note En le langage reconnu par l'automate A... Dans la suite, 6 désigne le 
mot vide.

1. Soient m, n des entiers naturels non nuls. Justifier précisément 
l'équivalence :

£...C£n©m b.

Que signifie ceci pour les avions de cette compagnie ?

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



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

Ce sujet comporte six exercices complètement indépendants qui permettent de
réviser la quasi-totalité du cours d'informatique. La difficulté n'est pas 
homogène :
certains exercices ne posent guère de difficultés tandis que d'autres 
nécessitent des
rédactions délicates.
· Le premier exercice concerne la programmation sur des listes et des tableaux.
Les codes demandés ne sont pas compliqués. Il faut en revanche réfléchir un peu
si l'on ne veut pas se retrouver à écrire des fonctions d'une page de long.
· Le deuxième exercice propose de reconnaître des morceaux de codes. Les deux
premiers se comprennent très facilement. En revanche, le dernier est plus 
délicat
à identifier et l'explication de son rôle n'est de surcroît pas simple à 
rédiger.
· Les exercices 3 et 4 demandent d'écrire des fonctions d'arithmétique. Les 
codes
sont simples et très courts.
· Le cinquième est un problème classique d'automates. C'est la partie la plus
difficile à rédiger même si l'intuition du résultat vient rapidement.
· Pour finir, le sixième exercice porte sur la logique. Il est court et sans 
prétention.
Tout ceci constitue finalement une épreuve variée et intéressante bien qu'elle 
ne
propose pas l'étude approfondie d'une problématique précise. C'est un très bon 
sujet
pour vérifier que l'on maîtrise l'ensemble des connaissances du programme.

Indications
1.a Utiliser des boucles pour parcourir le tableau tout en comparant les données
d'indices (i, j) et (j, i).
1.b Écrire une fonction récursive qui compare dans un premier temps les têtes de
listes puis effectue un appel récursif sur les queues.
1.c Utiliser la variable x comme une variable indiquant l'état possible du 
tableau
et initialisée à 0 (le tableau est supposé constant au départ). Comparer T[i]
et T[i+1] pour i allant de 0 à  - 1 et mettre à jour la variable x en fonction
des résultats des tests.
Pour le programme de fusion, commencer par déterminer l'ordre des tableaux
puis écrire une version modifiée de la fonction de fusion vue en cours sur les 
tris.
2.a Justifier que le code retourne la plus petite valeur dont le carré est 
supérieur
à 2007.
2.b Justifier que la première fonction extrait une partie d'un tableau T. 
Démontrer
ensuite que la seconde fonction renvoie la -ième plus petite valeur pour l'ordre
naturel sur les entiers parmi les éléments du tableau T.
3 Écrire dans un premier temps un programme qui calcule la somme des diviseurs
d'un entier n (qui fonctionne à l'aide d'une boucle).
4 Écrire une fonction récursive qui calcule le produit des chiffres d'un entier 
n en
utilisant la division euclidienne de n par 10.
Écrire ensuite un code récursif qui calcule la persistance d'un entier n. 
Remarquer que sauf cas particulier, cette dernière est égale à celle du produit 
des
chiffres de n augmentée de 1.
5.1 Prouver que si m > n, le mot am est rejeté dans l'automate An à la lecture 
du
(n + 1)-ième a.
5.2 Justifier que L1 = {aa} {, a}.

5.3 Décomposer un mot u de L2 suivant le parcours effectué dans A2 à la lecture
de ce mot.
5.4.a Utiliser une technique similaire à la question précédente, sachant que 
l'on doit
revenir à 0.
5.4.b Même remarque qu'à la question précédente, sachant que l'on doit cette 
fois
aboutir en j.
5.4.c Démontrer par récurrence sur n que l'on peut calculer une expression de 
L0,j
n
pour tout entier n et tout j  [[ 0 ; n ]].
S
Remarquer ensuite que Ln = 06j6n L0,j
n .
6.1 Utiliser le connecteur logique = pour représenter les formules.
6.2 On rappelle que x = y est équivalent à (¬x)  y.
6.3 Démontrer l'impossibilité de contredire la formule à l'aide de la table de 
vérité.

Pour une épreuve touchant à des domaines aussi variés du programme,
il est difficile de dresser une synthèse globale des difficultés rencontrées par
les élèves. Toutefois, la lecture du rapport révèle deux principaux écueils :
· les programmes obscurs et/ou non commentés ; si le jury n'accorde
pas une importance démesurée à la justesse syntaxique, il est toutefois
sensible au fait que chaque fonction soit dissociée en plusieurs sousprogrammes 
ou que chaque partie du code comporte des explications.
· les questions théoriques mal justifiées ; il est fréquent que les résultats
de certaines questions soient rapidement devinés, mais les élèves sont
parfois incapables de les justifier rigoureusement. Le rapport du jury
rappelle donc à juste titre que les épreuves d'informatique nécessitent
autant de rigueur que celles de mathématiques.

Exercice 1
1.a L'énoncé n'est pas clair dans cette question. La variable resultat suggère 
de
renvoyer un booléen. Pourtant, 0 ou 1 sont du type entier. Faisons donc le 
choix de
respecter la signature de la fonction, et donc de renvoyer des booléens.
Pour déterminer si une matrice A est symétrique, il suffit de vérifier la 
définition c'est-à-dire vérifier que Ai,j = Aj,i pour tout (i, j)  [[ 1 ; n ]]2 
. Il suffit pour
cela d'utiliser deux boucles imbriquées qui parcourent tous les couples 
d'indices
(i, j)  [[ 1 ; n ]]2 . On peut toutefois remarquer que l'on peut se contenter 
des couples
satisfaisant i < j pour raccourcir les boucles. Par défaut, la matrice est 
supposée
symétrique. La variable x est ainsi initialisée à true. Lorsqu'on trouve un 
couple (i, j)
qui ne vérifie pas la condition Ai,j = Aj,i , cette variable passe à false et 
l'exécution
peut s'arrêter. À la fin de l'exécution, il n'y a plus qu'à renvoyer le contenu 
de x.
On obtient alors le code suivant. Le type 'a vect vect est ici utilisé pour M 
mais
d'autres possibilités sont envisageables (comme le type 'a list list).
let Sym M n =
let x = ref true and i = ref 0 and j = ref 1 in
while !x = true && !i < n do
while !x = true && !j < n do
if M.(!i).(!j) <> M.(!j).(!i) then x := false;
incr j;
done;
incr i;
j:=i+1;
done;
!x;;
Comme dans la plupart des codes testant si un certain nombre de propriétés
sont satisfaites par une donnée, on gagne du temps en stoppant l'exécution
quand une condition n'est pas satisfaite. Il faut bien noter toutefois que cela
ne change jamais la complexité dans le pire des cas, et que l'on améliore
rarement
l'ordre de grandeur de la complexité moyenne (qui ici reste en

O n2 opérations élémentaires).

1.b Pour tester si deux listes sont égales, il suffit de vérifier si leurs 
têtes et
leurs queues sont égales. Cela donne la version récursive suivante de la 
fonction
Egalite_listes. La récursivité s'arrête lorsque l'on atteint la fin d'une liste 
(à savoir
une valeur -1), auquel cas il faut simplement vérifier que l'on est également à 
la fin
de l'autre liste.
let rec Egalite_listes L L' =
match (L,L') with
|([-1],_) -> (hd L') = [-1]
|(_,[-1]) -> (hd L) = [-1]
|(a::q,b::r) -> if a=b then Egalite_listes q r else false
|(_,_) -> failwith "Liste non conforme" ;;
Le symbole "-" de tiret est interprété comme une soustraction par Caml
et ne peut être utilisé au sein d'un nom de variable. C'est pourquoi il a été
remplacé par le symbole "_" (tiret bas, ou plus communément underscore)
dans le nom de la fonction Egalite_listes. Suivre scrupuleusement le nom
choisi par l'énoncé conduit à une erreur de compilation.
Le programme donné ci-dessus ne fonctionne que pour les listes respectant les 
conventions de l'énoncé. Notamment, il ne s'applique que pour des
listes d'entiers, et génère une erreur s'il n'y a pas de -1 dans l'une des 
listes.
Il est très facile de modifier le programme précédent pour qu'il fonctionne
quel que soit le type de liste :
let rec Egalite_listes L L' =
match (L,L') with
|([],_) -> L' = []
|(_,[]) -> L = []
|(a::q,b::r) -> (a=b)&&(Egalite_listes q r) ;;
Au passage, on profite de l'évaluation paresseuse des booléens pour raccourcir
le code (l'appel récursif n'est effectué que si le premier test a réussi).

1.c Pour déterminer la nature d'un tableau, initialisons la variable x à 0, ce 
qui
signifie que le tableau est supposé constant par défaut. Parcourons alors le 
tableau de
gauche à droite en comparant T[i] et T[i+1] pour i allant de 0 à n - 1, en 
mettant
à jour la variable x. Tant que la variable est à 0, plusieurs cas sont 
envisageables :
· T[i] < T[i+1] : le tableau ne peut plus être constant. En revanche, il peut
toujours être rangé par ordre croissant. On passe donc la variable x à 1.
· T[i] > T[i+1] : à nouveau, le tableau ne peut plus être constant. Cependant,
il peut être rangé par ordre décroissant. On passe donc la variable x à -1.
· T[i] = T[i+1] : il n'y a rien à faire.
Lorsque l'on est passé dans l'état 1, il n'y a plus que deux cas de figures 
pour la
mise à jour de x :
· T[i] <= T[i+1] : il n'y a rien à faire.
· T[i] > T[i+1] : le tableau ne peut plus être trié ni par ordre croissant, ni 
par
ordre décroissant. On passe donc la variable x à 2.