Autoévaluation |
 |
Question 1
Vous travaillez dans un centre d’astronomie. Vous avez une énorme base de données contenant des étoiles et leur classification. Comment calculeriez-vous le nombre d’étoiles par type en utilisant la méthodologie « MapReduce » ?
Question 2
Calculez le graphe d’adjacence pour le graphe de « de Bruijn » sur les trigrammes ABB, BCB, BBC,DDD. (Pour un rappel sur le graphe de « de Bruijn », voir l’article d’introduction aux graphes dirigés.)
![\left [ \begin{array}{llll}
0 & 0 & 1 & 0\\
0 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1
\end{array} \right ].](local/cache-TeX/af74de75f51ec713ebeae12580fcc5ac.png "\left [ \begin{array}{llll}
0 & 0 & 1 & 0\\
0 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1
\end{array} \right ].")
Question 3
Sans utiliser une calculatrice ou un ordinateur, calculez la matrice suivante :
![\left [ \begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array} \right ]^{16}.](local/cache-TeX/2d513aa856a6d1eb6a79d7532ebb2ad6.png "\left [ \begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array} \right ]^{16}.")
Indice : cela se fait en moins de 30 secondes.
![T= \left [ \begin{array}{lll}
0 & 0 & 1 \\
1& 0 & 0 \\
0 & 1 & 0
\end{array} \right ]](local/cache-TeX/1bde8ccd855b738aa7148d227c13fa7f.png "T= \left [ \begin{array}{lll}
0 & 0 & 1 \\
1& 0 & 0 \\
0 & 1 & 0
\end{array} \right ]")
. Nous avons 
, 
, 
et 
. Ainsi, nous avons
![T^2= \left [ \begin{array}{lll}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{array} \right ]](local/cache-TeX/297132f8abed2a038f597368cea9d29d.png "T^2= \left [ \begin{array}{lll}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{array} \right ]")
et
![T^{4}= \left [ \begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array} \right ]](local/cache-TeX/68028db55dcdcea44181dc9872d22241.png "T^{4}= \left [ \begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array} \right ]")
et
![T^{8}= \left [ \begin{array}{lll}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{array} \right ]](local/cache-TeX/46c0cbdaf3007562ef99d1bebe78b475.png "T^{8}= \left [ \begin{array}{lll}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{array} \right ]")
et
![T^{16}= \left [ \begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array} \right ].](local/cache-TeX/001bbeff857d55fada919e5875520d3e.png "T^{16}= \left [ \begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array} \right ].")
Question 4
Soit un « web » constitué de deux pages web. L’une fait un lien vers l’autre qui ne contient aucun lien. Écrivez la matrice de transition de l’algorithme PageRank simplifié. Est-ce que la matrice de transition est régulière ? Est-elle ergodique ?
![\left [ \begin{array}{ll}
0 & 1 \\
\frac{1}{2}& \frac{1}{2}
\end{array} \right ]](local/cache-TeX/4dafc0273d6b11e13bceae6d9d523ad3.png "\left [ \begin{array}{ll}
0 & 1 \\
\frac{1}{2}& \frac{1}{2}
\end{array} \right ]")
.
Elle est ergodique, mais non régulière (un zéro apparaît !).
Question 5
Soit deux pages web. L’une fait un lien vers l’autre qui ne contient aucun lien. Écrivez la matrice de transition de l’algorithme PageRank non simplifié. La matrice de transition est-elle régulière ? Est-elle ergodique ?
![\left [ \begin{array}{ll}
\frac{1-q}{2} & \frac{q+1}{2} \\
\frac{1}{2}& \frac{1}{2}
\end{array} \right ]](local/cache-TeX/bcb4e60cb9c5c970054b2c2ae1c792b3.png "\left [ \begin{array}{ll}
\frac{1-q}{2} & \frac{q+1}{2} \\
\frac{1}{2}& \frac{1}{2}
\end{array} \right ]")
où 
.
La matrice est régulière et donc ergodique, comme c’est toujours le cas avec l’algorithme PageRank non simplifié.
Question 6
Soit deux pages web. L’une fait un lien vers l’autre qui ne contient aucun lien. Calculez le PageRank de chaque page en utilisant l’algorithme PageRank non simplifié. Êtes-vous surpris du résultat ?
![T=\left [ \begin{array}{ll}
\frac{1-q}{2} & \frac{q+1}{2} \\
\frac{1}{2}& \frac{1}{2}
\end{array} \right ]](local/cache-TeX/c673178f280a63305d1cfcb0bc427165.png "T=\left [ \begin{array}{ll}
\frac{1-q}{2} & \frac{q+1}{2} \\
\frac{1}{2}& \frac{1}{2}
\end{array} \right ]")
où ![T^{16}=\left [ \begin{array}{ll}
\approx 0.35 & \approx 0.65 \\
\approx 0.35 & \approx 0.65
\end{array} \right ]](local/cache-TeX/d269afdd3ea5204dd9aba70d5c9e23fa.png "T^{16}=\left [ \begin{array}{ll}
\approx 0.35 & \approx 0.65 \\
\approx 0.35 & \approx 0.65
\end{array} \right ]")
. Le PageRank de la première page est donc 0.35 alors que le PageRank de la seconde page est 0.65. Le résultat n’est pas surprenant : une page fait un lien vers l’autre, ce qui nous porte à penser que la seconde page est plus importante.
Question 7
Un expert en optimisation de sites web suggère à votre patron de minimiser le nombre de liens contenus dans votre site pour améliorer le facteur PageRank de votre site web. Commentez votre réponse.
Question 8
Une page web A pointe vers une seule page web (B). La page web B ne compte aucun lien. La page web C pointe vers la page web A.
Calculez le PageRank de chaque page en utilisant l’algorithme PageRank simplifié.
![T= \left [ \begin{array}{lll}
0 & 1 & 0 \\
1/3 & 1/3 & 1/3 \\
1 & 0 & 0
\end{array} \right ].](local/cache-TeX/098abc036a5cdf634786e3f19f04cd44.png "T= \left [ \begin{array}{lll}
0 & 1 & 0 \\
1/3 & 1/3 & 1/3 \\
1 & 0 & 0
\end{array} \right ].")
