Sources : Manuels SNT Hatier et Bordas
Sommaire
La principale difficulté des moteurs de recherche consiste à classer, de la manière la plus pertinente possible, l'ensemble des pages contenant les mots clés demandés, pour choisir quelles pages présenter en premier.
En 1998, les informaticiens américains Larry Page et Sergey Brin proposent l'algorithme de PageRank* qui a conduit à la création du moteur de recherche Google et permis de proposer une définition à l'idée de "popularité" d'une page.*
L'algorithme PageRank* repose sur le principe de calculer la popularité d'une page à partir de la popularité des pages qui la citent.*
Six pages Web nommées de A à F comportent des liens hypertextes formant une toile selon le schéma suivant :
Des internautes arrivent par hasard sur la page A. Ils suivent de manière aléatoire les liens proposés par chaque page. Chaque clic sur un lien de la page augmente son compteur de vue.
Nous allons essayer d'approcher la réponse à la question suivante : quelle sera la page la plus populaire après le passage des internautes ?
from random import choice
# Partie déclarative
# -------------------------------------------------
# Liste des pages
nom = ["A", "B", "C", "D", "E", "F"]
# Nombre de visites des pages A, B, C, D, E et F
nbVisites = [0, 0, 0, 0, 0, 0]
# Nombre de déplacements à simuler
nbDeplacements = 10
# le depart se fait sur la page A (indice 0 de la liste nom)
page = 0
Les flèches sur le graphe représentent les déplacements possibles à partir de chacune des pages. Elles sont codées par les sous-listes dans la liste hyperliens ci-dessous.
Activité 1. Modifiez la liste hyperliens dans le code ci-dessous pour qu'elle corresponde au graphe.
# Partie déclarative suite
# Exemple : la page C à la position nom[2] est reliée
# aux pages A, nom[0] et F, nom[5] d'où la sous liste [0,5]
# à la position hyperliens[2]
hyperliens = [[4], [0, 4], [0, 5],[?],[?],[?]] # A modifier
On donne le début de la partie exécutive du code.
# Partie exécutive
# ------------------------------------------
for i in range(nbDeplacements):
page = choice(hyperliens[page]) # ligne 4
print("Page actuelle : " + nom[page]) # ligne 5
Activité 2. Exécutez dans l'ordre les trois zones de code ci-dessus et expliquez ce que font les deux lignes de code dans la boucle for. Quelle est l'utilité de la méthode choice dans ce programme ?
Aide : vous pouvez exécuter la boucle for "à la main" pour faire apparaître l'évolution des variables dans le tableau ci-dessous (à recopier au brouillon).
Réponse : ???
Activité 3. Faites plusieurs simulations. A quoi correspond ce qui est affiché par le programme ?
Réponse : ???
Activité 4. Complétez le code ci-dessous pour que la liste nbVisites contienne le nombre de passages dans la page E. Affichez ce résultat à la suite du parcours réalisé.
Exemple de résultat attendu
from random import choice
# Partie déclarative
# -------------------------------------------------
# Liste des pages
nom = ["A", "B", "C", "D", "E", "F"]
# Liste des liens
hyperliens = [[4], [0, 4], [0, 5], [0, 4], [1, 2, 3, 5], [4]]
# Nombre de visites des pages A, B, C, D, E et F
nbVisites = [0, 0, 0, 0, 0, 0]
# Nombre de déplacements à simuler
nbDeplacements = 10
# le depart se fait sur la page A (indice 0 de la liste nom)
page = 0
# Partie exécutive à modifier
# ------------------------------------------
for i in range(nbDeplacements):
page = choice(hyperliens[page])
print("Page actuelle : " + nom[page])
# Placez votre code
# ici
print(f"On est passé {nbVisites[4]} fois par la page E")
Activité 5. Complétez le code ci-dessous pour qu'il affiche maintenant le passage dans chacune des pages.
from random import choice
# Partie déclarative
# -------------------------------------------------
# Liste des pages
nom = ["A", "B", "C", "D", "E", "F"]
# Liste des liens
hyperliens = [[4], [0, 4], [0, 5], [0, 4], [1, 2, 3, 5], [4]]
# Nombre de visites des pages A, B, C, D, E et F
nbVisites = [0, 0, 0, 0, 0, 0]
# Nombre de déplacements à simuler
nbDeplacements = 10
# le depart se fait sur la page A (indice 0 de la liste nom)
page = 0
# Partie exécutive à modifier
# ------------------------------------------
for i in range(nbDeplacements):
page = choice(hyperliens[page])
print("Page actuelle : " + nom[page])
# Placez votre code
# ici
for k in range(len(nom)):
print(f"Visite de {nom[k]} : {nbVisites[k]}")
Activité 6. Complétez le code ci-dessous pour qu'il calcule le score d'une page en pourcentage.
from random import choice
# Partie déclarative
# -------------------------------------------------
# Liste des pages
nom = ["A", "B", "C", "D", "E", "F"]
# Liste des liens
hyperliens = [[4], [0, 4], [0, 5], [0, 4], [1, 2, 3, 5], [4]]
# Nombre de visites des pages A, B, C, D, E et F
nbVisites = [0, 0, 0, 0, 0, 0]
# Nombre de déplacements à simuler
nbDeplacements = 10000
# le départ se fait sur la page A (indice 0 de la liste nom)
page = 0
# Partie exécutive à modifier
# ------------------------------------------
for i in range(nbDeplacements):
page = choice(hyperliens[page])
# print("Page actuelle : " + nom[page])
# votre code
# nbVisites = # A compléter
for k in range(len(nom)):
print(f"Visite de {nom[k]} : {nbVisites[k]} %")
Activité 7. On met print("Page actuelle : " + nom[page]) en commentaire. Faites des tests pour nbDeplacements = 100, 1000 et 10000.
Activité 8. Quelle page est la plus populaire ? Comment expliquer ce succès ?
Réponse : ???
Activité 9. En observant le tracé du graphe, dites pourquoi il faut diviser par 4 la popularité de E et par 2 la popularité de C.
Réponse : ???
Activité 10. En raisonnant comme à la question précédente, établissez une relation pour la popularité de E.
Réponse : ???