INF411 — TD3
Au téléphone avec le Président

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.

Le problème

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.

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

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 (S_i) par la relation de récurrence

• Pour 0 ≤ i ≤ 54, S_i = (300007i ³ + 900021i ² + 700018i + 200007) mod m,
• Pour 55 ≤ i, S_i = (S_i − 24 + S_i − 55) mod m.

On souhaite pouvoir traiter des valeurs de m de l'ordre du million et calculer plusieurs centaines de millions de termes de la suite (S_i).

On observe que pour i = 54, on a 300007i ³ = 47240302248 ≥ 2³¹. Or le type int de Java permet de représenter les entiers compris entre −2³¹ et 2³¹ − 1 (inclus) uniquement. Il faudra donc faire attention à la façon de mener les calculs pendant la phase d'initialisation du générateur.

Question 1

Écrivez une classe PRNG fournissant

• un constructeur public PRNG(int m),
• une méthode 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 (S₀, S₁, …) un à un.

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

Déposez le fichier TD3.java.

2. Les appels téléphoniques

Les appels sont définis à partir de la suite (S_i), avec un paramètre m égal à la population du réseau.

Au temps i (pour i = 0, 1, 2, …), l'individu S_2i appelle l'individu S_2i+1. L'appel est réussi si S_2i ≠ S_2i+1 ; les individus S_2i et S_2i+1 sont alors reliés. Lorsque S_2i = S_2i+1, l'appel échoue et il ne se passe rien.

On se propose dans un premier temps de répondre aux questions suivantes :

• Combien y a-t-il eu d'appels avant le premier appel impliquant le Président, sans compter les appels qui ont échoué ? Et avant le deuxième ?
• Lors de ces appels, qui appelle, et qui est appelé ?

Question 2

Écrivez une classe Network fournissant

• un constructeur 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),
• une méthode public int getCallCount() qui renvoie le nombre d'appels réussis depuis l'initialisation du réseau,
• deux méthodes public int getLastCaller() et public int getLastCallee() qui renvoient respectivement le dernier appelant et le dernier appelé,
• une méthode 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.

3. Connectivité du réseau

Le but de cette partie est de répondre à des questions portant sur la connectivité du réseau, à savoir :

1. Après combien d'appels (réussis) y a-t-il une suite d'appels qui relie le Président à la Première ministre ?
2. Au premier appel impliquant le Président, combien y a-t-il d'individus en lien avec le Président ? Et au deuxième ?

sans oublier la question initiale :

3. Après combien d'appels réussis 99% des individus (au moins) sont-ils reliés au Président ?

Question 3.1

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.

Question 3.2

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.

Question 3.3

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 ?)

Déposez le fichier TD3.java.

4. Bonus (facultatif)

Avant de continuer...

Si vous n'avez pas terminé le TD2, c'est le moment d'y revenir.

Question 4

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.)