Prérequis : maîtriser les bases de la programmation Python (variables, boucles, entrées/sorties, fonctions)
Contexte de la mise en œuvre de l'activité : en classe, en présence de l'enseignant
Ressources, matériel, documents nécessaires : bibliothèque Python (random)
Présentation
Nous vous proposons, au travers cette activité, de comprendre comment les pages web peuvent être classées par votre moteur de recherche.
La plupart des pages web présentent des liens vers d’autres pages web, appelés liens hypertextes. Le principe général est que si le lien vers une page web est présent dans beaucoup d'autres pages web, cette page est considérée comme "importante" ou "populaire" et sera bien classée par les moteurs de recherche.
Pour mesurer cette popularité par un nombre, on applique l’algorithme suivant :
- on part d’une page web au hasard (on suppose que cela n’a pas d’importance, ce qui est partiellement vrai) ;
- sur chaque page visitée, on : clique sur un lien au hasard sur cette page (pour visiter une nouvelle page) ;
- on répète cette étape un grand nombre de fois.
Durant l’exécution de l’algorithme, on n’oublie pas de compter le nombre de fois que chaque page a été visitée. Le score de chaque page est alors la fréquence du nombre de visites de cette page. Les pages avec le plus haut score seront visitées plus souvent que les autres.
Ce concept est celui dusurfeur aléatoire.
Exemple
Le graphe "Représentation de pages web" représente un ensemble de page web, nommées A à F.
Les arêtes (flèches) représentent des liens entre les pages. Il y a une arête allant de la page B à la page F, ce qui signifie qu’il est possible, en visitant la page B, de cliquer sur un lien pour se retrouver sur la page F (ignorer les numéros pour le moment).
Représentation de pages web - Schéma
Préparation
Une liste d'éléments en python s'écrit :
une_liste = ['a', 'b', 'c']avec 0, 1, 2 les indices respectifs de a, b et c. On peut obtenir le deuxième élément avec :
une_liste[1]renvoie b
On peut obtenir l'indice du troisième élément (c) avec :
une_liste.index('c') renvoie 2
Le maximum d'une liste peut être déterminé avec la fonctionmax, que les éléments soient des nombres ou des lettres :
max_liste = max(une_liste) renvoie 'c' qui est la plus grande lettre dans l'ordre alphabétique.
Pour donner une valeur entière comprise entre deux autres valeurs, on utiliserandintdu modulerandomque l'on importe avec :
from random import randint
Il suffit ensuite d'appeler la fonction :
nb_aleatoire = randint(100, 200)pour obtenir un nombre entre 100 et 200.
Traitement des données avec Python
On souhaite indexer les six pages web "Représentation de pages web". On utilise une fonctionsurfeurqui parcours 100 fois les pages de façon aléatoire et une fonctionpopulairequi indique la page ayant obtenue le meilleur score.
1. Complétez le programme python suivant :
from random import randint
def surfeur(pages, compteurs):
page = pages[0] # on part de la page A
for _ in range(100): # répète 100 fois
s = randint(0, 5) # choisir l'un des six compteurs aléatoirement
if page == 'A': # de A
if s < 3:
compteurs[1] += 1 # on va vers la page B
page = pages[1]
elif 5 > s > 2:
compteurs[2] += 1 # on va vers la page C
page = pages[2]
elif s > 4:
compteurs[3] += 1 # on va vers la page D
page = pages[3]
elif page == 'B':
..........# A compléter, plusieurs lignes !
return compteurs
def populaire(pages, compteurs):
..........# A compléter, plusieurs lignes !
return pages[id]
pages = ['A', 'B', 'C', 'D', 'E', 'F']
compteurs = [1, 0, 0, 0, 0, 0] # la page A vaut 1, les autres 0
compteurs = surfeur(pages, compteurs)
print(pages)
print(compteurs)
pagep = populaire(pages, compteurs)
print("La page la plus populaire est la page ", pagep)