{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Rang d'une page web" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Écrire votre nom ici \n", "\n", "Nom : \n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Google...**\n", "\n", "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 Citation 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é ... Google !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "## L'objectif:\n", "\n", "**Nous allons simuler le comportement d'un internaute**\n", "\n", "* ***On démarre sur une page web au hasard***\n", "* ***On suit au hasard un lien hypretexte sur cette page***\n", "* ***Ainsi de suite***\n", "\n", "***On tient également compte du fait que dans 15% des cas l'internaute abandonne sa recherche pour repartir sur une page au hasard***\n", "\n", "***Notre utilisateur va se balader de pages en pages, en faisant son petit tour du net.***\n", "\n", "***A chaque fois que l'utilisateur tombe sur une page donnée, cette page gagne un point.***\n", "\n", "***Et à la fin, la page ayant le plus de point est alors la page la plus populaire du réseau !***\n", "\n", "\n", "
\n", "\n", "\n", "### Notre exemple :\n", "\n", "***Considérons 6 sites web : A, B, C, D, E, F ayant des liens hypertexte entre eux.***\n", "\n", " * Le site A contient un lien vers les sites \"B\", \"C\" et \"E\" (3 liens sortants)\n", "\n", " * Le site B contient un lien vers le site \"F\" (1 lien sortant)\n", "\n", " * Le site C contient un lien vers les sites \"A\" et \"E\" (2 liens sortants)\n", "\n", " * Le site D contient un lien vers les sites \"B\" et \"C\" (2 liens sortants)\n", "\n", " * Le site E contient un lien vers les sites \"A\", \"B\", \"C\", \"D\" et \"F\" (5 liens sortants)\n", "\n", " * Le site F contient un lien vers le site \"E\" (1 lien sortant)\n", " \n", "***La situation peut se représenter à l'aide d'un graphe***\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "***Dans le code ci-dessous on a mis dans des variables toutes ces informations***\n", "\n", "*****On utilise la bibliothèque random, qui permet de faire des choix aléatoire (au hasard)*****\n", "\n", "**On a oublié de mettre les liens hypertexte sortant de C**\n", "\n", "**Rajoutez les..**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "# création d'un dictionnaire Hypertexte\n", "Hypertext = {}\n", "# création d'un dictionnaire pour le nombre de visite\n", "Walk_Number = {}\n", "# une variable pour le nombre total de visite\n", "Total_Walk = 0\n", "#liste des sites web\n", "Websites = [\"A\",\"B\",\"C\",\"D\",\"E\",\"F\"]\n", "# les liens hypertextes\n", "# le dictionnaire possède des clés ( nom des sites)\n", "# Qui contiennent des listes (liens hypertextes)\n", "Hypertext[\"A\"] = [\"B\",\"C\",\"E\"] # le site A possède des liens vers les sites B,C et E\n", "Hypertext[\"B\"] = [\"F\"]\n", "\n", "Hypertext[\"D\"] = [\"B\",\"C\"]\n", "Hypertext[\"E\"] = [\"A\",\"B\",\"C\",\"D\",\"F\"]\n", "Hypertext[\"F\"] = [\"E\"]\n", "print(Hypertext)\n", "# On initialise à 0.0 les visites des sites \n", "Walk_Number[\"A\"] = 0.0\n", "Walk_Number[\"B\"] = 0.0\n", "Walk_Number[\"C\"] = 0.0\n", "Walk_Number[\"D\"] = 0.0\n", "Walk_Number[\"E\"] = 0.0\n", "Walk_Number[\"F\"] = 0.0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### Simulation du comportement de l'internaute\n", "\n", "**Voici l'algorithme de calcul:**\n", "\n", "
\n",
    "i=0\n",
    "tant que i ‹ 1000:\n",
    "   On choisit au hasard un site → x  \n",
    "   tant qu'un nombre aléatoire est inférieur à 0.85:  \n",
    "      le nombre de visite de x est incrémenté de 1     \n",
    "      le nombre total de visite est incrémenté de 1     \n",
    "      x ← un lien hypertexte visitable   \n",
    "   i=i+1\n",
    "on fait afficher les résultats\n",
    "\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Questions:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "***Combien de fois boucle cet algorithme ?***\n", "\n", "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "***Pourquoi 0.85 ?***\n", "\n", "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "***Voici l'algorithme de calcul écrit en Python:***" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i = 0\n", "while i < 1000:\n", " x = random.choice(Websites)\n", " while random.random() < 0.85:\n", " Walk_Number[x] = Walk_Number[x] + 1\n", " Total_Walk = Total_Walk + 1\n", " x = random.choice(Hypertext[x])\n", " i = i + 1\n", "print (Walk_Number)\n", "print(Total_Walk)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### À faire:\n", "\n", "***Écrire ci-dessous le programme qui simule le comportement de l'internaute ci-dessous***\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Écrire le code ici" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Questions:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "***Quel est le site le plus populaire ?***\n", "\n", "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "***Classez les sites par ordre de popularité***\n", "\n", "Réponse :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### À faire:\n", "\n", "***Rajoutez quelques sites et leurs liens sortants***\n", "\n", "***Faites fonctionner le programme pour en faire ressortir le site le plus populaire***" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Écrire le code ici" ] } ], "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.2" } }, "nbformat": 4, "nbformat_minor": 2 }