%% Last modified: <suites_py_16.tex modifié par  Guillaume CONNAN le dimanche 3 avril 2016 à 23h 52min 36s>

\chapterimage{avila.png}
\chaptertext{Comme leur nom l'indique, les  méthodes itératives (i.e. les suites
  définies par une  relation $x_{n+1}=f(x_n)$ sont intimement liées  à la notion
  de boucle. Nous verrons ensuite  comment elles permettent d'effectuer certains
  calculs sur machine.

Mais ce n'est qu'un point de départ...Henri \textsc{Poincaré} s'est intéressé à la fin du XIX\eme
siècle à l'évolution des systèmes dynamiques en partant d'un problème de
mécanique  céleste:  le   soleil  est  beaucoup  plus   massif  que  les
planètes,  c'est  pourquoi  les   planètes  décrivent  des  trajectoires
elliptiques  autour  de lui.  Cependant,  chaque  planète est  également
influencée par  ses congénères mais dans une mesure bien moindre: les
trajectoires  elliptiques   sont  certes  déformées,  mais   de  manière
extrêmement  lente.  Que va-t-il  se  passer  dans  le long  terme:  ces
micro-changements  vont-ils avoir  une grande  influence ou  bien rester
négligeables? L'étude  des systèmes  dynamiques était  née: on  étudie un
système très simple  a priori, décrit par un petit  nombre de paramètres
dont la loi dévolution est déterminée, et on étudie son évolution à long
terme:  la   simplicité  des  systèmes  cache   parfois  une  incroyable
complexité de l'évolution à long terme.

Cette  théorie a  été  
popularisée par la médiatisation de  certains résultats de la théorie du
chaos, de l'étude des fractales. 
En  informatique, elle  a influencé  par exemple  certains modes  de compression
d'images.

Elle pose aussi le problème de la prédictibilité: le futur peut-il être déduit
du présent? C'est  un domaine passionnant, riche  mathématiquement et en
lien avec la physique, la biologie,  les sciences de l'ingénieur,
l'informatique...

C'est enfin un domaine mathématique très vivant: l'un des gagnants de la
médaille Fields 2014 est en effet le franco-brésilien \textbf{Artur \textsc{AVILA}} dont
le domaine de recherche est justement lié aux systèmes dynamiques. 

}
\chapter{Méthodes itératives}





\section{Une boucle sous toutes ses formes}


\subsection{Généralité}


\setindent{-1cm}
\begin{flushleft}
\begin{minipage}[t]{4cm}
%\begin{figure}
  \includegraphics[width=4cm]{goldi2}
%\caption{W.\bsc{Kahan (1933 -)}}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-10.5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


Regardons une simple boucle:


\begin{algo}[numbered]
\ALGO{Une boucle}
\STATE{r \recoit{} $\mathrm{r}_0$}
\FOR{k}{1}{n}
\STATE{r \recoit $f$(r)}
\ENDFOR
\RETURN{r}
\end{algo}

On construit  ainsi une \textit{suite} de  valeurs prises par la  variable r qui
varie avec l'incrément k. Si on note  $r_k$ la valeur de la variable $r$ lorsque
l'incrément vaut $k$:

$$r_{k+1}=f(r_k)$$

L'algorithme \texttt{boucle} peut d'ailleurs être écrit récursivement:

\begin{algo}[numbered]
\FUNC{boucle}{\pfarg{r}{type 1}\pfarg{n}{entier naturel}}{type 2}
\IF{n == 0}
\RETURN{r}
\ELSE
\RETURN{boucle(f(r),n-1)}
\ENDIF
\end{algo}


Ce qui peut s'écrire de manière plus concise à l'aide d'un \textit{pliage}:

\begin{pythoncode}
def boucle(f, r0, n) :
    functools.reduce(lambda r, k: f(r), r0, range(1, n + 1)) 
\end{pythoncode}

et pour avoir la liste de toutes les valeurs intermédiaires on remplace \lstinline+foldl+ par 
\lstinline+scanl+. 


Le programmeur voudrait savoir si sa boucle va effectivement renvoyer ce qui est
prévu  dans sa  spécification et  surtout en  combien de  temps: s'il  s'agit de
calculer la vitesse d'une voiture en fonction de la distance qui la sépare de la
voiture qui est en face, il faut faire vite.


\subsection{Complexité de la somme}




Nous  allons étudier  le plus  classique des  problèmes: il  s'agit de
calculer la somme des entiers de 1 à un entier naturel $ n$ non nul donné.

La  \textit{spécification}  est immédiate:  on  crée  une fonction  ayant  pour
argument  l'entier   naturet  $  n$  et   renvoyant  l'entier  naturel
correspondant à la somme des entiers de 1 à $ n$.

Il reste à s'occuper de la \textit{réalisation}.

\subsection{Procédure et processus}

Appelons  $  S(n)$  la  somme  des  entiers   de  1  à  $  n$  avec  $
n\in\bbn\setminus \bigl\{0\bigr\}$.

On a $ S(1)=1$ et $ S(n) = n + S(n-1)$.

\begin{pythoncode}
def s1(n) :
    assert n > 0, "l'argument doit être un entier naturel non nul" 
    if n == 1 :
         return 1
    return n + s1(n - 1)
\end{pythoncode}



Que  se passe-t-il  quand  on calcule  \texttt{s1(5)}?  On utilise  le
modèle de \textit{substitution}:



{\ttfamily
s1(5)\\
5 + s1(4)\\
5 + (4 + s1(3))\\
5 + (4 + (3 + s1(2)))\\
5 + (4 + (3 + (2 + s1(1))))\\
5 + (4 + (3 + (2 + 1)))\\
5 + (4 + (3 + 3))\\
5 + (4 + 6)\\
5 + 10\\
15
}


On commence par quatre expansions suivies de cinq réductions.

La  \textit{procédure} est  récursive  car syntaxiquement  \texttt{s1}
apparaît dans sa propre définition (\texttt{return s1(n - 1) + n}).

Le  \textit{processus} est  également récursif:  les évaluations  sont
retardées.  Intuitivement, cela  est le  cas car  on progresse  du cas
compliqué vers le cas simple: on \og descend\fg{} ici de $ n$ vers 1.
L'interpréteur doit \textit{empiler} les résultats des expansions tant
qu'il ne peut pas les réduire.
La taille de  la pile nécessaire étant proportionnelle  à l'argument $
n$, on dit qu'il s'agit d'un processus linéairement récursif.

\bigskip

