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)
     

Énoncé obtenu par reconnaissance optique des caractères


L-eni

Option informatique O
pl

MP ©

4 heures Calculatrice autorisée ON

Les candidat devront utiliser le langage Caml, à l'exclusion de tout autre, 
pour traiter ce sujet. Ils devront donner
le type de chaque fonction écrite.

Dans tout le problème, n désigne un entier naturel non nul.
Six e {0;1}, x désigne 1 -- x.
On note @ l'opérateur ou exclusif (également appelé XOR). Il est défini sur {0; 
1} par la table suivante :

0 1
00 1
111,0

On prolonge cette définition à N de la manière suivante.
Soit (x,y) EUR N? vérifiant x < 2 et y < 2 où p est un entier naturel non nul. On décompose x et y en base 2: p p Ti S ay2* et y = ÿ bof, k=0 k=0 où les coefficients a; et b, sont des éléments de {0;1}. On définit alors x @ y par: p rOY-- Sax @ by)2f. k=0 I Code binaire de Gray On cherche à obtenir tous les n-uplets composés de 0 et 1 de deux manières différentes. Ces n-uplets seront implémentés à l'aide de listes. IA - Dans cette sous-partie, on obtient ces n-uplets dans l'ordre lexicographique. Q 1. Écrire une fonction suivant transformant un n-uplet en son suivant dans l'ordre lexicographique. Par exemple, si t = (0;1;0;0;1;1;1), après exécution de suivant (t), on at -- (0;:1;0;:1:0;0;0). Cette fonction modifie la liste qu'elle reçoit en argument. De plus elle renvoie un booléen, valant vrai si elle a pu déterminer un n-uplet suivant, ou bien faux si le n-uplet fourni en argument était le dernier. Dans ce dernier cas, la valeur de ce n-uplet après exécution de la fonction est non spécifiée. Q 2. Écrire une fonction affichant tous les n-uplets dans l'ordre lexicographique. On pourra commencer par écrire une fonction affichant les éléments d'un n-uplet : affiche _nuplet : int list -> unit

I.B - Pour certaines applications, par exemple pour éviter des états 
transitoires intermédiaires dans les
circuits logiques ou pour faciliter la correction d'erreur dans les 
transmissions numériques, on souhaite que le
passage d'un n-uplet au suivant ne modifie qu'un seul bit. Dans un brevet de 
1953, Frank Gray! définit un ordre
des n-uplets possédant cette propriété.

Pour produire la liste des n-uplets dans l'ordre de Gray, un algorithme 
consiste à partir de la liste des 1-uplets
(0, 1) et à construire la liste des (n + 1)-uplets à partir de celles de 
n-uplets en ajoutant un 0 en tête de chaque
n-uplet puis un 1 en tête de chaque n-uplet en parcourant leur liste à 
l'envers. On obtient ainsi pour n = 2, la
liste (00, 01, 11, 10), pour n = 3, la liste (000, 001, 011, 010, 110, 111, 
101, 100), etc.

Les n-uplets sont représentés par des listes, une liste de n-uplets sera donc 
une liste de listes.

Q 3. Écrire une fonction ajout telle que si a est un entier et { une liste de 
n-uplets d'entiers, ajout a 1
renvoie une liste contenant les éléments de / auxquels on a ajouté a en tête.

Frank Gray (1887-1969) était un chercheur travaillant chez Bell Labs ; il à en 
particulier produit de nombreuses innovations dans
le domaine de la télévision.

2019-03-18 17:25:07 Page 1/3 (cc) BY-NC-SA
Q 4. Écrire deux fonctions mutuellement récursives monte et descend prenant en 
argument un entier n et
renvoyant les n-uplets dans l'ordre de Gray. L'une les renverra de 00...0 à 
10...0, l'autre en sens inverse.

Q 5. Évaluer la complexité de ces fonctions en termes d'appels à monte et 
descend.
Q 6. Décrire une façon simple d'améliorer cette complexité.
I.C - Dans tout ce qui suit, l'expression représentation binaire, désigne la 
représentation traditionnelle

en base 2. Étant donné k EUR N*, on a de manière unique
P .
k -- da? avec pEN, a EURe{0;1}, a, #0

La représentation binaire canonique de k est aa (le bit de poids fort, qui est 
non nul, en premier). On dira
que tout n-uplet constitué d'un nombre quelconque de 0 suivis de la 
représentation binaire canonique de Æ est
une représentation binaire de k.

On définit une fonction g sur N de la manière suivante. Pour k EUR N et n tel 
que £ < 2", on considère la liste dans l'ordre de Gray des 2" n-uplets : on indice cette liste de 0 à 2° -- T ; g(k) est le nombre dont une représentation binaire est le n-uplet d'indice k. Par exemple, si on énumère les 3-uplets selon l'ordre de Gray, on a (000, 001, 011, 010, 110, 111, 101, 100). Dans cette liste, l'élément d'indice 0 est 000 donc g(0) = 0, le 3-uplet d'indice 7 est 100 donc g(7) = 4. Soit n un entier naturel et & un entier compris entre 2" et 212 1:k=92" +7 avec 0 < r < 2". Q 7. Démontrer que g(k) = 2" + g(27--1--7r). Q 8. En déduire que, si la représentation binaire de k est b,,---0, et si on pose b,,, -- 0, la représentation binaire de g(k) est a,---aÿ où, pour tout j entre 0 et n, a; =b;@b;,1. Q 9. Exprimer, pour k EUR N, g(k) en fonction de k (à l'aide de @). Q 10. Montrer que g est une bijection de N dans N et, avec les notations précédentes, exprimer b; en fonction de az, k 2 j. ID -- On cherche à réaliser les fonctions g et g ! avec des circuits logiques. Une porte logique sera représentée par un rectangle contenant son nom (AND, OR, XOR, NOT) et on indiquera les entrées et sorties par des flèches. Par exemple : AND -- On se place d'abord dans le cas n = 3. Q 11. Donner un circuit logique à 3 entrées représentant les trois bits d'un entier k inférieur ou égal à 7 et à trois sorties représentant les trois bits de g(k). On pourra utiliser la porte logique XOR. Q 12. Donner un circuit pour l'opération inverse. Q 13. Sin > 2, donner un circuit permettant de passer d'un nombre k à n bits à 
g(k). Faire de même pour
l'opération inverse en utilisant le moins possible de portes. Préciser le 
nombre de portes utilisées.

