\newpage
\section{Notation asymptotique}

\subsection{crible d'Eratostène}

L'analyse des temps de calcul d'un programme
fait appara\^{\i}tre des fonctions d\'efinies
sur l'ensemble des entiers naturels. En g\'en\'eral,
ces fonctions ont un comportement assez cahotique. On
introduit des \emph{notations asymptotiques} pour d\'ecrire
grossi\`erement ces fonctions.

\begin{definition}
Un entier naturel  est dit composé s'il s'écrit comme
un produit de deux nombres différents de $1$. Un nombre  
qui n'est pas composé est dit premier. 
\end{definition}


\begin{exercice} 
Un nombre composé est divisible par un
nombre premier, pourquoi ?
\end{exercice}


\begin{exercice} 
Montrer par l'absurde qu'il existe une infinité de nombres premiers.
\end{exercice}

Le nombre de premiers inf\'erieurs \`a $x$ est
traditionnellement not\'e $\pi(x)$. Nous allons
faire une expérience numérique pour mettre en
évidence une certaine régularité dans la répartiton
des nombres premiers.

\lstinputlisting[float,firstline=4,style=gcc]{asymp/crible.c}


Le programme \gcc{crible.c} est une implantation du c\'el\`ebre
crible d'Eratostène de Cyrène (-\siecle 2) qui permet de déterminer
la valeurs  de $\pi(10^9)$ sans difficulté. La repr\'esentation 
graphique \voirfig{PI} est r\'ealis\'ee par le fichier 
\shell{makefile} \lstinputlisting[float, style=make, title={Fichier makefile}]{asymp/makefile} qui s'appuie sur le fichier 
de commandes \shell{gnuplot}:

\lstinputlisting[language=gnuplot]{asymp/pi.plt}

On constate que le nombre de premiers inf\'erieurs \`a $x$, 
est compris entre deux multiples positifs  de $x/\log x$. 
Nous noterons
$$
\pi(x) = \Theta\big( \frac x{\log x}\big)
$$ 
qui signifie que $\pi(x)$ est asymptotiquement du
m\^eme ordre de grandeur que la fonction $\frac x{\log x}$. En
r\'ealit\'e, ces deux fonctions sont \'equivalentes \`a l'infini!

$$
\pi(x) \sim  \frac x{\log x}
$$ 
un r\'esultat conjectur\'e par Gauss au \siecle{18}, 
d\'emontr\'e beaucoup plus tard 
par Hadamard et De la Vall\'ee-Poussin. Le temps de
calcul du crible s'écrit :

\[
\label{TCRIBLE}
	T(n) = \alpha n + \beta \pi(n) + \gamma n \omega(n)  
\]

où $\alpha$, $\beta$, $\gamma$ sont des nombres postifs et
$\omega(x)$ la somme des inverses des premiers inférieurs
à $x$. On remarque sans difficulté que
$$
	\omega(x) 
=\sum_{p\leq n} \frac 1p 
\leq  \sum_{k\leq n} \frac 1k
\sim \log n
$$

Il en résulte un algorithme rapide dont l'implantattion
est davantage limité par la mémoire que par la célérité
des processeurs. 


\begin{exercice}
La compilation \shell{gcc -S crible.c} produit un code
en assembleur qui permet de visualiser les opérations 
élémentaires pour prédire les valeurs des constantes
cachées : $\alpha$, $\beta$ et $\gamma$. Estimer le
temps de calcul sur une machine cadencée à 2Ghz.  
\end{exercice}
 
\begin{multicols}2
\lstinputlisting[style=asm, firstline=5, lastline=54]{asymp/crible.s}
\end{multicols}

\begin{exercice}
Concernant le crible, quelques  améliorations sont possibles,
lesquelles ?
\end{exercice}

\begin{exercice}
Donner une implantation du crible basée sur un tableau de bits,
donc 8 fois plus économique en mémoire que pour un tableau d'octet.
\end{exercice}

\begin{exercice}
Utilisez \shell{gnuplot} pour vous concaincre de
$$
\omega(x) = \sum_{p<x} \frac 1p \sim \log \log x,
\quad\text{(Euler)}.
$$
\end{exercice}



\subsection{ordre de grandeur}

\begin{definition} Soient $f,g\colon\N\rightarrow\R$ deux fonctions
positives. On dit que $f$ et $g$ sont asympotiquement du m\^eme ordre
de grandeur s'il existe deux nombres positifs $A$ et $B$, et un
rang $n_0$ tels que
$$
\forall n\geq n_0,\quad A f(n) \leq g(n) \leq Bf(n).
$$ 
De fa\c con condens\'ee, on note $g =\Theta( f )$.
\end{definition}

\begin{figure}
\includegraphics[scale=0.5]{asymp/pi.png}
\caption{\label{PI}Graphe de la fonction $\pi(x)$. On
constate que $\pi(x) = \Theta\big(x/\log x\big)$.}
\end{figure}

\begin{definition} Soient $f,g\colon\N\rightarrow\R$ deux fonctions
positives. On dit que $f$ et $g$ sont asympotiquement \'equivalentes
$$\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} = 1, $$
et on note  $g\sim f$.
\end{definition}

Il s'agit de deux relations d'\'equivalence, la seconde est plus fine
que la premi\`ere qui demeure suffisante pour la plupart des
applications en algorithmique. 

\begin{definition} Soient $f,g\colon\N\rightarrow\R$ deux fonctions
positives. On dit que $g$ domine $f$ (asymptotiquement) s'il existe 
un nombre positif $B$, et un rang $n_0$ tels que
$$
\forall n\geq n_0,\quad  f(n) \leq B g(n)
$$
On note $ f= \bigo( g )$, ou bien $ g = \Omega(f)$. 
\end{definition}

\begin{exercice}
Montrer que la relation : $f$ est du même ordre de
grandeur que $g$ est une relation d'équivalence
sur l'ensemeble des fonctions positives.
\end{exercice}

\subsection{somme basique}

Consid\'erons l'implantation \shell{bash} de l'algorithme 
de tri par sélection, le nombre de comparaisons entre des 
\'e\'ements du tableau \`a l'etape $i$ est
\'egal \`a $(n-i)-(i+1)+1$. Le nombre total de comparaisons
est donn\'e par la somme de $n$ termes en progression
arithm\'etique de raison 1 :

\begin{equation}
C(n) =\sum_{i=0}^{n-1} (n-i-1) =\sum_{0}^{n-1}i= n\frac{n-1}2 \sim \frac {n^2}2= \Theta( n^2)
\end{equation}


\lstinputlisting[float,style=bash]{asymp/triselect.sh}

D'une manière générale, pour appréhender les 
temps de calul des algorithmes de ce cours,
il faut absolument maîtriser les deux les formules 
sommatoires arithmétique et géométrique:

\begin{equation}
\label{BASICSUM}
   1+2+\cdots+(n-1) = \frac{(n-1)n}2,
\quad
   q^0+q^1+\cdots+q^{n-1}=\frac{q^n-1}{q-1}
\end{equation}

Un peu moins connue
\begin{equation}
\label{CARRE}
   1^2+2^2+\cdots+(n-1)^2 = \frac{n(n-1)(2n-1)}6,
\end{equation}

et la surprenante relation
\begin{equation}
\label{CARRE}
   1^3+2^3+\cdots+(n-1)^3 =  \left( 1+2+\cdots+(n-1) \right)^2
\end{equation}

\subsection{série et intégrale}


Les résultats de la section précédente sont 
généraux. En effet, si $f$ est une fonction
continue sur $\R+$, positive et croissante
ou décroissante mais pas trop alors :

\begin{figure}
\includegraphics[scale=0.5]{asymp/sumint.png}
\end{figure}

\begin{equation}
\label{COMP}
\sum_{k=1}^n f(k)  \sim \int_1^n f(t) {\rm d}t
\end{equation}


La preuve instructive est laissée.


\lstinputlisting[float,language=gnuplot]{asymp/sumint.plt}

\begin{proposition}
\label{SERIE}
\begin{align}
     \sum_{k=1}^n \frac 1k       &\sim \log n\\
     \sum_{k=1}^n k^{s-1}  &\sim \frac 1s n^s\\
     \sum_{k=1}^n \log k         &\sim n\log n
\end{align}
où $s$ est un entier supérieur à 1.
\end{proposition}
\begin{proof}
Facile.
\end{proof}

\subsection{nombre de Bernoulli}

Soit $f(X)$ un polynôme de degré $s$ à coefficients
positifs, de coefficient dominant $\gamma$ :
$$
      f(n)   \sim \gamma n^s.
$$

Il semble que Jacques Bernoulli ait été  
l'un des premiers mathématiciens à s'être
intéressé aux sommes :
$$
S(n,s) = \sum_{k=0}^{n-1} k^{s-1}.
$$

Il a établi que $S(n,s)$ est un polyôme de degré
$s$ en $n$.


\begin{proposition}
Soit un entier $s>1$. Il existe un polynôme $r$ 
de degré $s$ tel  que :
$$
     S(n,s) = \sum_{k=0}^{n-1} k^{s-1} = \frac 1s n^s + r(n) \sim \frac 1s n^s
$$
\end{proposition}
\begin{proof}
On peut déterminer $r$ à partir de la formule du binôme de Newton:

$$
	(a+b)^s = \sum_{i=0}^s \binomial si a^i b^{s-i}.
$$
$$
\begin{array}{ccccl}
      n^s &- &(n-1)^s 	 &= &\sum_{k=0}^{s-1} \binomial sk (n-1)^k\\
      (n-1)^s   &- &(n-2)^s &= &\sum_{k=0}^{s-1} \binomial sk (n-2)^k\\
              &		    &\vdots\\
      2^s   &- &1^s     &= &\sum_{k=0}^{s-1} \binomial sk 1^k\\
\end{array}
$$

En sommant,

\begin{align*}
      (n+1)^s      &= 1 + \sum_{k=0}^{s-1} \binomial sk S(n,k)\\
\end{align*}
\end{proof}

\subsection{dérivation discrète}

Je vous propose astucieux  raisonnement emprunté 
à l'analyse  différentielle \footnote{suggéré par Jean-Jacques}
pour montrer que $S(n,s)$ est un polynôme de 
degré $s$ en $n$. 

Soit $\mathcal P(\Q)$ l'espace des fonctions à valeurs
dans le corps $\Q$ des rationnels définies sur l'ensemble
des entiers naturels. Pour $f\in\mathcal P(\Q)$, on note $f'$ la
dérivée discrète de $f$, elle est définie par :
$$
           f'(n) = f(n+1) - f(n)
$$
\begin{enumerate}
\item Résoudre l'équation $f' = 0$.
\item Résoudre l'équation $f' = 1$.
\item Montrer que $\deg( f' ) =  \deg(f) - 1$.
\item Montrer que si $f'$ est polynomiale alors $f$ est
un polynôme.
\end{enumerate}


\subsection{exercice}

\begin{exercice}
Déterminer le temps de calcul du 
programme \gcc{loops}. Procéder à
une vérification expérimentale basée
sur la commande \shell{time} , puis
une autre basée sur le profileur
\shell{gprof}.
\end{exercice}


\lstinputlisting[float,style=gcc]{asymp/loops.c}
