Centrale Informatique MP 2002

Thème de l'épreuve Le problème de la remise de monnaie
Principaux outils utilisés raisonnement par l'absurde, récursivité, récurrences

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


 % e....___... ...30_Ëëoec..._z_ ää... NËN ooeäofiOE - QOEÈOEU OE:oocoü Préliminaires : Le sujet traite du problème du monnayeur : comment rendre la monnaie en utilisant le plus petit nombre possible de pièces ? Les deux premières parties mettent en place le for-- malisme et les outils qui serviront pour la suite. On étudiera dans la partie III « l'algorithme glouton ». Ladernière partie présente un algorithme permettant de décider si l'algorithme glouton est optimal pour un système de pièces donné. Cette dernière partie utilise les résultats établis dans les parties précédentes. Il est rappelé que cette épreuve est une épreuve d'informatique, et que l'absence de programmes sera donc sanctionnée comme il se doit. Les algorithmes demandés seront décrits en français ; les programmes seront rédigés en langage Caml ou en langage Pascal. Les candidats indiqueront impérativement au tout début de leur copie le langage de programmation qu'ils ont choisi d'utiliser. Une approche modulaire est vivement conseillée, comme l'a indiqué René Descartes, il convient « de diviser chacune des difficultés que j'examinerais- en autant de parcelles qu'il se pourrait, et qu'il serait requis pour les mieux résoudre ». Lorsque les candidats choisiront d'écrire une fonction annexe non demandée, il leur est demandé avec insis- tance d'expliquer avant les spécifications de Cette fonction. Certaines questions ou remarques sont réservées soit aux candidats ayant choisi le lan- gage Caml, soit à ceux ayant choisi le langage Pascal. Dans ce cas, la question ou remar-- que est annoncée par un encadré, et se termine par un trait de séparation pointillé ou un nouvel encadré. . Pour les questions de complexité, on demande d'évaluer les coûts globalement en terme d'opérations élémentaires telles que des affectations, des opérations arithmétiques, compa- raisons, tests... En particulier, on ne s'attachera pas à des considérations concernant la taille des données. Notations : ° Lorsque E est un ensemble fini, )El désigne son cardinal. ° Lorsque x E IR, ij désigne la partie entière inférieure de x , et Îxl sa partie entière supérieure : ce sont les uniques entiers relatifs vérifiant __\ ijsx c2 > > c = 1 . Isism m ki est donc le nombre de pièces (Ci) qui seront rendues. Pour épargner les poches des clients, nous souhaitons minimiser le poids de cette représentation, c'est-à-dire la quantité: m llkll= Eki=k°l, i=l avec 1 = (1, 1) (le m -uplet dont toutes composantes sont égales à 1 ). Partie I - Systèmes de pièces Note à l'attention des candidats qui ont choisi le langage Caml Nous utiliserons des listes d'entiers pour représenter aussi bien un système (liste de valeurs de pièces) qu'une représentation d'un montant dans ce système. Par exemple, la liste [4 ; 1 ; 3 ] est une représentation de 30 dans le système (6, 3, 1) .' | La question suivante est destinée aux candidats qui ont choisi le langage Caml \ I.A - Rédiger en Caml une fonction de signature est_un_systeme : int list --> bool spécifiée comme suit : est_un_systeme c indique si la liste c est bien un sys- tème. Par exemple, est_un_systeme [ 5 ; 2 ; 1 ] rendra la valeur true, tandis que est_un_systeme [5 ; 7 ; 1 ]rendra la valeur false, tout comme le fera est_un_systeme [7;5;2]. Note à l'attention des candidats qui ont choisi le langage Pascal. Nous utiliserons des listes d'entiers pour représenter aussi bien un système (liste de valeurs de pièces), qu'une représentation d'un montant dans ce système. Le type utilisé est défini comme suit : type Liste = "Cellule; type Cellule = record contenu : integer; suivant : Liste end ; La liste vide est représentée par la constante nil. Pour créer des listes, nous dis- posons d'une procédure et d'une fonction dont les en-têtes sont : procedure pCons(x:inteqer; var c:Liste); function fCons(x:integer; c:liste):Liste; spécifiées comme suit : pCons(x, c) ajoute en tête de liste c une cellule dont le champ contenu vaut x. fCons(x,c) rend une liste dont la première cellule contient x dans son champ contenu , et dont le champ suivant vaut c. Par exemple, le programme suivant construit les listes Ll : (5,2, 1), L2 : (5,7, 1) et L3 : (7, 5,2) dont il sera question dans la suite . var L1,L2,L3:Liste; begin Ll:=nil; pCons(l,L1); pCons(2,L1) ; pCons(5,L1); L2:=fCons(5,fCons(7,fCons(l,nil))); L3:=fCons(7,fCons(5,fCons(2,nil))); end; La question suivante est destinée aux candidats qui ont choisi le langage Pascal. I.B - Rédiger en Pascal une fonction d'en--tête function est_un_systeme(c:Liste):boolean; spécifiée comme suit : est_un_systeme(c) indique si la liste c est bien un système. Par exemple, est_un_systeme(Ll) rendra la valeur true, tandis que est_un_systeme(L2) rendra la valeur false, tout comme le fera est_un_systeme(L3). Partie II - Représentations de poids minimal Soient c : (cl, ..., cm) un système et x E ]N. Nous notons Mc(x) (ou même M(x) lorsqu'aucune ambiguïté n'est à craindre) le plus petit nombre de pièces nécessaires pour représenter x dans le système 0 : M(x) : min{llklll kEle et (k-c=x)} Nous nous intéresserons aux représentations de poids minimal de x : ce sont les représentations k telles que llkll : M (x) . Pour alléger la rédaction, nous parle- rons simplement de représentations minimales. II.A - Prouver l'encadrement {î]sM(x)sx. C1 II.B - Exhiber un système c et un nombre x E ]N* possédant plusieurs repré- sentations dans ce système. II.C - Soient c un système et x E ]N* . Montrer que M (x) 5 1 + M (x -- ej) pour tout indice j tel que cj 5 x. II.D - Soient c un système, x E ]N* , etj tel que cj 5 x .Montrer soigneusement que M (x) = 1 + M (x--c j) si, et seulement si, il existe une représentation mini- male k de x , faisant intervenir cj (c'est-à-dire telle que k]. > 0 ). ILE - Soit x > 1 ; notons s le plus petit indice i tel que ci 5 x . Justifier l'égalité M(x) : 1+ min M(x--ci). ssism II.F - Soit x > 0. Montrer que l'on peut construire la liste des valeurs de M ( y) pour y 5 x , pour un coût O(mx) (au sens précisé dans les préliminaires). La question suivante est destinée aux candidats qui ont choisi le langage Caml. II.G - Rédiger en Caml une fonction de signature : poids_minimaux : int -> int list --> int list spécifiée comme suit : poids_minimaux x c construit la liste des valeurs de Mc(y) pour 1 s y 5 x . Par exemple, poids_minimaux 5 [5 ; 2; 1 ] rendra la liste [1 ; 1 ;2 ;2 ;1]. Cet exemple fournit d'ailleurs l'ordre dans lequel on souhaite que les M C( y) apparaissent dans la liste résultat. On utilisera la formule de la question ILE). De plus, on pourra utiliser, si on le souhaite, les fonctions list_of_vect, vect_of_list et make_vect de signatures respectives : list_of_vect :'a vect --> 'a list vect_of_list :'a list --> 'a vect make_vect : int -> 'a -> 'a vect La question suivante est destinée aux candidats qui ont choisi le langage Pascal. II.H - Rédiger en Pascal une fonction d'en-tête , function poids_minimaux(x:integer; c:Liste):Liste; spécifiée comme suit : poids_minimaux ( x, c) rendra une liste des valeurs de M c( y) , pour 1 s y 5 x . Par exemple, poids_minimaux( 5 , L1 ) rendra la liste (1 ,1 ,2 ,2,1) . Cet exemple fournit d'ailleurs l'ordre dans lequel on souhaite que les M c( y) apparaissent dans la liste résultat. On utilisera la formule de la question ILE, et on pourra employer librement la constante mMax, le type vecteur, la fonction vecteur_vers_liste et la pro- cédure liste_vers_vecteur qui pourraient être définis ainsi : const mMax =1000; type vecteur = array[l..mMax] of integer; function vecteur_vers_liste(V:vecteur; r:integer):Liste; var p:Liste; k:integer; begin ' p:= nil; for k:=r downto 1 do pCons(v[k],p); vecteur_vers_liste:=p end; procedure liste_vers_vecteur (L:Liste; var 'v:vecteur;var taillezinteger); begin taille:=0; while L<>nil do begin taillez=taille+l v[taille]:=L".contenu; L:=L*.suivant end end; Ainsi, vecteur_vers_liste ( v, r) retourne la liste des (v,- 1 S i 5 r sous réserve que l'encadrement 1 s r s mMax soit vérifié. Si r s 0 , elle rend la liste vide ; si r > mMax , le résultat n'est pas spécifié. L'appel liste_vers_ vecteur(L,v, t) place quant à lui les éléments de la liste L dans un vecteur v , en mettant à jour la variable t représentant le nom- bre d'éléments de la liste. Partie III - L'algorithme glouton Avertissement : Dans cette partie, on travaillera obligatoirement sur des listes sans passer par des vecteurs. L'algorithme glouton pour rendre une somme x >0 consiste à choisir le plus grand ci 5 x, puis à rendre récursivement x4ci. Par exemple, avec le système c = (10, 5, 2, 1) , l'algorithme décomposera 27 en 10+10+5 +2. Avec le forma- lisme proposé, la solution fournie par l'algorithme glouton est donc k = (2, 1, 1,0) . Le fonctionnement de l'algorithme glouton peut être accéléré par la remarque suivante : notant q : L£J , cet algorithme rend q pièces de valeur c1 , puis rend le C1 montant x -- qc1 en utilisant le système (c2, cm) . La question suivante est destinée aux candidats qui ont choisi le langage Caml. III.A - Rédiger en Caml une fonction de signature : glouton : int --> int list --> int list spécifiée comme suit : glouton x c construit la représentation de x dans le système c en utilisant l'algorithme glouton. Par exemple, glouton 13 [5 ; 2 ; l] rendra la liste [2 ; 1 ; 1]. La question suivante est destinée aux candidats qui ont choisi le langage Pascal. III.B - Rédiger en Pascal une fonction d'en-tête function glouton(x:integer; c:Liste):Liste; spécifiée comme suit : glouton ( x , c ) retourne une liste contenant la représen- tation de x dans le système c , en appliquant l'algorithme glouton. Par exemple, glouton (13 , L1 ) retournera la liste (2,1,1). Soient c : (cl, cm) un système et x E ]N. Nous noterons Fc(x) la représenta- tion gloutonne de x dans le système c , (c'est-à-dire la représentation obtenue en appliquant l'algorithme glouton), et Gc(x) (ou même G(x) lorsqu'aucune ambi-- guïté n'est à craindre) le nombre de pièces utilisées par l'algorithme glouton : Gc(x) = ||rc(x)n. Nous dirons qu'un système @ est canonique lorsque l'algorithme glouton nous donne toujours une représentation minimale ; on a alors M (x) : Gc(x) pour tout x E IN . III.C - Montrer que tout système c : (c1,02) est canonique. III.B - Exhiber un système c : (cl, 02, c3) non canonique (en justifiant). III.E - Soient q et n deux entiers z 2 . Montrer que le système (qn, q" _1 est canonique. , ...,q, 1) III.F - Montrer que le système « Euro » (200, 100, 50, 20, 10, 5,2, 1) est canonique. On pourra montrer que dans une représentation minimale de x: k=(kl,...,k8),onakgs1,2k7+k854,5k6+2k7+k859... III.G -Avant la réforme de 1971 (introduisant un système décimal), le Royaume--Uni utilisait le système (30, 24, 12, 6, 3, 1). Montrer que ce système n'est pas canonique. Partie IV - L'algorithme de Kozen et Zahs Nous allons voir ici un algorithme efficace permettant de déterminer si un sys- tème c est canonique. Nous dirons qu'un entier x est un contre-exemple pour c si M (x) < Gc(x) . Un système canonique n'admet donc pas de contre-exemple. Dans la suite, m 2 3 . IV.A - Soit 0 un système non canonique. Il admet donc des contre-exemples. Montrer que le plus petit d'entre-eux, disons x , vérifie : cm_2+l q tel que le système (a(q), q, 1) ne soit pas canonique, et admette a(q) + 2 comme plus petit contre-exemple. IV.D - Que vient-on de faire dans les deux questions précédentes '? Le résultat de la question IV.A nous donne un algorithme déterminant si un sys- tème est canonique : il suffit de rechercher un contre-exemple dans l'intervalle discret [[cm_2 + 2, c] + 02 -- 1]] . Ceci nécessiterait la construction (coûteuse) des représentations minimales de chacun des éléments de cet intervalle. Nous allons étudier un algorithme plus efficace, dû & Kozen et Zaks. Leur méthode repose sur la notion de témoin. Nous dirons qu'un entier x est un témoin pour le système c : (cl, ...,cm) s'il existe un indice i tel que ci bool spécifiée comme suit : kozen_zaks c indique si la liste c est canonique. Par exemple, kozen_zaks [5 ; 2 ; l] rendra la valeur true et kozen_zaks [ 6 ; 5 ; 1 ] rendra la valeur false. On utilisera l'algorithme de Kozen et Zaks. | La question suivante est destinée aux candidats qui ont choisi le langage Pascal. \ IV.J - Rédiger en Pascal une fonction d'en-tête function kozen_zaks(chiste):boolean; spécifiée comme suit : kozen_zaks ( c) indique si la liste 6 est canonique. Par exemple, kozen_zaks (L1 ) rendra la valeur true. On utilisera l'algorithme de Kozen et Zaks. IV.K - Montrer que le coût de l'algorithme de Kozen et Zaks peut être exponen- tiel, par rapport au nombre m de pièces du système. On exhibera deux systèmes (l'un canonique, l'autre pas) pour lesquels le coût de l'algorithme est exponentiel en m . ooo FIN 000 À titre culturel, on signale l'existence d'un algorithme, dû à Pearson, résolvant le même problème mais dont le coût est polynômial en m dans le pire des cas.

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


 Centrale Informatique MP 2002 -- Corrigé Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été relu par Samuel Mimram (ENS Lyon) et Jean-Baptiste Rouquier (ENS Lyon). Ce sujet traite d'un problème de formulation très simple qui consiste à déterminer comment rendre la monnaie en utilisant le plus petit nombre de pièces. Les valeurs possibles des pièces sont représentées par une liste ordonnée c appelée système. On définit une représentation d'un entier x dans un système comme un ensemble de pièces dont la somme vaut x. Le problème se compose de quatre parties : · La première partie ne comporte qu'une question. Il s'agit d'écrire un programme qui teste si une liste représente bien un système. · La deuxième partie étudie la fonction qui, pour un système c et un entier x, donne le nombre de pièces minimum que doit comporter une représentation de x dans c. On établit une formule de récurrence pour cette fonction, ce qui permet d'implémenter un algorithme calculant ses valeurs. · La troisième partie introduit un algorithme glouton qui, pour un entier x et un système c, donne une représentation de x dans c. On introduit alors la notion de système canonique, pour lequel cet algorithme fournit toujours une représentation minimale, et on détermine si quelques exemples sont ou non canoniques. · Enfin, la quatrième partie amène par quelques questions purement mathématiques à implémenter un algorithme qui décide si un système donné est canonique. Une grande partie de ce sujet est commune à l'épreuve d'informatique de la même année de l'École Polytechnique (qui est d'ailleurs plus détaillé). Dans l'ensemble, il y a relativement peu de programmes à écrire et ils ne sont pas compliqués une fois les questions théoriques résolues (voire admises). Les raisonnements mathématiques demandés sont très hétérogènes. Certaines questions se résolvent très simplement, d'autres sont bien plus difficiles et nécessitent une très bonne intuition et une certaine aisance dans les manipulations de sommes d'entiers. On utilise principalement des raisonnements par l'absurde et des doubles inégalités pour montrer les résultats. Dans l'ensemble, les parties et les questions sont relativement indépendantes les unes des autres. Pour conclure, il s'agit d'un sujet atypique qui ne nécessite quasiment aucune connaissance de cours et seulement une expérience de la programmation. Il est en grande partie abordable, quitte à sauter les questions difficiles. Indications Première partie I.A Écrire une fonction qui teste si le premier élément de la liste est inférieur au second et fait de même, récursivement, sur la suite de la liste. Deuxième partie II.A Considérer une représentation minimale (k1 , . . . , kn ) de l'entier x, dont le poids vaut donc M(x). Écrire que la valeur de x est la somme des valeurs des pièces de sa représentation et utiliser deux majorations grossières. II.B N'importe quel système à deux pièces convient. II.C Construire à partir d'une représentation minimale de M(x - cj ) une représentation de x. II.D Réciproquement, construire une représentation de x - cj à partir d'une représentation minimale de x faisant intervenir cj . II.E Utiliser le résultat des deux questions précédentes en notant qu'une représentation minimale de x fait forcément intervenir au moins un élément cj . II.F Introduire un algorithme qui construit par récurrence, en utilisant le résultat de la question précédente, la suite des valeurs Mc (0), Mc (1), Mc (2), . . . , Mc (x). II.G Implémenter directement l'algorithme de la question précédente. Utiliser de préférence un vecteur dont toutes les coordonnées sont à 0 initialement. Une fois les valeurs de la fonction Mc calculées, utiliser la fonction list_of_vect. Troisième partie III.A Construire un algorithme récursif en utilisant les indications de l'énoncé. III.C Déterminer toutes les réprésentations d'un entier x dans ce système et chercher celle de poids minimum. III.D Considérer le système (6, 5, 1) (qui est proposé par l'énoncé lui-même à la question IV.H). III.E Considérer une représentation minimale d'un entier x et montrer en raisonnant par l'absurde que tous les coefficients de la représentation (sauf éventuellement le premier) sont inférieurs ou égaux à q - 1. En déduire une majoration de x - k1 c1 et la valeur de k1 . Déterminer ensuite la valeur de k2 , k3 et ainsi de suite pour en déduire que la représentation minimale est forcément celle donnée par l'algorithme glouton. III.F Utiliser un raisonnement similaire à celui de la question précédente après avoir démontré ce que suggère l'énoncé. III.G Montrer que 48 est un contre-exemple. Quatrième partie IV.A Pour la minoration, utiliser le résultat de la question III.C. La majoration est plus difficile à montrer. Dans un premier temps, montrer que si x est le plus petit contre-exemple de c, toute représentation minimale de x ne comporte aucune pièce de valeur c1 . Considérer ensuite la représentation gloutonne d'un élément de la forme x - ci bien choisi. IV.B Montrer que 2q est un contre-exemple et que c'est le plus petit. IV.C Montrer que (q) = 2q - 2 convient. IV.D Établir le lien entre les deux questions précédentes et le résultat de la question IV.A. IV.E Si x est témoin, construire une représentation de x de poids strictement inférieur à G(x). IV.F Montrer que 12 est un contre-exemple qui n'est pas témoin. IV.G Si x est le plus petit contre-exemple alors pour tout entier y inférieur à x, on a M(y) = G(y). Raisonner alors par l'absurde et utiliser le résultat de la question II.E. IV.H Appliquer le principe de l'algorithme en calculant G(x) ainsi que les valeurs G(x - ci ) i[[ 1 ; m ]] pour x allant de cm-2 + 2 à c1 + c2 - 1. IV.I Implémenter un algorithme qui détermine si un entier x donné est témoin pour un système c donné (en utilisant la fonction glouton de la question III.A). Utiliser alors une boucle for pour tester si l'un des entiers de l'intervalle [[ cm-3 + 2 ; c1 + c2 ]] est témoin. IV.K Considérer l'exemple de la question III.E. Il suffit alors d'ajouter une pièce au système pour qu'il ne soit plus canonique (s'inspirer des exemples de systèmes non canoniques déjà connus). I. Systèmes de pièces I.A Il suffit d'écrire un programme qui teste si les éléments sont en ordre décroissant, et si le dernier est égal à 1. Pour cela, on teste si le premier élément est plus grand que le second. Si oui, on continue le test sur la liste privée de son premier élément, sinon on renvoie false. Le programme se termine lorsque la liste ne contient plus qu'un élément. Il ne reste alors plus qu'à tester si ce dernier élément est bien égal à 1. Le code du programme est donc le suivant. let rec est_un_systeme l = match l with |[] -> false |[a] -> a = 1 |a::b::q -> if a > b then est_un_systeme (b::q) else false ;; II. Représentations de poids minimal II.A Soient x un entier, c un système de pièces et k une représentation de poids minimal de x. Notons d'une part c = (c1 , . . . , cm ) avec c1 > c2 > · · · > cm = 1 et d'autre part k = (k1 , . . . , km ) avec k1 + · · · + km = M(x) Puisque k est une représentation de x, k1 c1 + · · · + km cm = x Par ailleurs, la suite (ci )i[[ 1 ; m ]] étant une suite décroissante dont le premier terme est c1 et le dernier terme cm est 1, il vient les deux inégalités : k1 + · · · + km 6 x 6 c1 (k1 + · · · + km ) soit, comme k est de poids minimal M(x) 6 x 6 c1 M(x) L'inégalité de droite assure que M(x) est supérieur à x/c1 et, puisqu'il s'agit d'un entier, on a bien x x N 6 M(x) 6 x. c1 II.B Prenons le système c = (2, 1) et x = 2. Alors l'entier x admet deux représentations puisque x=1×2+0×1 et x=0×2+2×1 D'une manière générale, dès qu'un système a au moins deux éléments et que x a une valeur supérieure à celle de l'avant dernière pièce, il admet plusieurs représentations.