TD3 : Classes disjointes, 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 :

Avant de commencer

Contexte

On va simuler la connectivité des utilisateurs dans un réseau de télécommunications, ici un réseau téléphonique (ce pourrait être un réseau IP, un réseau social...) Chaque abonné du réseau possède un identifiant qui est son numéro de téléphone, composé de 6 chiffres décimaux. Il y a 106 numéros possibles, de 000 000 à 999 999. Lorsqu'un utilisateur dont le numéro est N0 appelle un correspondant dont le numéro est N1, distinct de N0, alors N0 et N1 sont en relation et il y a une connexion établie entre ces deux utilisateurs.

Pour simuler les numéros des appels téléphoniques, on utilise un générateur pseudo-aléatoire de nombres entre 0 et 106 − 1, appelé aussi PRNG pour Pseudo Random Number Generator. Il y a un appel téléphonique de Ni = PRNG.getNext() vers Ni+1 = PRNG.getNext(), pour deux nombres consécutifs générés par le PRNG. Si Ni = Ni+1, il s'agit simplement de quelqu'un qui écoute son répondeur. Si les premiers nombres générés par le PRNG sont 200 007, 100 053, 600 183, 500 439, 600 863, 701 497, alors les appels ont été les suivants :

Appel Appelant Appelé
n Ni Nj
1 N0=200 007 N1=100 053
2 N2=600 183 N3=500 439
3 N4=600 863 N5=701 497
... ... ...

À partir du début de la base de données des appels, on sait qu'il y a une connexion entre deux utilisateurs identifiés par leur numéros de téléphone Ni et Nj si Ni a appelé Nj ou inversement si Nj a appelé Ni. On étend cette relation par transitivité : Ni est relié à Nk si Ni est connecté à Nj et Nj est connecté à Nk. Toute longueur de chaîne de connexion est possible pour relier deux utilisateurs du réseau. Par exemple, si Nk désigne le (k+1)-ième appel au PRNG (N0 est le premier appel au PRNG que l'on va programmer dans ce TD), on a N804 = 328 092, N805 = 068 816, puis plus loin on obtient de nouveau ce numéro : N1120 = 328 092 = N804 et N1121 = 523 748 ce qui donne les relations 068 816 — 328 092 — 523 748. On peut ainsi définir des classes disjointes d'utilisateurs en relation.

La question que l'on se posera en section 4 est la suivante :

Le numéro du Président est 524 287. Après combien d'appels 99% des utilisateurs (le Président inclus) sont reliés au Président via des appels téléphoniques entre utilisateurs ?

Le TD adopte le plan suivant :

  1. Définition du PRNG qui doit renvoyer des nombres pseudo-aléatoires entre 0 et 106 − 1, classe PRNG.
  2. Simulation des appels téléphoniques, classes Network et NetworkSimulation.
  3. Utilisation de classes disjointes (classe UnionFind vue en cours) pour représenter la connectivité entre utilisateurs. Modification de UnionFind pour calculer le nombre de correspondants pour chaque classe disjointe.
  4. Connectivité du réseau : réponse à la question.

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

En cours, pour générer un labyrinthe parfait aléatoirement, on a utilisé le Mélange de Knuth. Ici, nous allons utiliser un générateur pseudo-aléatoire pour modéliser les numéros de téléphone des appels. Les valeurs des numéros vont de 000 000 à 999 999 (soit 106 numéros possibles).

Les nombres S0, S1, S2, … sont les termes du générateur pseudo-aléatoire de Fibonacci (Lagged Fibonacci generator) et l'on choisit l'initialisation suivante (toutes les valeurs sont considérées modulo m = 1000000) :

Afin de calculer le terme suivant de cette suite, on n'a pas besoin de conserver tous les termes précédents, seuls les 55 derniers nombres sont nécessaires. Ces 55 nombres forment l'état interne du PRNG. On définit la variable stateSize = 55.

Le tableau state stocke stateSize entiers (ici stateSize vaut 55) du type primitif int (sur 32 bits). L'instruction

       this.state = new int[this.stateSize];

réserve stateSize cases mémoire de 32 bits et initialise toutes les valeurs à 0. On a alors state[i] qui vaut 0 pour tout indice i de 0 à 54.

state0.png

Le but de cette partie est de mettre à jour le tableau state.

Indication pour le tableau state :

Question 1. Calcul de Sn avec la Méthode de Horner

Écrivez le corps de la méthode getNext() dans PRNG.java (que vous avez extrait de TD3.zip dans src) qui contient un squelette de la classe PRNG. La méthode getNext()

  1. calcule le terme suivant. Lorsque i < 55, on utilise la méthode de Horner décrite plus loin ;
  2. met à jour l'état interne (state) ;
  3. incrémente l'indice de l'état interne (index) ;
  4. renvoie le terme qui vient d'être calculé.

Si l'on calcule le terme suivant pour i < 55 directement avec la formule Si = (300007i3 + 900021i2 + 700018i + 200007) mod 1000000 en écrivant

// ceci va causer un problème de débordement à cause du type int, qui s'arrête à 2^31-1.
int i = this.index;
if(i < this.stateSize){
    this.state[i] = (300007*i*i*i + 900021*i*i + 700018*i + 200007) % this.modulus;
}

alors pour i = 19 il y a un débordement de l'arithmétique car avant de réduire modulo 1000000, la valeur est 2396155943 qui est plus grande que 231 = 2147483648. Afin d'éviter ce problème d'une part, et de gagner en efficacité d'autre part, on utilise la méthode de Horner pour évaluer le polynôme de degré 3 en i, et on réduit modulo 1000000 à chaque étape.

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

Écrivez le corps de la méthode getNext() avec cette astuce. Attention aux parenthèses.

Il y a deux modulo distincts : modulo 1000000 pour les numéros de téléphone, modulo 55 pour les indices du tableau state.

    public int getNext(){
        // TODO: remove the following statement and replace it with the formula of the PRNG
        throw new Error("Methode getNext() a remplir (Question 1)");
    }

Testez avec le fichier Test1.java qui teste les valeurs obtenues avec le PRNG. Notez que la suite est complètement déterministe : les coefficients multiplicateurs choisis au départ déterminent toute la suite de nombres.
Déposez votre fichier PRNG.java.

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

2. La simulation des appels téléphoniques

Dans cette partie le code est écrit dans ces deux fichiers :

Question 2.1

Dans la classe Network, écrivez le corps de la méthode nextCall() qui fait deux appels au PRNG pour simuler un appel téléphonique. Le premier appel au PRNG donne le numéro de téléphone de l'appelant, le deuxième est le numéro de l'appelé. Puis la méthode fait la connexion entre les deux numéros avec union. Cette méthode met à jour les champs caller (l'appelant) et called (l'appelé).

    void nextCall(){
        // TODO
    }

Testez avec le fichier Test2.java.
Déposez votre fichier Network.java.

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

Question 2.2

Au bout de combien d'appels y a-t-il un appel entrant ou sortant avec le Président, dont le numéro est 524 287 ? Est-ce un appel entrant ou sortant, autrement dit est-ce le Président qui passe l'appel, ou bien le reçoit-il ?

Pour répondre à cette question, créez une nouvelle classe NetworkSimulation dans un fichier NetworkSimulation.java, qui contiendra une méthode main dans laquelle vous utiliserez les classes et leurs méthodes des questions précédentes. Vous afficherez le résultat avec System.out.println.

Question 2.3

Combien y a-t-il eu d'appels au répondeur (caller == called dans Networkautrement dit Si = Si + 1 pour i pair) parmi ces appels avant d'obtenir un appel présidentiel ? Complétez la méthode main de la classe NetworkSimulation de la question précédente.

Déposez votre fichier NetworkSimulation.java.

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

Pour cette partie, on ne vous fournit pas de fichier de tests, les valeurs attendues sont sur cette page.

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

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, de même taille.

À l'initialisation, chaque élément est unique dans sa classe disjointe. Avec quelle(s) valeur(s) initialisez-vous le tableau size ? Ajoutez l'initialisation dans le constructeur de la classe UnionFind.

À chaque union de deux classes disjointes, on souhaite mettre à jour le tableau size. Pour l'efficacité, on décide que seul l'indice du représentant de la classe disjointe contient le nombre d'éléments de sa classe. Le représentant d'un élément i est obtenu en appelant la méthode find(i). En vous inspirant de la mise à jour du tableau rank lors de l'union de deux classes, ajoutez la mise à jour du tableau size dans la méthode union.

Écrivez le corps de la méthode

    int getSize(int i){
        // TODO
    }

dans la classe UnionFind qui renvoie le nombre d'éléments dans la classe de i.

Testez avec le fichier Test31.java.
Déposez votre fichier UnionFind.java.

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

3.2 Taille des classes disjointes dans le réseau de télécommunications.

Écrivez le corps de la méthode getSize(int N) dans la classe Network qui renvoie le nombre d'utilisateurs reliés dans la classe disjointe de l'utilisateur N.
Testez avec le fichier Test32.java.

Question : Lors du premier appel qui fait intervenir le numéro du président (Question 2 précédente), combien y a-t-il d'utilisateurs en lien avec le président, autrement dit quelle est la taille de la classe disjointe à laquelle appartient le président à ce moment ?

Pour répondre à cette question, vous ajouterez le code dans la méthode main de la classe NetworkSimulation, dans le fichier NetworkSimulation.java, comme pour la question 2.

Déposez votre fichier NetworkSimulation.java.

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

La réponse attendue est sur cette page.

4. La connectivité du réseau après n appels

On souhaite maintenant étudier la connectivité du réseau, et répondre à la question initiale :

Le numéro du Président est 524 287. Après combien d'appels n (on ne compte pas 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 ?

Vous ajouterez le code dans la méthode main de la classe NetworkSimulation, dans le fichier NetworkSimulation.java, comme pour les questions 2 et 3.

Déposez votre fichier NetworkSimulation.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
Une solution vous est proposée ici : TD3_solutions.zip


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

Utilisez le générateur de pseudo-aléa mais avec un module plus grand et un réseau plus grand, pouvant tous deux supporter cent millions d'utilisateurs (numéros à 8 chiffres, module = 108).

Le type int de Java couvre les nombres entiers de -231 = - 2 147 483 648 à 231-1 = 2 147 483 647. Les indices de tableaux en Java sont des int et les numéros à 8 chiffres tiennent aussi sur un int. Cependant, lors de l'initialisation des valeurs de state (index de 0 à 54), on multiplie un numéro à huit chiffres avec un indice à deux chiffres, or 54 * (108-1) est plus grand que 231-1.

Vous pouvez utiliser le type primitif long (entiers sur 64 bits) pour le calcul intermédiaire de l'état interne state pour les indices inférieurs à 55.

Si votre classe s'appelle PRNGLarge, vous pouvez utiliser ce fichier de tests : Test5.java.

Cette fois-ci, le numéro de la Première Ministre est le 64 40 34 11 et son secrétaire d'État 25 08 61 23.

  1. Après combien d'appels obtient-on le numéro de la Première Ministre ? Combiens d'utilisateurs sont liés à la Première Ministre, autrement dit dans la même classe disjointe ?
  2. Après combien d'appels obtient-on le numéro du secrétaire d'État ? 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 disjointe ? Pour répondre à cette question, pensez à rajouter une méthode dans la classe Network qui appelle la méthode appropriée de la classe UnionFind.
  4. Combien d'appels faut-il pour que 95% des utilisateurs soient dans la même classe disjointe que la Première Ministre ?

Vous pouvez déposer vos fichiers dans une archive zip.

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

Les réponses numériques aux questions sont ici.
Une solution vous est proposée ici : TD3_bonus_solutions.zip

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.