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