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], [0, 4], [1, 2, 3, 5], [4]] # Corrigé
On donne le début de la partie exécutive du code.
# Partie exécutive
# ------------------------------------------
for i in range(nbDeplacements):
page = choice(hyperliens[page])
print("Page actuelle : " + nom[page])
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 : le code de la boucle "for..." affiche la page sur laquelle a eu lieu le déplacement. Dans ce programme choice choisit un lien parmi ceux disponibles sur une page.
Activité 3. Faites plusieurs simulations. A quoi correspond ce qui est affiché par le programme ?
Réponse : le programme affiche le déplacement entre les pages.
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])
# Corrigé
if nom[page] == 'E':
nbVisites[4] += 1
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])
# Corrigé
if nom[page] == 'A':
nbVisites[0] += 1
elif nom[page] == 'B':
nbVisites[1] += 1
elif nom[page] == 'C':
nbVisites[2] += 1
elif nom[page] == 'D':
nbVisites[3] += 1
elif nom[page] == 'E':
nbVisites[4] += 1
elif nom[page] == 'F':
nbVisites[5] += 1
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 obtenu par 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])
# Corrigé
if nom[page] == 'A':
nbVisites[0] += 1
elif nom[page] == 'B':
nbVisites[1] += 1
elif nom[page] == 'C':
nbVisites[2] += 1
elif nom[page] == 'D':
nbVisites[3] += 1
elif nom[page] == 'E':
nbVisites[4] += 1
elif nom[page] == 'F':
nbVisites[5] += 1
nbVisites = [100*j/nbDeplacements for j in 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 : d'après la simulation, c'est la page E. En répétant un grand nombre de fois le test, on remarque que la popularité de la page F(15%) est égale à la popularité de la page E divisée par quatre (10%) plus la popularité de la page C divisée par deux (5%) soit F = E/4 + C/2.
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 : quatre liens sortent de E dont un destiné à F, la probabilité que F soit atteinte à partir de E est donc égale à E/4. Deux liens sortent de C dont un destiné à F, d'où C/2.
Activité 10. En raisonnant comme pour la question précédente, établissez une relation pour la popularité de E.
Réponse : A, B, D, F ont des liens orientés vers E. E = A + F + (B + D)/2.