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?

Réponse : Le site le plus populaire est le E

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.

1. Recopier le programme précédent et modifier la fin du programme pour obtenir des pourcentages.
2. 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

1. Copier/coller le programme ci-dessus dans le cadre ci-dessous.
2. 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.

1. Copier/coller le programme ci-dessus dans le cadre ci-dessous,Recopier à la fin de votre programme les lignes suivantes :

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