\documentclass[10pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc}%ATTENTION codage en utf8 ! \usepackage{fourier} \usepackage[scaled=0.875]{helvet} \renewcommand{\ttdefault}{lmtt} \usepackage{amsmath,amssymb,makeidx,stmaryrd} \usepackage[normalem]{ulem} \usepackage{fancybox} \usepackage{tabularx} \usepackage{ulem} \usepackage{dcolumn} \usepackage{textcomp} \usepackage{stmaryrd} \usepackage{lscape} \newcommand{\euro}{\eurologo{}} \usepackage[dvips]{color} \usepackage{pstricks,pst-plot,pst-text,pst-tree,pstricks-add} \usepackage[left=3.5cm, right=3.5cm, top=2cm, bottom=3cm]{geometry} \newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\D}{\mathbb{D}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \renewcommand{\theenumi}{\textbf{\arabic{enumi}}} \renewcommand{\labelenumi}{\textbf{\theenumi.}} \renewcommand{\theenumii}{\textbf{\alph{enumii}}} \renewcommand{\labelenumii}{\textbf{\theenumii.}} \def\Oij{$\left(\text{O},~\vect{\imath},~\vect{\jmath}\right)$} \def\Oijk{$\left(\text{O},~\vect{\imath},~\vect{\jmath},~\vect{k}\right)$} \def\Ouv{$\left(\text{O},~\vect{u},~\vect{v}\right)$} \usepackage{fancyhdr} \usepackage{hyperref} \hypersetup{% pdfauthor = {APMEP}, pdfsubject = {CAPES 2016 }, pdftitle = {Épreuve 4 avril 2017}, allbordercolors = white, pdfstartview=FitH} \usepackage[french]{babel} \usepackage[np]{numprint} \begin{document} \setlength\parindent{0mm} \rhead{\textbf{A. P{}. M. E. P{}.}} \lhead{\small} \lfoot{\small{CAPES externe 4 avril 2017}} \rfoot{\small{}} \pagestyle{fancy} \thispagestyle{empty} \marginpar{\rotatebox{90}{\textbf{A. P. M. E. P.}}} \begin{center} {\Large \textbf{\decofourleft~CAPES Concours externe et CAFEP session 2017~\decofourright\\[7pt] Épreuve 2}} \vspace{0,5cm} Cette épreuve est constituée de deux problèmes indépendants \bigskip {\Large \textbf{Problème \no 1 }} \end{center} Notations \medskip $\N$ désigne l'ensemble des entiers naturels et $\R$ l'ensemble des nombres réels. On considère le quart de cercle unité du plan usuel, représenté sur la figure ci-dessous : \begin{center} \psset{unit=4cm} \begin{pspicture}(-0.1,-0.1)(1.1,1.1) \psaxes[linewidth=1.25pt]{->}(0,0)(-0.1,-0.1)(1.1,1.1) \psarc(0,0){1}{0}{90} \end{pspicture} \end{center} \textbf{I.} Quelle est l'aire $\mathcal{A}$ du quart de disque $D$ délimité par les deux axes de coordonnées et ce quart de cercle ? \textbf{II.} Montrer que cette aire est également la valeur de l'intégrale \[\displaystyle\int_0^1 \sqrt{1 - x^2}\:\text{d}x.\] Par la suite, on considère la fonction \[\phi : \left\{\begin{array}{l c l} [0~;~1]&\to &\R\\ x&\mapsto & \sqrt{1 - x^2} \end{array}\right.\] \textbf{III.} On s'intéresse tout d'abord à une évaluation de $\mathcal{A}$ grâce à la \emph{méthode des rectangles}. \begin{center} \psset{unit=4cm,comma=true} \begin{pspicture}(-0.1,-0.1)(1.1,1.1) \psaxes[linewidth=1.25pt,Dx=0.2,Dy=0.2]{->}(0,0)(-0.05,-0.05)(1.1,1.1) \psaxes[linewidth=1.25pt,Dx=0.2,Dy=0.2](0,0)(0,0)(1.1,1.1) \multido{\nx=0.0+0.1}{10}{\psframe[linewidth=0.2pt](\nx,0)(! \nx \space 0.1 add \nx \space dup mul neg 1 add sqrt)} \multido{\nx=0.1+0.1}{9}{\psframe[linewidth=0.2pt](\nx,0)(! \nx \space 0.1 add \nx \space 0.1 add dup mul neg 1 add sqrt)} \multido{\nx=0.1+0.1}{9}{\psframe[fillstyle=solid,fillcolor=lightgray](! \nx \space 0 add \nx \space 0.1 add dup mul neg 1 add sqrt) (! \nx \space 0.1 add \nx \space dup mul neg 1 add sqrt)} \psarc(0,0){1}{0}{90} \end{pspicture} \end{center} On fixe un entier naturel $n \geqslant 2$. On introduit une subdivision \[0 = x_0 < x_1 < \ldots < x_n = 1\] à pas constant de l'intervalle [0~;~1], c'est-à-dire que : \[\forall i \in \llbracket 0~;~n\rrbracket,\: x_i = \dfrac{i}{n}.\] Pour $i \in \llbracket 0~;~n\rrbracket$, on considère les points $A_i\left(x_i,\:\phi\left(x_i\right)\right)$ et, pour $i \in \llbracket 0~;~n - 1\rrbracket$, on construit sur chaque intervalle $\left[x_i~;~x_{i+1}\right]$ le rectangle \emph{au-dessous de la courbe} de sommets \[\left(x_i~;~0\right), \qquad \left(x_{i+1}~;~0\right), \qquad \left(x_{i+1}~;~\phi\left(x_{i + 1} \right)\right), \qquad \left(x_{i}~;~\phi\left(x_{i + 1} \right)\right)\] et le rectangle au-dessus de la courbe de sommets \[\left(x_i~;~0\right), \qquad \left(x_{i+1}~;~0\right), \qquad \left(x_{i+1}~;~\phi\left(x_{i} \right)\right), \qquad \left(x_{i}~;~\phi\left(x_{i} \right)\right)\] On a représenté ces rectangles pour $n = 10$ sur la figure ci-dessus. La différence ensembliste de ces rectangles a été grisée. On note $\breve{s}(n)$ la somme des aires des rectangles au-dessous la courbe et $\hat{s}(n)$ la somme des aires des rectangles au-dessus de la courbe. \medskip \begin{enumerate} \item Un élève de terminale scientifique affirme à propos de cette méthode: \og Plus le nombre de rectangles augmente, plus les sommets des rectangles se rapprochent de la courbe, donc la somme des aires des rectangles tend vers $\mathcal{A}$ \fg. Que répondez-vous à cet élève ? \item Montrer que pour tout entier naturel $n \geqslant 2$, \[\breve{s}(n) = \dfrac{1}{n} \displaystyle\sum_{i=1}^{n} \phi\left(x_i\right) \leqslant \mathcal{A} \leqslant \hat{s}(n) = \displaystyle\sum_{i=0}^{n-1} \phi\left(x_i\right).\] \item Montrer que la somme des aires des rectangles grisés sur la figure précédente est \[\hat{s}(n) - \breve{s}(n) = \dfrac{1}{n}.\] \item Déterminer un entier $N$ tel que, pour $n \geqslant N$, on ait $\left|\mathcal{A} - \hat{s}(n)\right| \leqslant 10^{-3}$. \item Représenter sur une même figure $\hat{s}(2),\: \breve{s}(2), \hat{s}(4)$ et $\breve{s}(4)$. Comparer $\hat{s}(2)$ et $\hat{s}(4)$, puis $\breve{s}(2)$ et $\breve{s}(4)$. \item Montrer que les suites de terme général $\hat{s}(2n)$ et $\breve{s}(2n)$ sont adjacentes. \item En quoi ce résultat peut-il vous aider à répondre à l'élève de la question 1 ? \item Écrire un algorithme de calcul de $\hat{s}(n)$. \end{enumerate} \textbf{IV.} On s'intéresse ici à une évaluation de $\mathcal{A}$ grâce à la méthode dite \emph{méthode des trapèzes}. Pour tout entier naturel $n \geqslant 2$, on note \[s(n) = \dfrac{\hat{s}(n) + \breve{s}(n)}{2}.\] \medskip \begin{enumerate} \item Justifier le nom de \emph{méthode des trapèzes}. On représentera $s(4)$ sur une figure. \item Montrer que pour tout entier naturel $n \geqslant 2$,\: $\breve{s}(n) \leqslant s s(n) \leqslant \hat{s}(n)$. \item Indiquer laquelle des trois valeurs $\hat{s}(n), \breve{s}(n)$ ou $s(n)$ est la meilleure approximation de $\mathcal{A}$. \end{enumerate} \textbf{V.} On s'intéresse maintenant à une autre méthode, appelée \emph{méthode de Monte-Carlo}. Il s'agit de tirer aléatoirement un point du carré unité de façon uniforme et de calculer la fréquence des points qui sont dans le quart de disque $D$. \begin{center} \psset{unit=4cm} \begin{pspicture}(-0.1,-0.1)(1.1,1.1) \psaxes[linewidth=1.25pt]{->}(0,0)(-0.1,-0.1)(1.1,1.1) \psarc(0,0){1}{0}{90} \psframe(1,1) \psdots[dotscale=0.7](0.14,0.04)(0.12,0.21)(0.09,0.33)(0.14,0.45)(0.17,0.56)(0.08,0.67)(0.12,0.78)(0.15,0.8)(0.18,0.95)(0.24,0.17)(0.22,0.08)(0.19,0.37)(0.24,0.41)(0.27,0.52)(0.18,0.63)(0.22,0.72)(0.25,0.89)(0.28,0.96)(0.34,0.17)(0.32,0.28)(0.29,0.07)(0.34,0.42)(0.37,0.51)(0.28,0.68)(0.32,0.70)(0.35,0.89)(0.38,0.96)(0.44,0.15)(0.42,0.23)(0.39,0.33)(0.44,0.11)(0.47,0.53)(0.38,0.62)(0.42,0.78)(0.45,0.89)(0.48,0.96)(0.64,0.13)(0.62,0.25)(0.59,0.35)(0.64,0.46)(0.67,0.55)(0.58,0.64)(0.62,0.76)(0.65,0.89)(0.68,0.96)(0.84,0.12)(0.82,0.27)(0.79,0.37)(0.84,0.48)(0.87,0.57)(0.58,0.66)(0.82,0.74)(0.85,0.89)(0.88,0.96) \end{pspicture} \end{center} On admet que la probabilité qu'un point tiré de cette manière soit dans le quart de disque est égale à $\mathcal{A}$. \medskip \begin{enumerate} \item Soit $M(x~;~y)$ un point du carré $[0~;~1]^2$. Montrer que ce point est dans le quart de disque dont on cherche à mesurer l'aire si, et seulement si, $x^2 + y^2 \leqslant 1$. \item On dispose de la fonction (sans argument) \textbf{alea}, qui renvoie à chaque appel un nombre réel tiré au hasard uniformément dans l'intervalle [0~;~1]. Écrire un algorithme qui simule un tirage aléatoire de $N$ points du carré unité et calcule la fréquence $f$ des points figurant dans le quart de disque $D$. \item $f$ étant la fréquence obtenue lors d'un tirage aléatoire de $N$ points du carré unité, déterminer un intervalle de confiance de $\mathcal{A}$ au niveau de confiance 95\,\%. \item En déduire le nombre $N$ de tirages à effectuer pour obtenir, au niveau de confiance 95\,\%, une estimation de $\mathcal{A}$ avec une précision égale à $10^{-3}$. \item Comparer ce résultat avec celui de la question \textbf{III. 4.} \end{enumerate} \begin{center} {\large \textbf{Problème \no 2}} \end{center} Notations $\N$ désigne l'ensemble des entiers naturels et $\R$ l'ensemble des nombres réels. Pour $m$ et $n$ deux entiers naturels, $\llbracket m,~ n \rrbracket$ désigne l'ensemble des entiers $k$ tels que $m \leqslant k \leqslant n$. Pour $n$ un entier naturel non nul, $\mathcal{M}_n(\R)$ désigne l'ensemble des matrices à $n$ lignes et $n$ colonnes, à coefficients réels. On note $I_n$ la matrice identité d'ordre $n$. Le module d'un nombre complexe $z$ est noté $|z|$. \bigskip \textbf{Définitions} \medskip Soit $\left(X^{(k)}\right)_{k\geqslant 0}$ une suite de vecteurs de $\R^n$ et $X = \left(x_1,\: ... , x_n\right)$ un vecteur de $\R^n$. Pour tout entier naturel $k$, on pose $X^{(k)} = \left(x_1^{(k)}, ... , x_n^{(k)}\right)$. On dit que la suite $\left(X^{(k)}\right)_{k\geqslant 0}$ converge vers $X$ si pour tout $i \in \llbracket 1~;~n\rrbracket$, la suite $\left(x_i^{(k)}\right)_{k\geqslant 0}$ converge vers $x_i$. Soit $\left(A^{(k)}\right)_{k\geqslant 0}$ une suite de matrices de $M_n(\R)$ et $A = \left(a_{i,j}\right)_{1\leqslant i,j\leqslant n}$ une matrice de $M_n(\R)$. Pour tout entier naturel $k$, on pose $A^{(k)} = \left(a_{i,j}^{(k)}\right)_{1\leqslant i,j \leqslant n}$. On dit que la suite $\left(A^{(k)}\right)_{k\geqslant 0}$ converge vers $A$ si pour tous $i,j \in \llbracket 1~;~n\rrbracket$, la suite $\left(a_{i,j}^{(k)}\right)_{k\geqslant 0}$ converge vers $a_{i,j}$. Soit $G$ un graphe orienté fini et soient $i$ et $j$ deux sommets de ce graphe. On dit que $j$ est un sommet voisin de $i$ s'il existe une arête orientée de $G$ reliant $i$ à $j$. \newpage \begin{center} {\large \textbf{Partie A : marche aléatoire sur un graphe}} \end{center} On considère un graphe orienté fini dont les sommets sont numérotés de 1 à $n$. Un point se déplace aléatoirement d'un sommet à un autre de ce graphe au cours d'étapes, le nombre d'étapes pouvant tendre vers l'infini. À chaque étape, le point se déplace du sommet où il se trouve vers l'un des sommets voisins de façon équiprobable. Ceci entraîne notamment que la probabilité de passer du sommet $i$ au sommet $j$ ne dépend pas du rang de l'étape. Pour $1 \leqslant i,\: j \leqslant n$, on note $a_{i,j}$, la probabilité que le point passe du sommet $i$ au sommet $j$ ; en particulier, s'il n'y a pas d'arête reliant $i$ à $j$,\: $a_{i,j} = 0$. La matrice dont le coefficient de la ligne $i$ et de la colonne $j$ est égal à $a_{i,j}$ est notée $A$. Cette matrice s'appelle la \emph{matrice de transition} du graphe. Pour $k \in \N$, on note $P^{(k)}$ le vecteur ligne $\left(p_1^{(k)},\:p_2^{(k)}, ... , p_{n-1}^{(k)},\: p_n^{(k)}\right)$, où pour $1 \leqslant i \leqslant n$,\: $p_ik^{(p)}$ est la probabilité que le point soit sur le sommet $i$ à l'étape de rang $k$. \medskip \textbf{I. }Résultats généraux \medskip \begin{enumerate} \item Justifier que, pour tout entier naturel $k$,\: $p_1^{(k)} + \ldots + p_n^{(k)} = 1$. \item Montrer que, pour tout tout entier naturel $k$, $P^{(k+1)} = P^{(k)} A$. \item En déduire, pour tout entier naturel $k$, une expression de $P^{(k)}$ en fonction de $A$, $k$ et $P^{(0)}$. \item On suppose que la suite de vecteurs $\left(P^{(k)}\right)_{k\geqslant 0}$ converge vers un vecteur $P = \left(p_1, \ldots ,p_n\right)$. Montrer que $PA = P$ et que $p_1 + \ldots + p_n = 1$. \end{enumerate} \medskip \textbf{II. Marche aléatoire sur un tétraèdre} \medskip Dans cette question, on suppose que G est le graphe ci-dessous: \begin{center} \psset{unit=0.8cm} \begin{pspicture}(5,5) \cnodeput(2.5,4.5){C}{1} \cnodeput(0.5,0.5){A}{2}\cnodeput(4.5,0.5){B}{3}\cnodeput(2.5,2){D}{4} \ncline{<->}{A}{C}\ncline{<->}{A}{D}\ncline{<->}{A}{B} \ncline{<->}{B}{D}\ncline{<->}{B}{C}\ncline{<->}{C}{D} \end{pspicture} \end{center} On remarque que, lorsque le point est sur l'un des sommets du graphe, il a la même probabilité de se rendre sur chacun des trois autres sommets du graphe. On suppose qu'au départ, le point est sur le sommet 1, de sorte que : \[P^{(0)} = \begin{pmatrix}1 &0 &0 &0\end{pmatrix}.\] On pose: \[U = \begin{pmatrix}0&1&1& 1 \\1& 0& 1&1\\1 &1& 0& 1\\ 1 &1& 1& 0\end{pmatrix}.\] \medskip \begin{enumerate} \item Exprimer la matrice de transition $A$ en fonction de $U$. \item Calculer $U^2$ et $U3$. \item Montrer qu'il existe deux suites $\left(\alpha_k\right)_{k\geqslant 0}$ et $\left(\beta_k\right)_{k\geqslant 0}$ telles que pour tout entier naturel $k$ : \[U^k = \begin{pmatrix}\alpha_k&\beta_k&\beta_k&\beta_k\\\beta_k&\alpha_k&\beta_k&\beta_k\\\beta_k&\beta_k&\alpha_k&\beta_k\\\beta_k&\beta_k&\beta_k&\alpha_k\end{pmatrix}.\] Montrer de plus que, pour tout entier naturel $k$, \[\left\{\begin{array}{l c l} \alpha_{k+1} &=&3\beta_k\\ \beta_{k+1} &=& \alpha_k + 2\beta_k \end{array}\right.\] \item En déduire que, pour tout entier naturel $k$, $\beta_{k+2} = 2\beta_{k+1} + 3\beta_k$. \item En déduire que, pour tout entier naturel $k$, \[\beta_k = \dfrac{3^k - (- 1)^k}{4}\quad \text{et}\quad \alpha_k = \dfrac{3^k + 3(- 1)^k}{4}.\] \item En déduire pour tout entier naturel $k$ une expression de $P^{(k)}$. \item Montrer que la suite de vecteurs $\left(P^{(k)}\right)_{k\geqslant 0}$ converge et déterminer la limite de $P^{(k)}$ lorsque $k$ tend vers $+ \infty$. \end{enumerate} \textbf{III. Marche aléatoire sur une pyramide tronquée à base carrée} \medskip Dans cette question, on suppose que $G$ est le graphe ci-dessous: \begin{center} \psset{unit=0.8cm} \begin{pspicture}(5,5) \cnodeput(0.5,4.5){A}{1} \cnodeput(4.5,4.5){B}{2}\cnodeput(4.5,0.5){C}{3}\cnodeput(0.5,0.5){D}{4} \cnodeput(1.5,3.5){E}{5}\cnodeput(3.5,3.5){F}{6}\cnodeput(3.5,1.5){G}{7} \cnodeput(1.5,1.5){H}{8} \ncline{<->}{A}{B}\ncline{<->}{B}{C}\ncline{<->}{C}{D} \ncline{<->}{A}{D}\ncline{<->}{E}{F}\ncline{<->}{F}{G} \ncline{<->}{H}{G}\ncline{<->}{E}{H} \ncline{<->}{A}{E}\ncline{<->}{F}{B}\ncline{<->}{C}{G}\ncline{<->}{D}{H} \end{pspicture} \end{center} On rappelle que, lorsque le point est sur l'un des sommets du graphe, il a la même probabilité de se rendre sur chacun des sommets à qui il est relié. On suppose qu'au départ, le point est sur le sommet 1, de sorte que: \[P^{(0)} = \begin{pmatrix}1& 0& 0& 0& 0& 0 &0 &0\end{pmatrix}.\] On note $X = \{1, 3, 6, 8\}$ et $Y = \{2, 4, 5, 7\}$. \medskip \begin{enumerate} \item Donner la matrice de transition $A$ de ce graphe et calculer \[\begin{pmatrix}1& 1& 1& 1& 1& 1 &1 &1\end{pmatrix}A.\] \item Montrer que si le point se trouve sur un sommet de la partie $X$ à une étape donnée, il se trouvera sur un sommet de $Y$ à l'étape suivante, et que s'il se trouve sur un sommet de $Y$ à une étape donnée, il se trouvera sur un sommet de $X$ à l'étape suivante. \item \begin{enumerate} \item Démontrer que les coefficients de $P^{(k)}$ dont les indices sont des éléments de $X$ sont nuls si $k$ est impair, et que les coefficients de $P^{(k)}$ dont les indices sont des éléments de $Y$ sont nuls si $k$ est pair. \item La suite de vecteurs $\left(P^{(k)}\right)_{k\geqslant 0}$ converge t-elle ? \end{enumerate} \end{enumerate} \medskip \textbf{IV.} On revient au cas général d'un graphe $G$ à $n$ sommets. Parmi les trois liens logiques condition nécessaire, condition suffisante et condition nécessaire et suffisante, quel est celui qui relie les deux propositions suivantes ? (i) la suite de vecteurs $\left(P^{(k)}\right)_{k\geqslant 0}$ converge ; (ii) il existe un vecteur $P = \left(p_1, \ldots , p_n\right)$ de $\R^n$, avec $p_1, \ldots ,p_n$ positifs ou nuls et $p_1 + \ldots + p_n = 1$, tel que $PA = P$. \smallskip La réponse, qui devra être soigneusement justifiée, sera présentée sous deux formes : une phrase rédigée en français et une proposition mathématique comportant une implication ou une équivalence. \bigskip {\large \textbf{Partie B matrices stochastiques et densités de probabilité}} \medskip \textbf{Définitions} \medskip Soit $X = \left(x_1, \ldots ,x_n \right)$ un vecteur de $\R^n$. On dit que $X$ est une densité de probabilité si pour tout $i \in \llbracket 1,~ n\rrbracket,\: x_i \geqslant 0$ et $x_1 + \ldots + x_n = 1$. Soit $A$ une matrice de $M_n(\R)$. On dit que $A$ est une matrice stochastique si chaque ligne de $A$ est une densité de probabilité. \medskip \textbf{I.}. Soit $A \in M_n(\R)$, dont tous les coefficients sont positifs ou nuls. Montrer que $A$ est une matrice stochastique si et seulement si \[A\begin{pmatrix}1\\\vdots\\1\end{pmatrix} = \begin{pmatrix}1\\\vdots\\1\end{pmatrix}.\] \textbf{II.} Montrer que la matrice de transition d'un graphe (définie dans la partie A.) est une matrice stochastique et que, pour tout entier naturel $k$, le vecteur $P^{(k)}$, lui aussi défini dans la partie A., est une densité de probabilité. \textbf{III.} Soit $A \in M_n(\R)$ une matrice stochastique et $X \in \R^n$ une densité de probabilité. Montrer que $XA$ est une densité de probabilité. \textbf{IV.} Soient $A$ et $B$ deux matrices stochastiques de $M_n(\R)$. \medskip \begin{enumerate} \item Montrer que $AB$ est une matrice stochastique. \item Soit $\alpha \in [0~;~1]$. Montrer que $\alpha A + (1 - \alpha)B$ est une matrice stochastique. \end{enumerate} \textbf{V.} Soit $\left(X^{(k)}\right)_{k\geqslant 0}$ une suite de vecteurs de $\R^n$, convergeant vers un vecteur $X$. Montrer que, si pour tout entier naturel $k,\: X^{(k)}$ est une densité de probabilité, alors $X$ est une densité de probabilité. \textbf{VI.} Soit $\left(A^{(k)}\right)_{k\geqslant 0}$ une suite de matrices de $M_n (\R)$, convergeant vers une matrice $A$. Montrer que, si pour tout entier naturel $k,\ A^{(k)}$ est une matrice stochastique, alors $A$ est une matrice stochastique. \bigskip {\large \textbf{Partie C PageRank, un premier modèle}} \medskip Le moteur de recherche Google annonce environ \np{339000} résultats à la requête \og capes mathématiques\fg. Sur la première page de résultats, il classe en premier le site \texttt{capes-math.org}, puis le site \texttt{www.devenirenseignant.gouv.fr}. Le succès de ce moteur de recherche tient à sa rapidité, son exhaustivité et la qualité du classement qu'il effectue entre les différentes pages, à partir d'une \og mesure d'importance\fg{} attribuée à chacune. Cette mesure d'importance d'une page s'appelle sa pertinence. On se propose d'étudier deux algorithmes permettant de déterminer la pertinence de chaque page du web. Le second algorithme, connu sous le nom de \emph{PageRank}, a été inventé par Sergey Brin et Larry Page. \smallskip Le mot \og PageRank\fg{} lui-même est une marque déposée par Google. Le procédé a été breveté par l'université de Stanford qui en a accordé une licence exclusive à Google. On modélise le web par un graphe orienté à $n$ sommets représentant chacun une page et dont les arêtes représentent les liens entre celles-ci (liens hypertextes, citations d'articles, etc.) ; la notation $i \to j$ traduit le fait que la page $i$ pointe vers la page $j$. Pour tout entier $i \in \llbracket 1,~ n\rrbracket$, $\lambda_i$ désigne le nombre de liens issus de la page $i$ et $\mu_i$ désigne la pertinence de cette page. On impose à la suite $\left(\mu_j \right)_{1\leqslant j \leqslant n}$ des pertinences des pages du web de vérifier les deux conditions suivantes : \smallskip (i) la pertinence d'une page dépend des pertinences des pages qui pointent vers elle de manière affine ; (ii) plus il y a de liens issus d'une page, plus la contribution de cette page dans la pertinence des pages vers lesquelles elle pointe est faible. \medskip \textbf{I.} Montrer que toute suite $\left(\mu_j \right)_{1\leqslant j \leqslant n}$ de nombres réels positifs ou nuls satisfaisant aux $n$ conditions \[(*)\qquad \forall j \in \llbracket 1,~ n\rrbracket,\:\mu_j = \sum_{i\to j} \dfrac{1}{\lambda_i} \mu_i.\] vérifie les conditions (i) et (ii). Toute solution $\left(\mu_j\right)_{1\leqslant j\leqslant n}$ du système linéaire $(*)$ formée de réels positifs ou nuls fournit les pertinences des $n$ pages du web. Dans la pratique, la résolution de ce système est impossible, le nombre $n$ de pages du web étant beaucoup trop élevé. Pour cette raison, on cherche une autre méthode pour obtenir les pertinences. \textbf{II.} Soient $i,j \in \llbracket 1,~ n\rrbracket$. \begin{itemize} \item Si $i \ne j$, on pose \[a_{i, j} = \left\{\begin{array}{l l} 0&\text{s'il n'y a pas de lien de la page }\:i \:\text{vers la page }\:j ;\\ \frac{1}{\lambda_i}&\text{si}\: i \to j. \end{array}\right.\] \item Si $i = j$, dans le cas où il n'y a aucun lien qui permette de sortir de la page $i$, on convient d'écrire $a_{i,i} = 1$, pour indiquer que si on arrive sur cette page, on y reste ; sinon, on note $a_{i, i} = 0$. \end{itemize} Pour $1 \leqslant i, j \leqslant n$, le coefficient $a_{i,j}$ peut s'interpréter comme la probabilité qu'une personne navigant sur le web et se trouvant sur la page $i$ suive le lien vers la page $j$ en choisissant au hasard entre les $\lambda_i$ liens disponibles à partir de la page $i$ s'il y en a et reste sur la page $i$ sinon. Soit $A$ la matrice de $M_n(\R)$ dont le coefficient de la ligne $i$ et de la colonne $j$ est $a_{i, j}$. Montrer que $A$ est une matrice stochastique. \textbf{III.} Montrer que la suite finie $\left(\mu_j\right)_{1\leqslant j \leqslant n}$ vérifie les conditions (*) introduites à la question 1. si et seulement si la matrice ligne $M = \left(\mu_1,~\mu_2, \ldots,\:\mu_n\right)$ vérifie $M = MA$. \textbf{IV.} On note dans la suite $\left(P^{(k)}\right)_{k \geqslant 0}$ la densité de probabilité après $k$ clics : le coefficient d'indice $i$ de la matrice ligne $P^{(k)}$ est la probabilité que le \og surfeur\fg se trouve sur la page $i$ après $k$ clics. \medskip \begin{enumerate} \item Vérifier que pour tout entier naturel $k$,\: $P^{(k+1)} = P^{(k)} A$. \item Montrer que si la suite $\left(P^{(k)}\right)_{k \geqslant 0}$ converge vers une densité de probabilité limite $P$, alors cette densité de probabilité vérifie les conditions (*) et fournit donc une mesure de la pertinence des pages du web. \end{enumerate} \bigskip {\large \textbf{Partie D PageRank, un second modèle}} \medskip On a vu dans la partie \textbf{A.} que l'existence de cette densité de probabilité limite n'est pas toujours assurée. De plus, il peut arriver que certaines pages ne comportent aucun lien vers d'autres pages. Selon le premier modèle, lorsque le surfeur arrive sur l'une d'entre elles, il lui est impossible de la quitter. Ce modèle n'étant pas conforme à la réalité, on étudie un second modèle qui introduit la possibilité de quitter à chaque clic une page quelconque pour se diriger vers une autre choisie au hasard, et ce avec une probabilité fixe $\alpha \in ]0~;~1[$, appelée \emph{facteur d'amortissement}. Non seulement ce modèle permet de mieux rendre compte de la réalité, mais en plus on va montrer qu'il garantit l'existence d'une densité de probabilité limite fournissant une mesure de la pertinence des $n$ pages. On considère la matrice \[ B = (1 - \alpha)A + \dfrac{\alpha}{n}J\] où $J$ est la matrice de $M_n(\R)$ dont tous les coefficients sont égaux à 1, A la matrice stochastique définie dans la partie \textbf{C.} et $L$ la matrice ligne possédant $n$ coefficients tous égaux à 1 : \[J = \begin{pmatrix}1&\ldots&1\\ \vdots& &\vdots\\1& \ldots&1\end{pmatrix} \qquad \qquad L = \begin{pmatrix}1,& \ldots,&1\end{pmatrix}.\] \medskip \textbf{I.} Montrer que B est une matrice stochastique. \textbf{II.} On suppose qu'il existe un vecteur ligne $N = \begin{pmatrix}v_1,& \ldots,& v_n\end{pmatrix}$ de réels positifs ou nuls vérifiant $N = NB$, tel que $v_1 + \ldots + v_n = 1$. Montrer que la suite $\begin{pmatrix}v_1,& \ldots,& v_n\end{pmatrix}$ vérifie les conditions (i) et (ii) énoncées dans la partie \textbf{C.} \textbf{III.} Montrer que, si $Q$ est une densité de probabilité, alors $QJ = L$. \textbf{IV.} Justifier que la matrice colonne $U$ de taille $n$ dont tous les coefficients sont égaux à 1 vérifie $AU = U$. En déduire que $1$ est une valeur propre de la matrice $A$. \textbf{V.} Soit $\lambda \in \C$ une valeur propre de $A$ et $Z = \begin{pmatrix}z_1\\\vdots\\z_n\end{pmatrix}$ où $z_i \in \C$ pour tout $i \in \llbracket 1,\: n\rrbracket$, un vecteur propre associé. On note \[|Z\ = \max_{1\leqslant j \leqslant n} \left|z_j\right|.\] \medskip \begin{enumerate} \item À l'aide de l'inégalité triangulaire appliquée à une coordonnée bien choisie du vecteur $AZ$, montrer que $\lambda| \leqslant 1$. \item En déduire que, si $\beta$ est un nombre réel strictement supérieur à 1, la matrice $A - \beta I_n$ est inversible. \item En déduire que si $\gamma$ est un nombre réel strictement compris entre 0 et 1, la matrice $I_n - \gamma A$ est inversible. \end{enumerate} \textbf{VI.} \begin{enumerate} \item Justifier que la matrice $I_n - (1 - \alpha)A$ est inversible. Cela permet de poser \[H = \dfrac{\alpha}{n}L\left(I_n - (1 - \alpha)A\right)^{-1}.\] \item Vérifier que $H = (1 - \alpha)H A + \dfrac{\alpha}{n}L$. \end{enumerate} \textbf{VII.} Soit $Q$ une densité de probabilité. On définit la suite $\left(Q^{(k)}\right)_{k\geqslant 0}$ par $Q^{(k)} = Q B^k$ pour tout entier naturel $k$. \medskip \begin{enumerate} \item Démontrer, pour tout entier naturel $k$, l'égalité $\left(Q^{(k+1)} - H\right) = (1- \alpha)\left(Q^{(k)} - H\right)A$. \item En déduire que, pour tout entier naturel $k$, \[Q^{(k)} - H (1 - \alpha)^k (Q - H) A^k.\] \end{enumerate} \textbf{VIII.} En utilisant le fait que $A^k$ est une matrice stochastique, montrer que les suites formées par les coefficients des matrices lignes (Q - H)A k sont bornées. Que peut-on en déduire pour la suite des densités de probabilité Q(k) ? \textbf{IX.} Que peut-on en conclure pour le vecteur ligne $H$ ? \textbf{X.} Quel est l'avantage de cette méthode par rapport à celle exposée dans la partie C. ? \textbf{XI.} Le calcul de l'inverse de la matrice $I_n - (1 - \alpha)A$ permettant de calculer $H$ étant très coûteux, on se contente d'approcher $H$ par $Q^{(k)} = QB^k$ pour des valeurs de $k$ suffisamment grandes. Quelle justification mathématique peut-on apporter à cette pratique ? \end{document}