II Enumération des combinaisons

On souhaite maintenant parcourir toutes les combinaisons de p éléments pris 
dans un ensemble de cardinal n
avec 0 < p < n. On supposera que cet ensemble est celui des n premiers entiers naturels. On le note E,, : E, = {0,..,n -- 1}. Les éléments d'une combinaison de Æ, seront systématiquement considérés dans l'ordre Croissant. IT. À - On se place dans le cas p -- 5. Q 14. Écrire une fonction d'argument n affichant les combinaisons de 3 éléments pris dans {0,...,n -- 1}: on souhaite que ces combinaisons apparaissent dans l'ordre lexicographique. Par exemple pour n = 4: 1[0,1,2}, 10, 1,3], [0,2,3), [1,2,3]. II. B --- On revient au cas p entier quelconque entre 1 et n. Q 15. Donner la première et la dernière combinaison de p éléments de E, (p < n) lorsqu'on énumère ces combinaisons dans l'ordre lexicographique. On suppose que Cj---c,_, est une combinaison de Æ,, vérifiant cj < + < c,_1, stockée sous la forme d'un vecteur ou d'un tableau ; on suppose également que cette combinaison n'est pas la dernière. Q 16. Ecrire une fonction comb_suivante permettant de transformer une combinaison en la combinaison suivante dans l'ordre lexicographique. On pourra commencer par chercher le plus petit indice j tel que Cjn > C+lL

2019-03-18 17:25:07 Page 2/3 (Cc)EATE:
Q 17. En déduire une fonction d'arguments n et p, énumérant et affichant toutes 
les combinaisons de p
éléments de Æ,, dans l'ordre lexicographique.

Q 18. Déterminer le nombre de combinaisons affichées avant d'arriver à la 
combinaison c--c,_1.

Q 19. En déduire que tout nombre entier naturel non nul N peut s'écrire sous la 
forme

"y

oOÙÙULN << <--  3) objets 05,0, _, et d'un sac 
dont la charge maximale
est M. Chaque objet o;, a une valeur v, et une masse m,. Soit p un entier entre 
1 et n -- 2. On veut choisir p
objets parmi les n de façon à ce que la masse totale de ces p objets soit 
inférieure à M et leur valeur totale soit
la plus grande possible.

Q 22. De quelle manière peut-on utiliser la fonction ci-dessus pour résoudre ce 
problème ?

Q 23. Évaluer le nombre d'additions effectuées (on ne s'intéressera qu'aux 
additions entre m, et entre v,).

IT. D --- Pour améliorer cet algorithme, on souhaite passer d'une combinaison à 
une autre en ne faisant que
deux modifications.

Q 24. Expliquer comment représenter une combinaison de p éléments pris parmi n 
par un n-uplet de O0 et 1.

Q 25. Modifier les fonctions monte et descend de la question 4 pour qu'elles 
renvoient les n-uplets représen-
tant les combinaisons de p éléments pris parmi n, dans le même ordre que 
précédemment.

Q 26. Déterminer le premier et le dernier n-uplet renvoyé par l'appel monte n p.

Q 27. Montrer qu'entre deux éléments successifs de la liste de n-uplets 
renvoyés par monte ou descend, seuls
deux bits changent. Montrer que cette propriété est également vraie entre le 
dernier et le premier n-uplets.

Soit a l'un de nos n-uplets, et soit a" son successeur. On admet qu'il existe 
un unique entier 7, 1 < 7j < max(p,n -- p) tel que g (a) -- g (a) = 2} mod 2" Q 28. En déduire un algorithme simple pour passer d'un n-uplet contenant p bits à 1 au suivant. Le décrire et le programmer sous la forme d'une fonction suivant. ILE -- Q 29. En déduire un algorithme qui donne un remplissage optimal du sac. Cet algorithme aura comme entrée : -- les valeurs des n objets, -- Jes masses des n objets, dans le même ordre, -- l'entier p, -- Ja masse maximum M. Il rendra en résultat les p indices des objets choisis. On ne demande pas la programmation explicite de cet algorithme. eeeFrINeee 2019-03-18 17:25:07 Page 3/3 (C2) BY-NC-SA

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).