Des nombres de Fibonacci aux graphes probabilistes et à Google

vendredi 7 mai 2010
par  Jérôme Germoni

Le calcul des nombres de Fibonacci par la formule de Binet, qui en donne une expression en fonction de l’indice et du nombre d’or, peut être fait en diagonalisant une matrice 2×2. Le même type de calcul donne des expressions explicites des suites de probabilités dans lesgraphes probabilistes à deux états que l’on voit en terminale ES, ainsi bien sûr que l’expression de l’état stable.

Dans ce texte, on développe à l’identique les deux calculs pour montrer leur similitude. Puis on étend —sans preuves— les deux problèmes aux suites satisfaisant une récurrence linéaire et à (une version simple de) l’algorithme PageRank utilisé par Google pour hiérarchiser les pages Internet.

Comme chacun sait, les pages correspondant à une requête faite sur le moteur de recherche Google arrivent dans un ordre qui n’est pas aléatoire. C’est ce qui a rendu le moteur si célèbre. Cet ordre reflète une hiérarchie définie par le résultat de l’algorithme PageRank. Cet algorithme prend en entrée le web à un moment donné et produit une liste de « scores », un réel compris entre 0 et 1 pour chaque page du web. À chaque requête, les pages sont présentées par ordre décroissant de score.

L’idée de l’algorithme, c’est de marcher au hasard sur le web et de compter combien de fois on passe sur chaque page. Le \em credo, c’est que plus on revient souvent sur une page, plus elle est pertinente.

L’approche fréquentiste des probabilités suggère que les fréquences de passage sur chaque page après une longue marche sont les probabilités de s’y trouver. Pour cela, la théorie des graphes probabilistes, que l’on peut appeler plus pompeusement la théorie des chaînes de Markov finies et qui est fondée sur les probabilités et un peu d’algèbre linéaire, donne une façon concrète de calculer ces probabilités.


Documents joints

Des lapins au web, de Fibonacci à Perron
Des lapins au web, de Fibonacci à Perron

Commentaires

Brèves

25 mars 2010 - Réforme du lycée...

C’est celle de 1902 : conférences de Henri Poincaré, Émile Borel. Références mentionnées par (...)

21 février 2010 - Preuve avec mots : 2+11-1=12

En contrepoint des « preuves sans mots », Art Benjamin le mathémagicien propose une preuve avec (...)

4 février 2010 - Feuille @ problèmes

Le numéro 16 de la feuille à problèmes vient de sortir. Son thème : algorithmes.

22 janvier 2010 - Statistiques sur l’Éducation nationale

De nombreux chiffres sur l’enseignement et l’éducation en France et en Europe compilés sur le site (...)

13 octobre 2009 - Algorithmes et logique au lycée

Nouvelle publication de l’IREM d’Aix-Marseille : Algorithmes et logique au lycée. Cette brochure (...)