cas particulier de la dimension 2

Publié le par jö

Lorsque le critère de découpe est binaire, on constitue exactement deux groupes tels que le premier est composé des p éléments possédant une propriété et l'autre des a éléments ne la possédant pas. On note toujours p+a = j et on va montrer une méthode permettant de calculer entropy({p,a}, u) = entropy(u,{p,a}) où u={u_1, u_2, ..., u_n} est un uplet d'entiers non nuls tel que  n<=j  et  sum(k=1, k=n,  u_k) = j.

On commence par construire un tableau t de p+1 lignes (a+1 colonnes respectivement) numérotées de 0 à p (0 à a), et on met en évidence les n diagonales correspondant à u dans une numérotation arbitraire dont la seule contraintes est que la suite des distances de deux diagonales consécutives doit reprendre un à un tous les u_k de u : on aura besoin de n+1 diagonales et seules les cases mises en évidence seront calculées dans le tableau.

La case t_{p,a} est symboliquement initialisée à 1 et représente une diagonale. Voici une initialisation possible avec p=7, a=11 et u={7,6,3,1,1}:

7                        1
6                        
5                      
4                        
3                        
2                        
1                        
0                        
i_p/i_a 0 1 2 3 4 5 6 7 8 9 10 11
.
L'idée est alors d'imaginer un vecteur ((0,0),(11,7)) qu'on doit annuler pour aboutir à ((0,0),(0,0)) et compter de combien de manières cela est possible en ne jouant que sur le point initialement à (11,7) : chaque élément (i_a,i_p) d'une diagonale est calculé en sommant tous les termes possédant un indice ligne >= i_p ET un indice colonne >= i_a de la diagonale précédente. Ainsi la première "vraie" diagonale est toujours composée de 1 ( la première diagonale conventionnelle est un unique élément et est posée égale à 1 ) :



7          1              1
6            1            
5  3            1        
4    4            1        
3      5            1      
2  18      6            1    
1  40  22      7            1  
0  87  47  25      7            1
i_p/i_a 0 1 2 3 4 5 6 7 8 9 10 11

Le résultat est le dernier élément calculé :
entropy({11,7},{7,6,3,1,1}) = entropy({7,6,3,1,1},{11,7}) = t_{0,0} = 87.

On peut vérifier que le résultat ne dépend pas du choix de l'ordre des diagonales dont se sert cette méthode qui pourrait d'ailleurs être généralisée à plus de 2 dimensions mais en perdant bien sûr son caractère représentable.

Publié dans mathblog

Commenter cet article