%Last modified: <iut_asymptotic.tex modifié par  Guillaume Connan le dimanche 4 décembre 2011 à 21h 15min 44s>
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\chapterimage{concrete-book}
\chaptertext{On distingue les  mathématiques CONtinues des mathématiques
  disCRÈTES.  Les  premières  correspondent   à  celles  que  vous  avez
  découvertes   au  lycée   avec  le   calcul   différentiel  (dérivées,
  intégrales)  alors que les  secondes correspondent  à celles  que vous
  avez  étudiées  jusqu'à  maintenant  à l'IUT  (suites,  arithmétiques,
  dénombrement, graphes,  automates,...). Nous allons  dans cette partie
  les  lier plus  étroitement: l'informaticien  doit en  effet  faire le
  lien entre  l'univers physique  qui l'entoure qui  est continu  et la
  mémoire de son ordinateur qui  est discrète. C'est la même distinction
  que l'on fait entre un système analogique (une montre à gousset) et un
  système digital (une montre à affichage par cristaux liquides).}


%\modeexercice % entre en mode exercice
\chapter{Mathématiques concrètes}

\section{Complexité d'algorithmes}

Nous avons déjà parlé de la  complexité du calcul du déterminant avec la
définition  et avec  la méthode  du  pivot de  \textsc{Gauss}: pour  une
matrice de  taille 30 on peut  effecteur le calcul  en quelques secondes
dans un cas et en quelques milliards d'années dans l'autre: ce n'est pas
un détail de s'occuper de la complexité d'un algorithme...

\medskip

Cela demande souvent une certaine agilité en calcul!...

Vous  avez  étudié  le tri  fusion  l'an  passé.  En voici  une  version
pythonesque:

\begin{lstlisting}[caption={}]
def divise(liste):
    n = len(liste)
    if n == 0:
        return [],[]
    return liste[: n//2], liste[n//2:]

def fusionner(L1,L2):
    if len(L1) == 0:
        return L2
    if len(L2) == 0:
        return L1
    if L1[0] < L2[0]:
        return ([L1[0]] + fusionner(L1[1:],L2))
    else:
        return ([L2[0]] + fusionner(L2[1:],L1))
    
def tri_f(L):
    if len(L) == 1:
        return L
    return fusionner(tri_f(divise(L)[0]),tri_f(divise(L)[1]))
\end{lstlisting}




Nous  allons étudier  la  complexité temporelle  de  cet algorithme.  La
complexité spatiale est en effet tombée en désuétude quand une modeste clé USB
à  cinq  euros contient  en  mémoire ce  qui  tenait  dans des  armoires
occupant plusieurs étages d'un immeuble  dans les années 1970 et coûtait
le prix d'un château... 

Soit $n$ la longueur de la liste à trier. 
Le  coût  de  la  division  est  constant et  celui  de  la  fusion  est
proportionnel à $n$.  Il faut ensuite ajouter le coût de la fusion des deux
sous-listes issues des appels récursifs.

Appelons $K$ la fonction coût associé au tri par fusion, alors:

$$
\begin{cases}
K(0)=K(1)=0\\
K(n)=K    \left(\lceil    \frac{n}{2}   \rceil\right)+K    \left(\lfloor
  \frac{n}{2} \rfloor\right)+cn
\end{cases}
$$

Posons  $u_n=K(n)$.  La  récurrence  définissant la  suite  $(u_n)$  est
compliquée mais, comme pour la dichotomie, nous 
allons l'étudier dans le cas particulier où $n$ est une puissance de 2.
On peut toutefois montrer rapidement par récurrence que la suite $(u_n)$
est croissante.



Posons maintenant $n=2^k$ et $u_n=u_{2^k}=x_k$, alors
$ x_0=0$ et, pour $k\in\bbn^*$, $x_k=2x_{k-1}+2^{k}c$. On obtient successivement:

$$x_k=2 \left(2x_{k-2}+2^k\right)+c2^{k}=2 \left(2 \left(2x_{k-3}+2^{k-1}\right)+2^k\right)+c2^{k}$$
On montre  alors par récurrence  que $$x_k=2^{k}x_0+(k-1)\cdot 2^{k+1}+c2^k=(k-1+c/2)\cdot
2^{k+1}$$


Or, pour tout entier  $n$ non nul, $$2^{\lfloor \log_2(n)\rfloor} \leqslant
n \leqslant 2^{\lfloor \log_2(n)\rfloor+1}$$ donc

$$
2^{\lfloor \log_2(n)\rfloor+1}(\lfloor \log_2(n)\rfloor-1+c/2) \leqslant K(n) \leqslant 2^{\lfloor \log_2(n)\rfloor+2}\left(\lfloor \log_2(n)\rfloor+c/2\right)
$$

c'est-à-dire


$$2n(\lfloor \log_2(n)\rfloor-1+c/2) \leqslant K(n) \leqslant 4n \left(\lfloor \log_2(n)\rfloor+c/2\right)$$


Par  exemple, si  on prend  $c=2$ et  qu'on travaille  sur une  liste de
taille $\numprint{10000}$, alors:

$$\numprint{265600}=\numprint{20000}\times 13,28\leqslant K(\numprint{10000})\leqslant 40000(13,28+1)=\numprint{571200}$$

Pour avoir un ordre de comparaison,  si l'on prend le tri par insertion,
dans      le      pire     des      cas,      il     faut      effectuer
$n+(n-1)+(n-2)+\cdots+2+1=\frac{n(n+1)}{2}$  comparaisons,  ce qui  nous
donne  pour  une  liste   de  taille  $\numprint{10000}$,  au  pire  une
complexité de l'ordre de $\numprint{100000000}$.


Si l'on  effectue $10^6$ opérations élémentaires par  seconde, il faudra
donc moins d'une seconde pour trier  dans un cas et presque deux minutes
dans l'autre: il n'y a pas photo...


On voit bien cependant qu'on ne peut prévoir au millième de seconde près
ce qui va se passer: on se contente d'un ordre de grandeur. Il nous faut
donc un critère pour comparer les ordres de grandeurs de fonctions.



\section{Relations de domination}


\begin{quote}
  {\it Brooks's Law [prov.]

\og Adding manpower to a late software project makes it later\fg{} -- a result
of  the fact that  the expected  advantage from  splitting work  among N
programmers is $O(N)$, but the complexity and
communications cost associated with  coordinating and then merging their
work is $O(N^2)$}
\begin{flushright}
  in \og The New Hacker's Dictionnary\fg{}\\
\href{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}
\end{flushright}
\end{quote}

Les notations  de \textsc{Landau}(1877-1938) ont  en fait été  crées par
Paul 
\textsc{Bachmann}(1837-1920) en 1894, mais bon, ce sont tous deux des 
mathématiciens allemands.

Par exemple, si l'on considère l'expression: $$f(n)=n+1+\frac{1}{n}+\frac{75}{n^2}-\frac{765}{n^3}+\frac{\cos(12)}{n^{37}}-\frac{\sqrt{\numprint{765481}}}{n^{412}}$$


Quand  $n$  est  \og  grand\fg{}, disons  $\numprint{10000}$,  alors  on
obtient:

$$f(\numprint{10000})=\numprint{10000}+1+0,0001+0,00000000075-0,0000000000000765+{\rm
  peanuts}$$

Tous les  termes après  $n$ comptent  pour du beurre  quand $n$  est \og
grand\fg{}.  Donnons une définition pour plus de clarté:

\begin{definition}[\og Grand O\fg{}]
Soit $f$ et $g$ deux fonctions  de $\bbn$ dans $\bbr$. On dit que $f$
est un \og grand O\fg{} de $g$ et on note $f=O(g)$ ou $f(n)=O(g(n))$ si,
et  seulement si,  il existe  une constante positive C telle  que $|f(n)|\leqslant
C|g(n)|$ pour tout $n\in \bbn$.
\end{definition}



Dans  l'exemple précédent,  $\frac{1}{n} \leqslant  \frac{1}{1}\times 1$
pour tout entier $n$ supérieur à 1
donc $\frac{1}{n}=O(1)$.

De   même,  $\frac{75}{n^2}   \leqslant  \frac{75}{1^2}\times   1$  donc
$\frac{75}{n^2}=O(1)$ mais on peut dire mieux:
 $\frac{75}{n^2}\leqslant  \frac{75}{1}\times\frac{1}{n}$  et  ainsi  on
 prouve que $\frac{75}{n^2}=O \left(\frac{1}{n}\right)$.

En fait, un grand  O de $g$ est une fonction qui  est au maximum majorée
par un multiple de $g$.

Point  de vue  algorithmique, cela  nous donne  un renseignement  sur la
complexité au pire.

Pour  le   tri  fusion,  on  obtient  pour   $n>1$:  $$K(n)\leqslant  4n
\left(\lfloor                        \log_2(n)\rfloor+c/2\right)\leqslant
4n\log_2(n)\left(1+\frac{c}{2\log_2(n)}\right) \leqslant 4\left(1+\frac{c}{2}\right)n\log_2(n)$$

On en déduit que $K(n)=O(n\log_2(n))$: la complexité est au pire en
$n\log_2(n)$,  c'est ce  qui nous  importe. Le  rôle des  constantes est
accessoire  car  chercher trop  de  précisions  serait illusoire:  l'\og
oubli\fg{}  de ces constantes  correspond en  fait au  différences entre
langages, processeurs, etc.

On peut  cependant faire  mieux avec le  tri fusion  car on a  aussi une
minoration.

C'est le moment d'introduire une nouvelle définition:

\begin{definition}[\og Grand Oméga\fg{}]
  Soit $f$ et $g$ deux fonctions  de $\bbr$ dans lui-même. On dit que $f$
est un \og grand Oméga\fg{} de $g$ et on note $f=\Omega(g)$ ou $f(n)=\Omega(g(n))$ si,
et  seulement si,  il existe  une constante positive C telle  que $|f(n)|\geqslant
C|g(n)|$ pour tout $n\in \bbn^*$.
\end{definition}

\begin{remarque}
Comme   $\Omega$  est   une  lettre   grecque,  on   peut,   par  esprit
d'unification, parler de \og grand omicron\fg{} au lieu de \og grand O\fg{}...
\end{remarque}

\begin{remarque}
   $f=\Omega(g)\Longleftrightarrow g=O(f)$...
\end{remarque}


On    montre    donc    facilement    pour    le    tri    fusion    que
$K(n)=\Omega(n\log_2(n))$     grâce     à    l'inégalité     $2n(\lfloor
\log_2(n)\rfloor-1+c/2) \leqslant K(n)$.


Ainsi   on  a   dans  ce   cas  en   même  temps   $f=O(n\log_2(n))$  et
$f=\Omega(n\log_2(n))$:  c'est  encore  plus  précis et  nous  incite  à
introduire une nouvelle définition:

\begin{definition}[\og Grand Théta\fg{}]
$$f=\Theta(g)\Longleftrightarrow
\begin{cases}
  f=O(g)\\ f=\Omega(g)
\end{cases}
$$
\end{definition}

Le coût de l'algorithme se trouve donc coincé entre deux valeurs de même
ordre.  On peut  ainsi  dire que  la  complexité du  tri  fusion est  en
$n\log_2(n)$ ce qui  est \textit{souvent} mieux que le tri  par insertion dont la
complexité \textit{au  pire} est  en $n^2$. Mais  attention! \textit{Au  pire} ne
signifie pas \textit{toujours}:  si la liste est déjà  triée, le tri par
insertion est plus économique.


Voici maintenant une petite table pour illustrer les différentes classes
de complexité rencontrées habituellement:

\begin{center}
             \begin{tabularx}{\linewidth}{Y{3}}
	     \whline
             \backslashbox{coût}{$n$}&100&$\numprint{1000}$&$10^6$&$10^9$\\
             \whline
             $\log_2(n)$&$\approx7$&$\approx10$&$\approx 20$&$\approx 30$\\
             \hline
             $n\log_2(n)$&$\approx 665$&$\approx \numprint{10000}$&$\approx  2\cdot  10^{7}$&$\approx 3\cdot 10^{10}$\\
             \hline
             $n^2$&$10^4$&$10^6$&$10^{12}$&$10^{18}$\\
             \hline
             $n^3$&$10^6$&$10^9$&$10^{18}$&$10^{27}$\\
             \hline
             $2^n$&$\approx 10^{30}$&$>10^{300}$&$>10^{10^5}$&$>10^{10^8}$\\
             \whline
             \end{tabularx}
             \end{center}

Gardez en tête que l'âge de l'Univers est environ de $10^{18}$ secondes...


Il existe  également deux autres \og comparateurs\fg{}  que l'on utilise
peu  en algorithmique  mais qui  peuvent s'avérer  utiles  dans d'autres
domaines.

\begin{definition}[\og Petit o\fg{}]
$f=o(g)$ si, et seulement  si, pour toute constante positive $\varepsilon$,
il existe un entier $n_0$ tel 
que, pour tout $n \geqslant n_0$, $\left|f(n)\right| \leqslant \varepsilon\left|g(n)\right|$
\end{definition}


On dit alors souvent que $f$ est \textit{négligeable} devant $g$.


Contrairement au  grand O, la majoration  doit se faire  quelque soit la
constante $\varepsilon$ et non pas seulement pour une constante arbitraire.

\begin{definition}[Fonctions équivalentes]
  $f(n)\sim g(n)\Longleftrightarrow f(n)=g(n)+o \left(g(n)\right)$
\end{definition}

Voici  quelques   propriétés  fort   utiles  que  nous   démontrerons  à
l'occasion:

\begin{proprietes}[Manipulation des O]
  \begin{itemize}
  \item $O(f)+O(g)=O(f+g)$;
\item $f=O(f)$;
\item $k\cdot O(f)=O(f)$ si $k$ est une constante;
\item $O \left(O(f)\right)=O(f)$;
\item $O(f)\cdot O(g)=O(f\cdot g)$;
\item $O(f\cdot g)=f\cdot O(g)$.
  \end{itemize}
\end{proprietes}

Par exemple, $2n^3+3n^2+5n=O(n^3)+O(n^3)+O(n^3)=O(n^3)$.

Voici quelques résultats  que nous ne démontrerons pas  mais qui s'avère
utile de connaître:

\hrulefill

{\centering \textbf{Approximations asymptotiques quand  \textit{n} tend vers l'infini ou
quand \textit{x} tend vers 0}}

\hrulefill


$\displaystyle n!  = \sqrt{2\pi n}
\left(\frac{n}{\mathrm{e}^{}}\right)\left(1+\frac{1}{12n}+\frac{1}{288n^2}+O
\frac{1}{n^3}\right)$


$\displaystyle \mathrm{e}^{x}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+O(x^5)$

$\displaystyle\ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+O(x^5)$

$\displaystyle\frac{1}{1-x}=1+x+x^2+x^3+x^4+O(x^5)$

$\displaystyle(1+x)^\alpha=1+\alpha   x+{\alpha   \choose  2}x^2+{\alpha
  \choose 3}x^3+{\alpha \choose 4}x^4+O(x^5)$

\hrulefill

\section{L'infini à portée de main}


\subsection{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.

\subsection{Inégalité de \textsc{Bernoulli}}

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$$


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

\subsection{Le retour d'Achille}

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:


\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}




\section{Calcul différentiel et informatique}




\subsection{Le problème}


Rappelons la définition que vous connaissez bien:

\begin{definition}[Dérivabilité]
Soit $f$ une fonction numérique définie sur un intervalle I de $\bbr$.

Soit $a\in I$. On dit que $f$  est dérivable en $a$ si, et seulement si,
le rapport:

$$\tau_a(h)=\frac{f(a+h)-f(a)}{h}$$
admet une limite finie lorsque $a$ tend vers 0.

Dans ce cas on note $f'(a)$ cette limite.

\end{definition}


Rappelons que $f'(a)$ est aussi  le coefficient directeur de la tangente
à la courbe représentative de $f$ au point d'abscisse $a$.

\begin{theoreme}
Si    $f$    est    dérivable     en    $a$    avec    $f'(a)\neq    0$,
alors $$f(x)-f(a)\underset{a}{\sim}f'(a)\times (x-a)$$
\end{theoreme}

Vous pourrez le démontrer en TD.


\begin{definition}[D\'{e}riv\'{e}e $k^{\grave{e}me}$]

Si $f^{\prime }$ est d\'{e}rivable sur $I$ on note $f^{\prime \prime }$ ou $%
f^{(2)}$ la d\'{e}riv\'{e}e de $f^{\prime }$ et on l'appelle la d\'{e}riv%
\'{e}e seconde de $f.$ De m\^{e}me si $f^{\prime \prime }$ est d\'{e}rivable
sur $I,$ $f^{\prime \prime \prime }$ ou $f^{(3)},$ la d\'{e}riv\'{e}e de $%
f^{\prime \prime },$ est la d\'{e}riv\'{e}e troisi\`{e}me de $f.$ Plus g\'{e}%
n\'{e}ralement on note $f^{(k)}$ la d\'{e}riv\'{e}e $k^{i\grave{e}me}$ de $f$
avec la convention $f^{(0)}=f,$ $f^{(k+1)}=\left( f^{(k)}\right) ^{\prime }.$

\end{definition}


\begin{definition}[Fonctions de classe $\mathcal{C}^{n},$ de classe $\mathcal{C}%
^{\infty }$]

On dit que $f$ est de classe $\mathcal{C}^{n},$ $n\in \mathbb{N},$ sur $I$
ssi $f$ est $n$ fois d\'{e}rivable et ses $n$ d\'{e}riv\'{e}es sont
continues sur $I.$ On remarquera que si $f^{(n+1)}$ existe sur $I$ alors $f$
est de classe $\mathcal{C}^{n}$ sur $I$ qui s'\'{e}crit $f\in \mathcal{C}%
^{n}(I).$ On dit que $f$ est de classe $\mathcal{C}^{\infty }$ sur $I$ pour
exprimer que $f$ est ind\'{e}finiment d\'{e}rivable et, a fortiori, que
toutes ses d\'{e}riv\'{e}es sont continues.

\end{definition}



On  peut alors  chercher à  obtenir  une approximation  numérique de  la
dérivée de certaines fonctions avec un ordinateur:

\begin{lstlisting}[caption={}]
def diff(f,h):
    def fp(x):
        return (f(x+h) - f(x))/h
    return fp
\end{lstlisting}

Notez bien  qu'il s'agit ici de  programmation qui à une  fonction et un
réel associe une fonction.

Si  on veut  connaître  le nombre  dérivé  de $x\mapsto  x^2$  en 1,  on
obtient:

\begin{lstlisting}[caption={}]
>>> def g(x):
    return x**2

>>> diff(g,1e-10)(1)
2.000000165480742
\end{lstlisting}

Notez bien le double parenthésage!


Nous allons maintenant essayer d'enchaîner les dérivations:

\begin{lstlisting}[caption={}]
def diffn(f,h,n):
    if n == 0:
        return f
    else:
        return diff(diffn(f,h,n-1),h)
\end{lstlisting}

Essayons avec  l'exponentielle dont  la  dérivée est
assez  simple  puisque c'est  elle-même.  On  ne  devrait pas  noter  de
différences au fur et à mesure des dérivations:

\begin{lstlisting}[caption={}]
>>> from math import exp
>>> diff(exp,1e-5)(0)
1.000005000006965
>>> diffn(exp,1e-5,2)(0)
1.0000111849706173
>>> diffn(exp,1e-5,3)(0)
0.8881784197001251
>>> diffn(exp,1e-5,4)(0)
22204.46049250314
>>> diffn(exp,1e-5,5)(0)
-6661338147.75094
\end{lstlisting}

Ouh la  la!... La  naïveté ne  paie pas en  informatique! Il  va falloir
mettre le nez  dans le processeur et faire un  peu de mathématiques pour
éviter d'écrire d'énormes bêtises en seulement quatre tours de récursion.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% E X E R C I C E S
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vfill

\eject

\modeexercice % entre en mode exercice
\section{Exercices}

\begin{exercice}[Domination]
Prouvez les propriétés 1-1 du cours.
\end{exercice}




\begin{exercice}[Complexité]
 Voici deux algorithmes:

\begin{multicols}{2}
\begin{algo}
\FUNC{algo1}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\RETURN{a*algo1(a,n-1)}
\ENDIF
\END
\end{algo}


\begin{algo}
\FUNC{algo2}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\VAR
\DECLVAR{i,r}
\ENDVAR
\BEGIN
\STATE{r \recoit{} 1}
\FOR{i}{1}{n}
\STATE{r \recoit{} a*r}
\ENDFOR
\RETURN{r}
\END
\end{algo}
\end{multicols}

Que calculent-ils? Quelle est leur complexité?

En voici un troisième:


\begin{algo}
\FUNC{algo3}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\IF{n=1}
\RETURN{a}
\ELSE
\IF{n est pair}
\RETURN{algo3(a*a,n/2)}
\ELSE
\RETURN{a*algo3(a*a,(n-1)/2)}
\ENDIF
\ENDIF
\ENDIF
\END
\end{algo}

Que calcule-t-il? Quelle est sa complexité?

Comparez  le temps  de  calcul de  algo3($\numprint{1000000000}$) et  de
algo1($\numprint{1000000000}$).
\end{exercice}

\vfill

\eject

\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{}...


\item Proposez une  animation graphique avec le langage  que vous voulez
  pour illustrer le grignotage.
\end{enumerate}



\end{exercice}







\begin{exercice}[La bille qui rebondit]

Vous  aurez besoin d'utiliser  quelques lois  physiques du  programme de
Terminale qui font partie de la culture générale d'un scientifique:
\begin{itemize}
\item En chute libre verticale, l'altitude $z$ suit la loi $z(t)=-\fr{1}{2}gt^2+v_0t+z_0$
\item la vitesse suit la loi $v(t)=-gt+v_0$ en coordonnées algébriques
\item Théorème de l'énergie cinétique et de la conservation de l'énergie:$$\ER_C(B)-\ER_C(A)=\fr{1}{2}mv_B^2-\fr{1}{2}mv_A^2=-mg(z_B-z_A)$$
\end{itemize}


\begin{enumerate} \item Une balle part d'une certaine hauteur $h_0$ au dessus du sol (sans vitesse initiale). Combien de temps met-elle pour arriver
sur le sol (n\'egliger les frottements)~? Quelle est son \'energie cin\'etique lorsqu'elle arrive au niveau du sol~?

\item On mod\'elise le rebond de la fa{\c c}on suivante~: lorsque la balle rebondit elle perd une certaine proportion $p$ de son \'energie
cin\'etique (par exemple $p=10\%$). \'Etant partie de la hauteur $h_0$, à quelle hauteur $h_1$ va-t-elle remonter~? Quelle est la dur\'ee
$t_0$ entre les deux premiers rebonds~?

\item Combien de fois la balle rebondit-elle~? Pendant combien de temps rebondit-elle~?

\item Question subsidiaire : vous connaissez le bruit d'une bille qui rebondit, avec des rebonds de plus en plus rapproch\'es. Imaginez
maintenant une balle qui rebondit, non plus selon le mod\`ele ci-dessus, mais selon un autre loi. Par exemple la dur\'ee du $n$-i\`eme
rebond est donn\'e par $1/n$. Que va-t-on entendre ?

\item Proposez un programme dans le langage que vous voulez qui permette
  de  voir la bille  rebondir et  un autre  qui permette  d'entendre une
  série rebondir...
\end{enumerate}
\end{exercice}


\begin{exercice}[Dérivées successives]
Calculez les dérivées d'ordre $n$ des fonctions suivantes:

\begin{multicols}{5}
  \begin{enumerate}
  \item $x\mapsto \mathrm{e}^{x} $
    \item $x\mapsto \frac{1}{1+x}$
      \item $x\mapsto \frac{1}{1-x}$
        \item $x\mapsto \ln(1+x)$
        \item $x\mapsto \cos(x)$
  \end{enumerate}
\end{multicols}
\end{exercice}

\begin{exercice}[Dérivée d'une composée]
Calculez  la dérivée de  la fonction  $x\mapsto \ln  \left(\ln \left(\ln
    \left(\ln(x)\right)\right)\right)$; Faites de même avec  $x\mapsto \sin
\left(\sqrt{\sqrt{\ln \left(\cos(x)\right)}}\right)$.
\end{exercice}


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