Page 1 sur 1

Google et les maths

MessagePosté: Samedi 10 Mai 2008, 16:32
par guiguiche
Suite à cette discussion, je soumets à votre sagacité mathématique ce problème fraîchement tombé lors d'une épreuve de concours (même si la référence explicite à Google est un peu limite à mes yeux).

Re: Google et les maths

MessagePosté: Samedi 10 Mai 2008, 21:01
par OG
Cher Guiguiche

Amusant j'ai fait travailler mes 3 étudiantes de prépa agreg cette semaine sur le texte

http://agreg.dnsalias.org/Textes/pub2008-B1.pdf

Idem je soumets à votre sagacité mathématique, etc.
Ce n'est pas le texte le plus difficile du site.
Je pense que la référence à Google est tout de même sérieuse même si depuis la création de l'algo pageranking ils en y a eu d'autres, des complémentaires, des mélanges, etc.

j'ajoute : quel classement trouvez-vous dans l'exemple donné dans le texte ?

Cordialement
O.G.

Re: Google et les maths

MessagePosté: Dimanche 03 Août 2008, 14:02
par surjay
Quelqu'un pourrait il m'aider à faire la question II.B.3 du premier sujet svp ?

Dans cette question on a Q une matrice stochastique NxN, U un vecteur ne contenant que des 1 et on a établi :
$Q^t U = U$
Si $Q - I_N$ est inversible alors $Q^t - I_N$ l'est aussi.
La question étant : en déduire que 1 est une valeur propre de Q, ie $\exists V ,\; QV = V$, soit $(Q - I_N)V = 0$

D'après moi, comme on a $Q^t U = U \Leftrightarrow (Q^t - I_N) U =0$, $Q^t - I_N$ n'est pas inversible car sinon on aurait $U=0$ d'où $Q - I_N$ non-inversible.
Mais maintenant je bloque, comment en déduire que 1 est VP de Q ?

Re: Google et les maths

MessagePosté: Dimanche 03 Août 2008, 14:14
par Arnaud
Si $Q-I$ n'est pas inversible, ce n'est pas injectif ( dimension finie ), donc il existe $U'$ tel que $(Q-I)U'=0$.

Re: Google et les maths

MessagePosté: Mardi 12 Août 2008, 20:36
par surjay
Merci Arnaud, j'ai terminé le 1er sujet :)

Pour l'exemple du second sujet, je trouve : 8 > 9 > 7 > 6 > 5 > 4 > 2 > 3 > 10 > 1
Vous confirmez, OG ?

Sinon, dans le texte il est donné $N=10^{10}$ pour la taille de la matrice.
Il s'agit sans doute du nombre de pages du web tout entier (cf cuil).
Mais pour une recherche classique, le nombre de pages considérées est probablement moindre (15 millions pour "mathématiques") et demande d'autant moins de calculs (même si 15 millions c'est toujours énorme).

Qu'en pensez vous ?

Re: Google et les maths

MessagePosté: Mardi 26 Août 2008, 09:15
par OG
vbnul a écrit:Pour l'exemple du second sujet, je trouve : 8 > 9 > 7 > 6 > 5 > 4 > 2 > 3 > 10 > 1
Vous confirmez, OG ?


J'avais la matrice en fichier Scilab sur mon PC !
Je trouve la même chose.
Par contre dans mon mail la dernière phrase est à oublier.
Effectivement il n'y a qu'un seul couple valeur propre/vector propre à calculer et correspond à la valeur propre de plus grand module.
As-tu implémenté la méthode de la puissance histoire de voir ? Et le texte ?

vbnul a écrit:Sinon, dans le texte il est donné $N=10^{10}$ pour la taille de la matrice.
Il s'agit sans doute du nombre de pages du web tout entier (cf cuil).
Mais pour une recherche classique, le nombre de pages considérées est probablement moindre (15 millions pour "mathématiques") et demande d'autant moins de calculs (même si 15 millions c'est toujours énorme).

Qu'en pensez vous ?


Tous les algorithmes de Google ne sont pas publics. Il y a nécessairement un traitement en amont (ne considérer que les pages avec le mot mathématiques et donc diminuer la taille de la matrice) ou en aval. Dans tous les cas la taille des objets est énorme et les algos sont optimisés. La moindre optimisation a un impact énorme.

Cordialement
O.G.

Re: Google et les maths

MessagePosté: Mardi 26 Août 2008, 20:19
par surjay
Je ne suis pas allé jusqu'à utiliser la matrice creuse, peut être plus tard.
Remarquez, l'implémentation ne doit pas être très différente de celle avec la matrice pleine une fois qu'on a les bons outils.

Il y a en effet bien moins de $10^{10}$ pages à considérer dans l'algorithme, contrairement à ce que les deux textes ci dessus laissent entendre.
Pour ceux qui sont curieux de ce genre de détails, M. Eisermann a écrit un très bon texte sur le sujet, à la fois vulgarisé et détaillé mathématiquement.

Re: Google et les maths

MessagePosté: Mercredi 27 Août 2008, 10:21
par masiuxus
Très bon article ! Voir que les math permettent de faire ça fait plaisir : au moins, on pourra dire aux élèves que les maths peuvent rendre riche (vu qu'il n'y a que ça qui les intéresse ...)

Re: Google et les maths

MessagePosté: Mercredi 27 Août 2008, 15:09
par surjay
Pour devenir riche, ils peuvent aussi casser le RSA et vendre le secret à la NSA.

masiuxus a écrit:vu qu'il n'y a que ça qui les intéresse ...

Maaaiiis non, y'a aussi l'alcool et le sexe :bomb: