X Informatique MP 2002

Thème de l'épreuve Porte-monnaie et systèmes monétaires
Principaux outils utilisés algorithmes et complexité, programmation, listes, vecteurs, ordre lexicographique

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE FILIÈRE MP OPTION INFORMATIQUE CONCOURS D'ADMISSION 2002 COMPOSITION D'INFORMATIQUE (Durée : 4 heures) L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie. On attachera une grande importance à. la clarté, a la précision et a la concision de la rédaction. '**'* Dans tout le problème un système monétaire est un ensemble de n entiers naturels non--nuls distincts D : {d1,d2, . . .,dn}, avec n > 0 et dn : 1. Les d,-- sont les dénominations du système. Par convention, les dénominations sont présentées par ordre décroissant. Par exemple, le système de l'euro est l'ensemble {500, 200, 100, 50, 20, 10, 5, 2, 1}. Unesomme (d'argent) est une suite finie (61,62, . . . ,e...) d'entiers appartenant à D. Les éléments de cette suite sont des espèces. On remarquera bien que deux espèces d'une somme peuvent porter la même dénomination, qu'une somme peut être vide, et qu'il n'y a pas nécessairement d'espèces de dénomination 1 dans une somme. Par convention, les espèces sont présentées par ordre de dénominations décroissantes. La valeur d'une somme S, notée V(S), est tout simplement la somme arithmétique de ses espèces, tandis que sa taille, notée |S|, est le nombre de ses éléments (l'entier m ci-dessus). Étant donné un entier naturel 1), une somme de valeur 1) est un représentant de 2). Par exemple, le portefeuille d'un citoyen européen peut contenir 3 billets de 10 euros, deux billets de 5 euros et une pièce de 1 euro. Cette somme est notée (10,10,10,5,5,1), sa valeur est 41 et sa taille 6. Une somme S est emtraz'te d'une autre P dite portefeuille, si et seulement si S est une suite extraite de P. Intuitivement, << la somme S est extraite de P >> signifie que l'on paye sa valeur à l'aide d'espèces prises dans le portefeuille P. Par exemple, notre citoyen européen peut payer exactement 15 euros en extrayant un billet de 10 euros et un autre de 5 euros de son portefeuille. PROGRAMMATION. Dans les deux premières parties du problème, les systèmes monétaires et les sommes sont représentés en machine par des listes d'entiers. (* Caml *) { Pascal} type liste = "cellule ; cellule = record contenu : integer ; suivant : liste ; end ; systeme = liste ; somme = liste ; type systeme == int list ;; type somme == int list ;; En outre, on supposera (pour les arguments) et on garantira (pour les résultats) les propriétés suivantes : -- tous les entiers présents dans les listes sont strictement positifs; -- toutes les listes sont triées en ordre décroissant; -- les listes de type systeme contiennent des entiers distincts; leur dernier élément est 1. En Pascal, la liste vide est nil et l'on pourra pour construire les listes utiliser la fonction suivante : function cons(contenu : integer ; suivant : liste) : liste ; var r : liste ; begin new(r) ; r".contenu := contenu ; r".suivant := suivant ; cons := r end ; Cette fonction est applicable pour construire les listes des deux types somme et systeme. Question 1. Ecrire la fonction valeur qui prend une somme en argument et renvoie sa valeur. (* Caml *) { Pascal } valeur : somme --> int function valeur(szsomme) : integer ; I. Payer le compte exact. Dans cette partie on considère le problème du paiement exact. Dans les termes du préambule, cela revient, étant donné un entier naturel p, a trouver un représentant de p. Une démarche possible pour payer exactement le prix p est la démarche dite gloutonne, que l'on peut décrire informellement ainsi : -- donner l'espèce la plus élevée possible -- c'est a dire de la plus grande dénomination d disponible et telle que d { p; -- recommencer en enlevant l'espèce donnée au prix à payer -- c'est dire poser 19 égal à p -- d. Évidemment, le processus s'arrête lorsque le prix initial est entièrement payé. Question 2. Dans cette question, on suppose que l'acheteur dispose toujours des espèces dont il a besoin. a) Montrer que la démarche gloutonne réussit toujours. b) Écrire une fonction glouton qui prend en argument un système monétaire sys et un prix à payer p et renvoie la liste des espèces à utiliser pour payer. La sommme renvoyée sera calculée en suivant la démarche gloutonne. (* Caml *) { Pascal} function glouton glouton : systeme --> int --> somme . (syszsysteme ; p:1nteger)zsomme ; Question 3. On tient cette fois compte des ressources de l'acheteur. Dans les termes du préambule cela revient à trouver une somme ayant pour valeur le prix a payer et extraite d'une somme donnée, dite portefeuille. a) Montrer, a l'aide d'un exemple utilisant le système européen, que la stratégie gloutonne peut échouer pour un prix donné, même si il est possible de payer compte tenu des ressources disponibles. b) Écrire une fonction payeglouton qui prend en argument une somme pf, représentant le contenu du portefeuille, ainsi qu'un prix p; et qui renvoie une somme extraite de pf et dont la valeur est p. La somme renvoyée sera calculée en suivant la démarche gloutonne, si cette démarche échoue, la fonction paye_gloutonckfitrenvoyerlalüme\dde. (* Caml *) { Pascal } function paye_glouton paye_glouton : somme --> int --> somme , (pfzsomme ; p:1nteger)zsomme ; Question 4. Écrire une fonction compte_paiements qui prend en arguments un portefeuille pf et un prix p; et qui renvoie le nombre de façons de payer p a l'aide des espèces de pf. Autrement dit cette fonction renvoie le cardinal de l'ensemble des représentants de p extraits de pf. (* Caml *) { Pascal } function compte_paiements compte_paiements : somme --> int --> int . . (pfzsomme ; p:1nteger)z1nteger ; REMARQUE. Deux espèces de même dénomination sont distinguées. Ainsi, si le portefeuille est (2, 2, 2) et le prix 2, alors il y a trois façons de payer. II. Payer le compte exact et optimal. Une somme est optimale lorsque sa taille est minimale parmi un ensemble de sommes de valeur donnée. Par exemple, la somme S = (20,20,1) montre que le portefeuille de notre citoyen européen (P = (10,10, 10,5, 5, 1)) n'est pas optimal parmi les sommes de valeur 41. En effet, la taille de S est 3 et elle est strictement inférieure à la taille de P. Dans cette partie un portefeuille P est fixé. Pour tout entier naturel 1), on pose M (19) égal à un représentant de p optimal parmi les représentants de 19 extraits de P, si une telle somme existe; ou la somme vide, si une telle somme n'existe pas. Le but de cette partie est la détermination de M (p) Question 5. Le but de cette question préalable est de préciser quelques opérations sur les sommes. a) Soit une somme S comprenant k: espèces de dénomination d, on définit l'ajout de d à S, noté S + (d), comme la somme qui comprend k: + 1 espèces de dénomination d et qui est inchangée autrement. Écrire la fonction ajoute qui prend en arguments une somme s et une dénomination d et qui renvoie la liste représentant l'ajout de d à s. (* Caml *) { Pascal} function ajoute ajoute : somme --> int --> somme _ (szsomme ; d:1nteger)zsomme ; b) On définit la différence de deux sommes S et S ' , notée S -- S ' , comme suit. Pour toute dénomination d, soit k: le nombre d'espèces de dénomination d comprises dans S et k' le nombre d'espèces de dénominations d comprises dans S ' : , -- si [<: > k' , alors S -- S ' comprend k -- k:' espèces de dénomination d; -- sinon, S -- S ' ne comprend aucune espèce de dénomination d. Écrire la fonction diff qui prend deux sommes en arguments et renvoie leur différence. (* Caml *) { Pascal} diff : somme --> somme --> somme function diff(s,tzsomme)zsomme ; Question 6. Soit l un entier naturel. On note T(z') l'ensemble des entiers naturels p, tels que la somme M (p) est de taille fl. On définit également une suite de fonctions M0, M1,. . .où la fonction M,-- est la restriction à U T(j) de la fonction M. 0 int --> int list --> int list On notera : -- les listes représentant T (2) et T (2 + 1) ne sont pas nécessairement triées; -- la condition << tab est de taille suffisante >> est précisée : le tableau tab est supposé tel qu'il existe bien des cases d'indice q, pour q inférieur ou égal à p. b) En déduire une fonction optimal qui prend en argument un portefeuille pf et un prix p et qui renvoie une somme optimale de valeur p et dont les espèces sont extraites de pf. Si il n'est pas possible de faire l'appoint, la fonction optimal renverra la liste vide. (* Caml *) { Pascal } optimal : somme --> int --> somme function optimal(pfzsomme ; p:integer)zsomme ; III. Étude des systèmes monétaires. Un système monétaire est dit canonique, lorsque la stratégie gloutonne sans limitation de ressources (cf. question 2) appliquée à tout prix p produit une somme optimale parmi les représentants de p. Question 8. Montrer que l'ancien système britannique (240, 60, 30, 24, 12, 6, 3, 1) n'est pas canonique. Le but de cette partie est de produire un programme qui décide si un système monétaire est canonique. Dans cette étude on fixe un système monétaire D de n dénominations, représenté cette fois par le vecteur de n entiers naturels D = (d1,d2, . . . ,dn). Une somme S sera également représentée par un vecteur de n entiers naturels, S = (81,82, . . . ,sn), mais s,-- est cette fois le nombre d'espèces de dénomination d,- présentes dans la somme S. Ainsi le système européen est le vecteur (500, 200, 100, 50, 20, 10, 5, 2, 1) et le portefeuille du citoyen est le vecteur (0,0,0,0,0,3,2,0,1). Les définitions (et les notations) de la valeur et de la taille sont inchangées : v = Es.-- - d.. ISI = Es. i=1 i=1 Par ailleurs les sommes sont ordonnées (totalement) selon l'ordre lexicographique, noté  IV] ou (|Ul = |V| et U int --> tsomme (sysztsysteme ; p:integer) : tsomme; Question 10. a) Montrer que p < q entraîne G (p) > ci--dessus est la différence des sommes, que l'on peut simple-- ment voir comme la soustraction appliquée aux vecteurs et définie composante par composante.) c) De même, si p est tel que M (p) comprend au moins une espèce de dénomination dk, montrer que l'on a alors M(p -- dk) : M(p) -- Ik. Question 11. Dans cette question on suppose le système monétaire D non--canonique et on considère le contre--exemple minimal 11), c'est à dire l'entier w tel que : -- M(w) # G(w) (et donc M(w)  w, M(w') : G(w'). On note M (w) : (m1, m2, . . . ,mn). Soient encore 73 l'indice minimal tel que m,-- > 0 et j l'indice maximal tel que mj > 0. a) On note G(w) : (g1,gg, . . . ,gn). Montrer qu'il n'existe pas d'indice k, tel que mk > 0 et Q,, > 0. b) Montrer que l'on a i > 1. c) Montrer que l'on a d,-1 < w < d,-1 + dj. monétaire, Question 12. Toujours en supposant le système D non-canonique et en conservant les définitions et notations de la question précédente, on admet l'encadrement suivant (qui cette fois s'applique aux sommes) : M(w) _ 1,-- @ G(di_1 - 1)  bool_ function canonique(sysztsysteme) : boolean Le coût de canonique doit être en O(n3 ) c) Montrer que le système européen est canonique.

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


 X Informatique MP 2002 -- Corrigé Ce corrigé est proposé par Mathieu Giraud (ENS Lyon) ; il a été relu par Xavier Goaoc (ENS Cachan) et Sébastien Desreux (ENS Ulm). Ce sujet comporte trois parties consacrées à l'étude des porte-monnaie et des systèmes monétaires. Chaque partie suit une progression logique même si quelques questions sont autonomes. · La première partie ouvre le sujet par des questions traitant du paiement exact et de ses variantes. Elle est majoritairement composée de questions de programmation manipulant des listes. · La deuxième partie s'intéresse à la recherche d'un paiement optimal. Elle commence par quelques questions sur des listes et l'étude d'un exemple concret. · La troisième partie concerne la canonicité des systèmes monétaires par l'algorithme polynomial de Pearson. Des questions plus théoriques interviennent (algorithmes, complexités). Elles exigent une bonne compréhension des définitions, notamment au sujet de l'ordre lexicographique, ainsi que l'assimilation des notions des deux parties précédentes. La programmation met ici en jeu des tableaux. La programmation est très présente dans ce sujet. Au début de chaque partie figurent des applications directes du cours, comme des parcours de listes ou de tableaux. Les programmes demandés dans les fins de partie sont plus conséquents et demandent plus d'initiative. Les fonctions traitant des listes sont le plus souvent récursives. Le langage Caml est particulièrement adapté à ce type de fonctions et rend des solutions particulièrement élégantes, ce qui n'est pas toujours le cas avec Pascal. L'épreuve d'informatique du concours Centrale-Supélec 2002 était similaire à celle-ci. Indications 1 La récursivité fournit des solutions simples et efficaces lorsqu'on utilise des listes. Partie I 2.a 2.b 3.a 3.b 4 Quelle est la valeur de dn ? Parcourir la liste. Chercher par exemple dans le portefeuille h50, 20, 20, 20i. Parcourir le portefeuille pf tout en construisant la liste demandée. Écrire une fonction récursive qui explore l'arbre binaire dont les feuilles sont toutes les sommes possibles. Partie II 6 Commencer par déterminer T(0), en déduire T(1) puis T(2). Observer avec attention le cas de la valeur 10. 7.a La technique de la question 6 peut se formaliser en T(i + 1) = { c = a + b | a T(i) et b P r Mi (a) } r T(i) Effectuer de manière imbriquée les parcours de T(i) et de P r Mi (a). Utiliser les fonctions définies aux questions 5.a et 5.b. 7.b Faire boucler etape en arrêtant dès que le représentant optimal est déterminé ou impossible à réaliser. Partie III 8 La dénomination 30 n'est pas le double de la précédente. 9 Utiliser la division entière. 10.a Observer le comportement de l'algorithme glouton lorsqu'il arrive à la première dénomination où G(p) et G(q) diffèrent. 10.b Remarquer que G(p - dk ) + Ik est un représentant de p et que G(p) - Ik est un représentant de p - dk . 10.c Utiliser le même raisonnement qu'à la question 10.b. 11.a Il y a une erreur d'énoncé dans la définition du contre-exemple minimal : la seconde condition concerne les w tels que w < w (et non w > w). Raisonner par l'absurde et utiliser les résultats des questions 10.b et 10.c. 11.b Raisonner par l'absurde en considérant la première étape de l'algorithme glouton. 11.c Prouver séparément chaque inégalité. 12.a Réécrire l'inégalité admise en faisant apparaître toutes les composantes. 12.b Essayer la technique de la question 12.a sur toutes les paires (i, j) envisageables pour traquer un contre-exemple minimal. On pourra supposer l'existence de fonctions donnant la valeur et le poids d'une somme, et commencer par une fonction auxiliaire appliquant le résultat de la question 12.a. Utiliser aussi la fonction définie à la question 9. 12.c Mettre en oeuvre l'algorithme de la question 12.b. Dans tout ce corrigé, les listes en Caml sont filtrées par le motif t::q (tête et queue). 1 Version Caml let rec valeur (s : somme) = match s with | [] -> 0 | t::q -> t + valeur (q : somme) ;; Version Pascal function valeur(s:somme) : integer ; begin if (s = nil) then valeur := 0 else valeur := s.contenu + valeur(s.suivant) ; end ; I. Payer le compte exact 2.a Par hypothèse, la dernière dénomination dn vaut 1. À sa dernière étape, l'algorithme glouton peut toujours utiliser p fois cette dernière espèce pour payer le prix p. La stratégie gloutonne réussit toujours. 2.b On suppose ici que l'acheteur dispose toujours des espèces dont il a besoin et on parcourt la liste sys pour déterminer le paiement glouton. Puisque dn = 1, cette stratégie réussit toujours d'après la question précédente : on ne teste donc pas le cas où la liste sys est vide. Version Caml let rec glouton sys p = match (sys, p) with | _, 0 -> [] | t::q, _ -> if (t <= p) then t::(glouton sys (p-t)) else glouton q p ;; Version Pascal function glouton(sys:syteme; p:integer) : somme ; begin if (p = 0) then glouton := nil else if (sys.contenu <= p) then glouton := cons(sys.contenu, glouton(sys, p - sys.contenu)) else glouton := glouton(sys.suivant, p) ; end ; 3.a Dans le système européen, la stratégie gloutonne appliquée au prix de 60 euros pour le portefeuille h50, 20, 20, 20i commence par utiliser le billet de 50 euros puis échoue, alors que la somme h20, 20, 20i conviendrait. Ainsi : La stratégie gloutonne tenant compte des ressources de l'acheteur peut échouer. 3.b La version Caml présentée ici utilise les exceptions pour sortir de la boucle interne. La version Pascal est plus classique. Version Caml exception Echec_Glouton ;; let rec paye_glouton_ex pf p = match (pf, p) with | _, 0 -> [] | [], _ -> raise Echec_Glouton | t::q, _ -> if (t <= p) then t::(paye_glouton_ex q (p-t)) else paye_glouton_ex q p ;; let paye_glouton pf p = try paye_glouton_ex pf p with Echec_Glouton -> [] ;; Version Pascal function paye_glouton(pf:somme; p:integer) : somme ; var resultat : somme ; begin resultat := nil ; while (pf <> nil and p > 0) do begin if (pf.contenu <= p) then begin p := p - pf.contenu ; resultat := cons(pf.contenu, resultat) ; end pf := pf.suivant ; end ; if (p > 0) then paye_glouton := nil else paye_glouton := resultat ; end ;