Arbres de Fenwick et inversions dans un tableau

INF411 · TD6

 Login :  Mot de passe :

Exprimez-vous

1 Mise en place

L’objectif de ce TD est d’implémenter une nouvelle structure de données, les arbres de Fenwick, et de voir comment ils peuvent être utilisés pour calculer rapidement le nombre d’inversions dans un tableau.

Pour commencer:

2 Arbres de Fenwick

On peut penser à deux implémentations naïves. La première incrémente la case a[i] d’un tableau int[] a à chaque appel de inc(i) (temps constant) ; cumulative(i) renvoie la somme des a[j] pour 0 ≤ j < i (temps linéaire en H − L).

La seconde stocke directement les valeurs de tous les cumulative(i), de sorte que cumulative(i) est calculé en temps constant mais c’est inc qui s’exécute en temps linéaire.

Dans cet exercice, on va construire une structure de données, appelée arbre de Fenwick, qui représente un tableau d’entiers avec des indices dans [L, H[ et qui permet d’exécuter les deux opération suivantes en temps O(log (H − L)) :

void inc(int i)
ajoute 1 à l’élément d’indice i du tableau représenté par this ; ne fait rien si i n’est pas dans [L, H[.
int cumulative(i)
renvoie la somme de tous les éléments du tableau représenté par this avec des indices dans ] − ∞, i[ ∩ [L, H[.

Dans la marge de gauche, deux implémentations naïves sont suggérées qui garantissent un temps linéaire pour ces deux opérations.

class Fenwick {
    private final Fenwick left;
    private final Fenwick right;
    private final int lo;
    private final int hi;
    private int acc;

}

Un arbre de Fenwick sur l’intervalle [L, H[ est défini comme suit. C’est un arbre binaire équilibré où chaque nœud a 0 ou 2 sous-arbres. Chaque nœud représente un intervalle. La racine correspond à l’intervalle [L,H[. Puis, pour tout nœud correspondant à l’intervalle [lo,hi[:

Chaque nœud d’un arbre de Fenwick stocke une valeur (représentée par le champ acc). Celle-ci est égale à la somme des valeurs des cases du tableau dont les indices sont dans [lo,hi[. En particulier, les feuilles contiennent juste la valeur de la case du tableau correspondante.

Le schéma ci-dessous illustre un arbre de Fenwick sur l’intervalle [0, 19[ représentant le tableau [2, 2, 3, 1, 0, 0, 1, 1, 2, 0, 1, 3, 4, 2, 0, 0, 2, 1, 3].

Schéma d’un arbre de Fenwick

 

Toutes les méthodes de cette partie seront implémentées dans la classe Fenwick du fichier TD6.java.

2.1 Constructeur

class Fenwick {
    ...
    Fenwick(int lo, int hi) {
        /* TODO */
    }
}

Compléter le constructeur Fenwick(int lo, int hi) qui construit l’arbre de Fenwick associé au tableau dont les indices sont dans [lo, hi[ et où toutes les cases ont pour valeur 0 (on supposera toujours que lo < hi).

Il contiendra des appels récursifs pour construire les sous-arbres, le cas échéant.

Le champ acc dans la classe Fenwick permet de stocker la valeur associée au nœud.

Tester le code en exécutant Test21.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.2 Méthode get

Pour se familiariser avec la structure de l’arbre, on peut, par exemple, chercher les feuilles de l’arbre comme dans un arbre binaire de recherche (voir les diapos de l’amphi 5). On peut le faire itérativement ou récursivement.

class Fenwick {
    ...
    Fenwick get(int i) {
        /* TODO */
    }
}

Compléter la méthode get(i) qui renvoie la feuille associée à l’intervalle singleton [i, i+1[ si elle existe et null sinon.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Test22.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.3 Méthode inc

On veut maintenant implémenter la méthode inc. Un appel inc(i) incrémente les accumulateurs de tous les nœuds de l’arbre associés à un intervalle contenant i. L’appel ne fait rien si i n’est pas dans [lo, hi[. On implémentera cette méthode avec des appels récursifs.

Le schéma ci-dessous illustre l’appel inc(12). Les flèches jaunes représentent les appels récursifs. Les nœuds jaunes ont reçu un appel inc(12), incrémenté leurs compteurs et transmis l’appel à leurs sous-arbres. Les nœuds beiges ont reçu un appel inc(12) mais n’ont rien fait.

Appel inc(12) dans un arbre de Fenwick


class Fenwick {
    ...
    void inc(int i) {
        /* TODO */
    }
}

Compléter la méthode inc.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Test23.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.4 Méthode cumulative

La méthode cumulative(i) renvoie la somme des éléments aux indices strictement inférieurs à i du tableau représenté par l’arbre. On remarque que si le nœud courant a des sous-arbres, alors cumulative(i) est égal à left.cumulative(i) + right.cumulative(i). Mais selon la valeur de i un calcul sans récursion est parfois possible.

Le schéma ci-dessous illustre l’appel cumulative(13). Il renvoie 21, la somme des nœuds jaunes (12+1+3+5), qui est aussi la somme des feuilles numérotées de 0 à 12. Les flèches jaunes représentent les appels récursifs. Les nœuds jaunes et beiges n’ont pas eu besoin de récursion pour renvoyer le résultat.

Appel cumulative(13) dans un arbre de Fenwick


class Fenwick {
    ...
    int cumulative(int i) {
        /* TODO */
    }
}

Compléter la méthode cumulative.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Test24.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3 Inversions dans un tableau.

On va maintenant utiliser les arbres de Fenwick pour dénombrer efficacement les inversions dans un tableau. Étant donné un tableau tab dont les indices sont compris dans [0,n[, on dit que la paire d’indices {i,j} forme une inversion si i<j et tab[i]>tab[j].

Par exemple dans le tableau [5,-2,10,3], il y a 3 inversions qui correspondent aux paires d’indices {0,1}, {0,3} et {2,3} (qui correspondent respectivement aux paires de valeurs {5,-2}, {5,3} et {10,3}).

Toutes les méthodes de cette partie seront implémentées dans la classe CountInversions du fichier TD6.java.

3.1 Méthode naïve pour compter le nombre d’inversions


class CountInversions {
    ...
   static int countInversionsNaive(int[] a) {
        /* TODO */
    }
}

On commence par compléter une méthode countInversionsNaive(int[] a) qui prend un tableau d’entiers en argument et renvoie son nombre d’inversions. La complexité de cette méthode devra être quadratique en la longueur du tableau.

Tester le code en exécutant Test31.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3.2 Inversions et arbres de Fenwick.

On va maintenant utiliser les arbres de Fenwick pour compter plus efficacement le nombre d’inversions dans un tableau a. On procède de la manière suivante.


class CountInversions {
    ...
   static int countInversionsFen(int[] a) {
        /* TODO */
    }
}

En utilisant les remarques ci-dessus, compléter la méthode countInversionsFen(int[] a) qui prend un tableau d’entiers en argument et renvoie son nombre d’inversions.

Si on note N = a.length et span = max(a)-min(a), alors la complexité de cette méthode devra être en O(span + N⋅ log (span)).

Tester le code en exécutant Test32.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3.3 Inversions et arbres de Fenwick : version optimisée

L’algorithme utilisé dans la partie précédente n’est pas efficace si la valeur de span pour a est grande par rapport à la taille de a, par exemple si a=[-10000,9999,2,350654,10]. Pour améliorer sa complexité, on va utiliser la remarque suivante : le nombre d’inversions d’un tableau ne dépend que de l’ordre relatif de ses éléments et pas de leur valeur.

Par exemple a=[-10000,9999,2,350654,10] et b=[0,3,1,4,2] ont le même nombre d’inversions, convainquez-vous en!


class CountInversions {
    ...
   static int countInversionsBest(int[] a) {
        /* TODO */
    }
}

En utilisant les remarques ci-dessus, compléter la méthode countInversionsBest(int[] a) qui prend un tableau d’entiers en argument et renvoie son nombre d’inversions.

On pourra utiliser les méthodes suivantes de la classe Arrays :

  • int[] copyOf(int[] a, int n) : qui renvoie un tableau de longueur n, rempli avec les valeurs a[0],…,a[n-1].

  • void sort(int [] a) : qui trie le tableau a. Attention, cette méthode modifie a ! (Si on note N la longueur de a, la complexité de cette méthode est en O(Nlog N). Plus d’infos sur les tris la semaine prochaine !)

  • int binarySearch(int[] a, val) : qui prend en argument un tableau trié et qui renvoie un entier i tel que a[i]=val. (Si on note N la longueur de a, la complexité de cette méthode est en O(log N).)

Si on note N la longueur de a, la complexité de countInversionsBest(int[] a) devra être en O(Nlog N).

Tester le code en exécutant Test33.java puis déposer TD6.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer