Ce TD est plus court que les précédents, mais aussi moins guidé.
Votre code est à placer comme d'habitude dans un fichier
TD3.java.
Il n'y a pas de squelette de code fourni, seulement
quelques fichiers
pour vous aider à tester votre code à certaines questions.
Vous pouvez aussi, comme d'habitude, vous aider de la
documentation officielle
de la bibliothèque standard de Java.
Le sujet est adapté de ce problème du Projet Euler.
On considère un réseau dynamique qui évolue de la façon suivante.
Initialement, le réseau est constitué de m sommets (les « individus ») sans lien entre eux. Chaque individu est identifié par un entier compris entre 0 et m − 1 inclus (son « numéro de téléphone »).
De manière répétée, on choisit deux numéros de téléphone et, s'ils ne le sont pas déjà, on relie les individus correspondants par une arête (un « appel téléphonique »). Si les deux numéros de téléphone sont égaux, on ne fait rien.
L'objectif est de déterminer au bout de combien d'appels téléphoniques un sommet donné (le « Président ») est relié à une certaine proportion, par exemple 99%, de la population totale.
Pour tirer « au hasard » les appels téléphoniques,
on utilise un générateur pseudo-aléatoire,
c'est-à-dire un procédé déterministe dont le résultat
« ressemble » du point de vue statistique à une suite de nombres aléatoires.
(La méthode Math.random() que l'on a utilisée au TD1 donne aussi
accès à un générateur pseudo-aléatoire.
Mais aujourd'hui, nous allons implémenter le nôtre.)
Le générateur utilisé ici s'appelle un
générateur de Fibonacci à retard.
On définit une suite (Si) par la relation de récurrence
On souhaite pouvoir traiter des valeurs de m de l'ordre du million et calculer plusieurs centaines de millions de termes de la suite (Si).
On observe que pour i = 54, on a
300007i 3 = 47240302248 ≥ 231.
Or le type int de Java permet de représenter les entiers compris
entre −231 et 231 − 1 (inclus) uniquement.
Il faudra donc faire attention à la façon de mener les calculs pendant
la phase d'initialisation du générateur.
Écrivez une classe PRNG fournissant
public PRNG(int m),
public int getNext(),
de sorte que les appels successifs à getNext() sur un objet de la
classe PRNG nouvellement construit renvoient
les termes de la suite (S0, S1, …) un à
un.
Testez votre code en exécutant le fichier Test1.java.
long
dans les calculs intermédiaires, ou encore réduire modulo m
certains résultats intermédiaires.
On rappelle que (comme pour double !), stocker le
résultat d'un calcul dans une variable de type long
n'est pas suffisant pour que le calcul lui-même utlise le type
long.
Déposez le fichier TD3.java.
Les appels sont définis à partir de la suite (Si), avec un paramètre m égal à la population du réseau.
Au temps i (pour i = 0, 1, 2, …), l'individu S2i appelle l'individu S2i+1. L'appel est réussi si S2i ≠ S2i+1 ; les individus S2i et S2i+1 sont alors reliés. Lorsque S2i = S2i+1, l'appel échoue et il ne se passe rien.
On se propose dans un premier temps de répondre aux questions suivantes :
Écrivez une classe Network fournissant
public Network(int m) qui initialise un nouveau
réseau de m individus, où aucun appel n'a encore été passé
(le premier appel aura lieu au temps i = 0),
public int getCallCount() qui renvoie le nombre
d'appels réussis depuis l'initialisation du réseau,
public int getLastCaller() et
public int getLastCallee()
qui renvoient respectivement le dernier appelant et le dernier appelé,
public void runUntilCall(int u) qui simule
des appels jusqu'à trouver un appel (réussi) impliquant l'individu u
(en tant qu'appelant ou en tant qu'appelé).
Notez qu'il n'est pas utile à ce stade de garder trace de quels individus sont reliés.
Testez votre code en exécutant le fichier Test2.java.
Déposez le fichier TD3.java.
Le but de cette partie est de répondre à des questions portant sur la connectivité du réseau, à savoir :
sans oublier la question initiale :
Ajoutez à la classe Network une méthode
public void runUntilConnected(int u, int v)
qui simule des appels jusqu'à ce que les
deux individus u et v soient reliés
(par une suite d'appels téléphoniques, sans tenir compte de qui appelle et qui
est appelé).
Testez votre code en exécutant le fichier Test3.java.
On pourra utiliser la structure de données union-find étudiée en amphi.
Ajoutez à la classe Network une méthode
public int getContactCount(int u)
qui renvoie le nombre d'individus connectés
à un individu u donné (en comptant u lui-même).
Testez votre code en exécutant le fichier Test3.java après y avoir
décommenté la ligne correspondante.
runUntilConnected et runUntilCall
contiennent chacun une implémentation du passage d'un appel, il faut
penser à modifier les deux... Ou mieux, factoriser le code en
introduisant une fonction auxiliaire !
Le numéro de téléphone du Président est 524287, et la population compte un million d'individus. Après combien d'appels réussis au moins 1% des individus (le Président inclus) sont-ils reliés au Président ? 50% ? 99% ? 100% ? (Avant de faire le calcul, avez-vous une idée de l'ordre de grandeur du résultat attendu ?)
1% — 1 840 579 appels.
50% — 1 840 579 appels.
99% — 2 325 629 appels.
100% — 8 834 905 appels.
Déposez le fichier TD3.java.
Si vous n'avez pas terminé le TD2, c'est le moment d'y revenir.
Tracez la courbe de la taille du plus grand groupe d'utilisateurs reliés entre eux en fonction du nombre d'appels réussis, par exemple pour un réseau de 1000 utilisateurs.
On pourra adapter le code de l'amphi pour la manipulation de fenêtres graphiques.
Qu'observe-t-on ? (Un peu de lecture à ce sujet.)