Accueil  / Semaine 12 / Travail noté sur les algorithmes topologiques

Travail noté sur les algorithmes topologiques

Consignes du travail noté 5

Vous devez transmettre deux programmes Java au chargé d’encadrement. L’objet de votre courriel doit commencer par « [INF6104][TRAVAIL5] » afin de permettre au chargé d’encadrement de classer rapidement ses messages. Dans le corps de votre message ainsi que dans vos programmes Java, vous devez bien indiquer vos nom et numéro d’étudiant ainsi que le numéro du travail. Vous devez joindre un bref document de discussion (en format « pdf », « Word 97/2000/XP », « RTF », « OpenDocument » ou « texte »).

Le travail est noté sur 10 points.

Question 1 (5 points)

Écrivez un court programme Java — moins de 1000 lignes — qui calcule le score PageRank simplifié de toutes les pages d’un graphe web. Nommez votre programme « PageRank.java ». Assurez-vous que le total des scores PageRank soit de 1.

Votre programme doit lire des fichiers de données contenant les graphes web en utilisant la classe suivante : Graphe.java.

Le format des données suit cet exemple :

index.html -> menu.html
index.html -> velo.html
index.html -> page.html
velo.html -> menu.html
page.html -> index.html
menu.html -> velo.html
menu.html -> page.html

Vous devez utiliser ce fichier :

Classe Java lisant des graphes

La commande suivante doit donner la solution :

java PageRank donnees.txt

Donnez la solution obtenue et discutez.

Question 2 (5 points)

Suivant le même principe que la question précédente, écrivez un court programme Java qui calcule les coefficients « authority » et « hub » de chaque page d’un graphe web. Votre programme doit spécifier ce que « recommande » l’algorithme HITS à l’utilisateur. Nommez votre programme « Hits.java ». (Initiez l’algorithme HITS en prenant comme point de départ unique la page velo.html.)

La commande suivante doit donner la solution :

java Hits donnees.txt

Donnez la solution obtenue et discutez.

Indice. Dans vos calculs, vérifiez que votre matrice A est correcte : A_{i,j} a la valeur 1 si et seulement si la page j a un lien vers la page i. Ainsi, la somme des composantes d’une colonne donne le nombre de liens présents sur la page correspondante. Si une page n’a aucun lien, la colonne correspondante ne doit alors contenir que des zéros.


Les travaux du cours INF 6104 ne sont pas sous une licence Creative Commons.