Introduction

Le TP est à rendre sur arche ou par mail au responsable du cours, et ce avant 16h05.

Les différents fichiers nécessaires à la résolution du TP sont ici.

Le rendu consiste en quelques fichiers Java, quelques fichiers à lire avec gnuplot et un petit fichier texte répondant à la dernière question de la deuxième partie.

Introduction

La classe Tableau.java qui vous est donné permet de représenter un tableau d'entiers. Comme vous pouvez le voir, le tableau est représenté en interne par une ArrayList d'entiers, mais ce n'est pas important.

La classe dispose des méthodes suivantes:

Attention les cases du tableau sont numérotées à partir de 0.

Première partie - Algorithmes

  1. Ecrire la fonction shuffle() qui mélange le tableau. On utilisera l'algorithme de Fisher-Yates vu en devoir.
  2. Ecrire la fonction select(int x) qui renvoie le ième plus petit élément du tableau. On utilisera la méthode quickselect vue en TD (voir la fin de ce document pour un rappel sur quickselect)
  3. Ecrire le constructeur Tableau(int n, int no) qui crée un tableau contenant n cases dont no sont initialisées à la valeur 0 et les autres à 1. On appellera la fonction shuffle sur le résultat pour que la position des 0 soit aléatoire.
  4. Ecrire la fonction search() qui renvoie une position i où se trouve un 0. L'algorithme search fonctionnera de la façon suivante: Il choisit des cases au hasard jusqu'à trouver 0 (en particulier l'algorithme boucle s'il n'y a pas de 0 dans le tableau)
  5. Ecrire la fonction sample(int n) qui renvoie un tableau constitué de n cases distinctes du tableau T choisies aléatoirement. Par exemple, si T est le tableau [1,3,17,21,6,18,5], sample(3) peut renvoyer le tableau [6,17,1], ou encore [21,5,3].

Deuxième partie - Instrumentation

Afin d'étudier la complexité des algorithmes précédents, on va modifier le code pour savoir combien de cases ont été accédées.

  1. Modifier le code de la fonction get pour que chaque appel à cette fonction incrémente un compteur, qui nous permet ainsi de savoir combien de fois la fonction a été appelée. Attention: La variable compteur doit être du type static int, pour être partagée entre toutes les instances de la classe.
  2. Pour toutes les tailles de tableau entre n=10 et n=100, créer un tableau contenant les entiers de 1 à n, mélanger-le puis exécuter select(n/2) et regarder combien d'accès au tableau ont été nécessaires pour quickselect. On affichera les résultats avec gnuplot (voir l'exemple).
  3. Pour toutes les tailles de tableau entre n=10 et n=100, créer un tableau contenant n cases avec exactement n/3 symboles 0, appeler la méthode search et regarder combien d'accès au tableau ont été nécessaires pour search. On affichera les résultats avec gnuplot. Que constate-t-on ? Expliquer-le.

Troisième partie - Méthodes en ligne

Le but de cette partie est de s'intéresser à des algorithmes en ligne, c'est à dire des algorithmes qui n'ont le droit de lire leur entrée qu'une seule fois, et qui n'ont pas assez de place pour tout retenir.

Lire bien l'énoncé jusqu'au bout

  1. Ecrire une fonction int rand(Stack <Integer> s) qui prend une pile contenant des entiers et qui renvoie un des entiers de la pile au hasard. Vous n'avez le droit à aucune structure de données (pas de tableaux, pas d'ArrayList...), vous avez uniquement le droit d'utiliser des variables de type int (et une variable de type Random pour pouvoir produire des nombres aléatoires, évidemment).

    Attention: Sur une pile, les seules méthodes que vous avez le droit d'utiliser sont s.pop() qui dépile et vous renvoie le premier élément de la pile, et s.empty() qui teste si la pile est vide (vous pouvez aussi empiler, mais ca ne vous sera pas très utile ici). En particulier, la seule façon de connaître la taille de la pile est de tout dépiler, mais comme il n'y a pas moyen de garder en mémoire les éléments que vous avez lu (puisque qu'aucune structure de données n'est autorisée), vous allez perdre le contenu de la pile en le faisant.

Quatrième partie - FR Select

  1. Ecrire l'algorithme de selection de Floyd-Rivest ci-dessous, et comparer ses performances avec l'algorithme QuickSelect (on pourra utiliser gnuplot pour comparer).

Annexe - QuickSelect

On rappelle le principe de QuickSelect. QuickSelect part d'un tableau T et d'un entier i et cherche le ième plus petit élément du tableau T.

Annexe: FRSelect

FRSelect part d'un tableau T et d'un entier i et cherche le ième plus petit élément du tableau T.

  1. Si le tableau est de taille 1, renvoyer T[0].
  2. Choisir s éléments du tableau au hasard (avec la fonction sample). Appelons S le résultat
  3. Appeler FRSelect sur S avec paramètre i*s/n - g et noter u le résultat
  4. Appeler FRSelect sur S avec paramètre i*s/n + g et noter v le résultat
  5. Diviser T en trois parties T1,T2,T3: les éléments plus petits que u et v , les éléments entre u et v et les éléments plus grands que v
  6. Appeler récursivement FRSelect sur T1, T2 ou T3.

    Les paramètres s et g sont définis par s = n^{2/3} et g = sqrt(s).

    Si i*s/n-g est plus petit que 1, il faut bien entendu appeler FRSelect avec paramètre 1 et non pas is/n-g. De même si i*s/n+g est plus grand que n, il faut appeler FRSelect avec paramètre n.

    Pour avoir une bonne complexité et éviter des comparaisons inutiles, quand on divise T entre T1,T2,T3, il faut faire un cas selon i. Si i < n/2 on compare d'abord avec v puis avec u. Si i > n/2 on fait le contraire.