Rejoignez la communauté !
Co-construisez les ressources dont vous avez besoin et partagez votre expertise pédagogique.
Nombres complexes
Ch. 1
Nombres complexes, point de vue algébrique
Ch. 2
Nombres complexes, point de vue géométrique
Arithmétique
Ch. 3
Divisibilité dans Z
Ch. 4
PGCD et applications
Ch. 5
Nombres premiers
Graphes et matrices
Ch. 6
Calcul matriciel et applications aux graphes
Ch. 7
Suites et matrices
Annexes
Cahier d'algorithmique et de programmation
Chapitre 7
TP Info 2
Algorithme de PageRank
Ce document est actuellement projeté sur le côté de votre écran.
Énoncé
On considère le graphe orienté ci‑contre. Un internaute est placé initialement à sur le site . Chaque minute, il choisit un site vers lequel il se dirige. Chaque lien possible est équiprobable : ainsi, à , il a une probabilité égale à d'être en et une probabilité égale à d'être en .
Le zoom est accessible dans la version Premium.
Question préliminaire :
1. Quelle est la probabilité d'être en au temps ?
2. Quelle est la probabilité d'être en au temps ?
En assimilant les probabilités aux fréquences obtenues au bout d'un temps très long, on attribue une pondération à chaque sommet du graphe qui permet de classer les sites.
1. Quelle est la probabilité d'être en au temps ?
2. Quelle est la probabilité d'être en au temps ?
En assimilant les probabilités aux fréquences obtenues au bout d'un temps très long, on attribue une pondération à chaque sommet du graphe qui permet de classer les sites.
Ce document est actuellement projeté sur le côté de votre écran.
Objectif
Découvrir un algorithme PageRank à l'aide d'une des deux méthodes.
Ce document est actuellement projeté sur le côté de votre écran.
Méthode 1Tableur
1. Écrire la matrice de transition associée au graphe probabiliste.
2. a. Recopier la feuille de calcul suivante.
b. Quelle formule faut‑il écrire dans la cellule F6 et étirer sur la plage F6:J10 pour obtenir ?
c. Compléter les cellules de la plage F11:J15 en s'inspirant du contenu des cellules de la plage F6:J10 afin d'obtenir .
Calculer ensuite sur la plage F16:J20.
3. En déduire une estimation de la probabilité, au bout d'un temps très long, d'être sur chacun des sites.
4. Cette probabilité dépend‑elle du choix du site de départ ?
2. a. Recopier la feuille de calcul suivante.
Le zoom est accessible dans la version Premium.
b. Quelle formule faut‑il écrire dans la cellule F6 et étirer sur la plage F6:J10 pour obtenir ?
c. Compléter les cellules de la plage F11:J15 en s'inspirant du contenu des cellules de la plage F6:J10 afin d'obtenir .
Calculer ensuite sur la plage F16:J20.
3. En déduire une estimation de la probabilité, au bout d'un temps très long, d'être sur chacun des sites.
4. Cette probabilité dépend‑elle du choix du site de départ ?
Ce document est actuellement projeté sur le côté de votre écran.
Méthode 2Python
Le programme suivant permet de déterminer les pondérations de chaque site.
1. Compléter la fonction promenade qui simule les 1 000 premières minutes de la navigation du surfeur.
2. Simuler, avec la fonction PR à compléter ci‑dessous, la navigation de 1 000 surfeurs, et en déduire une estimation de la probabilité d'être sur chacun des sites au bout d'un temps très long.
3. Modifier le programme pour vérifier que le choix du site initial ne modifie pas les probabilités obtenues dans la question précédente.
1. Compléter la fonction promenade qui simule les 1 000 premières minutes de la navigation du surfeur.
import random def promenade(): # Simule les 1000 premières minutes de la marche aléatoire et renvoie le sommet sur lequel est le surfeur à la fin. sommet = "a" for pas in range(...): alea = random.random() if sommet == "a": if alea < 0.5: sommet = "b" else: ... elif ... elif ... elif ... else: ... return sommet
2. Simuler, avec la fonction PR à compléter ci‑dessous, la navigation de 1 000 surfeurs, et en déduire une estimation de la probabilité d'être sur chacun des sites au bout d'un temps très long.
def PR(): effectifs = 5*[0] surfeurs = ... for k in ...: sommetfinal = promenade() if sommetfinal == "a": effectifs[0] = effectifs[0] + 1/surfeurs elif ... elif ... elif ... else: ... return effectifs
3. Modifier le programme pour vérifier que le choix du site initial ne modifie pas les probabilités obtenues dans la question précédente.
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.
Oups, une coquille
j'ai une idée !
Nous préparons votre pageNous vous offrons 5 essais
YolèneÉmilieJean-PaulFatimaSarahUtilisation des cookies
Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.
