INF411 - TD3
Classes disjointes et
connectivité d'un réseau d'utilisateurs

Votre opinion sur le cours de lundi : Votre opinion sur le TD de la semaine dernière :

 Login :  Mot de passe :

Avertissement

Afin de minimiser les risques d'erreurs de manipulation lors des dépôts de fichiers, toutes les classes que vous avez à modifier sont réunies dans un même fichier TD3.java que vous devez déposer après chaque question.

(On rappelle néanmoins qu'en dehors de circonstances exceptionnelles, on écrit plutôt des classes différentes dans des fichiers différents, tant pour la lisibilité du code que pour l'efficacité de la compilation.)

Avant de commencer

Contexte

Plan

  1. Définition et implémentation du générateur de nombres pseudo-aléatoires (classe PRNG pour Pseudo Random Number Generator) qui renvoie des nombres compris entre 0 et 106 − 1.
  2. Simulation des appels téléphoniques, classes Network et NetworkSimulation.
  3. Utilisation de classes disjointes (classe UnionFind vue en cours) pour représenter les composantes connexes du réseau. Modification de UnionFind pour calculer le nombre d'éléments de chaque classe.
  4. On répond à la question suivante :

    Après combien d'appels le Président est-il relié à 99% de la population ?

1. Le générateur pseudo-aléatoire

Définition de la suite pseudo-aléatoire

Les termes du générateur pseudo-aléatoire de Fibonacci (Lagged Fibonacci generator), que l'on note S0, S1, S2, … sont calculés (modulo m = 1000000) au moyen de la relation de récurrence ci-dessous :

NB : la valeur m est stockée dans la variable modulus de la classe PRNG.

La suite ainsi générée « semble » aléatoire alors qu'elle est déterministe: c'est pourquoi on dit qu'elle est « pseudo-aléatoire ». La classe PRNG contient une méthode int getNext() qui au n+1ème appel renvoie Sn, nous allons voir comment l'implémenter efficacement.

État interne du générateur

Pour tout entier n, le terme Sn est nécessaire au calcul des 55 termes suivants et seulement ceux-là. Il faut donc garder en mémoire les 55 dernières valeurs calculées. La classe PRNG contient une constante

 private final int stateSize = 55;

et un état interne constitué des champs

 private int index = 0;
 private boolean warmUpDone = false;
 private int[] state = new int[stateSize];

On rappelle que, initialement, chacune des cases du tableau state contient la valeur 0 :

state0.png
La variable warmUpDone vaut true lorsqu'au moins 55 appels à la méthode getNext() ont été effectués. Elle permet de passer du premier mode de calcul (à l'aide d'un polynôme) au second (qui utilise les 55 dernières valeurs calculées).

Mise à jour de l'état interne

Le tableau state est utilisé de façon circulaire, la case state[index] contenant la valeur la plus ancienne. Chaque fois que la méthode getNext est appelée, seule la case state[index] est modifiée. Le champ index doit être maintenu entre 0 et 54 (inclus).

Exemples : les 56ème et 109ème appels à la méthode « getNext »

Avant le 56ème appel à getNext() l'état interne est :

state2.png

Après le 56ème appel à getNext() l'état interne est :

state22.png

Avant le 109ème appel à getNext() l'état interne est :

state3.png

Après le 109ème appel à getNext() l'état interne est :

state32.png

Calcul des 55 premiers termes par la méthode de Horner

On observe que pour i = 19 on a 300007i3 + 900021i2 + 700018i + 200007 = 2396155943 > 2147483647 = 231-1, et donc que la portion de code Java ci-dessous

int i = 19;
int S = (300007*i*i*i + 900021*i*i + 700018*i + 200007) % m;

provoque un dépassement de capacité, puisque 231-1 est le plus grand entier que le type int permet de représenter. On résout le problème en observant que la forme de Horner

(((((300007 * i + 900021) % m) * i + 700018) % m) * i + 200007) % m;

ne provoque pas de dépassement de capacité, tout en étant mathématiquement équivalente à l'expression

 (300007*i*i*i + 900021*i*i + 700018*i + 200007) % m;

On utilisera donc la forme de Horner pour calculer les 55 premiers termes de la suite.

Question 1

Dans la classe PRNG, complétez la méthode int getNext(). Il faut pour cela :

  1. calculer le terme suivant (à l'aide de la méthode de Horner pour les 55 premiers, voir ci-dessus) ;
  2. mettre à jour la case du tableau state contenant la plus ancienne valeur (voir « Mise à jour de l'état interne ») ;
  3. incrémenter index modulo 55 (i.e. stateSize);
  4. mettre à jour warmUpDone si besoin;
  5. renvoyer le terme qui vient d'être calculé.

Attention : les numéros de téléphone sont calculés modulo modulus (106), tandis que les indices du tableau state sont calculés modulo stateSize (55).

Testez votre code en exécutant le fichier Test1.java.

Déposez le fichier TD3.java.

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

2. La simulation des appels téléphoniques

Les termes d'indice pair de la suite pseudo-aléatoire sont les identifiants des « appelants » et ceux d'indice impair sont les identifiants des « appelés ». Autrement dit, pour tout entier i, l'individu S2i appelle l'individu S2i+1. Lorsque S2i = S2i+1 on considère que S2i a appelé son répondeur téléphonique. On a par exemple

Appel Appelant Appelé
Si Sj
1 S0=200 007 S1=100 053
2 S2=600 183 S3=500 439
3 S4=600 863 S5=701 497
... ... ...
403 S804=328 092 S805=068 816
... ... ...
561 S1120=328 092 S1121=523 748

de sorte qu'après le 561ème appel, les individus 068 816 — 328 092 — 523 748 sont dans la même classe.

La classe Network contient les champs suivants:

Question 2.1

Dans la classe Network, complétez la méthode void nextCall() qui

Testez votre code en exécutant le fichier Test21.java.

Déposez le fichier TD3.java.

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

Question 2.2

On veut répondre aux questions suivantes :

Pour répondre à ces questions, complétez la méthode int simulation22(int president, int population) de la classe NetworkSimulation en y ajoutant une boucle qui ajoute des liens (utilisez la méthode nextCall() de la classe Network) jusqu'à obtenir un appel impliquant le Président. La méthode renvoie le nombre total d'appels effectués (hors appel au répondeur).

Testez votre code en exécutant le fichier Test22.java.

Déposez le fichier TD3.java.

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

3. Taille des classes disjointes des utilisateurs du réseau

Question 3.1 : Champ size dans la classe UnionFind

Dans la classe UnionFind, ajoutez un champ private int[] size qui stocke le nombre d'éléments de chaque classe disjointe. C'est un tableau d'entiers semblable au tableau rank du code fourni, de même taille. Pour des raisons d'efficacité, seule la case qui correspond au représentant d'une classe contient son nombre d'éléments.

À l'initialisation, chaque élément est l'unique membre de sa classe. Complétez le constructeur de la classe UnionFind de manière à initialiser le tableau size.

Modifiez la méthode union (de la classe UnionFind) de sorte qu'à chaque appel, la case (du tableau size) correspondant au représentant de la réunion des classes passées en argument soit mise à jour.

Complétez la méthode int getSize(int i) de la classe UnionFind qui renvoie le nombre d'éléments de la classe de i.

Testez votre code en exécutant le fichier Test31.java.

Déposez le fichier TD3.java.

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

Question 3.2 : Taille des classes dans le réseau

Complétez la méthode int getSize(int i) dans la classe Network, qui renvoie le nombre d'utilisateurs reliés à un utilisateur donné i.

Testez votre code en exécutant le fichier Test32.java.

Déposez le fichier TD3.java.

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

Question 3.3

Au premier appel impliquant le Président (Question 2.2), combien y a-t-il d'utilisateurs en lien avec le président ?

Pour répondre à cette question, complétez la méthode int simulation33(int president, int population) de la classe NetworkSimulation pour qu'elle renvoie ce nombre.

Testez votre code en exécutant le fichier Test33.java.

Déposez le fichier TD3.java.

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

4. Connectivité du réseau après n appels

On revient à la question initiale :

Après combien d'appels n (on ignore les appels au répondeur), 99% des utilisateurs (le Président inclus) sont reliés au Président via différents appels téléphoniques entre utilisateurs ?

Pour répondre à cette question, complétez la méthode int simulation4(int president, int population) de la classe NetworkSimulation pour qu'elle renvoie ce nombre.

Testez votre code en exécutant le fichier Test4.java.

Déposez le fichier TD3.java.

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

5. Bonus possible pour ceux qui ont fini : un plus gros réseau

On voudrait répéter l'expérience précédente avec un réseau de cent millions d'utilisateurs (numéros à 8 chiffres, module = 108). On observe alors que les calculs effectués par le programme qui implémente le générateur de nombres (pseudo-)aléatoires (en particulier au moment de l'initialisation) peuvent dépasser la capacité de représentation du type int : par exemple 54 * (108-1) est strictement plus grand que 231-1.

Le plus grand entier représentable par le type long (entiers sur 64 bits) est 263-1, ce qui suffit largement aux besoins du problème.

Dans le fichier TD3.java, et en vous inspirant de la classe PRNG, complétez la classe PRNGLarge en utilisant, uniquement aux endroits opportuns, le type primitif long au lieu du type int. NB : Le calcul intermédiaire de l'état interne state pour les indices inférieurs à 55 nécessite certainement l'utilisation du type long. En revanche, on ne peut pas accéder aux cases d'un tableau en utilisant des valeurs de type long.

Testez PRNGLarge en exécutant le fichier Test5.java.

Le numéro de la Première Ministre et celui de son secrétaire d'État sont respectivement 64 40 34 11 et 25 08 61 23.

Dans le fichier TD3.java et en vous inspirant des classes UnionFind, Network, et NetworkSimulation, écrivez les classes UnionFindLarge, NetworkLarge, et NetworkSimulationLarge afin de répondre aux questions suivantes :

  1. Après combien d'appels obtient-on le numéro de la Première Ministre ? À ce moment là, combien d'utilisateurs sont liés à la Première Ministre, autrement dit dans la même classe ?
  2. Après combien d'appels obtient-on le numéro du secrétaire d'État ? À ce moment là, combien y a-t-il de numéros en relation avec le secrétaire d'État ?
  3. Combien d'appels faut-il pour que la Première Ministre et son secrétaire d'État soient dans la même classe ? Pour répondre à cette question, pensez à rajouter une méthode dans la classe NetworkLarge qui appelle la méthode appropriée de la classe UnionFindLarge.
  4. Combien d'appels faut-il pour que 95% des utilisateurs soient dans la même classe que la Première Ministre ?

Déposez le fichier TD3.java.

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

Les réponses numériques aux questions sont ici.

De la lecture pour ceux qui ont tout fini : pour aller plus loin sur les générateurs de pseudo-aléa

Le Mersenne twister est un générateur de pseudo-aléa. Ces générateurs sont très sensibles à l'initialisation (la graine ou seed, autrement dit la valeur initiale). Un article du New York Times sur une fraude à la loterie d'état dans l'Iowa qui utilisait cette vulnérabilité.


Ce sujet est inspiré du Projet Euler, en particulier ce problème.