{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)\n", "\n", "\n", "© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
\n", "Les activités partagées sur Capytale sont sous licence Creative Commons.\n", "\n", " Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Algorithme du surfeur aléatoire (corrigé) \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Elaboré par Larry Page et Sergey Brin, l’algorithme de Pagerank a permis à Google, nouvel arrivant, de prendre en quelque mois le monopole des moteurs de recherche thématique. \n", "\n", "L’idée est d'attribuer à chaque page une « note » ou « score » ou « Pagerank » entre 0 et 1 qui caractérise la pertinence de cette page, en respectant les règles suivantes :\n", "\n", "\n", "Le but de l'activité est de présenter une version simplifiée du PageRank : L'algorithme du surfeur aléatoire." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Modélisation à l'aide d'un graphe, introduction de l'algorithme" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour modéliser les interconnexions entre différentes pages, on utilise un graphe orienté dans lequel :\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Question 1 :\n", "\n", "Le graphe G1 ci-dessous correspond à une situation de 4 pages. Par exemple, la page 2 propose des liens vers les pages 1 et 4.\n", "\n", "Recopier le tableau et suivre les instructions suivantes pour le remplir :\n", "\n", " \n", "\n", "![GrapheG1](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/SNT/img/surfeur_schema1.png)\n", "\n", " Le classement obtenu est en général : 2 - 4 - 1 - 3 mais peut peut varier suivant la simulation. \n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Automatisation : Implémentation de l'algorithme en Python" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En langage Python, on modélise le graphe G1 précédent à l'aide de la structure Liens_G1 donnée ci-dessous.\n", "\n", "Question 2 : Expliquer brièvement comment les informations du graphe sont codées dans Liens_G1.\n", "\n", " Chaque numéro de sommet est suivi d'une liste contenant les sommets vers lesquels il pointe. \n", "\n", "\n", "\n", "\n", "La fonction parcours(Liens,n) fournie permet, lorsqu’on a défini une liste de liens, de simuler un parcours dans le graphe, avec n visites de pages, en comptant le nombre de fois que chaque sommet est visité.\n", "\n", "Attention : Penser à exécuter la zone ci-dessous (et les suivantes) avec SHIFT+Entrée. " ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "#Structure permettant de modéliser le graphe G1\n", "Liens_G1 = { 1:[2,3,4] , 2:[1,4] , 3:[1,4] , 4:[2] }\n", "\n", "#Cette instruction permet d'utiliser des fonctions de choix aléatoires\n", "from random import*\n", "\n", "def parcours(Liens,n):\n", " \"\"\"\n", " Cette fonction simule un parcours de n pages \n", " Les pages sont numérotés 1,2,...\n", " Les arêtes sont définies par les Liens\n", " \"\"\"\n", " #On choisit un sommet de départ au hasard\n", " Sommet=randint(1,len(Liens))\n", " \n", " # Initialisation des compteurs du nombre de passages pour chaque sommet\n", " # 1:0 2:0 ...\n", " Passages = {S:0 for S in Liens}\n", " \n", " #On répète n fois:\n", " for k in range(n):\n", " #on change de sommet\n", " Sommet = choice(Liens[Sommet])\n", " #on incrémente le compteur du sommet visité (augmente de 1)\n", " Passages[Sommet] += 1\n", " \n", " #La fonction renvoie les compteurs\n", " return Passages\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Question 3 :\n", " \n", "Exécuter l'appel à la fonction parcours ci-dessous. A l'aide du résultat, proposer un classement des 4 pages du graphe G1, et comparer avec la réponse à la question 1.\n", "\n", " On retrouve le classement : 2 - 4 - 1 - 3. \n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{1: 23020, 2: 38465, 3: 7694, 4: 30821}" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#Simulation du surfeur aléatoire pour le graphe G1\n", "parcours(Liens_G1,100000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Question 4 : \n", " \n", " On considère le graphe G2 ci-dessous, qui modélise les liens entre 6 pages. \n", "\n", "![GrapheG2](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/SNT/img/surfeur_schema2.png)\n", "\n", " 4.a Définir une structure Liens_G2 correspondant à ce graphe. \n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "#Créer une structure permettant de modéliser le graphe G2\n", "Liens_G2 = { 1:[5] , 2:[1,3,5] , 3:[1,6] , 4:[1,5] , 5:[2,3,4,6] , 6:[5] }" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " 4.b A l'aide d'un appel à la fonction parcours, compléter le tableau. \n", "\n", " Le tableau dépend de la simulation, mais permet d'établir le classement suivant pour les pages: 5 - 6 - 1 - 3 - 2 = 4 " ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{1: 14165, 2: 9610, 3: 12707, 4: 9451, 5: 38083, 6: 15984}" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#Effectuer un appel à la fonction parcours\n", "parcours(Liens_G2,100000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " On considère le graphe G3 obtenu en remplaçant, sur le graphe G2, le lien de la page 1 vers la page 5 par un lien de la page 1 vers la page 3.\n", " \n", " 4.c Tracer le graphe G3 et créer la structure Liens_G3 correspondante.\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "#Créer une structure permettant de modéliser le graphe G2\n", "Liens_G3 = { 1:[3] , 2:[1,3,5] , 3:[1,6] , 4:[1,5] , 5:[2,3,4,6] , 6:[5] }" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " 4.d À l'aide d'un appel à la fonction parcours, réaliser pour G3 un tableau similaire au précédent. \n", "\n", " Le tableau dépend de la simulation, mais permet d'établir le classement suivant pour les pages: 3 - 5 - 6 - 1 - 2 = 4 " ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{1: 18110, 2: 6139, 3: 26194, 4: 6017, 5: 24288, 6: 19252}" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#Effectuer un appel à la fonction parcours\n", "parcours(Liens_G3,100000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " 4.e Vérifier que, par rapport au graphe G2, les notes des pages 1 et 3 ont augmenté. Expliquer ce phénomène. \n", "\n", " La note de la page 3 a augmenté car elle est référencée par une page supplémentaire et a donc plus de chances d'être atteinte. Comme cette page 3 pointe sur la page 1 avec une probabilité 1/2, l'augmentation de sa note entraîne indirectement une augmentation de la note de la page 1. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Question 5 : \n", " \n", " On considère le graphe G ci-dessous, qui modélise les liens entre 5 pages. \n", "\n", "![GrapheG](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/SNT/img/surfeur_schema3.png)\n", "\n", " 5.a Si on supprime le lien de la page 5 vers la page 3, pensez-vous que la note de la page 4 va augmenter ou diminuer ? Justifier brièvement la réponse.\n", "\n", " Si on supprime le lien de la page 5 vers la page 3, la page 5 ne pointera plus que vers la page 4, ce qui va augmenter la note de la page 4. Ceci est d'autant plus vraie que la page 5 est fortement référencée et aura donc elle-même une note élevée. \n", "\n", "\n", " 5.b Effectuer les saisies Python nécessaires pour vérifier votre réponse. \n" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Une simulation avec 100000 déplacements donne: \n", " -le tableau {1: 4893, 2: 14969, 3: 30079, 4: 26763, 5: 23296} pour le graphe G initial\n", " -le tableau {1: 3700, 2: 11068, 3: 22217, 4: 37082, 5: 25933} pour le graphe G modifié.\n", "La note du sommet 4 est donc passée de 0.26763 à 0.37082\n" ] } ], "source": [ "#Effectuer les saisies nécessaires\n", "\n", "Liens_G={ 1:[5] , 2:[1,3,5] , 3:[2,4] , 4:[3,5] , 5:[3,4] }\n", "Liens_G_modif={ 1:[5] , 2:[1,3,5] , 3:[2,4] , 4:[3,5] , 5:[4] }\n", "\n", "N=100000\n", "T1=parcours(Liens_G,N)\n", "T2=parcours(Liens_G_modif,N)\n", "\n", "Conclusion=\"Une simulation avec \"+str(N)+\" déplacements donne: \\n -le tableau \"+str(T1)+\" pour le graphe G initial\\n -le tableau \"+str(T2)+\" pour le graphe G modifié.\\nLa note du sommet 4 est donc passée de \"+str(T1[4]/N)+\" à \"+str(T2[4]/N)\n", "print(Conclusion)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "© Copyright Franck CHEVRIER 2019-2021 https://www.python-lycee.com.
\n", "Les activités partagées sur Capytale sont sous licence Creative Commons." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.10" } }, "nbformat": 4, "nbformat_minor": 2 }