\def\NomChapitre{2}
\def\Type{DST}
\LeTitre{\NomChapitre}{Jeudi 16 janvier 2014}
\begin{exo}[8 points]
\begin{enumerate}
\item \'Ecrire en python une fonction permettant de chercher un mot dans un
  texte.
\item \'Ecrire en python une fonction permettant de trouver par dichotomie une
  solution approchée à \texttt{eps} près d'une équation $f(x)=0$, où $f$ est
  une fonction continue et monotone.
\end{enumerate}
\end{exo}

\begin{exo}[6 points]
On donne la fonction suivante, en Python. Les variables \texttt{x} et
\texttt{n} sont de type entier.
\begin{verbatim}
def Mystere(x,n) : # x et n sont des entiers
    res=1
    while n>0 :
        if n%2==1 :
            res=res*x
        n=n//2
        x=x*x
    return res
\end{verbatim}


\begin{enumerate}
\item Quelle est le nom de la variable locale dont le contenu est retournée par la fonction ? Quel
  est son type ?
\item Faire tourner \og{} à la main \fg{} la fonction pour $x=3$ et $n=3$ :
donner la valeur des variables à la fin du premier passage dans la boucle,
puis à chaque passage dans la boucle jusqu'à la fin de l'exécution de la
boucle.

 Même question pour $x=2$ et $n=10$. \label{ds2_13_2}
\item Que semble faire la fonction \texttt{Mystere} ?

Conjecturer, à partir de la question \ref{ds2_13_2} un invariant de
boucle, puis prouver la correction de l'algorithme par récurrence.
\item On suppose que $n=2^k$, avec $k\in \N$ fixé. Combien de passage doit-on
  faire dans la boucle ? En déduire la complexité en fonction de $k$ puis de
  $n$. 
\end{enumerate}
\end{exo}

\begin{exo}[6 points]
On pose $f(x) = \sqrt{\cos(x)}$, pour $x\in [-1,1]$. 
\begin{enumerate}
\item Rappeler une syntaxe python permettant d'utiliser les fonctions
  \texttt{cos} et \texttt{sqrt} de la bibliothèque \texttt{math}.

Définir une fonction \texttt{f} qui prend un float \texttt{x} en entrée et retourne $f(x)$
en sortie.
\item On supposera désormais la fonction \texttt{f} construite. Le but est de
  calculer l'intégrale $\int_{-1}^1 f(t) \dt$ par la méthode dite des
  rectangles.

Construire une
  fonction \texttt{Rectangles(f,a,b,n)} qui calcule un approximation de
  l'intégrale $\int_a^b f(t)\dt$ selon le dessin suivant :
%%%%% INTÉGRALE %%%%%
\begin{center}
\begin{tabular}{cc}
\shorthandoff{:}
\begin{tikzpicture}[scale=2.5,baseline=(current bounding box.north)]
% bornes
\def\xmin{-1}
\def\xmax{1}
\def\ymin{-0}
\def\ymax{1}
%\path[use as bounding box] (\xmin,\ymin.3) rectangle (\xmax,\ymax.3);

\def\xun{-1}
\def\xdeux{1}
\def\tifonction{sqrt(cos(\x r))}
% % courbe
% \filldraw[fill=black!10,dashed,smooth,domain=\xun:\xdeux] (\xun,0)
% -- plot (\x,{\tifonction}) -- (\xdeux,0) -- cycle;

%%% Rectangles %%%
\def\pas{8}
\def\finenumi{7}
%%% Rectangles ROUGES %%%
% \foreach \y in {1,2,...,\pas}
%   \def\x{\xun+\y*(\xdeux-\xun)/\pas} 
%   \draw[red,fill=red!10] ({\x},0) rectangle +({(\xun-\xdeux)/\pas},{\tifonction});
%%% /Rectangles ROUGES %%%
%%% Rectangles NOIRS %%%
\foreach \y in {0,1,...,\finenumi}
  \def\x{(\xun+\y*(\xdeux-\xun)/\pas)} 
  \draw[fill=black!20] ({\x},0) rectangle +({(\xdeux-\xun)/\pas},{\tifonction});
%%% /Rectangles NOIRS %%%
% Axes & co.
% \draw[step=.25cm,dotted] (\xmin,\ymin) grid (\xmax,\ymax);
% \filldraw [gray] (0,0) circle (.1cm) node[below left, black] {$O$};
 \draw[->,thick] (\xmin.2,0) -- node[at end,below] {$t$} (\xmax.5,0);
 \draw[->,thick] (0,\ymin.3) -- node[at end,left] {$f(t)$} (0,\ymax.3);
