1. Accueil
  2. prof
  3. le-web
  4. 6-moteurs-de-recherche

Moteurs de recherche (45 minutes)

Inspiré de Mesure de popularité d'une page web, de Julien Launay.

Matériel nécessaire : un dé à six faces par binôme.

  1. Avant le début de l'activité, le professeur a ouvert sur son ordinateur le fichier permettant de synthétiser les résultats de l'ensemble de la classe.

  2. Le professeur distribue le sujet (source), et lit avec les élèves l'énoncé.

  3. À la main, avec le dé, par binômes, les élèves simulent une marche aléatoire sur le graphe. Le professeur les laisse chercher deux minutes, puis il parcours la salle pour :

    • dire à chaque binôme (dés que la place est libre) qu'il peut aller reporter ses résultats sur l'ordinateur du professeur ;
    • ramasser son dé.

    À la fin de l'activité, sur l'ordinateur du professeur, le score PageRank de l'ensemble du graphe est disponible.

    Remarque : Le score PageRank devrait1 être (arrondi au centième) : $$\begin{array}{cccccc} A & B & C & D & E & F & G & H \\ \hline 0,17 & 0,09 & 0,20 & 0,25 & 0,03 & 0,21 & 0,04 & 0,01 \ \end{array}$$

  4. Les élèves répondent d'abord seuls, puis en faisant le bilan en grand groupe avec le professeur, à la suite de l'activité (parties Analyse et Search Engine Optimization).

    Deux réponses sont attendues à la dernière question :

    1. On peut créer des liens depuis les sites existants (en particulier les populaires) vers notre page. Cela peut se faire si ces sites web ont une section commentaire : il suffit de commenter avec l'adresse de notre site web.
    2. On peut créer plein de nouvelles pages web qui forment une clique avec le sommet F (c'est-à-dire que chaque sommet de F et des nouveaux sommets pointe vers les autres). Cela augmente artificiellement la popularité de ces pages, et permet de faire de F la page la plus populaire du graphe.

Remarquons qu'il est aussi possible de calculer le score des pages en utilisant un programme en Python. Cela permet de faire travailler la programmation. J'ai écrit un tel programme, mais il faudrait le nettoyer et l'adapter pour le faire manipuler pour des élèves de seconde.

  1. Calculé (fichier Xcas) comme le résultat approximatif de : $\begin{pmatrix}1&0&0&0&0&0&0\end{pmatrix}\times M^{1000}$, où $M$ est la matrice de transition du graphe probabiliste correspondant (les sommets ayant été triés par ordre alphabétique) :

    $$M = \begin{pmatrix} 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 \\ 1/3 & 0 & 0 & 0 & 1/3 & 0 & 1/3 & 0 \\ 1/2 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 1/2 & 0 & 0 \\ 1/3 & 0 & 0 & 0 & 0 & 0 & 1/3 & 1/3 \\ 0 & 1/3 & 1/3 & 1/3 & 0 & 0 & 0 & 0 \\ 1/2 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/3 & 0 & 1/3 & 0 & 0 & 0 & 1/3 & 0 \\ \end{pmatrix}$$↩