NSI Première
TP sur les dictionnaires
Rang d'une page Web
En 1998, deux jeunes doctorants de l’université de Stanford, Larry Page et Sergey Brin (en collaboration avec Motwani et Wynograd) publiaient un article intitulé "The PageRank Ci tation Ranking: Bringing Order to the Web" présentant les résultats d’un nouvel algorithme permettant de classer les pages web selon leur popularité et montrant la précision de cet algorithme sur un nouveau moteur de recherche appelé ...
L'algorithme PageRank est un algorithme permettant de calculer la popularité des pages Web afin de classer les pages de réponses avec beaucoup de pertinence. Dans cette partie, vous allez programmer cet algorithme qui a été l'idée révolutionnaire des fondateurs du moteur de recherche Google.
Voilà une version simplifiée de cet algorithme:
- On simulele comportement d’un internaute
- On démarre au hasard sur une page
- On suit de façon aléatoire un lien sur cette page
- Et ainsi de suite...
On impose le fait que dans 15% des cas, l’utilisateur abandonne sa navigation pour repartir
d’une page au hasard.
Notre utilisateur va se balader de pages en pages, en faisant son petit tour du net.
A chaque fois que l’utilisateur tombe sur une page donnée, cette page gagne un point.
Et à la fin, la page ayant le plus de point est alors la page la plus populaire du réseau!
Un cas en particulier
Un site web comprend 6 pages liées entre elles.
Elles sont représentées chacune par un nom de A à F.
Elles comportent au moins un lien hypertexte formant un graphe :
Des internautes arrivent au hasard sur l’une des 6 pages. Ils suivent de manière aléatoire les liens proposés par chacune des pages et augmente ainsi la popularité de chacune.
Nous savons par expérience que, dans 85 % des cas, si le sujet du site web les intéresse alors les internautes poursuivent leur navigation dans les autres pages du site.
Après le passage de 1000 internautes, quelle sera la page la plus populaire ?
Pour répondre à cette question, nous allons simuler cette expérience à l’aide d’un programme en Python.
✏️ Question 1 : D’après vous quel est le site le plus populaire?
Implémention des données
Etape 1¶
Observons le graphe ci-dessus :
- Les six pages web sont représentées chacune par un nom de A à F, elles sont enregistrées dans une liste nommée pageWeb.
- Les liens hypertextes sortants de chaque page vers d’autres sont représentés dans un dictionnaire nommé hypertexte.
✏️ Question 2 : En vous servant du graphe ci-dessus et de l’exemple complété de la page B du dictionnaire hypertexte, Créer un dictionnaire Hypertexte dont les clés sont les sites web et les valeurs la liste des sites vers lesquels ils ont un lien sortant
# Création d'une liste de pages
pageWeb = ["A","B","C","D","E","F"]
# Dictionnaire, à compléter, des liens sortants de chaque page.
hypertexte = {"A": ["E"],
"B" : ["A", "E"],
"C" : ["A","F"],
"D" : ["A","E"],
"E" : ["B", "C", "D", "F"],
"F" : ["E"]
}
✏️ Question 3 : Créer un dictionnaire nbClic dont les clés sont les sites web et les valeurs, initialisées à 0, sont le nombre de fois où la page a été visitée.
exemple: nbClic["A"] = 0
# Création d'un dictionnaire du nombre de clic d'un internaute.
nbClic = {"A" : 0,
"B" : 0,
"C" : 0,
"D" : 0,
"E" : 0,
"F" : 0
}
Calcul pour 1000 simulations
# Voici l’algorithme de calcul :
'''
import random
i = 0
tant que i < 1000
On choisit au hasard un une page –> page
Tant qu’un nombre aléatoire est inférieur à 0.85
Le nombre de visite de pages est incrémenté de 1
Le nombre de clic de page visitées est incrémenté de 1
page <– un lien hypertexte visitable choisi de façon aléatoire
i = i + 1
On fait afficher les résultats
'''
• L’instruction random.random() renvoie un nombre dans l’intervalle [0,1[
• L’instruction page = random.choice(pageWeb) permet de choisir au hasard une page et le
stocke dans page
• L’instruction page = random.choice(hypertexte[page]) permet de choisir aléatoirement une page les liens hypertexte
✏️ Question 3 : Compléter et exécuter le programme puis observez la page la plus populaire.
# Simulation du surf aléatoire de 1000 internautes.
import random
totalDesClics = 0
i = 0
while i < 1000:
page = random.choice(pageWeb)
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
while random.random() < 0.85:
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
page = random.choice(hypertexte[page])
i = i + 1
# Affichage du nombre de clics pour chaque page de 1000 internautes.
for page in pageWeb :
nbClicParPage = nbClic[page]
print (" Pour la page ",page,"il y a eu",nbClicParPage," clics.")
print ("Il y a eu au total",totalDesClics,"changements de pages dans le site.")
print("Exécute à nouveau le programme pour 1000 autres internautes.")
Pour la page A il y a eu 1049 clics. Pour la page B il y a eu 727 clics. Pour la page C il y a eu 711 clics. Pour la page D il y a eu 716 clics. Pour la page E il y a eu 2117 clics. Pour la page F il y a eu 963 clics. Il y a eu au total 6283 changements de pages dans le site. Exécute à nouveau le programme pour 1000 autres internautes.
Etape 2¶
On souhaite faire apparaître un pourcentage de popularité à la place du nombre de clics.
- Recopier le programme précédent et modifier la fin du programme pour obtenir des pourcentages.
- Utiliser la fonction « round » permettant d’afficher l’arrondi d’un résultat pour un arrondi au centième des pourcentages.
import random
# Création d'une liste de pages
pageWeb = ["A","B","C","D","E","F"]
# Dictionnairedes liens sortants de chaque page.
hypertexte = {"A" : ["E"],
"B" : ["A", "E"],
"C" : ["A","F"],
"D" : ["A","E"],
"E" : ["B", "C", "D", "F"],
"F" : ["E"]
}
# Dictionnaire du nombre de clic d'un internaute.
nbClic = {"A" : 0,
"B" : 0,
"C" : 0,
"D" : 0,
"E" : 0,
"F" : 0
}
# Simulation du surf aléatoire de 1000 internautes.
totalDesClics = 0
i = 0
while i < 1000:
page = random.choice(pageWeb)
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
while random.random() < 0.85:
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
page = random.choice(hypertexte[page])
i = i + 1
# Affichage du pourcentage de clics pour chaque page de 1000 internautes.
for page in pageWeb :
pClicParPage = round(nbClic[page]/totalDesClics *100,2)
print (" Pour la page ",page,"il y a eu",pClicParPage," % clics.")
print ("Il y a eu au total",totalDesClics,"changements de pages dans le site.")
print("Exécute à nouveau le programme pour 1000 autres internautes.")
Pour la page A il y a eu 16.31 % clics. Pour la page B il y a eu 11.04 % clics. Pour la page C il y a eu 11.47 % clics. Pour la page D il y a eu 11.55 % clics. Pour la page E il y a eu 34.47 % clics. Pour la page F il y a eu 15.16 % clics. Il y a eu au total 6206 changements de pages dans le site. Exécute à nouveau le programme pour 1000 autres internautes.
Vous venez de programmer une partie du programme de classement de la popularité des pages web du moteur de recherche de Google, appelée PageRank.
Etape 3¶
- Copier/coller le programme ci-dessus dans le cadre ci-dessous.
- Adapter votre programme au graphe ci-dessous et observez la page la plus populaire.
import random
# Création d'une liste de pages
pageWeb = ["A","B","C","D","E","F"]
# Dictionnairedes liens sortants de chaque page.
hypertexte = {"A" : ["B", "C", "D"],
"B" : ["C"],
"C" : ["A", "D", "E"],
"D" : ["A", "B", "C", "E", "F"],
"E" : ["C", "D", "F"],
"F" : ["E"]
}
# Dictionnaire du nombre de clic d'un internaute.
nbClic = {"A" : 0,
"B" : 0,
"C" : 0,
"D" : 0,
"E" : 0,
"F" : 0
}
# Simulation du surf aléatoire de 1000 internautes.
import random
totalDesClics = 0
i = 0
while i < 1000:
page = random.choice(pageWeb)
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
while random.random() < 0.85:
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
page = random.choice(hypertexte[page])
i = i + 1
# Affichage du pourcentage de clics pour chaque page de 1000 internautes.
for page in pageWeb:
pClicParPage = round(nbClic[page]/totalDesClics *100,2)
print (" Pour la page ",page,"il y a eu",pClicParPage," % clics.")
print ("Il y a eu au total",totalDesClics,"changements de pages dans le site.")
print("Exécute à nouveau le programme pour 1000 autres internautes.")
Pour la page A il y a eu 12.63 % clics. Pour la page B il y a eu 10.28 % clics. Pour la page C il y a eu 22.79 % clics. Pour la page D il y a eu 19.35 % clics. Pour la page E il y a eu 21.89 % clics. Pour la page F il y a eu 13.06 % clics. Il y a eu au total 6831 changements de pages dans le site. Exécute à nouveau le programme pour 1000 autres internautes.
Etape 4¶
On souhaite construire un diagramme en bâton du nombre de pages visitées par les 1000 internautes.
- Copier/coller le programme ci-dessus dans le cadre ci-dessous,Recopier à la fin de votre programme les lignes suivantes :
- Modifier cette partie de programme pour obtenir un diagramme en bâton du pourcentage de pages visitées.
import random
from matplotlib.pyplot import *
# Création d'une liste de pages
pageWeb = ["A","B","C","D","E","F"]
# Dictionnairedes liens sortants de chaque page.
hypertexte = {"A" : ["B", "C", "D"],
"B" : ["C"],
"C" : ["A", "D", "E"],
"D" : ["A", "B", "C", "E", "F"],
"E" : ["C", "D", "F"],
"F" : ["E"]
}
# Dictionnaire du nombre de clic d'un internaute.
nbClic = {"A" : 0,
"B" : 0,
"C" : 0,
"D" : 0,
"E" : 0,
"F" : 0
}
# Simulation du surf aléatoire de 1000 internautes.
totalDesClics = 0
i = 0
while i < 1000:
page = random.choice(pageWeb)
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
while random.random() < 0.85:
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
page = random.choice(hypertexte[page])
i = i + 1
# Affichage du pourcentage de clics pour chaque page de 1000 internautes.
for page in pageWeb:
pClicParPage = round(nbClic[page]/totalDesClics *100,2)
print (" Pour la page ",page,"il y a eu",pClicParPage," % clics.")
print ("Il y a eu au total",totalDesClics,"changements de pages dans le site.")
# Affichage du pourcentage de clics pour chaque page de 1000 internautes en diagramme baton
x = pageWeb
y = []
for page in pageWeb:
pClicParPage = round(nbClic[page]/totalDesClics *100,2)
y.append(pClicParPage)
bar(x, y)
show()
Pour la page A il y a eu 14.05 % clics. Pour la page B il y a eu 10.58 % clics. Pour la page C il y a eu 22.48 % clics. Pour la page D il y a eu 18.73 % clics. Pour la page E il y a eu 21.75 % clics. Pour la page F il y a eu 12.4 % clics. Il y a eu au total 6427 changements de pages dans le site.
import random
from matplotlib.pyplot import *
# Création d'une liste de pages
pageWeb = ["A","B","C","D","E","F"]
# Dictionnairedes liens sortants de chaque page.
hypertexte = {"A" : ["B", "C", "D"],
"B" : ["C"],
"C" : ["A", "D", "E"],
"D" : ["A", "B", "C", "E", "F"],
"E" : ["C", "D", "F"],
"F" : ["E"]
}
# Dictionnaire du nombre de clic d'un internaute.
nbClic = {"A" : 0,
"B" : 0,
"C" : 0,
"D" : 0,
"E" : 0,
"F" : 0
}
# Simulation du surf aléatoire de 1000 internautes.
totalDesClics = 0
i = 0
while i < 1000:
page = random.choice(pageWeb)
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
while random.random() < 0.85:
nbClic[page] = nbClic[page] + 1
totalDesClics = totalDesClics + 1
page = random.choice(hypertexte[page])
i = i + 1
# Affichage du nombre de clics pour chaque page de 1000 internautes.
for page in pageWeb :
nbClicParPage = nbClic[page]
print (" Pour la page ",page,"il y a eu",nbClicParPage," clics.")
print ("Il y a eu au total",totalDesClics,"changements de pages dans le site.")
# Affichage du pourcentage de clics pour chaque page de 1000 internautes en diagramme baton
x = pageWeb
y = []
for page in pageWeb:
nbClicParPage = nbClic[page]
y.append(nbClicParPage)
bar(x, y)
show()
Pour la page A il y a eu 892 clics. Pour la page B il y a eu 718 clics. Pour la page C il y a eu 1488 clics. Pour la page D il y a eu 1290 clics. Pour la page E il y a eu 1402 clics. Pour la page F il y a eu 843 clics. Il y a eu au total 6633 changements de pages dans le site.