ACTIONS
Un problème juridique ...
l'article & de la lol lntomauaue et llllenés
« Un traitement ne peut porter que sur des données à caractère personnel qui satisfont aux conditions suivantes :
1) Les données sont collectées et traitées de manière loyale
et licite;
2) Elles sont collectées pour des finalités déterminées, explicites et légitimes et ne sont pas traitées ultérieurement
de manière incompatible avec ces finalités. Toutefois,
un traitement ultérieur de données à des fins statistiques
ou à des fins de recherche scientifique ou historique est
considéré comme compatfüle avec les finalités initiales
de la collecte des données, s'il est réalisé dans le respect
des principes et des procédures prévus au présent chapitre, au chapitre IV et à la section 1 du chapitre V _llinsi
qu'aux chapitres IX et X et s'il n 'est pas utilisé pour
prendre des décisions à l'égard des personnes concernées ;
3) Elles sont adéquates, pertinentes et non excessives au regard
des finalités pour lesquelles elles sont collectées et de
leurs traitements ultérieurs ;
4) Elles sont exactes, complètes et, si nécessaire, mises à jour ;
les mesures appropriées doivent être prises pour que les
données inexactes ou incomplètes au regard des finalités pour lesquelles elles sont collectées ou traitées soient
effacées ou rectifiées ;
5) Elles sont conservées sous une forme permettant l'identification des personnes concernées pendant une durée
qui n 'excède pas la durée nécessaire aux finalités pour
lesquelles elles sont collectées et traitées.
S ' il n'y a qu ' une seule règle de collecte,
le problème est simple: il suffit de transmettre la conjonction impliquant le moins
d 'attributs. Le problème devient plu s
difficile lorsque le client souhaite bénéficier de plusieurs avantages ck si mul -
tané ment.
Afin de définir formellement le problè me mathé matique de la minimi sation des données co!Jectées (dit également
problème den-exposition) , posons
ER= llk (rk) = 11k (v;(llik.;)), appe lée formule booléenne del' ensemble de règles .
Le problème s'énonce formellement de
la manière suivante :
On se donn e un e nse mbl e de règ les
R = {ri' r 2 , r 3 ... } , un ense mble d'assertion s data 11 = {as I' as 2 , as 3 .. . asq} te l
que tou s les rk sont vra is , un ensemble
de variables booléennes
B = {/Jpp 2 . . . Pq} te l que
p 111 =vrai<=> as,,, est transmi s, et enfin la
formule boo lée nne de ! ' e nse mbl e de
règles R, notée~ = 11k(v;(11i k;)) où , quels
que soient les indices k , i et), bk.i j E B.
On dit que data,, est n- exposable par
rapport à R si, et seulement si, il ex iste
une affectation de valeurs boo léennes
aux vari ables de B te lle que ~ est vraie ,
et le nombre de p 1 , p 2 .. • p q prenant la
valeur vraie est inférie ur n.
Pour les données présentées dans l' encadré précédent , on peut fac ilement vérifi er que la soluti on
T a= {P 1 = V,P2 = Y, p 3 = F,p4 = F,
Ps = V, p 6 = V,p7 = Y, ps = F,p9 = F,
p 10 = F} valide bie n ER, et donc que R
est 5-exposable. Pour montrer que 5 est
bien la plu s petite valeur acceptable,
une manière est de tester toutes les affectations ayant quatre valeurs vraies (il en
ex iste Cio so it 2 10) , et montrer qu ' aucune ne convient.
li est poss ible de montrer que ce probl ème, dans sa généralité , est NP-compl et , en se fondant sur une réducti on à
un problème assez connu en log ique : le
problème de satis.fiabilité minimale avec
pondération (ou Min Weighted Sat). On
défi nit le problème d 'optimisation assoc ié, qui cherche à trou ve r le plu s petit
nombre d 'é léments de B (on notera m
cette vale ur) qu ' i I fa ut fi xer à vrai pour
que ER so it vraie. Le problème d ' opti -
mi sation est NP-difficil e, ce qui signi -
fie qu ' il peut être très coûteux de trouver
le rés ultat exact à cette questio n pour
de grandes valeurs de m. Pour ca lculer
la solution exacte du problè me , on pe ut
utili ser une méthode de force brute,
ri 16 Ta.ngente Hors-série n°52. Mathématiques & informatique
Un problème juridique ...
l'article & de la lol lntomauaue et llllenés
« Un traitement ne peut porter que sur des données à caractère personnel qui satisfont aux conditions suivantes :
1) Les données sont collectées et traitées de manière loyale
et licite;
2) Elles sont collectées pour des finalités déterminées, explicites et légitimes et ne sont pas traitées ultérieurement
de manière incompatible avec ces finalités. Toutefois,
un traitement ultérieur de données à des fins statistiques
ou à des fins de recherche scientifique ou historique est
considéré comme compatfüle avec les finalités initiales
de la collecte des données, s'il est réalisé dans le respect
des principes et des procédures prévus au présent chapitre, au chapitre IV et à la section 1 du chapitre V _llinsi
qu'aux chapitres IX et X et s'il n 'est pas utilisé pour
prendre des décisions à l'égard des personnes concernées ;
3) Elles sont adéquates, pertinentes et non excessives au regard
des finalités pour lesquelles elles sont collectées et de
leurs traitements ultérieurs ;
4) Elles sont exactes, complètes et, si nécessaire, mises à jour ;
les mesures appropriées doivent être prises pour que les
données inexactes ou incomplètes au regard des finalités pour lesquelles elles sont collectées ou traitées soient
effacées ou rectifiées ;
5) Elles sont conservées sous une forme permettant l'identification des personnes concernées pendant une durée
qui n 'excède pas la durée nécessaire aux finalités pour
lesquelles elles sont collectées et traitées.
S ' il n'y a qu ' une seule règle de collecte,
le problème est simple: il suffit de transmettre la conjonction impliquant le moins
d 'attributs. Le problème devient plu s
difficile lorsque le client souhaite bénéficier de plusieurs avantages ck si mul -
tané ment.
Afin de définir formellement le problè me mathé matique de la minimi sation des données co!Jectées (dit également
problème den-exposition) , posons
ER= llk (rk) = 11k (v;(llik.;)), appe lée formule booléenne del' ensemble de règles .
Le problème s'énonce formellement de
la manière suivante :
On se donn e un e nse mbl e de règ les
R = {ri' r 2 , r 3 ... } , un ense mble d'assertion s data 11 = {as I' as 2 , as 3 .. . asq} te l
que tou s les rk sont vra is , un ensemble
de variables booléennes
B = {/Jpp 2 . . . Pq} te l que
p 111 =vrai<=> as,,, est transmi s, et enfin la
formule boo lée nne de ! ' e nse mbl e de
règles R, notée~ = 11k(v;(11i k;)) où , quels
que soient les indices k , i et), bk.i j E B.
On dit que data,, est n- exposable par
rapport à R si, et seulement si, il ex iste
une affectation de valeurs boo léennes
aux vari ables de B te lle que ~ est vraie ,
et le nombre de p 1 , p 2 .. • p q prenant la
valeur vraie est inférie ur n.
Pour les données présentées dans l' encadré précédent , on peut fac ilement vérifi er que la soluti on
T a= {P 1 = V,P2 = Y, p 3 = F,p4 = F,
Ps = V, p 6 = V,p7 = Y, ps = F,p9 = F,
p 10 = F} valide bie n ER, et donc que R
est 5-exposable. Pour montrer que 5 est
bien la plu s petite valeur acceptable,
une manière est de tester toutes les affectations ayant quatre valeurs vraies (il en
ex iste Cio so it 2 10) , et montrer qu ' aucune ne convient.
li est poss ible de montrer que ce probl ème, dans sa généralité , est NP-compl et , en se fondant sur une réducti on à
un problème assez connu en log ique : le
problème de satis.fiabilité minimale avec
pondération (ou Min Weighted Sat). On
défi nit le problème d 'optimisation assoc ié, qui cherche à trou ve r le plu s petit
nombre d 'é léments de B (on notera m
cette vale ur) qu ' i I fa ut fi xer à vrai pour
que ER so it vraie. Le problème d ' opti -
mi sation est NP-difficil e, ce qui signi -
fie qu ' il peut être très coûteux de trouver
le rés ultat exact à cette questio n pour
de grandes valeurs de m. Pour ca lculer
la solution exacte du problè me , on pe ut
utili ser une méthode de force brute,
ri 16 Ta.ngente Hors-série n°52. Mathématiques & informatique