Centrale Informatique MP 2002

 

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