On peut avoir une autre idée:  partir du cas simple et \og monter\fg{}
vers  le   cas  compliqué  (on   parle  dans  ce   cas  habituellement
d'\textit{induction}).

Ici, la somme vaut  0 puis on ajoute 1, puis on  ajoute au résultat 2,
puis on ajoute au résultat 3, etc jusqu'à atteindre $ n$.

Techniquement, on  entretient un  \textit{accumulateur} de  termes qui
évolue et un compteur qui va évoluer de 1 jusque $ n$.

L'accumulateur et le compteur évoluent selon la règle:

\begin{algo}
  accumulateur \recoit{} accumulateur + compteur\\
  compteur \recoit{} compteur + 1
\end{algo}

la  somme  cherchée  étant  la valeur  de  l'accumulateur  lorsque  le
compteur a dépassé $ n$.




\begin{pythoncode}
def s2(n) :
    def s2rec(acc, compt) :
            if compt > n :
                return acc
            return s2rec(acc + compt, compt + 1)
    return s2rec(0, 1)
\end{pythoncode}


La procédure  \texttt{s\_iter} est  syntaxiquement récursive  car elle
est  définie  à  partir  d'elle-même  mais  le  processus  n'est  plus
récursif! les évaluations ne sont plus retardées:

{\ttfamily
s2(5)\\
s\_iter(0 , 1)\\
s\_iter(1 , 2)\\
s\_iter(3 , 3)\\
s\_iter(6 , 4)\\
s\_iter(10, 5)\\
s\_iter(15, 6)\\
15
}

Cette fois-ci, il  n'y a plus de phase d'expansion  suivie d'une phase
de réduction. À chaque étape, il  suffit de garder une trace des états
de  \texttt{acc}  et  \texttt{compt}.  On  parle  alors  de  processus
\textit{itératif}. 

En général, un processus itératif est un processus pouvant être décrit
par un nombre fixe de \textit{variables  d'état} et par une règle fixe
qui décrit l'évolution de chaque  variable à chaque étape du processus
ainsi qu'un éventuel test d'arrêt  qui indique sous quelles conditions
le processus doit s'arrêter. 

Ici, le  nombre d'étapes nécessaire  est proportionnel à la  taille de
l'argument $ n$. On parle de processus itératif linéaire.

En fait,  une autre manière  de distinguer un processus  itératif d'un
processu récursif  est de remarquer  que si le processus  itératif est
interrompu, on peut le relancer en donnant comme arguments les valeurs
des variables au moment de  l'interruption. Ce n'est pas possible pour
un processus  récursif car  l'interpréteur garde des  informations \og
cachées\fg{}  dans  une pile  non  accessibles  par les  variables  du
programme.


Attention!  Ici, les  deux procédures  sont syntaxiquement  récursives
mais les  processus sont  de nature  différentes. Cependant,  dans des
langages comme Pascal,  Ada, Python, un processus  itératif décrit par
une procédure récursive consommera malgré tout autant de mémoire qu'un
processus  récursif.   C'est  pourquoi  ces  langages   utilisent  des
\textit{boucles} (\texttt{for, while}).



On peut utiliser un pliage:

\begin{pythoncode}
def s3(n) :
     return functools.reduce(lambda x, y: x + y, range(1, n + 1), 0)
\end{pythoncode}


une boucle inconditionnelle:

\begin{pythoncode}
def s4(n) :
    s = 0
    for k in range(1,n+1) :
        s += k
    return s
\end{pythoncode}


ou conditionnelle:

\begin{pythoncode}
def s5(n) :
    s, k = 0, 1
    while k <= n :
        s += k
        k += 1
    return s
\end{pythoncode}



...ou directement la fonction \mintinline{python}{sum}:


\begin{pythoncode}
sum(range(100001))  
\end{pythoncode}

Faisons  une   petite  expérience:

\begin{pythoncode}
In [12]: %timeit s1(n)
100 loops, best of 3: 3.94 ms per loop

In [13]: %timeit s2(n)
100 loops, best of 3: 5.14 ms per loop

In [14]: %timeit s3(n)
1000 loops, best of 3: 1.18 ms per loop

In [15]: %timeit s4(n)
1000 loops, best of 3: 564 µs per loop

In [16]: %timeit sum(range(n+1))
10000 loops, best of 3: 185 µs per loop

In [17]: 
In [18]: %timeit s5(n)
1000 loops, best of 3: 1.04 ms per loop
\end{pythoncode}

Python ne gère pas les processus itératifs écrits récursivement.


\subsection{Itération non linéaire: Fibonacci}



Tout le monde  connaît l'exemple classique de la suite  des nombres de
\textsc{Fibonacci} dans laquelle  chaque nombre est la  somme des deux
précédents:

$$0,1,1,2,3,5,8,13,21,34,... $$

On pense alors naturellement à:


\begin{pythoncode}
def fib1(n) :
    assert n >= 0, "l'indice doit être un entier naturel !"
    if n <= 1 :
        return 1
    return fib1 (n - 1) + fib1 (n - 2)
\end{pythoncode}


Mais...

\begin{pythoncode}
In [31]: %timeit fib1(10)
10000 loops, best of 3: 25.4 µs per loop

In [32]: %timeit fib1(20)
100 loops, best of 3: 3.12 ms per loop

In [33]: %timeit fib1(25)
10 loops, best of 3: 35.1 ms per loop

In [34]: %timeit fib1(30)
1 loop, best of 3: 408 ms per loop

In [35]: %timeit fib1(35)
1 loop, best of 3: 4.38 s per loop
\end{pythoncode}




Qu'en pensez-vous?


On peut avoir une autre idée en utilisant deux variables:

\begin{algo}
suivant \recoit{} suivant + courant \\
courant \recoit{} suivant
\end{algo}

Construisez  un  processus itératif  donnant  plus  efficacement le  $
n$-eme nombre de \textsc{Fibonacci} (avec et sans boucle).


\begin{pythoncode}
In [17]: %timeit fib1(35)
1 loop, best of 3: 4.32 s per loop

In [18]: %timeit fib2(35)
100000 loops, best of 3: 6.14 µs per loop

In [19]: %timeit fib3(35)
100000 loops, best of 3: 1.88 µs per loop

In [20]: %timeit fib2(70)
100000 loops, best of 3: 12.4 µs per loop

In [21]: %timeit fib3(70)
100000 loops, best of 3: 3.71 µs per loop
\end{pythoncode}





Commentaires?


\section{L'algorithme de Babylone}



\setindent{-1cm}
\begin{flushleft}
\begin{minipage}[t]{4cm}
\begin{figure}
  \includegraphics[width=4cm]{YBC7289blanc}
\caption{Tablette YBC 7289 \\ XVII\eme avant JC}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


Il y a presque 4000 ans, les  petits Babyloniens calculaient la racine carrée de
2  avec 6  bonnes  décimales  en utilisant  un  algorithme  vu précédemment  (cf
section \vref{sec::heron}).

Il s'agit de reprendre ce qui a été vu précédemment avec par exemple:

$$
r_0=1.0 \ \text{ et }\ f~:~x\mapsto (x + 2/x)*0.5
$$



ou si vous préférez:

\begin{algo}[numbered]
\ALGO{Babylone}
\STATE{r \recoit{} $\mathrm{r}_0$}
\FOR{k}{1}{n}
\STATE{r \recoit (r+a/r)*0.5}
\ENDFOR
\RETURN{r}
\end{algo}

\textbf{Premier  problème}: est-ce  que  la suite  des valeurs  calculées  par la  boucle
converge vers $\sqrt{2}$?

Nous  aurons besoin  de  deux théorèmes  que  nous admettrons  et  dont nous  ne
donnerons que des versions simplifiées.

\begin{theoreme}[Théorème de la limite monotone]
Toute suite croissante majorée (ou décroissante minorée) converge
\end{theoreme}

Un théorème fondamental  est celui du point fixe. Il  faudrait plutôt parler des
théorèmes du point  fixe car il en  existe de très nombreux  avatars qui portent
les   noms   de   mathématiciens  renommés:   \textsc{Banach},   \textsc{Borel},
\textsc{Brouwer},    \textsc{Kakutani},    \textsc{Kleene},…Celui    qui    nous
intéresserait le plus  en informatique est celui  de \textsc{Knaster-Tarski}. On
peut en trouver une présentation claire dans \cite{dowek2010}.

Ils donnent tous  des conditions d'existence de points fixes  (des solutions de
$f(x)=x$ pour une certaine fonction).

Nous nous contenterons pour l'instant de la version \textit{light} vue au lycée.

\begin{theoreme}[Théorème du point fixe: version (très) édulcorée du lycée]
Soit I un intervalle fermé de $\bbr$, soit $f$ une fonction de Ι vers I et soit
$(r_n)$ une  suite d'éléments de I  telle que $r_{n+1}=f(r_n)$ pour  tout entier
naturel $n$. 

SI $(r_n)$ est convergente ALORS sa limite est UΝ \textit{point fixe} de $f$
appartenant à I.
  
\end{theoreme}

Cela va nous aider à étudier notre suite définie par $r_{n+1}= f(r_n)=\frac{r_n +
  \frac{2}{r_n}}{2}$ et $r_0=1$.

\begin{recherche}\label{exo::baby}
Démontrez que pour tout entier naturel non nul $n$, on a $r_n \geqslant \sqrt{2}
$ puis que la suite est décroissante.

Démontrez que $\sqrt{2}$ est l'unique point fixe positif de $f$ et conclure.
\end{recherche}


\textbf{Deuxième problème}: quelle  est la vitesse de convergence?  Ici, cela se
traduit  par   \og  combien   de  décimales  obtient-t-on   en  plus   à  chaque
itération?\fg{}.

\begin{recherche}
  Calculez $(r_{n+1} - \sqrt{2} )$ en  fonction de $(r_n- \sqrt{2} )$ et essayez
  de répondre à la question précédente à l'aide de ce résultat.
\end{recherche}


On  peut donc  être sûr  a priori  que le  résultat de  notre boucle  donnera le
résultat spécifié (avec la convergence).  
Le nombre d'itérations pour une précision donnée peut lui
aussi être calculé à l'avance en étudiant la vitesse.


Essayons  d'être un  peu plus  rigoureux et  général en  introduisant la  notion
d'ordre d'une suite:

\begin{definition}[Ordre d'une suite - Constante asymptotique d'erreur]
Soit $(r_n)$ une suite convergeant vers $\ell$. S'il existe un entier $k>0$ tel que:

$$
\displaystyle\lim_{n\to +\infty}\frac{|r_{n+1}-\ell|}{|r_n-\ell|^k}=C
$$

avec $C\neq 0$  et $C\neq +\infty$ alors  on dit que $(r_n)$ est  d'ordre $k$ et
que C est la constante asymptotique d'erreur.


\end{definition}

\begin{recherche}
Déterminez par exemple l'ordre et la constante asymptotique d'erreur de la suite
de Babylone donnant une approximation de $\sqrt{2}$.
\end{recherche}


Si l'on  connaît l'ordre d'une  suite, on va  pouvoir prévoir l'évolution  de la
précision atteinte au fur et à mesure de l'avance de la boucle.

Ainsi, pour une suite d'ordre $k$  avec comme constante asymptotique d'erreur C,
on a pour $n$ suffisamment grand:

$$|r_{n+1}-\ell|\approx C|r_n-\ell|^k$$

\begin{recherche}
  Quel est le  rapport entre $\log_{10}x$ et le nombre  de décimales d'un nombre
  plus petit que 1 en base 10?
\end{recherche}

En posant $d_n=-\log_{10}|r_n-\ell|$ et $D=-\log_{10}C$ on obtient:


$$d_{n+1}=...$$

\begin{recherche}
  Que peut-on en conclure?
\end{recherche}


Une  application :  on  peut  ainsi calculer  rapidement  sur  un petit  système
embarqué (voire un \textit{smart phone}) la vitesse de la
voiture en fonction de la distance la séparant de la voiture qui la précède.


\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{safety}
\end{center}
\caption{Application \href{http://www.sompo-japan.co.jp/safetysight\_app/index.html}{\textit{safety sight}} sur \textit{smart phone}}
\end{figure}



\section{Méthodes itératives pour résoudre une équation}




Résoudre une  équation du premier  ou du  second degré, vous  savez faire...Mais
dans les autres cas? 

Dans cette  section, nous nous intéresserons  à la résolution d'une  équation du
type $φ(x)=\ell$ où $φ$ est une fonction de $\bbr$ dans lui-même.


On se ramènera même à une équation de la forme $f(x)=0$ en posant $f(x)=φ(x)-\ell$.


\subsection{Dichotomie (ou méthode de bi-section)}


On veut résoudre une équation du type $f(x)=0$ sur un intervalle I avec 
 $f$ une fonction continue qui change
de signe sur un intervalle $[a,b]$ inclus dans I.

On  sait qu'il  existe au  moins  une solution  $\alpha$ de  notre équation  sur
$[a,b]$: pourquoi?

Soit $m$ le centre de l'intervalle. Trois cas se rencontrent:


\begin{itemize}
\item si $f(m)=0$ alors la vie est belle;
\item  si $f(m)$  a  le  même signe  que  $f(a)$ alors  $\alpha\in[m,b]$
  (pourquoi?);
\item si $f(m)$  a  le  même signe  que  $f(b)$ alors  $\alpha\in[a,m]$
  (pourquoi?);
\end{itemize}


\begin{recherche}
On  itère  ce  mécanisme   jusqu'à  obtenir  un  intervalle  d'amplitude
correspondant à la précision demandée sur $\alpha$: pourquoi cela suffit-il?
Quel  est l'avantage  de cette  méthode informatiquement  parlant? Quel  est son
principal désavantage?
\end{recherche}

Il est à noter que les divisions par 
 successives peuvent engendrer des problèmes selon la norme IEEE 754 (cf \cite{goualardPage}).


On parle  de \textit{dichotomie} du grec  $\delta \iota \chi o  \tau o \mu
\iota \alpha$ qui signifie \textit{division en deux parties égales.}
 


\subsection{Ordre d'une suite et formules de Taylor}\label{sec::ordre}

Considérons     une     suite convergente    générée    par     un     procédé     itératif
$x_{n+1}=φ(x_n)$. Supposons  que $φ$ est  de classe  $\CR^1$ au voisinage  de sa
limite $\ell$. Si l'on remarque que $x_{n+1}=φ(x_n)=φ(\ell + (x_n-\ell))$ alors:

$$
x_{n+1}=φ(\ell)+(x_n-\ell)φ'(\ell)+{\mathcal O}(|x_n-\ell|^2)
$$

On en déduit que:

$$
x_{n+1}-\ell=(x_n-\ell)φ'(\ell)+{\mathcal O}(|x_n-\ell|^2)
$$


\begin{recherche}
On  peut  alors en  conclure  des  choses sur  l'ordre  de  la suite  selon  que
$φ'(\ell)$ est nul ou pas: lesquelles?
\end{recherche}

\subsection{Méthode de Newton-Raphson-Halley-etc.}


La méthode de  résolution des équations numériques que  nous allons voir
à présent a été initiée par Isaac \textsc{Newton} vers 1669 sur des
exmples numériques   mais la formulation était fastidieuse. Dix ans plus
tard,  Joseph \textsc{Raphson}  met en  évidence une  formule de  récurrence. En
1694, la formule est encore  améliorée par  Edmund \textsc{Halley},
l'homme de la comète. Un
siècle  plus tard, \textsc{Mouraille}  et \textsc{Lagrange}  étudient la
convergence  des approximations successives  en fonction  des conditions
initiales  par  une  approche  géométrique.  Cinquante  ans  plus  tard,
\textsc{Fourier}  et  \textsc{Cauchy}  s'occupe  de la  rapidité  de  la
convergence. 

\subsubsection{Approche intuitive graphique}


\begin{itemize}


\item On part d'un nombre  quelconque $x_0$~;
 \item \`a partir de $x_0$, on calcule un nouveau nombre $x_1$ de la
mani\`ere suivante (voir figure )~: on trace la tangente au graphe
de $f$ au point d'abscisse $x_0$, et on d\'etermine le point
d'intersection de cette tangente avec l'axe des abscisses. On
appelle $x_1$ l'abscisse de ce point d'intersection~;
\item et on recommence~: on calcule un nouveau
nombre $x_2$ en appliquant le proc\'ed\'e d\'ecrit au point 2 o\`u
l'on remplace $x_0$ par $x_1$~;
\item etc.
\end{itemize}


\begin{center}
  \includegraphics[width=.6\linewidth]{newton.1}
\end{center}




\`A partir de cette description graphique de
la m\'ethode de Newton, trouver la formule, notée (1), donnant $x_1$ en
fonction de $x_0$, puis $x_{n+1}$ en fonction de $x_n$.\\
Quelles hypoth\`eses doit-on faire sur $f$ et les $x_n$ pour que la
formule ait un sens~?\\

\subsubsection{Approche intuitive \og taylorienne\fg{}}


Nous voulons résoudre l'équation $f(x)=0$. Utilisons à nouveau la ruse: 
$$
f(x_{n+1})=f(x_n+(x_{n+1}-x_n))=f(x_n)+(x_{n+1}-x_n)f'(x_n)+{\mathcal O}((x_{n+1}-x_n)^2)
$$


Intuitivement,  pour que  $f(x_{n+1})$ soit  de plus  en plus  petit, il  serait
pratique que la partie linéaire de cette expression, $f(x_n)+(x_{n+1}-x_n)f'(x_n)$, soit la plus petite possible,
c'est-à-dire nulle et on obtient à nouveau:

$$
x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}
$$

On  remarque alors  que  si la  suite  converge  vers une  limite  $\ell$ et  si
$f'(\ell)$ est non nul, alors on obtient bien $f(\ell)=0$.

Maintenant,  posons $φ(x)=x-\frac{f(x)}{f'(x)}$  et  supposons que  $f$ soit  de
classe $\CR^2$ sur un intervalle ouvert $V$ tel que l'équation $f(x)=0$ admette une
unique solution d'ordre 1 (c'est-à-dire que $f(\ell)=0$ mais $f'(\ell)\neq 0$).

La méthode de \textsc{Newton} revient à construire la suite définie par $x_{n+1}=φ(x_n)$
avec $x_0\in V$.


\begin{recherche}
Vérifiez que $φ$ est dérivable sur $V$ et que 
$$
φ′(x)=\frac{f(x)f''(x)}{(f'(x))^2}
$$
et concluez en utilisant les résultats de la section~\vref{sec::ordre}
\end{recherche}



\begin{NB}
  Il faut bien comprendre  que nos approches sont un peu  ole ole compte-tenu de
  nos outils mathématiques limités...

On retiendra que $x_0$ a besoin d'être suffisamment proche de la solution
pour que l'équation $f(x)=0$ admette une unique solution et
que $f'(\ell)$ soit non nul. En  fait, on pourrait montrer  que la méthode
marche encore si $\ell$ est une solution d'ordre 2.

Il faut aussi que la fonction $f$  soit suffisamment régulière. Bref, il ne faut
pas trop bricoler au hasard...
\end{NB}


\subsection{Étude de la suite associée à l'équation $\text{x}^{\text{3}}\text{-2x-5=0}$.}


On   veut   résoudre  l'équation   $x^3-2x-5=0$   par   la  méthode   de
\textsc{Newton-Raphson}.  On note
$f$ la fonction $x\mapsto x^3-2x-5$. C'est  en fait sur cet exemple que \textsc{Newton}
a raisonné.

\begin{recherche}
\begin{enumerate}
\item  Montrez  rapidement  que  l'équation $f(x)=0$  admet  une  unique
  solution $α$ sur $\bbr$. Montrez que $2<α<3$.

\item Déterminez la fonction  $φ$ telle que $x_{n+1}=φ(x_n)$, la suite
  $(x_n)$ étant celle décrite au paragraphe précédent en prenant $x_0=3$.
\item Étudiez  le sens de  variation de la  fonction $φ$ puis  celui de
  $φ'$ et déduisez-en que $[α,3]$  est stable par $φ$ et que $φ$
  est strictement croissante sur $[α,3]$.
\item Que pouvez-vous en déduire sur la convergence de la suite $(x_n)$~?
\end{enumerate}
\end{recherche}

\subsection{Test d'arrêt}


Afin  de  construire  un  algorithme  donnant  une  approximation  d'une
solution    d'une    équation    numérique    par    la    méthode    de
\textsc{Newton-Raphson},   il  faudrait   déterminer  un   test  d'arrêt
c'est-à-dire savoir à partir de quel rang $n$ $|x_n-α|$ restera 
inférieur à une valeur donnée.

Il suffit  de remarquer que  $f(x_n)=f(x_n)-f(α)$. Nous supposerons
$f$ de classe $\CR^2$ sur un \og bon\fg{} voisinage I de $α$ (ce
critère nous échappe encore à notre niveau).  Alors $f$ est en
particulier dérivable en $α$ donc

$$f(x_n)=f(x_n)-f(α)\sim f'(α)\times(x_n-α)$$

C'est-à-dire, puisque $f'(α)$ est supposé non nul:

$$x_n-α\sim \frac{f(x_n)}{f'(α)}$$

Or  $f$ étant de  classe $\CR^2$,  on a  $f'$ continue  et non  nulle en
$α$ donc $f'(α)\sim f'(x_n)$.

Finalement



$$x_n-\alpha\sim \frac{f(x_n)}{f'(x_n)}=x_n-x_{n+1}$$


Nous choisirons donc comme test d'arrêt $\left|\frac{f(x_n)}{f'(x_n)}\right|<p$
 avec $p$ la précision choisie.

Il ne reste plus qu'à écrire l'algorithme.

%\subsection{Méthode de \textsc{Newton} pour effectuer une division sur machine}






\section{Sommes}






%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{MadHatter}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.4cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


\begin{quote}
  {\itshape \og What is one and one  and one and one and one and one and
  one and one ?\fg{}\\
\og I don't know \fg{} said Alice. \og I lost count\fg{}.\\
\og She can't do Addition.\fg{}}
\end{quote}

\begin{flushright}
Alice in wonderland - Lewis \textsc{Caroll}
\end{flushright}


\subsection{Notation}


Si  on  écrit $1+2+3+4+\cdots+(n-1)+n$,  on  comprend  que les  $\cdots$
signifient qu'ils doivent  être remplacés selon le motif  induit par les
termes les entourant.


On   peut   être   amené   à   étudier  des   sommes   plus   générales:
$a_0+a_1+\cdots+a_n$,  chaque  \textbf{terme} $a_k$  de  la somme  étant
défini d'une manière quelconque.

Si  l'on écrit  la somme  avec des  $\cdots$, il  faut que  le  motif de
construction  soit présenté  de  manière suffisamment  claire pour  être
induit:


$$1+4+9+22+53+128+309+...$$


n'est pas évident à comprendre mais:

$$1+4+(2\times 4+1)+(2\times 9+4) +\cdots + (2a_{n-1}+a_{n-2})$$

est plus explicite.


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{fourier}
\caption{{\scriptsize Joseph \textsc{Fourier}  (1768-1830)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.9cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


En 1820, le  mathématicien Joseph \textsc{Fourier}\footnote{Nous aurions
pu ne  pas étuidier les sommes, ne  pas compresser les images  et le son
car \textsc{Fourier} échappa
de peu à la guillotine durant la Terreur: \href{http://www.youtube.com/watch?v=MwGD13BnH-o}{{http://www.youtube.com/watch?v=MwGD13BnH-o}}} introduit le fameux
sigma majuscule. Citons-le:

\begin{quote}
  {\it  Le signe  $ \displaystyle\sum_{i=1}^{+\infty}$  indique  que l'on
  doit donner  au nombre entier $i$  toutes ses valeurs 1,  2, 3,..., et
  prendre la somme des termes.}
\end{quote}

Notez bien,  en tant qu'informaticien(ne), que  le $i$ joue  ici le rôle
d'une variable  locale et aurait très  bien pu porter un  autre nom sans
changer le résultat.

Depuis, on a généralisé l'emploi  des bornes afin de définir les indices
à partir de certaines propriétés.  On peut par exemple écrire les sommes
suivantes avec ou sans bornes explicitement spécifiées:

$$\displaystyle\sum_{\substack{1      \leqslant      k<100     \\      k
\text{ impair}}}^{}k^2=\displaystyle\sum_{k=0}^{49}(2k+1)^2$$

Cette   formulation  est   particulièrement   adaptée  aux   changements
d'indices:




$$\displaystyle\sum_{1      \leqslant     k      \leqslant     n}^{}a_k=
\displaystyle\sum_{1 \leqslant k+1 \leqslant n}a_{k+1}^{}=\displaystyle\sum_{k=1}^{n}a_k=\displaystyle\sum_{i=0}^{n-1}a_{i+1}$$

La  dernière forme  demande un  peu de  réflexion alors  que  la deuxième
beaucoup moins.

L'informaticien canadien  Kenneth \textsc{Iverson}, prix \textsc{Turing}
en  1979 et  inventeur des  langages  \textsc{Apl} et  J, introduit  une
notation fort pratique mais peu utilisée en France, nommée 
\textbf{crochets d'\textsc{Iverson}}. Soit P
une certaine propriété:

$$[P]=
\begin{cases}
  1 \quad \text{si P est vraie}\\
0 \quad \text{sinon}
\end{cases}
$$

Par exemple: 

$$\displaystyle\sum_{\substack{1      \leqslant      k<100     \\      k
\text{  impair}}}^{}k^2=\displaystyle\sum_{k}^{}k^2 \left[1  \leqslant k
<100\right]\times \left[k \text{ impair }\right]$$


\subsection{Somme, boucle et récurrence}


Une somme suggère naturellement  l'emploi d'une boucle \og pour\fg{}. En
effet  $\sum_{k=1}^na_k$ se lit  \og somme  des $a_k$  \textbf{pour} $k$
variant \textbf{de} 1 \textbf{à} $n$\fg{}.


On  peut également penser  à une  somme en  terme de  suite. Si  on note
$S_n=\sum_{k=0}^nk^2$, alors:

$$S_0=0;\quad \forall n>0,\ S_{n}=S_{n-1}+n^2 $$

Cela   nous   rappelle   d'ailleurs   qu'une  \textbf{suite}   est   une
\textbf{fonction} de $\bbn$ dans tout autre ensemble (ici $\bbn$ lui-même).

\subsection{Manipulation de sommes}


La principale  difficulté du  calcul avec des  sommes est  d'obtenir par
diverses manipulation  une expression plus  simple. Tout dérive  le plus
souvent des trois lois suivantes:

\begin{description}
\item[Distributivité]  $\displaystyle\sum_{k\in K}^{}\lambda a_k=\lambda
\displaystyle\sum_{k\in K}^{}a_k \qquad (\lambda$ ne dépendant pas de $k$);
\item[Associativité]                             $\displaystyle\sum_{k\in
K}^{}(a_k+b_k)=\displaystyle\sum_{k\in   K}^{}a_k+\displaystyle\sum_{k\in
K}^{}b_k$;
\item[Commutativité]                             $\displaystyle\sum_{k\in
K}^{}a_k=\displaystyle\sum_{k\in K}^{}a_{\pi(k)} \qquad(\pi\in
\mathfrak{S}_{\card K})$.
\end{description}



Par exemple, nous  allons prouver un résultat fort  utile concernant les
suites géométriques.

Nous  voudrions calculer $S_n=\displaystyle\sum_{k=0}^{n}x^k$  pour tout
réel $x\neq 1$.

Or   $$S_n+x^{n+1}=   x^0+\displaystyle\sum_{1   \leqslant  k   \leqslant
n+1}x^k=x^0+\displaystyle\sum_{0       \leqslant      k-1      \leqslant
n}^{}x^{k}=x^0+\displaystyle\sum_{0      \leqslant     k-1     \leqslant
n}^{}x^{(k-1)+1}$$

En posant $i=k-1$ on obtient:

$$S_n+x^{n+1}=x^0+\displaystyle\sum_{0     \leqslant     i     \leqslant
n}^{}x^{i+1}=x^0+x\displaystyle\sum_{0     \leqslant     i     \leqslant
n}^{}x^{i}=1+xS_n$$

d'où:

$$S_n(1-x)=1-x^{n+1}$$

Finalement, comme $x\neq 1$, on obtient:

$$\displaystyle\sum_{k=0}^{n}x^k=\frac{1-x^{n+1}}{1-x}$$


\subsection{Sommes multiples}

Nous voulons  exprimer $S=a_1b_1+a_1b_2+a_1b_3+a_2b_1+a_2b_2+a_2b_3+a_3b_1+a_3b_2+a_3b_3$ avec
le symbole $\sum$: 

  \begin{eqnarray*}
    S&=&\displaystyle\sum_{i,j}^{}a_ib_j  \left[1  \leqslant  i,  j
  \leqslant 3\right]\\
&=&\displaystyle\sum_{i,j}^{}a_ib_j  \left[1  \leqslant  i\leqslant  3\right]
\left[1 \leqslant j\leqslant 3\right]\\
&=&\displaystyle\sum_{i}^{}\left(\displaystyle\sum_{j}^{}a_ib_j\left[1  \leqslant  i\leqslant  3\right]
\left[1 \leqslant j\leqslant 3\right]\right)\\
&=&\displaystyle\sum_{i}^{}a_i   \left[1  \leqslant   i  \leqslant
3\right]
\left(\displaystyle\sum_{j}^{}b_j   \left[1    \leqslant   j   \leqslant
3\right]\right) \\
&=&\left(\displaystyle\sum_{i}^{}a_i   \left[1  \leqslant   i  \leqslant
3\right]\right)
\left(\displaystyle\sum_{j}^{}b_j   \left[1    \leqslant   j   \leqslant
3\right]\right) \\
&=& \left(\displaystyle\sum_{i=1}^{3}a_i\right) 
\left(\displaystyle\sum_{j=i}^{3}b_j \right)
\end{eqnarray*}



Nous voulons cette fois exprimer $S'=a_1b_1+a_1b_2+a_1b_3+a_2b_2+a_2b_3+a_3b_3$ avec
le symbole $\sum$: 

  \begin{eqnarray*}
    S'&=&\displaystyle\sum_{i,j}^{}a_ib_j  \left[1  \leqslant  i\leqslant  j
  \leqslant 3\right]\\
&=&\displaystyle\sum_{i,j}^{}a_ib_j  \left[1  \leqslant  i\leqslant  3\right]
\left[i \leqslant j\leqslant 3\right]\\
&=&\displaystyle\sum_{i}^{}\left(\displaystyle\sum_{j}^{}a_ib_j\left[1  \leqslant  i\leqslant  3\right]
\left[i \leqslant j\leqslant 3\right]\right)\\
&=&\displaystyle\sum_{i}^{}a_i   \left[1  \leqslant   i  \leqslant
3\right]
\left(\displaystyle\sum_{j}^{}b_j   \left[i    \leqslant   j   \leqslant
3\right]\right) \\
&=& \displaystyle\sum_{i=1}^{3}a_i 
\left(\displaystyle\sum_{j=i}^{3}b_j \right)
\end{eqnarray*}

Nous verrons d'autres exemples en exercice.


\section{Sommes infinies (séries)}

\subsection{Les dangers des ... mal maîtrisés}

À          quoi           peut          bien          être          égal
$S=\frac{1}{2^0}+\frac{1}{2^1}+\frac{1}{2^2}+\cdots$?

Multiplions les deux membres par 2, nous obtenons:

$2S=2+\frac{1}{2^0}+\frac{1}{2^1}+\frac{1}{2^2}+\cdots=2+S$

donc $S=2$. Waouh, magique!

On recommence avec:

$T=2^0+2^1+2^2+\cdots$

alors:

$2T=2^1+2^2+2^3+\cdots=T-2^0=T-1$ donc $T=-1$.

Waouh!...Euh...Quoique, même réveillé brutalement en plein somme il peut
sembler bizarre  que la  somme de nombres  strictement positifs  donne un
nombre strictement négatif...

Il va falloir prendre des précautions.

\subsection{Séries}

\begin{definition}
Soit $u$ une suite r\'{e}elle d\'{e}finie sur $I=\left\{ n\in \mathbb{N\mid }%
n\geq n_{0}\right\} .$ On appelle s\'{e}rie de terme g\'{e}n\'{e}ral $u_{n}$
la suite $S$ d\'{e}finie par $S_{n}=\sum\limits_{k=n_{0}}^{n}u_{k}.$ Si la
suite $S$ converge, on dit que la s\'{e}rie de terme g\'{e}n\'{e}ral $u_{n}$
converge et on note $\sum\limits_{k=n_{0}}^{+\infty
}u_{k}=\lim\limits_{n\rightarrow +\infty }S_{n}$. Une s\'{e}rie qui ne
converge pas est dite divergente, dans ce cas l'\'{e}criture $%
\sum\limits_{k=n_{0}}^{+\infty }u_{k}$ \textbf{n'a pas de sens}.

La s\'{e}rie de terme g\'{e}n\'{e}ral $u_{n}$ est not\'{e}e $\left( \sum
u_{n}\right) .$

\end{definition}
Si on nous demande d'\'{e}tudier la s\'{e}rie $\left( \sum \frac{1}{n^{2}}%
\right) ,$ on nous demande d'\'{e}tudier la suite $S$ d\'{e}finie par $%
S_{n}=\sum\limits_{k=1}^{n}\frac{1}{k^{2}}$ avec \'{e}videmment $n\in 
\mathbb{N}^{\ast }.$

\begin{remarque}
Si la suite $u$ est d\'{e}finie \`{a} partir de $n_{0},$ rien ne nous emp%
\^{e}che de changer les notations pour travailler avec la m\^{e}me suite d%
\'{e}finie \`{a} partir du rang 0 ou du rang $1$ ou ... En effet, condid\'{e}%
rons la suite $v$ d\'{e}finie par $v_{n}=u_{n+n_{0}},$ il est cair que la
suite $v$ est definie sur $\mathbb{N}$ et, qu'\'{e}tudier la suite $v,$
c'est \'{e}tudier la suite $u.$ La cons\'{e}quence de ceci est que, dans ce
qui suit, les suites qui interviendront seront, suivant les besoins, d\'{e}%
finie \`{a} partir de $n=0$ ou $n=1$ ...
\end{remarque}

\begin{remarque}
$S_{n}$ est appel\'{e} une somme partielle.
\end{remarque}

\begin{theoreme}
Si la s\'{e}rie $\left( \sum u_{n}\right) $ converge alors on a $\underset{%
n\rightarrow +\infty }{\lim }u_{n}=0$
\end{theoreme}

La d\'{e}monstration est tr\`{e}s simple. 

Consid\'{e}rons $%
S_{n}=\sum\limits_{j=0}^{n}u_{j}$. Par hypoth\`{e}se $\lim\limits_{n%
\rightarrow +\infty }S_{n}=\lim\limits_{k\rightarrow +\infty }S_{k}=\ell$. Si
nous rempla\c{c}ons $k$ par $n-1,$ nous obtenons%
$$
\lim\limits_{n\rightarrow +\infty }S_{n}=\lim\limits_{n-1\rightarrow +\infty
}S_{n-1}=\ell
$$%
mais comme $S_{n}-S_{n-1}=u_{n}$ on en d\'{e}duit 
$$
\underset{n\rightarrow +\infty }{\lim }u_{n}=\underset{n\rightarrow +\infty }%
{\lim }\left( S_{n}-S_{n-1}\right) =\ell-\ell=0
$$

\begin{remarque}
La r\'{e}ciproque est totalement fausse, ce n'est pas parce que le terme g%
\'{e}n\'{e}ral d'une s\'{e}rie a pour limite z\'{e}ro que cette s\'{e}rie
converge.
\end{remarque}



\subsection{Série harmonique}

Nous allons d\'{e}montrer que la s\'{e}rie $\left( \sum \frac{1}{n}\right) $%
, qui porte le nom de s\'{e}rie harmonique, diverge. Nous avons donc $u_{n}=%
\dfrac{1}{n}$ avec $n\in \mathbb{N}^{\ast }$ \'{e}videmment et 
$$
S_{n}=\sum\limits_{j=1}^{n}u_{j}=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n%
}
$$%
La suite $S$ est une suite de termes strictement positifs et comme $%
S_{n+1}-S_{n}=\dfrac{1}{n+1}>0$ nous sommes assur\'{e}s que la suite $S$ est
strictement croissante:  ainsi, soit  elle diverge vers  $+\infty$, soit
elle converge vers une limite réelle $\ell$.

Calculons $S_{2n}-S_n$. 

\begin{eqnarray*}
S_{n} &=&\sum\limits_{j=1}^{n}u_{j}=1+\frac{1}{2}+\cdots +\frac{1}{%
n} \\
S_{n=2n} &=&\sum\limits_{j=1}^{2n}u_{j}=1+\frac{1}{2}+\cdots +%
\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+\cdots +\frac{1}{n+n}
\\
S_{2n}-S_{n} &=&\frac{1}{n+1}+\frac{1}{n+2}+\cdots +\frac{1%
}{n+n}
\end{eqnarray*}%
La derni\`{e}re somme comporte exactement $n$ termes tous $\geqslant \dfrac{1%
}{2n}.$ On obtient alors%

$$
S_{2n}-S_{n}\geqslant \frac{1}{2n}+\frac{1}{2n}+\cdots +\frac{1%
}{2n}=\frac{n}{2n}=\frac{1}{2}
$$%


Supposons que $(S_n)$ converge vers $\ell$, alors $
\displaystyle\lim_{n\to               +\infty}S_n=\displaystyle\lim_{n\to
+\infty}S_{2n}=\ell$.

En reportant dans l'inégalité obtenue précédemment: $\ell-\ell \geqslant
\frac{1}{2}$  ce qui est  absurde donc  $(S_n)$ diverge  vers $+\infty$,
doucement, mais sûrement.


\subsection{Séries télescopiques}
Int\'{e}ressons-nous \`{a} la convergence de la s\'{e}rie de terme g\'{e}n%
\'{e}ral $u_{n}=\dfrac{1}{n^{2}-1}$ ; il est \'{e}vident que $u_{n}$ n'est d%
\'{e}finie que pour $n\geq 2.$ Nous allons calculer $\lim\limits_{n%
\rightarrow +\infty }S_{n}$ avec $S_{n}=\sum\limits_{k=2}^{n}u_{k}$ en
utilisant la remarque indispensable suivante :%
$$
\frac{1}{x^{2}-1}=\frac{1}{2}\left( \frac{1}{x-1}-\frac{1}{x+1}\right)
$$%
Cela donne :%
\begin{eqnarray*}
S_{n} &=&\sum\limits_{k=2}^{n}u_{k}=\sum\limits_{k=2}^{n}\dfrac{1}{k^{2}-1}=%
\frac{1}{2}\sum\limits_{k=2}^{n}\left( \frac{1}{k-1}-\frac{1}{k+1}\right) \\
S_{n} &=&\frac{1}{2}\left( \sum\limits_{k=2}^{n}\frac{1}{k-1}%
-\sum\limits_{k=2}^{n}\frac{1}{k+1}\right)
\end{eqnarray*}%
Dans la premi\`{e}re sommation rempla\c{c}ons $k$ par $j+1$ et dans la deuxi%
\`{e}me $k$ par $j-1$ :%
$$
S_{n}=\frac{1}{2}\left( \sum\limits_{j=1}^{n-1}\frac{1}{j}%
-\sum\limits_{j=3}^{n+1}\frac{1}{j}\right) =\frac{1}{2}\left( 1+\frac{1}{2}-%
\frac{1}{n}-\frac{1}{n+1}\right)
$$%
On obtient alors%
$$
\underset{k\rightarrow +\infty }{\lim }S_{n}=\frac{3}{4}
$$%
Il est alors permis d'\'{e}crire que $\sum\limits_{n=2}^{+\infty
}u_{n}=\sum\limits_{n=2}^{+\infty }\dfrac{1}{n^{2}-1}$ a un sens ou existe
et vaut $\dfrac{3}{4}.$ On dit aussi que la somme de la s\'{e}rie est $%
\dfrac{3}{4}.$


\begin{remarque}
Il ne faut pas croire que l'on est capable de trouver la somme de toute s%
\'{e}rie convergente, c'est plut\^{o}t rare, par contre, on est tr\`{e}s
souvent capable de dire si une s\'{e}rie converge ou non mais nous ne pr\'{e}%
senterons pas les outils \'{e}volu\'{e}s qui le permettent.
\end{remarque}

% \begin{remarque}
% Dans certains journaux on vous propose souvent l'\'{e}nigme suivante : on
% consid\`{e}re la somme infinie%
% $$
% S=1-1+1-1+1-1+1-1+1-1+\cdots \cdots
% $$%
% qui s'\'{e}crit aussi 
% $$
% S=\left( 1-1\right) +\left( 1-1\right) +\left( 1-1\right) +\left( 1-1\right)
% +\left( 1-1\right) +\cdots \cdots
% $$%
% et on conclut $S=0.$ Mais on vous fait remarquer que%
% $$
% S=1+\left( -1+1\right) +\left( -1+1\right) +\left( -1+1\right) +\left(
% -1+1\right) +\cdots \cdots
% $$%
% et donc que $S=1.$ O\`{u} est donc l'erreur ? La r\'{e}ponse est que $S$
% n'existe pas et donc avec "quelque chose" qui n'existe pas, il n'est pas
% anormal d'obtenir un r\'{e}sultat d\'{e}bile comme $0=1$ ! Si vous n'\^{e}%
% tes pas convaincu, consid\'{e}rez la suite $u$ d\'{e}finie par $u_{n}=\left(
% -1\right) ^{n}.$ Dans ces conditions 
% $$
% S_{n}=\sum\limits_{j=0}^{n}\left( -1\right) ^{j}
% $$%
% or nous avons d\'{e}montr\'{e} que si la s\'{e}rie de terme g\'{e}n\'{e}ral $%
% u_{n}$ convergeait, obligatoirement $u$ avait pour limite $0.$
% \end{remarque}

\subsection{S\'{e}rie g\'{e}om\'{e}trique}

On appelle s\'{e}rie g\'{e}om\'{e}trique toute s\'{e}rie dont le terme g\'{e}%
n\'{e}ral est de la forme $u_{n}=q^{n}.$

 D'apr\`{e}s le th\'{e}or\`{e}me pr%
\'{e}c\'{e}dent, il est manifeste (\textbf{pourquoi?!}) qu'une s\'{e}rie g\'{e}om\'{e}trique
converge si, et seulement si,  $$\left\vert q\right\vert <1$$ Calculons dans ce cas la somme de
la s\'{e}rie :%
\begin{eqnarray*}
S_{n} &=&\sum\limits_{j=0}^{n}q^{j}=1+q+q^{2}+q^{3}+\cdots +q^{n}=\frac{%
1-q^{n+1}}{1-q}\text{ et} \\
\lim\limits_{n\rightarrow +\infty }S_{n} &=&\frac{1}{1-q}=\sum%
\limits_{j=0}^{+\infty }q^{j}
\end{eqnarray*}

\subsection{S\'{e}rie exponentielle}

C'est la s\'{e}rie dont le terme g\'{e}n\'{e}ral est de la forme $u_{n}=%
\dfrac{x^{n}}{n!}$ o\`{u} $x$ est un r\'{e}el quelconque. Nous admettons (la
d\'{e}monstration vous sera donn\'{e}e peut-être donnée l'ann\'{e}e prochaine) qu'une telle s\'{e}rie converge et que%
$$
\sum\limits_{k=0}^{+\infty }\frac{x^{k}}{k!}={\rm e}^{x},\text{ pour tout }x\text{
r\'{e}el.}
$$


% Une application d'un ensemble $I$ non vide dans un ensemble $E$ est appel%
% \'{e}e, si besoin, famille d'\'{e}l\'{e}ments de E index\'{e}s par $I.$ Si $%
% f(i)=x_{i,}$ la famille est not\'{e}e $(x_{i})_{i\in I}.$

% $(E,+)$ est un mono\"{\i}de\footnote{%
% Cela signifie que $+$ est une loi de composition interne dans $E,$ que $+$
% est associative et qu'elle admet un \'{e}l\'{e}ment neutre not\'{e} $0_{E}.$}
% (additif) et "on travaille" dans $E.$ $\sum\limits_{i=h}^{k}a_{i},$ o\`{u} $%
% h $ et $k$ sont des entiers naturels avec $k\geq h$ obligatoirement$,$ est
% la somme $a_{h}+a_{h+1}+\cdots +a_{k}.$

% Si $(x_{i})_{i\in I}$ est une famille index\'{e}e par $I,$ la somme de tous
% les \'{e}l\'{e}ments de cette famille, si cette somme a un sens\footnote{%
% Cette somme n'aura pas forc\'{e}ment un sens si $I$ est un ensemble infini.}%
% , est $\sum\limits_{i\in I}x_{i}.$

% \begin{exemple}
% $\sum\limits_{i=3}^{5}\frac{7}{i^{2}}=\frac{7}{3^{2}}+\frac{7}{4^{2}}+\frac{7%
% }{5^{2}}$
% \end{exemple}

% \begin{remarque}
% $\sum\limits_{i=5}^{3}\frac{7}{i^{2}}$ n'a pas de sens !
% \end{remarque}

% \begin{remarque}
% Certains acceptent des indices n\'{e}gatifs, par exemple 
% \[
% \sum\limits_{i=-3}^{5}\frac{7}{i^{2}+1}=\frac{7}{\left( -3\right) ^{2}+1}+%
% \frac{7}{\left( -2\right) ^{2}+1}+\cdots +\frac{7}{5^{2}+1} 
% \]%
% mais il est pr\'{e}f\'{e}rable de transformer la somme en 
% \[
% \sum\limits_{i=0}^{3}\frac{7}{\left( -i\right) ^{2}+1}+\sum\limits_{i=1}^{5}%
% \frac{7}{i^{2}+1} 
% \]
% \end{remarque}

% Il est utile de retenir (nous verrons en exercice "le pourquoi" de ces
% formules) :

% \begin{itemize}
% \item $\sum\limits_{i=1}^{n}\left( \sum\limits_{j=1}^{p}a_{i,j}\right)
% =\sum\limits_{j=1}^{p}\left( \sum\limits_{i=1}^{n}a_{i,j}\right) $

% \item $\sum\limits_{i=1}^{n}\left( \sum\limits_{j=1}^{i}a_{i,j}\right)
% =\sum\limits_{j=1}^{n}\left( \sum\limits_{i=j}^{n}a_{i,j}\right) $
% \end{itemize}

% $(E,\cdot )$ est un mono\"{\i}de (multiplicatif) et "on travaille"\ dans $E.$
% $\prod\limits_{i=h}^{k}a_{i},$ o\`{u} $h$ et $k$ sont des entiers naturels
% avec $k\geq h,$ est le produit $a_{h}\cdot a_{h+1}\cdot \cdots \cdot a_{k}.$

% Rappelons qu'une suite r\'{e}elle est une application d'un ensemble
% d'entiers cons\'{e}cutifs $I$ dans $\mathbb{R}.$ Si $u$ est une telle suite, 
% $u_{n}$ ou $u\left( n\right) $ avec $n\in I,$ est un terme de la suite, $%
% u_{n}$ n'est pas une suite, c'est un r\'{e}el ; la suite est not\'{e}e soit $%
% u,$ et on pr\'{e}cise qu'elle est d\'{e}finie sur $I,$ soit $(u_{n})_{n\in
% I}.$ Si $I$ est fini (ou born\'{e}) on dit que la suite est finie sinon on
% dit qu'elle est infinie. Une suite infinie converge ssi $u_{n}$ admet une
% limite finie lorsque $n$ tend vers $+\infty .$ Une suite qui ne converge pas
% diverge. Toute suite croissante et major\'{e}e converge, toute suite d\'{e}%
% croissante et minor\'{e}e converge.

% Une suite $(u_{n})_{n\in I}$ est dite arithm\'{e}tique de raison $r$ ssi
% elle v\'{e}rifie la relation de r\'{e}currence : 
% \[
% u_{n+1}=u_{n}+r 
% \]
% pour tout $n$ et $n+1$ \'{e}l\'{e}ments de $I.$

% Il faut retenir les deux formules fondamentales suivantes :

% \begin{itemize}
% \item $u_{k}=u_{h}+(k-h)r$, avec $h$ et $k$ appartenant \`{a} $I.$

% \item $\sum\limits_{i=h}^{k}u_{i}=\frac{(k-h+1)(u_{h}+u_{k})}{2}$ qui peut
% s'exprimer en fran\c{c}ais courant par : si $S=u_{h}+u_{h+1}+u_{h+2}+\cdots
% +u_{k-1}+u_{k}$ est la somme de termes cons\'{e}cutifs d'une suite arithm%
% \'{e}tique alors 
% \[
% S=\frac{\text{nombre de termes de la somme}\times (\text{le premier terme
% plus le dernier)}}{2} 
% \]
% \end{itemize}

% Une suite $(u_{n})_{n\in I}$ est dite g\'{e}om\'{e}trique de raison $q$ ($%
% q\neq 0)$ ssi elle v\'{e}rifie la relation de r\'{e}currence :

% \[
% u_{n+1}=qu_{n} 
% \]%
% pour tout $n$ et $n+1$ \'{e}l\'{e}ments de $I.$

% Il faut retenir les r\'{e}sultats suivants :

% \begin{itemize}
% \item $u_{k}=q^{k-h}u_{h},$ avec $h$ et $k$ appartenant \`{a} $I.$

% \item $\sum\limits_{i=h}^{k}u_{i}=\frac{u_{h}-qu_{k}}{1-q}=\frac{qu_{k}-u_{h}%
% }{q-1}$ si $q\neq 1$ et qui peut se retenir en fran\c{c}ais courant par : si 
% $S=u_{h}+u_{h+1}+u_{h+2}+\cdots +u_{k-1}+u_{k}$ est la somme de termes cons%
% \'{e}cutifs d'une suite g\'{e}om\'{e}trique de raison $q\neq 1$ alors 
% \[
% S=\frac{\text{premier terme de la somme}-\text{la raison que multiplie le
% dernier terme}}{1-\text{ la raison}} 
% \]

% \item $\lim\limits_{n\rightarrow +\infty }q^{n}=\left\{ 
% \begin{array}{c}
% +\infty \text{ si }q>1 \\ 
% 1\text{ si }q=1 \\ 
% 0\text{ si }\left\vert q\right\vert <1 \\ 
% \text{n'existe pas si }q\leq -1%
% \end{array}%
% \right. $
% \end{itemize}







\section{Logistique dynamique}


\subsection{Présentation du problème}

\ill{Le   mathématicien  Belge  Pierre-François   \textsc{Verhulst}  (28
  octobre 1804 - 15 février  1849) proposa en 1838 un modèle d'évolution
  des  populations  animales  qui  porte  son  nom  et  qui  rompt  avec
  l'habituelle  croissance exponentielle.  On suppose  qu'une population
  vaut  $p_n$  à   un  certain  instant  et  qu'il   existe  une  valeur
  d'équilibre $e$ telle  que la population tend à  y revenir avec autant
  de force  qu'elle s'en écarte.  Il existe donc un  coefficient positif
  $k$ tel que:
$$ \frac{p_{n+1}-p_n}{p_n}=-k(p_n-e)$$
}{Verhulst}


\medskip
\begin{recherche}
Déduisez-en qu'il existe une constante $R \geqslant 1$ telle que: $$ p_{n+1}=Rp_n(1-\frac{k}{R}p_n)$$

puis qu'il  existe une valeur  maximum de la population  $p_{{\rm max}}$
et que : $$ u_{n+1}=R u_n(1-u_n)$$

en notant $u_n$ le rapport $\frac{p_n}{p_{{\rm max}}}$.
\end{recherche}

Depuis  \textsc{Verhulst} on  désigne par  \textit{suite  logistique} ce
type  de  suite.  Il faut  bien  sûr  considérer  la plus  ancienne  des
définition du mot:

\begin{verse}
\textbf{LOGISTIQUE}  n.f. \textbf{1.} (1611)  Anc. nom  de la  partie de
l'algèbre qui traite des quatre règles.
\end{verse}

car nous  n'utiliserons que les quatre opérations  arithmétiques de base
mais n'étudierons pas les problème de ravitaillement des armées.


\begin{recherche}
Dans quel intervalle varie R?
\end{recherche}

Étudier la  suite $(u_n)$,  c'est étudier le  \textit{système dynamique}
défini   par   la   fonction    $f$.   L'ensemble   des   $x$,   $f(x)$,
$f(f(x))$,...,$f^n(x)$,... est appelé l'\textit{orbite} de $x$.

\subsection{Exploration au petit bonheur}

Peut-on  se contenter  d'observer le  comportement d'une  suite? L'outil
informatique permet-il de se passer d'une exploration théorique?

Commençons donc  par explorer  au petit bonheur  le comportement  de ces
suites à l'aide de Python.

\begin{recherche}
  Que fait \mintinline{python}{escargot}? 
Comment interpréter les résultats suivants? 

\end{recherche}

\begin{pythoncode}
import matplotlib.pyplot as plt
import numpy as np

def escargot(R, u0, n) :
    f = lambda x : R*x*(1-x)
    X = np.linspace(0, 1)
    plt.plot(X, X)
    plt.plot(X, f(X))
    Ordo = []
    u = u0
    for k in range(n):
        Ordo += [u,f(u)]
        u = f(u)
    plt.plot([u0] + Ordo, Ordo + [u])
\end{pythoncode}


\begin{pythoncode}
In [9]: escargot(3.2,0.2,100)

In [10]: plt.show()
\end{pythoncode}
  

%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{escargot}
\end{center}
%\end{figure}



En version animée:

\begin{pythoncode}
from matplotlib import animation

fig = plt.figure()
ax = plt.axes()
ligne, = plt.plot([],[])
axe, = plt.plot([],[])
courbe, = plt.plot([],[])
plt.xlim(0,1)
plt.ylim(0,1)
texte = ax.text(0.02, 0.95, '')

def init():
    X = np.linspace(0, 1)
    axe.set_data(X,X)
    courbe.set_data([],[])
    ligne.set_data([],[])
    texte.set_text('')
    return ligne,courbe,axe,texte
    
def anim_escargot(R, u0, n) :
    f = lambda x : R*x*(1-x)
    X = np.linspace(0, 1)
    courbe.set_data(X, f(X))
    texte.set_text('R = %.2f' % R)
    Ordo = []
    u = u0
    for k in range(n):
        Ordo += [u,f(u)]
        u = f(u)
    ligne.set_data([u0] + Ordo, Ordo + [u])
    return ligne,courbe,axe,texte

anim = animation.FuncAnimation(fig, lambda r : anim_escargot(r*0.01,0.2,50),init_func=init,  blit=True, frames=400, interval=60)
\end{pythoncode}







\subsection{Convergence et points fixes}

Vous  connaissez  parfaitement  votre  cours  sur le  rapport  entre  la
convergence des suites définies par une relation $u_{n+1}=f(u_n)$ et les
points fixes de $f$.

Malheureusement,  on  ne  parle  pas  assez du  caractère  attractif  ou
répulsif des points fixes.

À  l'aide du  théorème des  accroissements finis,  on peut  montrer que,
$\ell$ étant un point fixe de $f$:

\begin{itemize}
\item  si  $\left|f'(\ell)\right|<1$, le  point  fixe  est attractif  et
  $(u_n)$ converge vers $\ell$ avec $\left|u_n-\ell\right| \leqslant k^n
  \left|u_0-\ell\right|$ pour un certain $k \in ]0;1[$;
\item si $f'(\ell)=0$,  le point est dit \textit{super  attractif} et la
  suite converge très rapidement;
\item  si  $\left|f'(\ell)\right|>1$,  le  point fixe  est  répulsif  et
  $(u_n)$ ne converge que si elle est constante et égale à
  $\ell$ à partir d'un certain rang;
\item si $\left|f'(\ell)\right|=1$, le cas est litigieux.
\end{itemize}

\begin{recherche}
Mais au fait, ces points fixes, quels sont-ils?

Discuter selon les valeurs de $R$ et commencer à expliquer grossièrement
certains   comportements   observés.    Étudier   en   particulier   \og
l'attractivité\fg{} des points fixes.
\end{recherche}




\subsection{Étude de la convergence dans le cas 1<R<3}

\subsubsection{Cas 1<R<=2}

\begin{recherche}
Traiter le cas $R=2$.

Que peut-on dire du point fixe non nul dans les autres cas? Dans quel intervalle
se trouve-t-il?

Discuter alors selon la position de $u_0$ par rapport à ce point fixe et
à $\frac{1}{R}$
\end{recherche}
\subsubsection{Cas 2<R<3}

Les dessins obtenus avec Python peuvent donner des idées.

\begin{recherche}
Montrer que $I=\left[ \frac{1}{2}  ; \frac{R}{4} \right]$ est stable par
$f$.

En déduire  que si  $u_0\in I$, alors  $(u_{2n})$ puis  $(u_n)$ converge
vers le point fixe non nul.

Étudier ensuite le cas $u_0\in \left]0; \frac{1}{2} \right[$ puis le cas
$u_0\in \left]  \frac{R}{4};1 \right[$ et montrer qu'on  peut se ramener
aux cas précédents.
\end{recherche}


\subsection{Théorème de \textsc{Coppel} et conséquences}

On note $f^n=f\circ f\circ f\circ \cdots \circ f$.

Soit $f~:  I\to I$ une fonction continue.  Soit $x\in I$. Si  $x$ est un
point fixe  de $f^n$  mais n'est pas  un point  fixe de $f^k$  pour tout
$0<k<n$, on dit que $x$ est \textbf{\textit{n}-périodique}.

L'ensemble      $\bigl\{x,f(x),\cdots,f^{n-1}(x)\bigr\}$      est     un
\textbf{\textit{n}-cycle} pour $f$.

Soit $p_0$, $p_1$,...,$p_{n-1}$ un $n$-cycle
On dit qu'il est \textbf{attractif} si $\left|(f^n)'(p_i)\right|<1$ pour
tout entier  naturel $i$  strictement inférieur à  $n$. Dans ce  cas, si
$u_0$ est  suffisamment proche de l'un  des éléments du  cycle, la suite
admet les éléments du cycle comme valeurs d'adhérence.


\begin{theoreme}[Théorème de \textsc{Coppel}]
Soit  $f~:[a,b]\to[a,b]$ une fonction  continue. Si  $f$ n'admet  pas de
2-cycle,   alors,  pour   tout  $u_0\in   I$,  la   suite   définie  par
$u_{n+1}=f(u_n)$ converge.
\end{theoreme}

La  démonstration est assez  longue et  nous ne  nous en  occuperons pas
aujourd'hui.

Nous sommes pourtant en mesure de démontrer l'utile lemme suivant:

\begin{lemme}
Soit $f~:[a,b]\to[a,b]$  une fonction de  classe $\mathscr C^1$.  Si $f$
admet deux points fixes répulsifs consécutifs distincts $\alpha$ et $\beta$ avec
$\alpha<\beta$,  alors il  existe $p_2\in]\alpha,\beta[$  tel  que $p_2$
soit un point fixe de $f^2$.
\end{lemme}


Pour démontrer  ce lemme,  il suffit d'étudier  la fonction  définie sur
$[a,b]$ par  $$g(x)=f^2(x)-x$$ en précisant  en particulier le  signe de
$g'(\alpha)$ et $g'(\beta)$.

\begin{recherche}
Démontrer le lemme.
\end{recherche}



\subsubsection{Cas R=3}

C'est un cas ambigu car dans ce cas $\left|f'(p)\right|=\left|2-3\right|=1$.

Cependant, on peut utiliser  le théorème de \textsc{Coppel} pour montrer
que la suite converge.

\begin{recherche}
Démontrer  la
convergence de la suite $(u_n)$ dans le cas $R=3$.

On pourra utiliser la fonction \mintinline{python}{sympy.solve} 

\end{recherche}


\subsubsection{Cas R>3}

C'est maintenant que ça devient amusant...

\subsubsubsection{Cycles d'ordre 2}

\begin{recherche}
Les points fixes sont maintenant répulsifs: que peut-on en déduire?

Utiliser éventuellement Python pour déterminer les éventuels points fixes
de $f^2$.

Que se passe-t-il lorsque R tend vers 3 par valeurs supérieures?


\end{recherche}


\subsubsubsection{Attractivité des cycles d'ordre 2}

Soit $p_2$ un point fixe de $f^2$ autre que 0 et $p$.
Il faudrait maintenant savoir quand est-ce que le 2-cycle $(p_2,f(p_2))$
est attractif.


\begin{recherche}
 Montrer  que   $(f^2)'(p_2)=-p_2^2+2p_2+4$.  Pour  cela,   montrer  que
 $(f^2)'(p_2)=(f)'(p_2)\cdot f'(f(p_2))$  et utiliser le  fait que $p_2$
 et $f(p_2)$ sont des racines d'un polynôme du second degré introduit au
 paragraphe précédent.


Commenter alors les deux graphiques définis par:

\begin{pythoncode}
In [70]: escargot(0.99+6**0.5,0.5,200)

In [71]: plt.show()

In [72]: escargot(1.01+6**0.5,0.5,200)

In [73]: plt.show()
\end{pythoncode}




\end{recherche}


\subsubsubsection{Cycles d'ordre 4}


Le  2-cycle  cesse  d'être  attractif pour  $R>1+\sqrt{6}$.  D'après  le
théorème de  \textsc{Coppel}, on en  déduit que $f^2$ admet  un 2-cycle,
c'est-à-dire que $f$ admet un 4-cycle: jusqu'à quelle valeur de R?

C'est plus  difficile à déterminer. On peut  regarder graphiquement, par
affinements successifs:


\begin{pythoncode}
rmin = 3.5
rmax = 3.9
nbf = 10000

anim = animation.FuncAnimation(fig, lambda r : anim_escargot(rmin + r/nbf,0.2,100),init_func=init,  blit=True, frames=int((rmax-rmin)*nbf), interval=60)

plt.show()
\end{pythoncode}




\begin{recherche}
  Quel renseignement nous donne ce graphique?
\end{recherche}



\subsection{Théorème de \textsc{Feigenbaum}}


\subsubsection{Diagramme de \textsc{Feigenbaum}}

\begin{pythoncode}
def ucent(r,u0,nb) :
    f = lambda x : r*x*(1-x)
    tmp = 0.2
    for k in range(100) :
        tmp = f(tmp)
    res = []
    for k in range(nb) :
        tmp = f(tmp)
        res.append(tmp)
    return ([r for _ in range(nb)], res)

def feig(r1, r2, pas, u0, nb) :
    for r in (r1 + i*pas for i in range(int((r2-r1)/pas))) :
        X,Y = ucent(r, u0, nb)
        plt.scatter(X,Y,marker='.',s=1)
    plt.show()
\end{pythoncode}



\begin{recherche}
Interpréter le dessin obtenu:


%\begin{figure}
\begin{center}
  \includegraphics[height=12cm]{feig.png}
\end{center}
%\end{figure}



\end{recherche}

\subsubsection{Le théorème}

\ill{On doit au physicien Mitchell \textsc{Feigenbaum} des conjectures qui furent
  prouvées par  la suite par  des mathématiciens, des vrais,  mais c'est
  le  nom du  physicien qui  reste  attaché aux  bifurcations. Voici  un
  condensé des résultats proposé par Daniel \textsc{Perrin}}{feigenbaum}

\begin{theoreme}
Soit  $R_n$ la  borne inférieure  des  R tel  que $f$  admette un  cycle
d'ordre $2^n$.
\begin{itemize}
\item  on a $R_0=0$,  $R_1=3$, $R_2=1+\sqrt{6}$,  $R_3\approx 3,544090$,
  $R_4\approx 3,564407$;
\item la suite  $(R_n)$ est strictement croissante, majorée  par 4. Elle
  converge vers un réel $R_\infty\approx 3,5699456$;
\item Pour  $R_n<R<R_\infty$, $f_R$ admet un unique  $2^n$-cycle qui est
  attractif tant que $R$ est strictement inférieur à $R_{n+1}$;
\item pour $R<R_\infty$, $f_R$ n'a pas de cycle d'ordre $p$ si $p$ n'est
  pas une puissance de 2.
\end{itemize}
\end{theoreme}

Voici qui confirme nos intuitions.




\subsection{Exposant de Lyapounov}

Pour  mesurer  la  sensibilité  d'un système  dynamique  aux  conditions
initiales, on  mesure l'exposant de \textsc{Lyapounov}  introduit par le
mathématicien russe  Alexandre \textsc{Lyapounov} à la  fin du XIX\up{e}
siècle.

On considère une suite définie par la relation $u_{n+1}=f(u_n)$.  Quelle est l'influence d'un
écart $e_0$ sur $u_0$ pour la suite des itérés~?

Après une itération,  l'écart absolu vérifie $|e_1|=|f(u_0+e_0)-f(u_0)|$
et                  l'écart                 relatif                 vaut
$\frac{|e_1|}{|e_0|}=\frac{|f(u_0+e_0)-f(u_0)|}{|e_0|}\approx    f'(u_0)$
pour $|e_0|$ suffisamment petit.


Après $n$ itérations, l'écart relatif vaut 

$$\frac{|e_n|}{|e_0|}=\frac{|e_1|}{|e_0|}\times
\frac{|e_2|}{|e_1|}\times\cdots\times \frac{|e_n|}{|e_{n-1}|}=\prod_{k=1}^nf'(u_{k-1})$$


Si un des écarts devient nul, notre étude est sans intérêt.
Comme effectuer un produit  est une opération coûteuse, informatiquement
parlant, nous allons pouvoir considérer le logarithme de ce produit.

Notre  problème est  de savoir  si les  écarts s'amplifient  et  donc le
produit est supérieur à  1, ou bien si le système est  stable et donc le
produit est inférieur à 1.

$$\prod_{k=1}^nf'(u_{k-1})<1\ssi                          \sum_{k=1}^n\ln
\left(f'(u_{k-1})\right)<0$$

Pour relativiser le rôle du choix de $n$, nous allons normer cette somme
en la divisant par $n$.


On définit alors l'exposant de \textsc{Lyapounov}~:


$$\lambda=\lin \frac{1}{n}\sum_{k=1}^n\ln\left(f'(u_{k-1})\right)$$


\begin{recherche}
  Écrire  une fonction  \verb+lyapounov(u0,R,n)+  qui calcule  une
approximation  numérique de  l'exposant de  Lyapounov qui  dépend  de la
donnée de $u_0$, $R$ et le nombre $n$ d'itérations.


Ensuite, l'utiliser pour représenter l'exposant en fonction de R.

\end{recherche}

% Par exemple, avec $u_0=0,45$ et 50 itérations~:

% % \begin{lstlisting}
% % plot([seq([r*0.001,lyapounov(0.45,r*0.001,50)],r=3000..4000)],view=[-3..4,-3..1]);
% % \end{lstlisting}




% \begin{center}
%   \includegraphics[height=\linewidth,angle=270]{lyapou02}
% \end{center}


% \begin{recherche}
%   Comment interpréter ce graphique~?
% \end{recherche}



\subsection{Prolongements}

Pour  savoir  ce  qui  se   passe  au-delà  de  $R_\infty$,  étudiez  ce
merveilleux document:\\
\href{http://www.math.u-psud.fr/~perrin/Conferences/logistiqueDP.pdf}{http://www.math.u-psud.fr/~perrin/Conferences/logistiqueDP.pdf}
écrit en 2008 par Daniel \textsc{Perrin} de l'Université d'Orsay.








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% EXERCICES
%
%%%%%


\vfill

\eject




% exos sur les sommes sur ancien info2








\modeexercice

\section{EXERCICES}



\begin{exercice}
  On considère que op est une opération à temps constant.

Quelle est la complexité des boucles suivantes:

\begin{multicols}{2}



  \begin{algo}
    \FOR{i}{1}{n}
 \STATE{op}
\ENDFOR
  \end{algo}








\begin{algo}
  \FOR{i}{1}{n*n}
  \FOR{j}{1}{n*3}
  \FOR{k}{1}{n}
  \STATE{op}
  \ENDFOR
  \ENDFOR
  \ENDFOR
\end{algo}





\begin{algo}
 \FOR{i}{1}{n}
 \FOR{j}{1}{n}
 \STATE{op}
\ENDFOR
\FOR{k}{1}{n}
\STATE{op}
\ENDFOR
\ENDFOR
\end{algo}



  \begin{algo}
    \FOR{i}{1}{n}
\FOR{j}{1}{n}
 \STATE{op}
\ENDFOR
\ENDFOR
  \end{algo}




\begin{algo}
  \FOR{i}{1}{n}
  \FOR{j}{1}{n}
  \FOR{k}{1}{n}
  \STATE{op}
  \ENDFOR
  \ENDFOR
  \ENDFOR
\end{algo}


\begin{algo}
 \FOR{i}{1}{n}
 \FOR{j}{1}{90n}
 \STATE{op}
\ENDFOR
\FOR{k}{40n}{1}
\STATE{op}
\ENDFOR
\ENDFOR
\end{algo}


  \begin{algo}
    \FOR{i}{1}{n}
\FOR{j}{1}{i}
 \STATE{op}
\ENDFOR
\ENDFOR
  \end{algo}




\begin{algo}
  \FOR{i}{1}{n}
  \FOR{j}{1}{i}
  \FOR{k}{1}{j}
  \STATE{op}
  \ENDFOR
  \ENDFOR
  \ENDFOR
\end{algo}



\begin{algo}
  \STATE{s\recoit{}0}
  \STATE{i\recoit{}n}
  \WHILE{$\mathtt{i > 0}$}
  \FOR{j}{0}{$\mathtt{i - 1}$}
  \STATE{s\recoit{}$\mathtt{s + 1}$}
  \ENDFOR
  \STATE{i\recoit{}$\mathtt{i\ //\ 2}$}
  \ENDWHILE
  \RETURN{s}
\end{algo}






\begin{algo}
  \STATE{s\recoit{}0}
  \STATE{i\recoit{}1}
  \WHILE{$\mathtt{i < n}$}
  \FOR{j}{0}{$\mathtt{i-1}$}
  \STATE{s\recoit{}$\mathtt{s+1}$}
  \ENDFOR
  \STATE{i\recoit{}$\mathtt{i*2}$}
  \ENDWHILE
  \RETURN{s}
\end{algo}


\begin{algo}
  \STATE{s\recoit{}0}
  \STATE{i\recoit{}1}
  \WHILE{$\mathtt{i < n}$}
  \FOR{j}{0}{$\mathtt{n-1}$}
  \STATE{s\recoit{}$\mathtt{s+1}$}
  \ENDFOR
  \STATE{i\recoit{}$\mathtt{i*2}$}
  \ENDWHILE
  \RETURN{s}
\end{algo}





\end{multicols}

\end{exercice}


 \begin{exercice}[CCP MP 2015]
      
\begin{enumerate}

\item Donnez la décomposition en binaire (base 2) de l'entier 21.

On considère la fonction \texttt{mystere} suivante:

\begin{pythoncode}
def mystere(n, b) :
    """Données : n > 0 un entier et b > 0 un entier
       Résultat : ......."""
    t = [] # tableau vide
    while n > 0 :
        c = n % b
        t.append(c)
        n = n // b
    return t
\end{pythoncode}

On  rappelle  que la  méthode  \texttt{append}  rajoute  un  élément en  fin  de
liste. Si  l'on choisit  par exemple  \texttt{t =  [4,5,6]}, alors,  après avoir
exécuté    \mintinline{python}{t.append(12)},   la    liste   a    pour   valeur
\texttt{[4,5,6,12]}.

Pour $k\in\bbn^\star$, on note $c_k$, $t_k$  et $n_k$ les valeurs prises par les
variables  \texttt{c},  \texttt{t} et  \texttt{n}  à  la  sortie de  la  $k$-ème
itération de la boucle \og while\fg{}.

\item Soit  $n>0$ un  entier. On exécute  \mintinline{python}{mystere(n,10)}. On
  pose $n_0=n$.
  \begin{enumerate}
  \item Justifier la terminaison de la boucle \mintinline{python}{while}. 
  \item   On  note   $p$  le   nombre   d'itérations  lors   de  l'exécution   de
    \mintinline{python}{mystere(n, 10)}. Justifiez que pour tout $k\in\llbracket
    0,  p\rrbracket$,  on  a  $n_k \leqslant  \frac{n}{10^k}$.  Déduisez-en  une
    majoration de $p$ en fonction de $n$.


  \end{enumerate}
\item En vous aidant du script de la fonction \mintinline{python}{mystere},
  écrivez  une   fonction  \mintinline{python}{somme_chiffres}  qui   prend  en
  argument un entier  naturel et renvoie la somme de  ses chiffres. Par exemple,
  \mintinline{python}{somme_chiffres(256)} devra renvoyer 13.
\item     Écrivez      une     version     récursive     de      la     fonction
  \mintinline{python}{somme_chiffres}         que          vous         nommerez
  \mintinline{python}{somme_rec}. 
Est-elle plus efficace?
\item Écrivez une version en Haskell de cette fonction: est-elle plus efficace?
  \end{enumerate}
  \end{exercice}





\begin{exercice}[Maths II CCP MP 2015: sujet 0]

  \begin{enumerate}
  \item Écrire une fonction factorielle qui  prend en argument un entier naturel
    $ n$ et renvoie $ n!$ (on n'accepetra pas bien sûr de réponse utilisant la
    propre fonction factorielle du module math de Python ou Scilab).
  \item Écrire une fonction  \lstinline{seuil} qui prend en argument un  entier $ M$ et renvoie
    le plus petit entier naturel $ n$ tel que $ n!>M$.
  \item Écrire une fonction booléenne nommée \lstinline{est_divisible}, qui pend
    en argument un entier naturel $ n$  et renvoie \lstinline{True} si $ n!$ est
    divisible par $ n+1$ et \lstinline{False} sinon.
  \item On considère la fonction suivante nommée \lstinline{mystere}:
    \begin{pythoncode}
def mystere(n):
    s = 0
    for k in range(1,n+1):
        s = s + factorielle(k)
    return s
    \end{pythoncode}
    \begin{enumerate}
    \item Quelle valeur renvoie \lstinline{mystere(4)}?
    \item Déterminer    le     nombre    de    multiplications    qu'effectue
      \lstinline{mystere(n)}.
    \item Proposer une amélioration du script de la fonction \lstinline{mystere}
      afin d'obtenir une complexité linéaire.
    \end{enumerate}
  \end{enumerate}
\end{exercice}



  \begin{exercice}
Donnez l'ordre de complexité temporelle des fragments de code Java suivants:

\begin{javacode}
int sum = 0;
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++) 
      sum++;  
\end{javacode}

\pause

\begin{javacode}
int sum = 0;
for (int i = 1; i < N; i *= 2)
   for(int j = 0; j < i; j++)
      sum++;  
\end{javacode}

\pause

\begin{javacode}
int sum = 0;
for (int i = 1; i < N; i *= 2)
   for (int j = 0; j < N; j++)
      sum++;  
\end{javacode}

  \end{exercice}



  \begin{exercice}[Tri selectif]
    
On parcourt la liste, on cherche le plus grand et on l'échange avec l'élément le
plus à droite et on recommence avec la liste privée du plus grand élément.



On commence  par chercher l'indice du  maximum d'une liste.  On part de 0  et on
compare à chaque élément  de la liste en faisant évoluer  l'indice du maximum si
nécessaire.

\begin{pythoncode}
def ind_maxi(xs):
    ind_tmp = 0
    n       = len(xs)
    for i in range(n):
        if xs[i] > xs[ind_tmp]:
            ind_tmp = i
    return ind_tmp
\end{pythoncode}


Ensuite, on copie la liste donnée en argument pour ne pas l'écraser. On parcourt
la liste et on  procède aux échanges éventuels entre le  maximum et l'élément de
droite.


\begin{pythoncode}
def tri_select(xs):
    cs = xs.copy()
    n  = len(cs)
    for i in range(n - 1,0,-1):
        i_m = ind_maxi(cs[:i + 1])
        if i_m != i:
            cs[i_m],cs[i] = cs[i],cs[i_m]
        # print(cs) : pour suivre l'évolution
    return cs
\end{pythoncode}

On  va utiliser  \Colorbox{blue!10}{\lstinline{permutation}} de  la bibliothèque
\Colorbox{blue!10}{\lstinline{numpy.random}}   qui   renvoie   une   permutation
uniformément choisie par les permutations de $\mathfrak{S}_n$.

\begin{pythoncode}
In [5]: ls = list(permutation(range(10)))

In [6]: ls
Out[6]: [8, 0, 4, 3, 5, 2, 7, 1, 9, 6]

In [7]: tri_select(ls)
[8, 0, 4, 3, 5, 2, 7, 1, 6, 9]
[6, 0, 4, 3, 5, 2, 7, 1, 8, 9]
[6, 0, 4, 3, 5, 2, 1, 7, 8, 9]
[1, 0, 4, 3, 5, 2, 6, 7, 8, 9]
[1, 0, 4, 3, 2, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Out[7]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
\end{pythoncode}

\begin{enumerate}
\item Il s'agit de démontrer la \textbf{correction} de ces deux fonctions. 

Démontrez que pour la première,  l'invariant  de
boucle est: \og \lstinline{ind_temp}
est   l'indice    du   maximum   des
\lstinline{i + 1} premiers termes de
la liste en argument\fg{}.

Quel est celui de la seconde? Démontrez-le.

\item 
Nous mesurerons la complexité temporelle en
nombre de comparaisons.

Expérimentalement, nous pouvons en avoir une idée:


\begin{pythoncode}
In [10]: ls = list(permutation(100))

In [11]: %timeit tri_select(ls)
1000 loops, best of 3: 561 μs per loop

In [12]: ls = list(permutation(200))

In [13]: %timeit tri_select(ls)
100 loops, best of 3: 2.03 ms per loop

In [14]: ls = list(permutation(400))

In [15]: %timeit tri_select(ls)
100 loops, best of 3: 7.89 ms per loop
\end{pythoncode}



Démontrez-le.



\end{enumerate}

  \end{exercice}



\begin{exercice}[Questions sur le cours]
  Répondez aux questions de la page\vpageref{exo::baby}
\end{exercice}

\begin{exercice}[Dichotomie]
Déterminez la constante asymptotique de la méthode dichotomique.

Déterminez un  algorithme (impératif  et récursif) donnant  l'approximation d'une
solution avec  comme arguments la  fonction $f$,  les bornes de  l'intervalle de
départ $a$ et $b$ et la précision $p$.


Vous  éviterez les  \textit{tant  que}  et les  conditionnelles  basées sur  une
comparaison de flottants par sécurité...

\begin{pythoncode}
*Main> dicho2 (\ x -> x**2 - 2) 1 2 1e-15
1.414213562373095
*Main> sqrt 2
\end{pythoncode}

\end{exercice}


\begin{exercice}[Babylone]
  Existe-t-il un lien entre l'algorithme de Babylone et la méthode de \textsc{Newton-Raphson}?
\end{exercice}


\begin{exercice}[Newton 1]
Répondez aux questions posées dans  les encadré \textit{recherche} de la section
consacrée à la méthode de \textsc{Newton-Raphson}
 
\end{exercice}








\begin{exercice}[Newton 2]
  Programmez cette méthode...On pourra créer une fonction:

  \begin{pythoncode}
newtRaph :: (Fractional a, Ord a) => (a -> a) -> (a -> a) -> a -> a -> a
newtRaph                              f          f'          x    p = ...
  \end{pythoncode}

Et vérifiez par exemple:



\begin{pythoncode}
*Main> newtRaph (\ t -> t**2 - 2) (\ t -> 2*t) 1 1e-15
1.4142135623730951
\end{pythoncode}


Commentez ces résultats:


\begin{pythoncode}
*Main> newtRaph (\ t -> t**3 - t) (\ t -> 3*t**2 - 1) 0.25 1e-15
0.0
*Main> newtRaph (\ t -> t**3 - t) (\ t -> 3*t**2 - 1) 0.5 1e-15
-1.0
*Main> newtRaph (\ t -> t**3 - t) (\ t -> 3*t**2 - 1) (-1/(sqrt 5)) 1e-15
  C-c C-cInterrupted.
\end{pythoncode}

\end{exercice}


\begin{exercice}[Newton 3 : calcul de l'inverse sur machine]
  Utilisez la méthode de \textsc{Newton-Raphson} pour déterminer une approximation de l'inverse d'un flottant sur machine.

  \begin{pythoncode}
*Main> inverse 1.5 1 1e-15
0.6666666666666666
\end{pythoncode}

Pour étudier les problèmes dus aux arrondis, on pourra lire les pages 157 à 167 de \cite{MullerEtAl2010}.

\end{exercice}


\begin{exercice}[Newton 4 : influence de la première approximation]
  
Notons  $ε_n$ l'erreur  relative après  $n$ itérations  par  la méthode
de \textsc{Newton-Raphson} pour calculer $\sqrt{a}$.


Alors         $ε_n=\frac{x_n-\sqrt{a}}{\sqrt{a}}$        et        donc
$x_n=\frac{1+ε_n}{\sqrt{a}}$.                                         Or
$x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$. 


Montrez qu'alors $$ε_{n+1}=\frac{ε_n^2}{2(1+ε_n)}$$

Si  on  est  trop loin  de  la  solution  au  départ, $ε_n$  n'est  pas
négligeable devant 1: comparez  $ε_{n+1}$ et $ε_n$.

Que se passe-t-il sinon?

\end{exercice}




\begin{exercice}[Méthode de la sécante]
  Le calcul de la dérivée peut être embêtant sur machine. Que peut-il se passer si on remplace $f'(x_n)$ par $\dfrac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$?
\end{exercice}






\begin{exercice}[Exponentiations]
On  veut calculer  $x^n$ avec  $n$  un entier  naturel  et $x$  un élément  d'un
ensemble muni d'une loi multiplicative associative.

On pose $p_1=x$ et $p_j=x^j$.

On impose de déterminer un mécanisme qui  calcule $p_i$ si on connait déjà $p_1,
p_2,...,p_{i-1}$ sous la forme:

$$p_i=p_j\cdot p_k\qquad\text{avec } 0 \leqslant j,k \leqslant i-1$$

\begin{enumerate}
\item Donnez un algorithme naïf. Quel est son coût?
\item On écrit  l'exposant en binaire. On  remplace chaque 1 par CX  et chaque 0
  par C. On enlève le premier couple CX (le plus à gauche).

On traduit C par \og mettre au carré\fg{} et X par \og multiplier par $x$\fg{}.

Traduisez  cet   algorithme  de   manière  plus   constructive  et   étudiez  sa
complexité. Vous donnerez une version impérative et une version récursive.
\end{enumerate}
\end{exercice}





\begin{exercice}[Recherches séquentielles et par saut]
Un fichier séquentiel informatisé est schématiquement constitu%
é ainsi, chaque fiche contient


\begin{itemize}
\item \textit{L'adresse }$S$\textit{\ de la fiche suivante si elle existe
sinon }$\func{nil}$\textit{\ pour indiquer la fin du fichier.}

\item \textit{L'adresse }$P$\textit{\ de la fiche précédente si elle
existe sinon }$\func{nil}$\textit{\ pour indiquer qu'il n'y a rien en de\c{c}%
à.}

\item \textit{Une donnée }$D_{i}$\textit{\ alphanumérique}

\item \textit{Une première adresse }$\mathbf{d\acute{e}but}$\textit{\
qui est l'adresse de la première fiche.}
\end{itemize}

Nous supposerons que le fichier est trié suivant l'ordre croissant et
pour simplifier l'étude nous poserons $D_{i}=i$\ (la donnée est é%
gale au numéro de la fiche). Le fichier contient $N$\ fiches. Nous
appellerons temps d'accès à la fiche numéro $i$\ le nombre de
fiches lues en partant de $d\acute{e}but$\ pour arriver à la fiche $i$\
y compris la fiche $i.$\ Ainsi le temps d'accès à la fiche 1 est 1.

\textbf{Recherche séquentielle.}

Pour trouver la fiche $i$\ ($1\leq i\leq N)$\ on part de $d\acute{e}but,$\
on lit les fiches dans l'ordre des numéros jusqu'à obtenir la fiche $%
i.$%
% \[
% \FRAME{itbpF}{10.2846cm}{2.1703cm}{0cm}{}{}{ftp2.wmf}{\special{language
% "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
% "USEDEF";valid_file "F";width 10.2846cm;height 2.1703cm;depth
% 0cm;original-width 10.1594cm;original-height 2.089cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/FTP2.wmf';file-properties "XNPEU";}} 
% \]

Si on cherche successivement les fiches 1,2,3,$\cdots ,N$\ en repartant de $d%
\acute{e}but$\ à chaque fois, quel est le temps moyen d'accès à
une fiche ?

\textbf{Recherche par saut.}

\begin{itemize}
\item \textit{Nous supposerons ici que }$N$\textit{\ est le carré d'un
entier, }$N=a^{2}$\textit{\ (}$a\in N^{\ast }).$\textit{\ Soit }$k$\textit{\
un entier divisant }$N$\textit{\ et supérieur à 1, }$N=kj$\textit{.}

\item \textit{Nous créons un autre fichier dit de n\oe uds }$%
N_{1},N_{2},\ldots ,N_{j}.$

\item \textit{Le départ, noté }\textbf{dép}$,$\textit{\ contient
l'adresse du premier n\oe ud.}

\item \textit{Le premier n\oe ud contient l'adresse de la fiche numéro }$%
k,$\textit{\ la donnée de la fiche numéro }$k$\textit{\ l'adresse
du n\oe ud suivant et l'adresse de la fiche $k-1$.}

\item \textit{Le deuxième n\oe ud contient l'adresse de la fiche numé%
ro }$2k,$\textit{\ la donnée de la fiche numéro 2}$k$\textit{\ 
l'adresse du n\oe ud suivant et de la fiche numéro $2k-1$.}

\item ${\ldots \ldots }$

\item \textit{Le dernier n\oe ud (le }$j^{\grave{e}me})$\textit{\ contient
l'adresse de la fiche numéro }$N,$ et celle de $N-1$, \textit{\ la donnée de la fiche num%
éro }$N$\textit{\ et }$\func{nil}.$%
% \[
% \FRAME{itbpF}{14.3769cm}{4.4482cm}{0cm}{}{}{ftp3.wmf}{\special{language
% "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
% "USEDEF";valid_file "F";width 14.3769cm;height 4.4482cm;depth
% 0cm;original-width 14.2297cm;original-height 4.3515cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/FTP3.wmf';file-properties "XNPEU";}} 
% \]
\end{itemize}

Pour chercher une fiche $i$\ on part de \textbf{dép}, on passe au
premier n\oe ud et on regarde la donnée $\alpha $\ portée par le n%
\oe ud. Si $\alpha <i$\ on passe au n\oe ud suivant, sinon on passe à la
fiche indiquée par le n\oe ud et, si nécessaire, on revient en arri%
ère dans le fichier jusqu'à atteindre la fiche $i.$\ Un temps d'acc%
ès à une fiche sera le nombre de n\oe uds parcourus $+$\ le nombre
de fiches parcourues y compris celle cherchée.

Si on cherche successivement les fiches 1,2,3,$\cdots ,N$\ en repartant de 
\textbf{dép} à chaque fois, on se propose de déterminer le temps
moyen d'accès à une fiche et trouver la valeur de $k$\ qui minimise
ce temps moyen.

\begin{enumerate}
\item Relier la recherche par saut avec la \vref{exo::saut}

\item Déterminer le temps d'accès à la fiche $1$.

\item Déterminer le temps d'accès à la fiche $2$ (si $k>2).$

\item Déterminer le temps d'accès à la fiche $k$.

\item Déterminer le temps d'accès à la fiche $k-1$.

\item Déterminer le temps d'accès à la fiche $k+1.$

\item Déterminer le temps d'accès à la fiche $ik.$

\item Déterminer le temps d'accès à la fiche $N.$

\item Déterminer le temps d'accès à la fiche $j.$

\item Déterminer le temps total d'accès aux fiches du $i^{\grave{e}%
me}$\ paquet.

\item Déterminer le temps total d'accès à toutes les fiches.

\item Déterminer le temps moyen d'accès à une fiche en fonction
de $k$\ et de $N.$

\item Déterminer la valeur de $k$\ qui minimise ce temps moyen.

\item Comparer le temps moyen d'accès à une fiche par une recherche s%
équentielle et une recherche par saut en prenant $N=$\ 10 000 et une unit%
é de temps égale à $10^{-2}s.$
\end{enumerate}


\end{exercice}








\begin{exercice}[Multiplication du paysan russe]




Voici ce qu'apprenaient  les petits soviétiques pour multiplier  deux entiers. Une
variante de cet
algorithme a été retrouvée  sur le papyrus de Rhind datant de  1650 avant JC, le
scribe Ahmes affirmant que cet algorithme était  à l'époque vieux de 350 ans. Il
a survécu en Europe occidentale jusqu'aux travaux de Fibonacci.

%\setindent{0cm}
%\begin{flushleft}
%%\begin{minipage}[t]{5cm}
%\begin{figure}

% \begin{center}
%   \includegraphics[height=5cm]{rhind.jpg}
% \end{center}
  


%\end{figure}
%\end{minipage}
%\end{flushleft}
%\setindent{\indentationcours}
%\vspace{-6.3cm}
%\begin{minipage}[t]{\linewidth}
%\setindent{5cm}
\begin{algo}[numbered]
\FUNC{MULRUSSE}{\pfarg x entier ,y: entier, acc:entier}{entier}
\IF{x==0}
\RETURN{acc}
\ELSE
\IF{x est pair}
\RETURN{MULRUSSE(x/2,y*2,acc)}
\ELSE
\RETURN{MULRUSSE((x-1)/2,y*2,acc+y)}
\ENDIF
\ENDIF
\end{algo}
%\setindent{0cm}
%\end{minipage}

Que vaut \lstinline{acc} au départ?

Écrivez une  version récursive  de cet algorithme  en évitant  l'alternative des
lignes 5 à 9.

Écrivez une version impérative de cet algorithme.

Prouvez la correction de cet algorithme.

Étudiez sa complexité.

\pythonc

En python, \Colorbox{blue!10}{\lstinline{x  >> 1}} décale l'entier  $x$ d'un bit
vers la doite et \Colorbox{blue!10}{\lstinline{x << 1}} décale $x$ d'un bit vers
la gauche en complétant par  un zéro à droite, \Colorbox{blue!10}{\lstinline{x& y}}
renvoie  l'entier  obtenu en  faisant  la  conjonction  logique  bit à  bit  des
représentations  binaires de  $x$ et  $y$ et  \Colorbox{blue!10}{\lstinline{~x}}
renvoie le complément à 1 de $x$.

Ré-écrivez la  multiplication russe en  utilisant que  ces opérations bit  à bit
(pas de division ni de multiplication).
  

\end{exercice}















\begin{exercice}[Schéma de Horner-Ruffini-Holdred-Newton-Al-Tusi-Liu-Hui...]


%\subsection*{Un peu d'histoire...}



%\vspace{-6.2cm}
%\setindent{0cm}
%\begin{flushleft}
%\begin{minipage}[t]{4.2cm}
\begin{multicols}{3}
\begin{figure}
\begin{center}
  \includegraphics[height=3.5cm]{Ruffini}
\caption{Paolo \textsc{Ruffini}\\(1765 - 1822)}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
  \includegraphics[height=3.5cm]{horner}
\caption{William \textsc{Horner}\\(1765 - 1822)}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
  \includegraphics[height=3.5cm]{neuf_chapitres}
\caption{Neuf chapitres sur l'art mathématique}
\end{center}
\end{figure}
\end{multicols}
% \end{minipage}
%\end{flushleft}
%\setindent{\indentationcours}
%\vspace{-5cm}
%\begin{minipage}[t]{\linewidth}


%\end{minipage}

La  méthode que nous  allons voir  porte le  nom du  britannique William
George  \textsc{Horner} (1786  - 1837)  mais  en fait  elle fut  publiée
presque  10  ans  auparavant  par  un  horloger  londonien,  Theophilius
\textsc{Holdred} et simultanément par l'italien Paolo \textsc{Ruffini} (1765 - 1822)
mais fut déjà utilisée par  \textsc{Newton} 150 ans auparavant et par le
chinois \textsc{Zhu  Shije} cinq siècles  plus tôt (vers 1300)  et avant
lui  par le Persan  \textsc{Sharaf al-Din  al-Muzaffar ibn  Muhammad ibn
al-Muzaffar al-Tusi} vers (1100) et avant lui par le
Chinois \textsc{Liu  Hui} (vers 200)  révisant un des  résultats présent
dans \textit{Les Neuf
Chapitres sur l'art mathématique} publié avant la naissance de JC...



Il faut  cependant noter que  \textsc{Ruffini} l'avait employée  en fait
comme  un moyen  de calculer  rapidement le  quotient et  le  reste d'un
polynôme  par $(X-\alpha)$.  



Dans toute  la suite, un  polynôme de dégré  $n$ sera représenté  par le
vecteur de ses coefficients. Par exemple, \texttt{[1 2 3]} correspond au
polynôme $1+2x+3x^2$. 


Prenons   l'exemple   de   $P(x)=3x^5-2x^4+7x^3+2x^2+5x-3$.  Le   calcul
classique nécessite 5 additions et 15 multiplications.




On peut faire pas mal d'économies de calcul en suivant le schéma suivant :

\begin{center}
\begin{arrayl}
P(x)&=&\ds\underbrace{a_nx^n+\cdots+a_2x^2+a_1x}_{\text{on met $x$ en facteur}}+a_0\\
            &=&\left(\ds\underbrace{a_nx^{n-1}+\cdots+a_2x}_{\text{on met $x$ en facteur}}+a_1\right)x+a_0\\
            &=& \cdots\\
            &=& \left(\cdots(((a_nx+a_{n-1})x+a_{n-2})x+a_{n-3})x+\cdots\right)x+a_0\\
\end{arrayl}
\end{center}


Ici   cela   donne   $P(x)=(((((3x)-2)x+7)x+2)x+5)x-3$  c'est-à-dire   5
multiplications et 5 additions. 


 Comparez les
complexités au  pire du calcul de $P(t)$  pour $t\in\bbk$. Vous
prendrez comme \og unité de complexité\fg{} les opérations arithmétiques
de base: \texttt{+ - *}.

Déterminez une  fonction \texttt{horner(P,t)}  qui évalue  le polynôme
\texttt{P} en \texttt{t} selon le schéma de \textsc{Horner}.

\end{exercice}









\begin{exercice}[Local min]
  Write a program that, given an array a[] of N distinct integers, finds a local
  minimum: an index i such that both \texttt{a[i] < a[i-1]} and \texttt{a[i] < a[i+1]} (assuming
  the neighboring entry is in bounds). Your  program should use ~2 lg N compares
  in the worst case.  
\end{exercice}



\begin{exercice}[Bitonic search]
  An array is bitonic  if it is comprised of an  increasing sequence of integers
  followed immediately  by a  decreasing sequence of  integers. Write  a program
  that, given  a bitonic array  of N distinct  \texttt{int} values, determines  whether a
  given integer is  in the array. Your program  should use ~ 3 lg  N compares in
  the worst case. 
\end{exercice}


\begin{exercice}[Floor and ceiling]
  Given a set of  comparable elements, the ceiling of $x$  is the smallest element
  in the set  greater than or equal to  $x$, and the floor is  the largest element
  less than  or equal to $x$.  Suppose you have an  array of N items  in ascending
  order. Give an O(log N) algorithm to find the floor and ceiling of $x$.  
\end{exercice}


\begin{exercice}[Common elements]
  Given two arrays  of N 64-bit integers,  design an algorithm to  print out all
  elements that appear in both lists. The output should be in sorted order. Your
  algorithm should  run in N log  N. Hint: mergesort, mergesort,  merge. Remark:
  not possible to do better than N log N in comparison based model.  
\end{exercice}

\begin{exercice}[Mumixam]
 Given an array  a[] of N real  numbers, design a linear-time  algorithm to find
 the maximum value of a[j] - a[i] where j $\geqslant$  i.  
\end{exercice}

\begin{exercice}[DÉFI]
  Résolvez le problème suivant: \href{http://introcs.cs.princeton.edu/java/assignments/collinear.html}{http://introcs.cs.princeton.edu/java/assignments/collinear.html}
\end{exercice}














\begin{exercice}
On travaille dans $\mathbb{R}.$ Calculer les sommes :
\end{exercice}

\begin{enumerate}
\item $\sum\limits_{i=3}^{6}ij,$ $\sum\limits_{i=0}^{4}i^{2},$ $%
\sum\limits_{k=0}^{4}k^{2},$ $\sum\limits_{j=0}^{4}i^{2},\sum%
\limits_{i=1}^{50}a_{j}$

\item $\sum\limits_{i=1}^{n\geq 1}a,$ $\sum\limits_{i=h}^{n\geq h}a,$ $%
\sum\limits_{i=1}^{n\geq 1}3$

\item $\sum\limits_{1\leq i<j\leq 5}ij,$ $\sum\limits_{1\leq i<j\leq
5}(i+2j) $
\end{enumerate}


\begin{exercice}
On travaille dans $\mathbb{R},$ calculer les sommes $\sum\limits_{i=1}^{n}i,$
$\sum\limits_{i=50}^{100}j,$ $\sum\limits_{i=h}^{k}i,$ $\sum%
\limits_{i=h}^{k}(i+j),$ $\sum\limits_{i=h}^{k}ij,$ $\sum\limits_{i=h}^{k}(%
\alpha i+j)$
\end{exercice}

\begin{exercice}
On consid\`{e}re un tableau de nombres ayant $n$ lignes et $p$ colonnes. Les
lignes sont num\'{e}rot\'{e}es du haut en bas et les colonnes de la gauche
vers la droite. Le nombre se trouvant sur la $i^{\grave{e}me}$ ligne et $j^{%
\grave{e}me}$ colonne est not\'{e} $a_{i,j}$ ou $a_{ij}.$ Par exemple, si $%
n=4$ et $p=3,$ le tableau se pr\'{e}sente par%
\[
\begin{tabular}{|c|c|c|}
\hline
$a_{1,1}$ & $a_{1,2}$ & $a_{1,3}$ \\ \hline
$a_{2,1}$ & $a_{2,2}$ & $a_{2,3}$ \\ \hline
$a_{3,1}$ & $a_{3,2}$ & $a_{3,3}$ \\ \hline
$a_{4,1}$ & $a_{4,2}$ & $a_{4,3}$ \\ \hline
\end{tabular}%
\]%
On note $L_{i}$ la somme des nombres de la ligne num\'{e}ro $i$, $C_{j}$ la
somme des nombres de la colonne $j$ et $T$ la somme de tous les nombres du
tableau.
\end{exercice}

\begin{enumerate}
\item Exprimer $L_{i}$\ et $C_{j}$\ \`{a} l'aide d'un symbole $\sum .$

\item Exprimer $T$\ de deux fa\c{c}ons.
\end{enumerate}

\begin{exercice}
On reprend les notations de l'exercice pr\'{e}c\'{e}dent avec $n=p=5.$
Que calculent les sommes suivantes ? On pourra donner la solution en
grisant les cases du tableau qui correspondent aux nombres intervenant dans
les sommes.%
% \[
% \FRAME{itbpF}{2.7084cm}{2.7084cm}{0cm}{}{}{sommecases1.wmf}{\special%
% {language "Scientific Word";type "GRAPHIC";maintain-aspect-ratio
% TRUE;display "USEDEF";valid_file "F";width 2.7084cm;height 2.7084cm;depth
% 0cm;original-width 2.6228cm;original-height 2.6228cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/SommeCases1.wmf';file-properties "XNPEU";}} 
% \]

\begin{multicols}{3}

\begin{enumerate}
\item $\sum\limits_{i=1}^{5}\sum\limits_{j=1}^{5}a_{ij}$

\item $\sum\limits_{j=1}^{5}\sum\limits_{i=1}^{5}a_{ij}$

\item $\sum\limits_{i=1}^{5}\sum\limits_{j=1}^{i}a_{ij}$

\item $\sum\limits_{j=1}^{5}\sum\limits_{i=1}^{j}a_{ij}$

\item $\sum\limits_{i=1}^{5}\sum\limits_{j\geq i}a_{ij}$

\item $\sum\limits_{i+j=6}a_{ij}$

\item $\sum\limits_{1\leq i<j\leq 5}a_{ij}$
\end{enumerate}

\end{multicols}
\end{exercice}


% \item Exprimer \`{a} l'aide d'un (ou plusieurs) symbole $\sum $\ la somme
% des nombres se trouvant dans les cases gris\'{e}es 
% \[
% \FRAME{itbpF}{2.7084cm}{2.7084cm}{0cm}{}{}{sommecases.wmf}{\special{language
% "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
% "USEDEF";valid_file "F";width 2.7084cm;height 2.7084cm;depth
% 0cm;original-width 2.6228cm;original-height 2.6228cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/SommeCases.wmf';file-properties "XNPEU";}} 
% \]
%\end{enumerate}

\begin{exercice}
Un fichier s\'{e}quentiel informatis\'{e} est sch\'{e}matiquement constitu%
\'{e} ainsi, chaque fiche contient
\end{exercice}

\begin{itemize}
\item \textit{L'adresse }$S$\textit{\ de la fiche suivante si elle existe
sinon }$\func{nil}$\textit{\ pour indiquer la fin du fichier.}

\item \textit{L'adresse }$P$\textit{\ de la fiche pr\'{e}c\'{e}dente si elle
existe sinon }$\func{nil}$\textit{\ pour indiquer qu'il n'y a rien en de\c{c}%
\`{a}.}

\item \textit{Une donn\'{e}e }$D_{i}$\textit{\ alphanum\'{e}rique}

\item \textit{Une premi\`{e}re adresse }$\mathbf{d\acute{e}but}$\textit{\
qui est l'adresse de la premi\`{e}re fiche.}
\end{itemize}

Nous supposerons que le fichier est tri\'{e} suivant l'ordre croissant et
pour simplifier l'\'{e}tude nous poserons $D_{i}=i$\ (la donn\'{e}e est \'{e}%
gale au num\'{e}ro de la fiche). Le fichier contient $N$\ fiches. Nous
appellerons temps d'acc\`{e}s \`{a} la fiche num\'{e}ro $i$\ le nombre de
fiches lues en partant de $d\acute{e}but$\ pour arriver \`{a} la fiche $i$\
y compris la fiche $i.$\ Ainsi le temps d'acc\`{e}s \`{a} la fiche 1 est 1.

\textbf{Recherche s\'{e}quentielle.}

Pour trouver la fiche $i$\ ($1\leq i\leq N)$\ on part de $d\acute{e}but,$\
on lit les fiches dans l'ordre des num\'{e}ros jusqu'\`{a} obtenir la fiche $%
i.$%
% \[
% \FRAME{itbpF}{10.2846cm}{2.1703cm}{0cm}{}{}{ftp2.wmf}{\special{language
% "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
% "USEDEF";valid_file "F";width 10.2846cm;height 2.1703cm;depth
% 0cm;original-width 10.1594cm;original-height 2.089cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/FTP2.wmf';file-properties "XNPEU";}} 
% \]

Si on cherche successivement les fiches 1,2,3,$\cdots ,N$\ en repartant de $d%
\acute{e}but$\ \`{a} chaque fois, quel est le temps moyen d'acc\`{e}s \`{a}
une fiche ?

\textbf{Recherche par saut.}

\begin{itemize}
\item \textit{Nous supposerons ici que }$N$\textit{\ est le carr\'{e} d'un
entier, }$N=a^{2}$\textit{\ (}$a\in N^{\ast }).$\textit{\ Soit }$k$\textit{\
un entier divisant }$N$\textit{\ et sup\'{e}rieur \`{a} 1, }$N=kj$\textit{.}

\item \textit{Nous cr\'{e}ons un autre fichier dit de n\oe uds }$%
N_{1},N_{2},\ldots ,N_{j}.$

\item \textit{Le d\'{e}part, not\'{e} }\textbf{d\'{e}p}$,$\textit{\ contient
l'adresse du premier n\oe ud.}

\item \textit{Le premier n\oe ud contient l'adresse de la fiche num\'{e}ro }$%
k,$\textit{\ la donn\'{e}e de la fiche num\'{e}ro }$k$\textit{\ l'adresse
du n\oe ud suivant et l'adresse de la fiche $k-1$.}

\item \textit{Le deuxi\`{e}me n\oe ud contient l'adresse de la fiche num\'{e}%
ro }$2k,$\textit{\ la donn\'{e}e de la fiche num\'{e}ro 2}$k$\textit{\ 
l'adresse du n\oe ud suivant et de la fiche numéro $2k-1$.}

\item ${\ldots \ldots }$

\item \textit{Le dernier n\oe ud (le }$j^{\grave{e}me})$\textit{\ contient
l'adresse de la fiche num\'{e}ro }$N,$ et celle de $N-1$, \textit{\ la donn\'{e}e de la fiche num%
\'{e}ro }$N$\textit{\ et }$\func{nil}.$%
% \[
% \FRAME{itbpF}{14.3769cm}{4.4482cm}{0cm}{}{}{ftp3.wmf}{\special{language
% "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
% "USEDEF";valid_file "F";width 14.3769cm;height 4.4482cm;depth
% 0cm;original-width 14.2297cm;original-height 4.3515cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/FTP3.wmf';file-properties "XNPEU";}} 
% \]
\end{itemize}

Pour chercher une fiche $i$\ on part de \textbf{d\'{e}p}, on passe au
premier n\oe ud et on regarde la donn\'{e}e $\alpha $\ port\'{e}e par le n%
\oe ud. Si $\alpha <i$\ on passe au n\oe ud suivant, sinon on passe \`{a} la
fiche indiqu\'{e}e par le n\oe ud et, si n\'{e}cessaire, on revient en arri%
\`{e}re dans le fichier jusqu'\`{a} atteindre la fiche $i.$\ Un temps d'acc%
\`{e}s \`{a} une fiche sera le nombre de n\oe uds parcourus $+$\ le nombre
de fiches parcourues y compris celle cherch\'{e}e.

Si on cherche successivement les fiches 1,2,3,$\cdots ,N$\ en repartant de 
\textbf{d\'{e}p} \`{a} chaque fois, on se propose de d\'{e}terminer le temps
moyen d'acc\`{e}s \`{a} une fiche et trouver la valeur de $k$\ qui minimise
ce temps moyen.

\begin{multicols}{2}
\begin{enumerate}
\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $1$.

\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $2$ (si $k>2).$

\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $k$.

\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $k-1$.

\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $k+1.$

\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $ik.$

\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $N.$

\item D\'{e}terminer le temps d'acc\`{e}s \`{a} la fiche $j.$

\item D\'{e}terminer le temps total d'acc\`{e}s aux fiches du $i^{\grave{e}%
me}$\ paquet.

\item D\'{e}terminer le temps total d'acc\`{e}s \`{a} toutes les fiches.

\item D\'{e}terminer le temps moyen d'acc\`{e}s \`{a} une fiche en fonction
de $k$\ et de $N.$

\item D\'{e}terminer la valeur de $k$\ qui minimise ce temps moyen.

\item Comparer le temps moyen d'acc\`{e}s \`{a} une fiche par une recherche s%
\'{e}quentielle et une recherche par saut en prenant $N=10000$ et une unit%
\'{e} de temps \'{e}gale \`{a} $10^{-2}s.$
\end{enumerate}
\end{multicols}

\begin{exercice}[Achille et la tortue]


 Le paradoxe suivant a été imaginé par \textsc{Zénon d'Élée} (490-430 Avant
JC).  Achille fait  une  course avec  la  tortue. Il  part 100  m\`etres
derri\`ere  la tortue,  mais il  va dix  fois plus  vite  qu'elle. Quand
Achille arrive au  point de d\'epart de la tortue,  la tortue a parcouru
10 m\`etres. Pendant qu'Achille parcourt ces 10 mètres, la tortue a avanc\'e
d'un  m\`etre.  Pendant qu'Achille  parcourt  ce  m\`etre,  la tortue  a
avanc\'e  de 10cm...  Puisqu'on  peut r\'eit\'erer  ce raisonnement  \`a
l'infini, Z\'enon conclut qu'Achille ne peut pas d\'epasser la tortue...


Pour   étudier   ce  problème,   nous   aurons   besoin  d'un   résultat
intermédiaire.


Il est assez  simple de démontrer par récurrence,  par exemple, que pour
tout entier $n>1$ et tout réel $x>-1$, on a:

$$(1+x)^n>1+nx \quad (\text{Inégalité de \textsc{Bernoulli}})$$


Qu'en déduisez-vous au sujet de la limite des suites de terme général $q^n$?

Voici la situation:


%\begin{figure}
\begin{center}
  \includegraphics{zenon}
\end{center}
%\end{figure}


 Intéressons-nous d'abord  à la distance  Achille-Tortue. Notons $d_n$
la                                                               distance:
$$d_n=T_n-A_n=T_n-T_{n-1}=\fr{1}{10}(T_{n-1}-A_{n-1})=\fr{1}{10}d_{n-1}$$

La  suite $(d_n)$  est donc  géométrique de  raison $\ofr{1}{10}$  et de
premier       terme       100.        On       en       déduit       que
$d_n=100\times\pa{\fr{1}{10}}^{n-1}$.

 Or
$\ab{\ofr{1}{10}}<1$, donc $\lin\pa{\ofr{1}{10}}^{n-1}=0=\lin d_n$.


Ainsi Achille  va rattrapper la tortue,  mais au bout  d'une infinité de
trajets:~pour le Grec Zénon, la notion d'infini étant \og au-delà du
réel\fg{}; pour  lui Achille ne rattrapera  jamais la tortue,  ce qui est
absurde.  

Intéressons-nous plutôt à  la durée du  trajet d'Achille
pour atteindre la  tortue, en supposant sa vitesse  constante et égale à
$v$.

               Notons               $t_1=\fr{d_1}{v}=\fr{100}{v}$,
$t_2=\fr{d_2}{v}=\fr{1}{10}\fr{d_1}{v}=\fr{1}{10}t_1$, etc. La suite
$(t_n)$ est donc géométrique de raison $\fr{1}{10}$  de premier terme
$t_1=\ofr{100}{v}$,  d'où  $t_n=\fr{100}{v}\pa{\fr{1}{10}}^{n-1}$.  La
durée du trajet est alors:
\begin{center}
\begin{arrayl}                              \tau_n&=&t_1+t_2+\cdots+t_n\\
&=&\fr{100}{v}\pa{1+\fr{1}{10}+\pa{\fr{1}{10}}^2+\cdots+\pa{\fr{1}{10}}^{n-1}}\\
&=&\fr{1000}{9v}\pa{1-\pa{\fr{1}{10}}^n}
\end{arrayl}
\end{center} Nous  venons de voir  qu'Achille atteindra la  tortue quand
$n$ tend vers $+\infty$.  Or nous savons calculer $\lin \tau_n=\fr{1000}{9v}$ qui est un
nombre fini. Achille  va donc effectuer cette infinité  de trajets en un
temps fini égal à $\ofr{1000}{9v}$.\\ Zénon pensait qu'une somme infinie
de  termes strictement  positifs était  nécessairement infinie,  d'où le
paradoxe  à ses  yeux. Il  a fallu  des siècles  à l'esprit  humain pour
dépasser  cette \textit{limite}.  

Vous pouvez donc prouver le petit théorème suivant:

\setindent{\indentationcours}
\begin{theoreme}[Série géométrique]
La  suite  de   terme  général  $$S_n=  \displaystyle\sum_{k=0}^{n}q^n$$
converge si, et seulement si, $\left|q\right|<1$.
Dans ce cas: $$S=
\displaystyle\lim_{n\to +\infty}S_n=\frac{1}{1-q}
$$
\end{theoreme}
\setindent{0mm}
\end{exercice}




\begin{exercice}[Tapis de \textsc{Sierpinski}]
  

Monsieur \textsc{Sierpinski}  avait ramen\'e d'un voyage en Orient un tapis carr\'e de $1$ m\`etre de
c\^ot\'e dont il \'etait tr\`es content. Jusqu'au jour o\`u les mites s'introduisirent chez lui.

En 24 heures, elles d\'evor\`erent dans le tapis un carr\'e de
c\^ot\'e trois fois plus petit, situ\'e exactement au centre du
tapis. En constatant les d\'egats, Monsieur Sierpinski entra dans
une col\`ere noire~! Puis il se consola en se disant qu'il lui
restait huit petits carr\'es de tapis, chacun de la taille du
carr\'e disparu. Malheureusement, dans les 12 heures qui
suivirent, les mites avaient attaqu\'e les huit petits carr\'es
restants~: dans chacun, elles avaient mang\'e un carr\'e central
encore trois fois plus petit. Et dans les 6 heures suivantes elles
grignot\`erent encore le carr\'e central de chacun des tout petits
carr\'es restants. Et l'histoire se r\'ep\'eta, encore et encore~;
\`a chaque \'etape, qui se d\'eroulait dans un intervalle de temps
deux fois plus petit que l'\'etape pr\'ec\'edente, les mites
faisaient des trous de taille trois fois plus petite...

\begin{enumerate} \item Faire des dessins pour bien comprendre la g\'eom\'etrie du tapis trou\'e.
 Calculer le nombre total de trous dans le tapis de Monsieur Sierpinski
apr\`es $n$ \'etapes. Calculer la surface $S_n$ de tapis qui n'a
pas encore \'et\'e mang\'ee apr\`es $n$ \'etapes. Trouver la
limite de la suite $(S_n)_{n \geq 0}$. Que reste-t-il du tapis \`a
la fin de l'histoire~?

\item Calculer la dur\'ee totale du festin \og mitique\fg{}...


\end{enumerate}



\end{exercice}




\begin{exercice}
$\left\vert x\right\vert <1$ et on note $S_{n}\left( x\right)
=\sum\limits_{k=0}^{n}x^{k},\sigma _{n}\left( x\right)
=\sum\limits_{k=0}^{n}kx^{k}=\sum\limits_{k=1}^{n}kx^{k}.$
\end{exercice}

\begin{multicols}{2}
\begin{enumerate}
\item Calculer $S_{n}^{\prime }\left( x\right) .$

\item Calculer $\sum\limits_{k=0}^{+\infty }x^{k}.$

\item Calculer la limite de $S_{n}^{\prime }\left( x\right) $ lorsque $n$
tend vers $+\infty .$

\item Exprimer $\sigma _{n}\left( x\right) $\ \`{a} l'aide de $S_{n}\left(
x\right) .$

\item Calculer $\sum\limits_{k=0}^{+\infty }kx^{k}.$
\end{enumerate}
\end{multicols}

\begin{exercice}
On note $\Pr \left( \left[ X=k\right] \right) =\dfrac{\lambda ^{k}}{k!}%
e^{-\lambda }.$ Calculer
\end{exercice}

\begin{multicols}{2}
\begin{enumerate}
\item $E\left( X\right) =\sum\limits_{k=0}^{+\infty }k\Pr \left( \left[ X=k%
\right] \right) .$

\item $E\left( X^{2}\right) =\sum\limits_{k=0}^{+\infty }k^{2}\Pr \left( %
\left[ X=k\right] \right) .$

\item $E\left( X^{2}\right) -E\left( X\right) ^{2}.$
\end{enumerate}
\end{multicols}


\begin{exercice}
On note $\Pr \left( \left[ X=k\right] \right) =p(1-p)^{k-1}$ avec $p\in %
\left] 0,1\right[ .$ Calculer $\sum\limits_{k=1}^{+\infty }\Pr \left( \left[
X=k\right] \right) $ et $\sum\limits_{k=1}^{+\infty }k\Pr \left( \left[ X=k%
\right] \right) .$
\end{exercice}





%7
\begin{exercice}
  On considère le tableau $A=(a_{ij})=
 \left[ \begin{smallmatrix}
    1&2&-2&4&0\\
    0&1&2&-2&4\\
    4&0&1&2&-2\\
    -2&4&0&1&2\\
    2&-2&4&0&1
  \end{smallmatrix}\right]$.
Calculez:


{\small
\begin{multicols}{3}
\begin{enumerate}
\item $S_1=\sum\limits_{i=1}^{5}\sum\limits_{j=1}^{5}a_{ij}$

\item $S_2=\sum\limits_{j=1}^{5}\sum\limits_{i=1}^{5}a_{ij}$

\item $S_3=\sum\limits_{i=1}^{5}\sum\limits_{j=1}^{i}a_{ij}$

\item $S_4=\sum\limits_{j=1}^{5}\sum\limits_{i=1}^{j}a_{ij}$

\item $S_5=\sum\limits_{i=1}^{5}\sum\limits_{j\geq i}a_{ij}$

\item $S_6=\sum\limits_{i+j=6}a_{ij}$

\item $S_7=\sum\limits_{1\leq i<j\leq 5}a_{ij}$
\end{enumerate}
\end{multicols}
}
\end{exercice}


%8
\begin{exercice}
  Donnez   une    expression   la   plus   simple    possible   de   $
  \displaystyle\sum_{i=p}^{i=s-1}\left(k×i+ \frac{h(h-1)}{2}\right) $ sans symbole $\Sigma$, ni $\cdots$.
\end{exercice}



\begin{exercice}
On travaille  dans $\mathbb{R}.$ Calculer les sommes  le plus simplement
possible sans utiliser ni $\sum$ ni $...$:

\begin{multicols}{3}


 $S_1=\sum\limits_{i=3}^{6}ij$ 




 $S_{10}=\sum\limits_{1\leq i<j\leq 5}(i+2j) $


$S_{11}=\sum\limits_{i=1}^{n}i$


 $S_{100}=\sum\limits_{i=h}^{k}i$

 $S_{101}=\sum\limits_{i=h}^{k}(i+j)$

 $S_{110}=\sum\limits_{i=h}^{k}ij$


\end{multicols}


\end{exercice}




\begin{exercice}[DS]
  On considère la fonction u définie par:

\begin{pythoncode}
u(n) = pliage(lambda x, k : (x + 4 / x) * 0.5, range(1, n + 1), 2.5)
\end{pythoncode}
  


  \begin{enumerate}
  \item Traduisez cette fonction par une boucle \textit{pour} en pseudo-langage.
  \item  Traduisez cette  fonction sous  forme d'une  suite $(u_n)$  définie par
    récurrence.
  \item Démontrez  que, pour tout entier  naturel, $u_n \geqslant
    2$.
  \item Démontrez que la suite $(u_n)$ est décroissante.
  \item Déduisez-en le rôle de la fonction Python u.
  \end{enumerate}
\end{exercice}

\begin{exercice}[DS]
Le code C suivant...


\begin{ccode}
#include <stdio.h>
#include <float.h>
double truc(double x) {
  return x >= 0 ? x : -x;
}
double mystere(double t) {
  double d, x = 1;
  if (!t) return 0;
  if (t < 0) return 0./0.; 
  
  do {	d = (t / x - x) / 2;
    x+= d;
    printf("%1.20f, %1.20f\n",x,d);
  } while (truc(d) >= truc(x) * (DBL_EPSILON * 10));
  
  return x;
} 
int main() {
  double x = 2;
  printf("mystere(%g) = %1.15f\neps = %1.20f\n", x, mystere(x),DBL_EPSILON);
  return 0;
}
\end{ccode}


...affiche:

\lstset{
 language=bash,
        escapeinside={(*@}{@*)},
        %numbers=left,
        basicstyle={\small\ttfamily},
        commentstyle={\small\itshape\color{pink!60!black}},
        keywordstyle={\ttfamily\bfseries\fontfamily{ul9}\selectfont\color{black!60!blue}},
        stringstyle={\small\ttfamily\color{gray!50!black}\itshape},
        breaklines=true,
        breakatwhitespace=true,
        showtabs=False,
        showspaces=False,
        showstringspaces=False,
        extendedchars=true,
        %aboveskip=1em,
        %belowskip=1em,
        rulecolor=\color{gray},
        %rulesepcolor=\color{gray},
        %frame=trBL,
        frame=single,
        frameround=tttt,
        framerule=0.3pt,
        framesep=4pt,
        belowcaptionskip=2.1pt,
        literate={μ}{{$\mu $}}1,
title={{\setlength{\fboxsep}{1pt}\fcolorbox{gray}{gray!10}{\sffamily\scriptsize
      \textcolor{gray!10}{\_}Shell \textcolor{gray!10}{\_}}}}}

\begin{multicols}{2}
\begin{lstlisting}
1.50000000000000000000, 0.50000000000000000000
1.41666666666666651864, -0.08333333333333337034
1.41421568627450966460, -0.00245098039215674302
1.41421356237468986983, -0.00000212389981979477
\end{lstlisting}

\begin{lstlisting}
1.41421356237309492343, -0.00000000000159483537
1.41421356237309492343, 0.00000000000000011102
mystere(2) = 1.414213562373095
 eps = 0.00000000000000022204
\end{lstlisting}
\end{multicols}

En vous appuyant sur les résultats donnés  dans le chapitre 3 du poly, expliquez
ce que font les  fonctions truc et mystere, quels sont  les rôles des paramètres
et variables t, d et x, le rôle de  la ligne 9 et la signification du test de la
ligne 14.

\end{exercice}

\modenormal
%%% Local Variables: 
%%% TeX-master: "PolyAnalyse16py"
%%% End: 