%\foreach \x in {\xmin,...,-1,1,2,...,\xmax}
% \draw[xshift=\x cm] (0pt,1pt) -- (0pt,-1pt) node[below] {$\x$};
   % valeurs spe
 \draw[xshift=\xun cm] (0pt,2pt) -- (0pt,-2pt) node[below] {$a$};
 \draw[xshift=\xdeux cm] (0pt,2pt) -- (0pt,-2pt) node[below] {$b$};
 % Z\'ero
 \draw[xshift=0 cm] (0pt,1pt) -- (0pt,-1pt) node[below left] {$O$};
%\foreach \y in {\ymin,...,-1,1,2,...,\ymax}
%  \draw[yshift=\y cm] (1pt,0pt) -- (-1pt,0pt) node[left] {$\y$};
\clip (\xmin.2,\ymin.3) rectangle (\xmax.5,\ymax.5);
% suite dessin
\draw[very thick,smooth,domain=\xmin.2:\xmax.3] plot (\x,{\tifonction});
\node at (\xmax,\ymax) {$n= \pas$};
\end{tikzpicture}
\shorthandon{:}
&
\shorthandoff{:}
\begin{tikzpicture}[scale=2.5,baseline=(current bounding box.north)]
% bornes
\def\xmin{-1}
\def\xmax{1}
\def\ymin{-0}
\def\ymax{1}
%\path[use as bounding box] (\xmin,\ymin.3) rectangle (\xmax,\ymax.3);

\def\xun{-1}
\def\xdeux{1}
\def\tifonction{sqrt(cos(\x r))}
% % courbe
% \filldraw[fill=black!10,dashed,smooth,domain=\xun:\xdeux] (\xun,0)
% -- plot (\x,{\tifonction}) -- (\xdeux,0) -- cycle;

%%% Rectangles %%%
\def\pas{15}
\def\finenumi{14}
%%% Rectangles ROUGES %%%
% \foreach \y in {1,2,...,\pas}
%   \def\x{\xun+\y*(\xdeux-\xun)/\pas} 
%   \draw[red,fill=red!10] ({\x},0) rectangle +({(\xun-\xdeux)/\pas},{\tifonction});
%%% /Rectangles ROUGES %%%
%%% Rectangles NOIRS %%%
\foreach \y in {0,1,...,\finenumi}
  \def\x{(\xun+\y*(\xdeux-\xun)/\pas)} 
  \draw[fill=black!20] ({\x},0) rectangle +({(\xdeux-\xun)/\pas},{\tifonction});
%%% /Rectangles NOIRS %%%
% Axes & co.
% \draw[step=.25cm,dotted] (\xmin,\ymin) grid (\xmax,\ymax);
% \filldraw [gray] (0,0) circle (.1cm) node[below left, black] {$O$};
 \draw[->,thick] (\xmin.2,0) -- node[at end,below] {$t$} (\xmax.5,0);
 \draw[->,thick] (0,\ymin.3) -- node[at end,left] {$f(t)$} (0,\ymax.3);
%\foreach \x in {\xmin,...,-1,1,2,...,\xmax}
% \draw[xshift=\x cm] (0pt,1pt) -- (0pt,-1pt) node[below] {$\x$};
   % valeurs spe
 \draw[xshift=\xun cm] (0pt,2pt) -- (0pt,-2pt) node[below] {$a$};
 \draw[xshift=\xdeux cm] (0pt,2pt) -- (0pt,-2pt) node[below] {$b$};
 % Z\'ero
 \draw[xshift=0 cm] (0pt,1pt) -- (0pt,-1pt) node[below left] {$O$};
%\foreach \y in {\ymin,...,-1,1,2,...,\ymax}
%  \draw[yshift=\y cm] (1pt,0pt) -- (-1pt,0pt) node[left] {$\y$};
\clip (\xmin.2,\ymin.3) rectangle (\xmax.5,\ymax.5);
% suite dessin
\draw[very thick,smooth,domain=\xmin.2:\xmax.3] plot (\x,{\tifonction});
\node at (\xmax,\ymax) {$n= \pas$};
\end{tikzpicture}
\shorthandon{:}
\end{tabular}
\end{center}
%%%%% /INTÉGRALE %%%%%

On découpe l'intervalle $[a,b]$ en $n$ morceaux ($n\in \N^*$), le coin en haut
à gauche de chaque rectangle est en $y_i=f(x_i)$. %donner x_i ?
On approche l'aire sous la courbe par la somme des aires des rectangles : la
fonction retourne la somme de l'aire des $n$ rectangles.

On pourra utiliser l'expression suivante pour $x_i$ :
\[ \forall i \in \{0,\dots,n-1\} \qquad x_i = a+\frac{i}n(b-a)\]

%Proposer une telle fonction \texttt{Rectangle(f,a,b,n)}.
\end{enumerate}
\end{exo}


\FinEpreuve

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