\def\NomChapitre{2}
\def\Type{DST}
\LeTitrec{\NomChapitre}{Jeudi 16 janvier 2014}

\begin{exo}[Cours -- 8 points]
\begin{enumerate}
\item Comme ce n'était pas précisé par l'énoncé, on pouvait donner
  l'algorithme qui répond par un booléen ou celui qui répond par
  un indice.

  \url{http://www.normalesup.org/~dconduche/prepas/PTSI/AlgoClassiques/RechercheMot_Texte.py} 
\item \url{http://www.normalesup.org/~dconduche/prepas/PTSI/AlgoClassiques/Dichotomie_fonction.py}
\end{enumerate}
\end{exo}

\begin{exo}[Exponentiation rapide -- 6 points]
\begin{enumerate}
\item La fonction retourne le contenu de la variable locale
  \fbox{\texttt{res}}. 

Comme \texttt{x} est un entier, elle est de type \fbox{entier}

\item Cas $x=3$ et $n=3$ :
\begin{tabular}[t]{cccl}
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
3\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
3\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
1\\\hline
\end{tabular}
& avant le 1er passage (non demandé)\\%%%%%%%%%%%
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
9\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
1\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
3\\\hline
\end{tabular}
& à la fin du 1er passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
81\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
0\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
27\\\hline
\end{tabular}
& à la fin du 2e passage\\
\end{tabular}

Comme \texttt{n=0}, c'est le dernier passage dans la boucle.

Cas $x=2$ et $n=10$ :
\begin{tabular}[t]{cccl}
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$2$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$10$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$1$\\\hline
\end{tabular}
& avant le 1er passage (non demandé)\\%%%%%%%%%%%
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$4$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$5$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$1$\\\hline
\end{tabular}
& à la fin du 1er passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$16$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$2$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$4$ \\\hline
\end{tabular}
& à la fin du 2e passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$256$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$1$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$4$ \\\hline
\end{tabular}
& à la fin du 3e passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$256^2$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$0$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$1024$ \\\hline
\end{tabular}
& à la fin du 4e passage\\
\end{tabular}

Comme \texttt{n=0}, c'est le dernier passage dans la boucle.

On pouvait aussi donner les résultats \og{} sans effectuer les calculs \fg{},
ce qui donne une meilleure vue de ce que fait l'algorithme :


\begin{DeuxColSep}{.46}{.5}
\begin{tabular}{cccl}
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
3\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
3\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
1\\\hline
\end{tabular}
& avant le 1er p.\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$3^2$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
1\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
3\\\hline
\end{tabular}
& à la fin du 1er p.\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$(3^2)^2$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
0\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$3\times 3^2$\\\hline
\end{tabular}
& à la fin du 2e p.\\
\end{tabular}

&

\begin{tabular}{cccl}
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$2$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$10$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$1$\\\hline
\end{tabular}
& avant le 1er passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$2^2$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$5$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$1$\\\hline
\end{tabular}
& à la fin du 1er passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$2^4$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$2$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$2^2$ \\\hline
\end{tabular}
& à la fin du 2e passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$2^8$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$1$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$2^2$ \\\hline
\end{tabular}
& à la fin du 3e passage\\
\begin{tabular}{|c|}\hline
\texttt{x}\\\hline
$2^{16}$\\\hline
\end{tabular}\vspace{5pt}&
\begin{tabular}{|c|}\hline
\texttt{n}\\\hline
$0$\\\hline
\end{tabular}&
\begin{tabular}{|c|}\hline
\texttt{res}\\\hline
$2^2\times 2^8$ \\\hline
\end{tabular}
& à la fin du 4e passage\\
\end{tabular}
\end{DeuxColSep}

\label{ds2_13_2c}
\item \fbox{La fonction \texttt{Mystere} semble calculer $x^n$}

Notons $x_k$, $n_k$ et $res_k$ les valeurs de $x$, $n$ et $res$ lors du
$k$-ième passage dans la boucle.

Pour $k=0$, $x_0$, $n_0$ et $res_0$ sont les valeurs initiales de $x$,
$n$ et $res$ ($res=1$).


Il semblerait que $x^n\times res$ soit constant égal à $x_0^{n_0}$. Nous
allons donc vérifier que
\[ \cH_k: \quad  x_k^{n_k}\times res_k = x_0^{n_0}\]
\noindent est un invariant de boucle, vrai à la fin du $k$-ième passage dans
la boucle pour tout $k \in \N$.

\begin{itemiz}
\item $\recz$ est vraie par hypothèse : $res_0=1$ donc $x_0^{n_0}\times res_0
  = x_0^{n_0}$.
\item $\rec{k}{k+1}$: Supposons $\cH_k$ vraie.

\underline{Si $n_k=1 [2]$}, \cad{} si $n_k=2p+1$ est impair, alors 
$res_{k+1}=res_k \times x_k$ et $n_{k+1}=p=\frac{n_k-1}2$.

De plus $x_{k+1}=x_k^2$. 
Donc en remplaçant :
\[x_{k+1}^{n_{k+1}}\times res_{k+1}=(x_k^2)^{\frac{n_k-1}2} \times res_k
\times x_k = x_k^{n_k+1-1}\times res_k = x_0^{n_0} \qquad (\text{d'après }\cH_k)\]
Donc $\cH_{k+1}$ est vraie dans ce cas là.

\underline{Sinon}, $n_k=2p$ est pair, $res_{k+1}=res_k$ (pas de changement),
$n_{k+1}=p=\frac{n_k}2$ et $x_{k+1}=x_k^2$. D'où
\[x_{k+1}^{n_{k+1}}\times res_{k+1}=(x_k^2)^{\frac{n_k}2} \times res_k
 = x_k^{n_k}\times res_k = x_0^{n_0} \qquad (\text{d'après }\cH_k)\]
Donc $\cH_{k+1}$ est vraie là aussi.

Ainsi, quel que soit le résultat du branchement (\text{if}), $\cH_{k+1}$ est
vraie. 
\item \underline{Conclusion} : par récurrence, $\boxed{\forall k \geq 0    \qquad x_k^{n_k}\times res_k = x_0^{n_0}  }$
\end{itemiz}
Donc $x^n\times res=x_0^{n_0}$ est bien un invariant de boucle pour la
fonction mystère.

\underline{Terminaison} : La variable \texttt{n} est de type entier positif,
sa valeur décroît strictement après chaque passage dans la boucle
(\texttt{n//2}) donc \texttt{n}
atteint $0$ et \fbox{La boucle \texttt{while} se termine}

\underline{Correction} : Comme on divise $n$ par $2$ à chaque étape, la boucle
se termine sur la valeur $n=0$. En sortie de boucle l'invariant s'écrit donc :
\[x_k^{n_k}\times res_k = x_k^0 \times res_k=res_k=x_0^{n_0}\]
Donc la variable \texttt{res} contient à ce moment là $x^n$. Nous venons de
prouver que 
\begin{cfb}{La fonction \texttt{Mystere} calcule $x^n$}\end{cfb}

Une version modifiée de la fonction \texttt{Mystere} qui affiche la valeur des
variables, un compteur du nombre de passage dans la bouble, et l'invariant : 
\href{http://www.normalesup.org/~dconduche/prepas/PTSI/Evaluations/DST2_2013/DST2_ex2.py}{DST2\_ex2.py}
\item Si $n=2^k$, à chaque passage dans la boucle le test sera faux et la
  nouvelle valeur de $n$ sera $\frac n 2$, sauf au dernier passage.
 La boucle sera donc exécutée $k+1$ fois\footnote{dans ce genre de cas,
   toujours tester pour $n$ petit : est-ce que ça marche pour $k=0$ ? $k=1$
   ?}.

Il n'y a que des opérations élémentaires dans la boucle (pas de seconde
boucle, ou d'opération sur des types composés). Donc la complexité est en
$O($nombre de passage dans la boucle$)$, ici $O(k)$.

Comme $n=2^k$, $k=\frac{\ln n}{\ln 2}$ et par conséquent \fbox{La complexité
  est en $O(\ln n)$}

\rmqbla{Si $n$ n'est pas de la forme $2^k$, ce n'est pas grave. Il est encadré
  par des puissances de $2$ : $2^k \leq n \leq 2^{k+1}$ (comme $10^3 \leq
  5973\leq 10^4$ en base $10$). Donc la complexité sera encadrée par $k$ et
  $k+1$. Or, lorsque $k \to +\infty$, $k \sim k+1$, donc par encadrement
  $k\sim k+1\sim \frac{\ln n}{\ln 2}$. On pouvait raisonner \og{} comme si
  \fg{} $n$ était une puissance de $2$.}
\end{enumerate}
 \bigskip
\rmqbla{On remarque d'ailleurs à la question \ref{ds2_13_2c} que l'on peut
  améliorer la fonction en 
  supprimant le dernier calcul de \texttt{x} : la condition de sortie de
  boucle devient \texttt{n>1}, et juste avant le \texttt{return} (mais hors de
  la boucle) on rajoute \texttt{   if n\%==1 :
      res=res*x} : }
\begin{verbatim}
def Mystere(x,n) : # x et n sont des entiers
    res=1
    while n>1 :
        if n%2==1 :
            res=res*x
        n=n//2
        x=x*x
    if n%==1 :
        res=res*x
    return res
\end{verbatim}

\end{exo}

\begin{exo}[Méthode des rectangles -- 6 points]
%On pose $f(x) = \sqrt{\cos(x)}$, pour $x\in [-1,1]$. 
\begin{enumerate}
\item Il y a plusieurs syntaxes possibles :

\texttt{import math} puis \texttt{math.cos}

\texttt{import math as m} puis \texttt{m.cos} (simple abréviation)

\texttt{from math import cos,sqrt} puis \texttt{cos} (pour n'importer que
les fonctions \texttt{cos} et \texttt{sqrt}).


Exemple de programme :

\begin{verbatim}
from math import cos,sqrt
def f(x):#x dans [-1,1] donc cos >= 0
    return sqrt(cos(x))
\end{verbatim}

\item La fonction suivante convient :

\begin{verbatim}
def Rectangle(f,a,b,n):
    aire=0      #contient l'aire entre a et x_i
    pas=(b-a)/n #écart entre x_i et x_(i+1)
    for i in range(n):
        aire=aire+pas*f(a+i*pas)
    return aire
\end{verbatim}

Le rectangle $i$ est de largeur $\frac{b-a}n$ et de hauteur $f(x_i)$, donc son
aire est $ \frac{b-a}n\times f(x_i)$. 

La formule pour approcher l'intégrale à l'aide de la {\em méthode des
  rectangles} est donc 
\[\sum_{i=0}^{n-1} \frac{b-a}n \times f\left(a+i\times \frac{b-a}n \right) \]
\rmqbla{Vous le reverrez en cours de mathématiques sous le nom de {\em somme
    de Riemann}.}

\href{http://www.normalesup.org/~dconduche/prepas/PTSI/Evaluations/DST2_2013/DST2_ex3.py}{DST2\_ex3.py}
\end{enumerate}
\end{exo}


%\FinEpreuve

%%% Local Variables:
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: DST2_2013
%%% End:
