Centrale Informatique optionnelle MP 2019

Thème de l'épreuve Code de Gray, énumération de combinaisons et sac à dos
Principaux outils utilisés programmation, combinatoire, représentation binaire
Mots clefs code de Gray, combinaisons, ou exclusif, énumération, sac à dos

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)
     

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



Centrale Informatique optionnelle MP 2019
Corrigé
Ce corrigé est proposé par Olivier Levillain (enseignant-chercheur en école 
d'ingénieurs) ; il a été relu par Guillaume Batog (professeur en CPGE) et par 
Benjamin
Monmege (enseignant-chercheur à l'université).

Le sujet traite principalement du code binaire de Gray. Ce code décrit un 
algorithme pour énumérer les éléments de l'intervalle [[ 0 ; 2n - 1 ]] de 
manière à ce que
chaque transition ne modifie qu'un seul bit de la représentation binaire. Cette 
propriété peut s'avérer intéressante lorsque modifier un bit est une opération 
coûteuse
(actionnement d'un interrupteur, courant électrique nécessaire). Le sujet est 
organisé
en deux parties :
· Dans la première partie, il est question d'écrire du code pour énumérer les
n-uplets, tout d'abord de manière naïve, puis en utilisant le code de Gray.
L'énoncé propose ensuite d'étudier quelques propriétés de ce code, en 
particulier
la relation entre k et le k-ième élément du code de Gray.
· La seconde partie traite des combinaisons de p éléments pris dans un ensemble
de cardinal n. Il est proposé de développer du code pour énumérer ces 
combinaisons de plusieurs manières, et d'établir quelques propriétés liées à la 
décomposition combinatoire de degré p d'un entier. Les dernières questions de la
seconde partie consistent à étudier le problème du sac à dos en réutilisant des
résultats sur le code de Gray et sur les combinaisons de p éléments parmi n.
L'énoncé comporte 29 questions de difficultés très variées. Certaines questions
sur les combinaisons sont assez peu guidées et nécessitent de l'intuition pour 
les
résoudre. Les questions de programmation sont assez nombreuses et assez 
abordables.
Globalement, ce sujet couvre plusieurs thèmes classiques pour ce type 
d'épreuve. Il
s'agit donc d'un bon entraînement pour les concours, une fois les quelques 
coquilles
de l'énoncé corrigées (voir les indications).

Indications
Partie I
1 L'énoncé indique qu'il faut modifier la liste reçue en argument, mais il ne 
faut pas
prendre cette consigne littéralement, puisque les listes sont immuables en Caml.
Plutôt écrire une fonction de type int list -> int list * bool.
6 La question n'est pas très claire, mais une réponse simple vient 
naturellement si
on remarque que monte et descend sont essentiellement la même fonction.
8 Cette question peut se résoudre par récurrence. Il faudra utiliser la 
relation entre
la représentation binaire de 2n - 1 - r et celle de r.
10 On peut montrer que, pour tout n > 0, g est une bijection de l'intervalle [[ 
0 ; 2n -1 ]]
dans lui-même. Pour cela, pour un y donné, on pourra exhiber un antécédent de y
par g.
Partie II
16 La recherche de la combinaison suivante peut se faire via deux mécanismes : 
soit
on incrémente la dernière composante du tableau, soit on est obligé 
d'incrémenter
une autre composante. Pour ce deuxième cas, contrairement à ce que dit l'énoncé,
il faut en réalité s'intéresser au plus grand indice j tel que cj+1 > cj + 1.
18 Il semble plus aisé pour résoudre cette question de calculer le nombre de 
combinaisons affichées après la combinaison c0 · · · cp-1 . En effet, ce nombre 
peut s'exprimer
comme une somme de combinaisons, ce qui sera utilisé dans la question 19.
19 On utilisera la somme trouvée à la question 18.
20 Il faut commencer par prouver le lemme proposé à l'aide de propriétés 
classiques
sur les coefficients binomiaux.
21 On suppose qu'il existe deux décompositions et on s'intéresse au plus grand 
indice k tel que nk diffère de nk . On cherche ensuite à établir une inégalité 
en
utilisant la question précédente, ce qui devrait mener à une contradiction.
23 Pour évaluer la complexité de l'algorithme proposé, on peut considérer que la
masse cumulée et la valeur cumulée sont systématiquement calculées, même si
une optimisation évidente est possible. On obtient alors la complexité dans le
pire cas.
25 Ajouter un paramètre p aux fonctions, et assurer la contrainte suivante : 
les listes
produites doivent contenir exactement p éléments à 1.
27 Cette question se traite par récurrence sur n. Penser à utiliser les données 
de
l'énoncé sur n et p pour bien démarrer la récurrence.
28 Contrairement à ce que dit l'énoncé, la propriété à admettre est qu'il 
existe un
unique entier j tel que g -1 (a ) - g -1 (a)  2j mod 2n (on inverse a et a ). 
Avec
cette propriété, il suffit d'essayer tous les a possibles à partir de a. Pour 
cela, on
utilisera g, g -1 , l'ajout de 2j et on testera que le candidat contient bien p 
bits à 1.

I. Code binaire de Gray
1 La fonction demandée nécessite dans un premier temps de parcourir la liste 
jusqu'à
son dernier élément. Si cet élément vaut 0, on met l'élément à 1 et on 
reconstruit le
reste de la liste à l'identique. Si l'élément final vaut 1, on le met à 0 et on 
propage la
retenue, c'est-à-dire qu'on va ajouter 1 à l'élément immédiatement au-dessus.
La propagation de la retenue se fait en renvoyant false, alors que true signifie
qu'il n'y a plus rien à faire. Cette propagation s'arrête lorsqu'on rencontre 
un 0.
Si on ne rencontre aucun 0, l'argument passé était le dernier n-uplet dans 
l'ordre
lexicographique, et la fonction renvoie false, comme demandé.
La fonction suivant est du type int list -> int list * bool et peut être
implémentée de la manière suivante :
let
|
|
|
|

rec suivant t = match t with
[] -> [], false
(* cas impossible puisque n > 0 *)
[0] -> [1], true
[1] -> [0], false
b::bs -> let nouv_bs, retenue = suivant bs in
match b, retenue with
| _, true -> b::nouv_bs, true
| 0, false -> 1::nouv_bs, true
| 1, false -> 0::nouv_bs, false;;
L'énoncé demande d'implémenter une fonction transformant un n-uplet, mais
indique que ces n-uplets doivent être implémentés à l'aide de listes, qui sont
par nature immuables. Au sens strict, la fonction proposée ne transforme pas
la liste passée en argument, mais en reconstruit une nouvelle. Une solution
alternative aurait été d'utiliser des références pour stocker les valeurs (le 
type
d'un n-uplet aurait alors été int ref list), mais cela n'est pas cohérent avec
l'énoncé de la question suivante qui utilise le type int list.

2 Comme le suggère l'énoncé, il est pratique d'avoir une fonction affiche_nuplet
pour afficher les éléments d'un n-uplet. On peut l'écrire de façon récursive 
sur la liste
en ajoutant un saut de ligne à la fin :
let rec affiche_nuplet l = match l with
| [] -> print_newline ()
| x::xs -> print_int x; affiche_nuplet xs;;
Ensuite, la fonction affiche_nuplets, de type int -> unit, prend en argument
la taille des n-uplets considérés. Elle construit le n-uplet uniquement composé 
de 0.
Puis, la fonction parcourt l'ensemble des n-uplets à l'aide de la fonction 
suivant
de la question précédente, en affichant chaque valeur. La fonction s'arrête 
lorsque
suivant signale que le dernier élément a été atteint.
let affiche_nuplets n =
let rec zero k =
if k > 0 then 0::(zero (k-1)) else []
in
let rec parcours x =
affiche_nuplet x;
let s, valide = suivant x in
if valide then parcours s
in parcours (zero n);;

3 Écrivons la fonction ajout de manière récursive. Elle est de type int -> int
list list -> int list list.
let rec ajout a l = match l with
| [] -> []
| x::xs -> (a::x)::(ajout a xs);;
En réalité, la fonction ci-dessus a un type plus général que celui annoncé,
puisque rien n'impose que les éléments des listes considérées soient des 
entiers.
Le type inféré par Caml sera 'a -> 'a list list -> 'a list list.
4 Ces deux fonctions s'écrivent naturellement de manière récursive, à partir de 
la
définition du code de Gray. Elles ont pour type int -> int list list.
let rec monte
if n <= 0
then [[]]
else (ajout
and descend n
if n <= 0
then [[]]
else (ajout

n =

0 (monte (n-1))) @ (ajout 1 (descend (n-1)))
=

1 (monte (n-1))) @ (ajout 0 (descend (n-1)));;

5 Chaque appel à monte ou à descend avec un argument n+1 strictement positif
mène à un appel à chaque fonction avec l'argument n. En notant Cn la complexité
de monte (ou de descend, par symétrie) en nombre d'appels pour une taille n, on
obtient donc :
Cn+1 = 2 + 2Cn
En considérant la suite un = 2 + Cn , on a, pour tout n > 0,
un+1 =
=
=
un+1 =

2 + Cn+1
4 + 2Cn
2(2 + 2Cn )
2un

Sachant que C0 vaut 0, (un ) est une suite géométrique de raison 2 et de valeur
initiale u0 = 2. Ainsi, pour tout n,
d'où

un = 2n
Cn = 2 n - 2
La complexité des fonctions décrites est donc
exponentielle en le nombre d'appels récursifs.

6 On peut remarquer que descend et monte calculent essentiellement la même
chose, et qu'il suffit d'inverser la liste renvoyée par une de ces fonctions 
pour trouver
le résultat de l'autre fonction. Il est donc inutile de définir les deux 
fonctions. Le
code suivant conserve monte et remplace l'appel à descend (n-1) par un appel à
List.rev sur le résultat de monte (n-1).