ca lcu le r la plus petite va le ur acceptable
pour n ; ce nou veau problè me est qualifié dans ce cas de NP-difficile, et sa
résolution est au moins aussi coûte use
que la résolution du problème de déc ision NP-complet assoc ié .
Pour illu s tre r le probl ème, pre non s
com me exempl e de traite me nt automatique de données personnelles un système
informatique permettant d 'attribuer des
prêts bancaires personnalisés. Une banque
propose des prêts à la consommation de
5 000 dollars à 10 % sur troi s ans, personnali sables selon quatre critères: montant plus é levé du prê t , réduction du
taux. a ugmentation de la durée de re mboursement et réduction de l'assurance
liée au prêt. La déc is ion d 'attribuer c hacun de ces quatre critè res est prise sur
la base d'un ensemble de règles logiques,
dit modèle métier de la banque, exprimées avec des variables Boolée nn es
bk.i j ' o ù chaque règle r k permettant d 'obtenir un bénéfice ck est en forme normale disjonctive, et où certa ines variables
booléennes bk.i j interv ienne nt dans plusieurs règles. Dans l'exemple de l'encadré
c i-contre,on ab1.1. , =b 3 .1., =b 4 2 ., =p, ,
b 1 ., .2 = b 32 . 1 = b 4 .1., = p 2 et a insi de suite .
Il est intéressant de noter que, dans de
nombre ux cas, les règ les sont issues de
techniques de fouille de données (data
mi11ing) sur la base de décis ions pri ses
précédemment par des ex perts.
Considérons la règle r 1 :
(p I Il P2) V (p 3 Il p 4) ::::} C 1 ·
Elle ex prime le fait qu ' un c lie nt peut
o bte nir un prêt plus é levé (l'avantage
c 1
) si son revenu annuel est supé ri e ur à
30 000 $ e t s i son patrimoine est supérieur à I OO 000 $ ou bien s' il possède une
ass urance vie et un nanti ssement supérieur à I OO 000 $. Afin de bé néficier de
cet avantage, un client doit ex poser un
e nsemble d'assertions logiques as 1 , as 2 ,
CHANGER LE MONDE
Un exemple de prêt bancaire
Règles de collecte :
r 1
: (p 1 IIP,) V (p 3
11p 4
)
::::} c 1
r 2
: (p 5
llp 6 11p 7
) V (p 4
11p 8 11p 9
)
::::} c 2
r 3
: (p 1 11p 6 11p 7 ) V (p 2 llp 4 llp, 0
)
::::} c 3
r 4
: (p 2 11 p 5
11p 6 llp 7 ) V (p 1 11p 4 11p 8 11p 9
)
::::} c 4
avec
p, : revenu_annuel > $30.000,
p 3
: nantissement > $100.000,
p 5
: taux_impots > 10 %,
p 7
: enfants > o,
p 9 : age< 30,
et
c, = prêt_élevé,
c 3 = prêt_long,
Assertions Client :
as, : revenu_annuel = $35.000,
as 3
: nantissement= $175.000,
as 5
: taux_impots = 11.5 %,
as 7
: enfants = 1,
as 9
: age = 25,
p 2
: patrimoine > $100.000,
p 4
: assur_vie = 'oui',
p 6 : marié = vrai,
p 8 : edu = 'université',
p 10
: frais_sinistres < $5.000
c 2 = taux-5 %,
c 4 = assurance_réduite.
as 2
: patrimoine = $150.000,
as 4
: assur_vie = 'oui',
as 6 : marié = vrai,
as 8 : edu = 'univ',
as 10
: frais_sinistres = $250.
as 3 ... supposées de la forme attribut=
valeur, tel que cet ensemb le permet de
prouve r que le corps de la règ le
(p 1
11 p 2 ) v (p 3
11 p 4 ) est vrai.
Dan s l'exemple ,as 1 =}p"as 2 =} p 2 ,
as 3 ::::} p 3 et as 4 ::::} p 4 . Il est donc évide nt que le corps de règle r I est vrai, et
donc que ce client peut bé néficier d ' un
montant de prê t plus é levé. Toutefoi s, il
est inutile que le client transmette l' intégralité de ces informations pour bénéficier de cet avantage (on dit éga lement
qu ' il expose ces informations) . Il est en
réalité nécessaire et suffisant de ne transmettre que {as"as 2 } ou {as 3 ,as 4 } afin
de lim iter la co llecte de données personnelles (pour simplifier, on considère
que chaque attribut a la même sensibilité qu ' un autre ; il est ainsi aussi « problématique » pour le client de transmettre
son âge que son adresse). On préfère
donc transmettre le plus pe tit nombre
d'attributs.
Hors-série n• 52. Mathématiques & informatique Tangente
pour n ; ce nou veau problè me est qualifié dans ce cas de NP-difficile, et sa
résolution est au moins aussi coûte use
que la résolution du problème de déc ision NP-complet assoc ié .
Pour illu s tre r le probl ème, pre non s
com me exempl e de traite me nt automatique de données personnelles un système
informatique permettant d 'attribuer des
prêts bancaires personnalisés. Une banque
propose des prêts à la consommation de
5 000 dollars à 10 % sur troi s ans, personnali sables selon quatre critères: montant plus é levé du prê t , réduction du
taux. a ugmentation de la durée de re mboursement et réduction de l'assurance
liée au prêt. La déc is ion d 'attribuer c hacun de ces quatre critè res est prise sur
la base d'un ensemble de règles logiques,
dit modèle métier de la banque, exprimées avec des variables Boolée nn es
bk.i j ' o ù chaque règle r k permettant d 'obtenir un bénéfice ck est en forme normale disjonctive, et où certa ines variables
booléennes bk.i j interv ienne nt dans plusieurs règles. Dans l'exemple de l'encadré
c i-contre,on ab1.1. , =b 3 .1., =b 4 2 ., =p, ,
b 1 ., .2 = b 32 . 1 = b 4 .1., = p 2 et a insi de suite .
Il est intéressant de noter que, dans de
nombre ux cas, les règ les sont issues de
techniques de fouille de données (data
mi11ing) sur la base de décis ions pri ses
précédemment par des ex perts.
Considérons la règle r 1 :
(p I Il P2) V (p 3 Il p 4) ::::} C 1 ·
Elle ex prime le fait qu ' un c lie nt peut
o bte nir un prêt plus é levé (l'avantage
c 1
) si son revenu annuel est supé ri e ur à
30 000 $ e t s i son patrimoine est supérieur à I OO 000 $ ou bien s' il possède une
ass urance vie et un nanti ssement supérieur à I OO 000 $. Afin de bé néficier de
cet avantage, un client doit ex poser un
e nsemble d'assertions logiques as 1 , as 2 ,
CHANGER LE MONDE
Un exemple de prêt bancaire
Règles de collecte :
r 1
: (p 1 IIP,) V (p 3
11p 4
)
::::} c 1
r 2
: (p 5
llp 6 11p 7
) V (p 4
11p 8 11p 9
)
::::} c 2
r 3
: (p 1 11p 6 11p 7 ) V (p 2 llp 4 llp, 0
)
::::} c 3
r 4
: (p 2 11 p 5
11p 6 llp 7 ) V (p 1 11p 4 11p 8 11p 9
)
::::} c 4
avec
p, : revenu_annuel > $30.000,
p 3
: nantissement > $100.000,
p 5
: taux_impots > 10 %,
p 7
: enfants > o,
p 9 : age< 30,
et
c, = prêt_élevé,
c 3 = prêt_long,
Assertions Client :
as, : revenu_annuel = $35.000,
as 3
: nantissement= $175.000,
as 5
: taux_impots = 11.5 %,
as 7
: enfants = 1,
as 9
: age = 25,
p 2
: patrimoine > $100.000,
p 4
: assur_vie = 'oui',
p 6 : marié = vrai,
p 8 : edu = 'université',
p 10
: frais_sinistres < $5.000
c 2 = taux-5 %,
c 4 = assurance_réduite.
as 2
: patrimoine = $150.000,
as 4
: assur_vie = 'oui',
as 6 : marié = vrai,
as 8 : edu = 'univ',
as 10
: frais_sinistres = $250.
as 3 ... supposées de la forme attribut=
valeur, tel que cet ensemb le permet de
prouve r que le corps de la règ le
(p 1
11 p 2 ) v (p 3
11 p 4 ) est vrai.
Dan s l'exemple ,as 1 =}p"as 2 =} p 2 ,
as 3 ::::} p 3 et as 4 ::::} p 4 . Il est donc évide nt que le corps de règle r I est vrai, et
donc que ce client peut bé néficier d ' un
montant de prê t plus é levé. Toutefoi s, il
est inutile que le client transmette l' intégralité de ces informations pour bénéficier de cet avantage (on dit éga lement
qu ' il expose ces informations) . Il est en
réalité nécessaire et suffisant de ne transmettre que {as"as 2 } ou {as 3 ,as 4 } afin
de lim iter la co llecte de données personnelles (pour simplifier, on considère
que chaque attribut a la même sensibilité qu ' un autre ; il est ainsi aussi « problématique » pour le client de transmettre
son âge que son adresse). On préfère
donc transmettre le plus pe tit nombre
d'attributs.
Hors-série n• 52. Mathématiques & informatique Tangente