X Informatique MP 2002

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