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 ;