Google et les maths

Discussions générales concernant les mathématiques.
[forum modéré par les modérateurs globaux du site]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
guiguiche
Modérateur global
Modérateur global
Messages : 8074
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Google et les maths

Message 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).
Vous ne pouvez pas consulter les pièces jointes insérées à ce message.
Pas d'aide par MP : les questions sont publiques, les réponses aussi.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.

OG
Modérateur
Modérateur
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Google et les maths

Message 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.

surjay
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 153
Inscription : jeudi 27 décembre 2007, 16:37

Re: Google et les maths

Message 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 ?

Arnaud
Modérateur global
Modérateur global
Messages : 7095
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne

Re: Google et les maths

Message 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$.
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)

surjay
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 153
Inscription : jeudi 27 décembre 2007, 16:37

Re: Google et les maths

Message 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 ?

OG
Modérateur
Modérateur
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Google et les maths

Message 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.

surjay
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 153
Inscription : jeudi 27 décembre 2007, 16:37

Re: Google et les maths

Message 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.

masiuxus

Re: Google et les maths

Message 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 ...)

surjay
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 153
Inscription : jeudi 27 décembre 2007, 16:37

Re: Google et les maths

Message 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: