\chapterimage{complex}
\chaptertext{C'est le chapitre \oe cuménique du programme de deuxième année:
  l'informatique devient  un paradis  où s'ébattent dans  le plus  parfait amour
  mathématique théorique et sciences expérimentales <3 <3 <3}

\chapter{Complexité}





\section{Exemple introductif: problème des 3 sommes}

\subsection{Méthode scientifique ;-) }


Le  problème:  \textit{on dispose  d'une  liste  de  N nombres.  Déterminez  les
  triplets dont la somme est nulle}.

Utilisons la force brute (pour le lecteur impatient: nous ferons mieux plus tard...):

\begin{pythoncode}
def trois_sommes(xs):
    N = len(xs)
    cpt = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                if xs[i] + xs[j] + xs[k] == 0:
                    cpt += 1
    return cpt
\end{pythoncode}


Comparons les temps pour différentes tailles:


\begin{pythoncode}
In [23]: %timeit trois_sommes([randint(-10000,10000) for k in range(100)])
10 loops, best of 3: 27.5 ms per loop

In [24]: %timeit trois_sommes([randint(-10000,10000) for k in range(200)])
1 loops, best of 3: 216 ms per loop

In [25]: %timeit trois_sommes([randint(-10000,10000) for k in range(400)])
1 loops, best of 3: 1.82 s per loop
\end{pythoncode}


On peut plutôt s'intéresser aux ratios:

\begin{pythoncode}
from time import perf_counter
from math import log

t = [temps(range(100 * 2**k)) for k in range(4)]

ratio = [t[k + 1] / t[k] for k in range(3)]

def logD(x):
    return log(x)/log(2)

logratio = map(logD,ratio)
\end{pythoncode}

et on obtient:

\begin{pythoncode}
In [56]: ratio
Out[56]: [7.523860206447286, 9.118789882406599, 8.5098312160934]

In [57]: list(logratio)
Out[57]: [2.940628541715559, 3.133284732580891, 3.128693841844642]  
\end{pythoncode}


Bon, il semble que quand la taille double, le temps est multiplié par $2^3$.

Il ne  semble donc  pas aberrant  de considérer que  le temps  de calcul  est de
$aN^3$ mais que vaut $a$?



\begin{pythoncode}
In [62]: temps(range(400))
Out[62]: 4.005484320001415  
\end{pythoncode}

$4,00 = a\times 400^3 $ donc $a\approx 6,25\times 10^{-8}$

Donc pour $N=1000$, on devrait avoir un temps de $6,25\times 10^{-8}\times10^9=62,5$

\begin{pythoncode}
In [66]: temps(range(1000))
Out[66]: 68.54615448799996  
\end{pythoncode}

Presque mais Python reste Python...

Voici la même chose en C, sans vraiment chercher à optimiser le code.

\begin{minted}[linenos,breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,fontfamily=txtt]{c}
#include <stdio.h>
#include <time.h>

typedef int Liste[13000];

int trois_sommes(int N)
{
  int cpt = 0;
  Liste liste;

  for ( int k = 0; k < N; k++)
    {
      liste[k] = k - (N / 2);
    }
  
  for (int i = 0; i < N; i++)
    {
      for (int j = i + 1; j < N; j++)
	{
	  for (int k = j + 1; k < N; k++)
	    {
	      if (liste[i] + liste[j] + liste[k] == 0) {cpt++;}
	    }
	}
     }
  return cpt;
}

void chrono(int N)
{
  clock_t temps_initial, temps_final;
  float temps_cpu;

  temps_initial = clock();
  trois_sommes(N);
  temps_final   = clock();
  temps_cpu = ((double) temps_final - temps_initial) / CLOCKS_PER_SEC;
  printf("Temps en sec pour %d : %f\n",N, temps_cpu);

}
  
int main(void)
{
  chrono(100);
  chrono(200);
  chrono(400);
  chrono(800);
  chrono(1600);
  chrono(3200);
  chrono(6400);
  chrono(12800);

  return 1;
}
\end{minted}


Et on obtient:

\begin{minted}[linenos,breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,fontfamily=txtt]{sh}
$ gcc  -std=c99 -Wall -Wextra  -Werror -pedantic -O4 -o somm3 Trois_Sommes.c
$ ./somm3 
Temps en sec pour 100 : 0.00000
Temps en sec pour 200 : 0.000000
Temps en sec pour 400 : 0.020000
Temps en sec pour 800 : 0.090000
Temps en sec pour 1600 : 0.720000
Temps en sec pour 3200 : 5.760000
Temps en sec pour 6400 : 45.619999
Temps en sec pour 12800 : 360.839996
\end{minted}

On a la même évolution en $N^3$ avec  un rapport de 8 entre chaque doublement de
taille mais la constante est bien meilleure:

$45,61 = a\times 6400^3$ d'où $a\approx 1,74\times10^{-10}$

$360,84 = a\times 12800^3$ d'où $a\approx 1.72\times 10^{-10}$


\textbf{Conclusion}: Python  ou C,  l'algo est  le même et  on constate  la même
progression selon le cube de la taille.

Ce qui  nous intéresse en  premier lieu (et ce  que l'on mesurera  aux concours)
est donc un \textbf{ORDRE DΕ CROISSANCE}.


Cependant, les  temps sont  bien distincts:  ici, C  va 400  fois plus  vite que
Python ;-)

On a  donc une approche  expérimentale et  les expériences sont  plus facilement
menées que  dans les  autres sciences  et on  peut en  effectuer de  très grands
nombres.

La mauvaise  nouvelle, c'est  qu'il est difficile  de mesurer  certains facteurs
comme l'usage du cache, le comportement du ramasse-miettes, etc.

En C, on  peut regarder le code  assembleur généré mais avec  Python, c'est plus
mystérieux.


La bonne nouvelle, c'est qu'on peut cependant effectuer une analyse mathématique
pour confirmer nos hypothèses expérimentales.



\subsection{Notations}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3.5cm}
%\begin{figure}
  \includegraphics[width=3cm]{hackers}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.6cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}



\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+\text{
  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 strictement 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$.



On peut  cependant faire  mieux si l'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 strictement 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}

Si l'on a à la fois une minoration et une majoration, 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
  f=O(g)\ \ \wedge \ \ f=\Omega(g)
$
\end{definition}


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


% \begin{NB}
%   Ce qui  nous intéressera,  c'est en  fait le  taux de  croissance du
%   temps  d'exécution,   c'est  pourquoi  ces notations   sont  très
%   pratiques  en  algorithmique car  elle  font  abstraction des  temps
%   d'accès mémoire, de la cadence  du processeur, etc. qui dépendent de
%   chaque machine et également des langages utilisés.
% \end{NB}

\subsection{Analyse mathématique}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=2.8cm]{knuth}
\caption{
D. E. Knuth \\
Né en 1938
}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.2cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}

Une   bonne  lecture   de   chevet   est  le   troisième   volume   de  \og   Zi
Arte\fg{} (\cite{knuth:vol3}).

Le temps  d'exécution est la somme  des produits (coût $\times$  fréquence) pour
chaque opération.

\begin{itemize}
\item le coût dépend de la machine, du compilateur, du langage;
\item la fréquence dépend de l'algorithme, de la donnée en entrée.
\end{itemize}


Par exemple, l'accès à un élément dans un itérateur en Python n'est pas gratuit.

\begin{pythoncode}
In [12]: xs = range(-500,501)

In [13]: %timeit xs[900]
10000000 loops, best of 3: 129 ns per loop

In [14]: %timeit xs[900] + xs[800] 
1000000 loops, best of 3: 292 ns per loop

In [15]: %timeit xs[900] + xs[800] + xs[700]
1000000 loops, best of 3: 424 ns per loop
\end{pythoncode}


Mais si on travaille sur une liste:

\begin{pythoncode}
In [22]: xs = list(range(-500,501))

In [23]: %timeit xs[900]
10000000 loops, best of 3: 40.7 ns per loop
In [24]: %timeit xs[900] + xs[800] 
10000000 loops, best of 3: 114 ns per loop
In [25]: %timeit xs[900] + xs[800] + xs[700]
10000000 loops, best of 3: 165 ns per loop  
\end{pythoncode}

oui mais:

\begin{pythoncode}
In [26]: %timeit range(-500,501)
1000000 loops, best of 3: 292 ns per loop
In [27]: %timeit list(range(-500,501))
100000 loops, best of 3: 13.9 µs per loop  
\end{pythoncode}





Dans notre algorithme des 3 sommes en python, on peut donc gagner du temps:

\begin{pythoncode}
def trois_sommes(xs):
    N = len(xs)
    cpt = 0
    for i in range(N):
        xi = xs[i]
        for j in range(i + 1, N):
            sij = xi + xs[j]
            for k in range(j + 1, N):
                if sij + xs[k] == 0:
                    cpt += 1
    return cpt  
\end{pythoncode}


C'est mieux:

\begin{pythoncode}
In [28]:  xs = list(range(-50,51))
In [29]: %timeit trois_sommes(xs)
100 loops, best of 3: 12.9 ms per loop

In [30]:  xs = list(range(-100,101))
In [31]: %timeit trois_sommes(xs)
10 loops, best of 3: 94.4 ms per loop

In [32]:  xs = list(range(-200,201))
In [33]: %timeit trois_sommes(xs)
1 loops, best of 3: 851 ms per loop

In [34]:  xs = list(range(-400,401))
In [35]: %timeit trois_sommes(xs)
1 loops, best of 3: 7.04 s per loop  
\end{pythoncode}

En C, ça ne changera rien, car le compilateur est intelligent et a remarqué tout
seul qu'il pouvait garder en mémoire certains résultats.


On peut visualiser en échelle log-log:

\begin{pythoncode}
tailles = [2**k for k in range(7,11)]*
listes = [list(range(- N//2, N//2 + 1)) for N in tailles]
t = [temps(xs) for xs in listes]
for taille in tailles:
    plt.loglog(tailles, t, basex = 2, basey = 2)
plt.title('Temps de calcul selon la taille de la liste en échelle log-log')
plt.xlabel('Taille des listes')
plt.ylabel('Temps en s')
\end{pythoncode}

\vspace{-0.5cm}

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

C'est assez rectiligne.

Regardons de nouveau le code des  trois sommes et comptons le nombre d'opérations:
% \begin{pythoncode}
% def trois_sommes(xs):
%     N = len(xs) 
%     cpt = 0
%     for i in range(N):
%         xi = xs[i]
%         for j in range(i + 1, N):
%             sij = xi + xs[j]
%             for k in range(j + 1, N):
%                 if sij + xs[k] == 0:
%                     cpt += 1
%     return cpt  
% \end{pythoncode}

\smallskip

\begin{tabular}[!h]{|l|c|}
\hline
OPÉRATION & FRÉQUENCE\\
\hline
Déclaration de la fonction et du paramètre (l. 1)& 2\\
\hline
Déclaration de N, cpt et i (l. 2, 3 et 4)& 3\\
\hline
Affectation de N, cpt et i (l. 2, 3 et 4)& 3\\
\hline
Déclaration de xi (l. 5) & N\\
\hline
Affectation de xi (l. 5) & N\\
\hline
Accès à xs[i] (l. 5) & N\\
\hline
Déclaration de j (l.6) & N\\
\hline
Calcul de l'incrément de i (l. 6) & N\\
\hline
Affectation de j (l.6) & N\\
\hline
Déclaration de sij (l. 7) & $S_1$\\
\hline
Affectation de sij (l. 7) & $S_1$\\
\hline
Accès à xs[j] (l.7) & $S_1$\\
\hline
Somme (l.7) & $S_1$\\
\hline
Déclaration de k (l.8) & $S_1$\\
\hline
Incrément de j (l. 8) & $S_1$\\
\hline
Affectation de k (l.8) & $S_1$\\
\hline
Accès à x[k] (l.9) & $S_2$\\
\hline
Calcul de la somme (l.9) & $S_2$\\
\hline
Comparaison à 0 (l.9) & $S_2$\\
\hline
Incrément de cpt (l.9) & entre 0 et $S_2$\\
\hline
Affectation de la valeur de retour (l.11) &1\\
\hline
\end{tabular}

\smallskip

Que valent $S_1$ et $S_2$?

$$S_1=\sum_{i=0}^{N-1}N-(i+1)=\sum_{i'=0}^{N-1}i'=\frac{N(N-1)}{2} $$


\begin{eqnarray*}
  S_2&=&\sum_{i=0}^{N-1}\sum_{j=i+1}^{N-1}N-(j+1)\\
     &=&\sum_{i=0}^{N-1}\sum_{j'=0}^{N-(i+2)}j'\\
     &=&\sum_{i=0}^{N-2}\frac{(N-(i+2))(N-(i+1))}{2} \\
     &=&\sum_{i'=1}^{N-2}\frac{i'(i'+1)}{2}\\
     &=&\frac{1}{2}\left(\sum_{i=1}^{N-2}i^2+\sum_{i=1}^{N-2}i\right)\\
     &=&\frac{1}{2}\left(\frac{(N-2)(2N-3)(N-1)}{6}+\frac{(N-2)(N-1)}{2}\right)\\
     &=&\frac{N(N-1)(N-2)}{6}
\end{eqnarray*}


Notons  $a$  le   temps  constant  d'affectation,  $d$  le   temps  constant  de
déclaration, $x$ le temps constant d'accès  à une cellule, $s$ le temps constant
d'une somme, $c$ le temps constant d'une comparaison.


Le temps d'exécution vérifie:

$$\tau(N) \leqslant  (2d+3d+3a+a) + (d+a+x+d+s+a)N+(d+a+x+s+d+s+a)S_1+(x+s+c+s)S_2$$

Or $S_1\sim N^2$ et $S_2\sim N^3$ quand $N$ est \og grand\fg{}.


Finalement... $$\tau(N)=O(N^3)$$

...et ce, que l'on utilise C, Python, BrainFuck
(\href{https://fr.wikipedia.org/wiki/Brainfuck}{https://fr.wikipedia.org/wiki/Brainfuck}),
etc. 


C'est aussi ce que l'on a observé expérimentalement 

\begin{NB}
Moralité, on ne s'occupe que de ce qu'il  y a dans la boucle la plus profonde et
on oublie le reste....
\end{NB}

\section{Algorithme de Karatsouba}


Vous savez additionner deux entiers de $n$ chiffres: cela nécessite $\Theta(n)$ additions
de nombres de un chiffre compte-tenu des re-tenues.

Multiplier un  entier de $n$  chiffres par un entier  de 1 chiffre  prend $\Theta(n)$
unités de temps selon le même principe.

En utilisant  l'algorithme de l'école  primaire pour multiplier deux  nombres de
$n$ chiffres, on effectue $n$ multiplications d'un nombre de $n$ chiffres par un
nombre de  1 chiffre puis  une addition des $n$  nombres obtenus. On  obtient un
temps de calcul en $\Theta(n^2)$.

On  peut espérer  faire  mieux  en appliquant  la  méthode \textit{diviser  pour
  régner}.

On  coupe par  exemple chaque  nombre en  deux parties  de $m=\lfloor  n/2\rfloor$
chiffres:

$$xy=(10^mx_1+x_2)(10^my_1+y_2)=10^{2m}x_1y_1+10^m(x_2y_1+x_1y_2)+x_2y_2$$




\begin{algo}
\FUNC{MUL}{\pfarg x entier ,y: entier}{entier}
\IF{n==1}
\RETURN{x.y}
\ELSE
\STATE{$m$ \recoit{} $\lfloor n/2\rfloor$}
\STATE{$x_1$ \recoit{} $\lfloor x/10^m\rfloor$}
\STATE{$x_2$\recoit{} $x$ mod $10^m$}
\STATE{$y_1$ \recoit{} $\lfloor y/10^m\rfloor$}
\STATE{$y_2$\recoit{} $y$ mod $10^m$}
\STATE{$a$ \recoit{} MUL($x_1$,$y_1$,m)}
\STATE{$b$ \recoit{} MUL($x_2$,$y_1$,m)}
\STATE{$c$ \recoit{} MUL($x_1$,$y_2$,m)}
\STATE{$d$ \recoit{} MUL($x_2$,$y_2$,m)}
\RETURN{$10^{2m}a+10^m(b+c)+d$}
\ENDIF
\end{algo}



Les divisions et  les multiplications par des  puissances de 10 ne  sont que des
décalages effectués en temps constant.

L'addition finale est en $\Theta(n)$ donc le temps d'exécution est défini par:

$$T(n)=4T(\lfloor n/2\rfloor) +\Theta(n)\qquad T(1)=1$$


Peut-on exprimez $T(n)$ explicitement en fonction de $n$ sans récursion?

Si  nous  avions une  idée  de  la solution,  nous  pourrions  la démontrer  par
récurrence.

Cherchons une  idée donc...Ça serait plus  simple si $n$ était  une puissance de
2. Voyons, posons $n=2^k$ et $T(n)=T(2^k)=x_k$.




\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{Karatsuba}
\caption{
%\begin{otherlanguage}{russian}
A. Karatsouba
%\end{otherlanguage}\\
(1937 - 2008)
}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.2cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


Alors la relation de récurrence devient:

$$x_k=4x_{k-1}+\Theta(2^k)\qquad x_0=1$$

On obtient:


$$x_k=4(4x_{k-2}+\Theta(2^{k-1}))+\Theta(2^k)=4^kx_0+\sum_{i=1}^k\Theta(2^k)=4^k+k\Theta(2^k)=n^2+\log
n\Theta(n)=\Theta(n^2)$$


On montre alors par récurrence forte que ce résultat est vrai pour tout
entier naturel non nul $n$.



Bref, tout ça pour montrer que l'on n'a pas amélioré la situation...

Le grand 
\begin{otherlanguage}{russian}
Андрей Николаевич КОЛМОГОРОВ 
\end{otherlanguage}
finit  même par  conjecturer dans  les  années 1950  que l'on  ne pourra  jamais
trouver un algorithme de multiplication d'entiers en $o(n^2)$.

Lors d'un séminaire sur ce sujet en 1960, un jeune étudiant soviétique, 
\begin{otherlanguage}{russian}
Анатолий Алексеевич КАРАЦУБА
\end{otherlanguage}
propose  cependant   au  Maître  une   solution  plus  simple  et   navrante  de
simplicité...

Il fait remarquer à \begin{otherlanguage}{russian} КОЛМОГОРОВ 
\end{otherlanguage} que:

$$bc + ad = ac+bd -(a-b)(c-d)$$

\begin{recherche}
  En quoi cela simplifie le problème? Quelle est alors la nouvelle complexité?
\end{recherche}

On peut reprendre la méthode précédente ou étudier le paragraphe suivant.



















\section{Diviser pour régner: ze Master Theorem}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3.5cm}
\begin{figure}
  \includegraphics[width=3.5cm]{sunzi}
\caption{
%\begin{CJK}{UTF8}{song}
% {\large 孫子}
%\end{CJK}\\
Sun Zi
(544–496 av. J.-C.)
}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.6cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}

\begin{quote}
 \textit{ Le commandement  du grand nombre  est le même pour  le petit nombre,  ce n'est
  qu'une question de division en groupes.}

  \begin{flushright}
    in \og L'art de la guerre\fg{} 
\begin{CJK}{UTF8}{song}
{\large 孙子兵法}
\end{CJK}
de Sun Zi (VI\eme siècle avant JC)
  \end{flushright}
\end{quote}



On considère un problème  de taille $n$ qu'on découpe en  $a$ sous-problèmes de taille
$n/b$ avec $a$ et $b$ des entiers. Le coût de l'algorithme est alors:

$$
\begin{cases}
  T(1) = 1\\
  T(n) = a×T(n/b) + \text{Reconstruction(n)}
\end{cases}
$$

En général la reconstruction est de l'ordre de $c×n^α$.

Par exemple, pour l'algorithme de \begin{otherlanguage}{russian}
КАРАЦУБА
\end{otherlanguage}  nous avions  $T(n)=3T(\lfloor n/2\rfloor)  +\Theta(n)$ donc
$a=3$, $b=2$, $α=1$ et $c$ quelconque avec $n$ pair. On obtient:

$$T(n)=aT(n/b)+cn^α=a^2T(n/b^2)+ac(n/b)^α+cn^α=\cdots=a^kT(n/b^k)+∑_{i=0}^{k-1}a^ic(n/b^i)^α$$

On peut poser $n=b^{k_n}$ et alors:

$$T(n)=a^{k_n}+cn^α∑_{i=0}^{k_n-1}(a/b^α)^i$$

On distingue trois cas:


\begin{enumerate}
\item  \fbox{$a> b^α$}  alors la  somme géométrique  est équivalente  au premier  terme
  négligé    à     une    constante    multiplicative    et     additive    près
  ($\frac{1}{a/b^α-1}\left(\frac{a}{b^α}\right)^{k_n} -\frac{1}{a/b^α-1} $ ) à savoir $(a/b^α)^{k_n}$ et $T(n)=O(a^{k_n})$ soit
  \fbox{$T(n)=O(n^{\log_b(a)})$}
\item \fbox{$a=b^α$} alors \fbox{$T(n)=O(n^α\log_b(n))$}
\item \fbox{$a <  b^α$} alors la série géométrique  est convergente: $S(n)\simeq
  n^{\log_b(a)}+cn^α/(1-a/b^α)$ or $a<b^α$ donc $\log_b(a)<α$. Finalement \fbox{$T(n)=O(n^α)$}
\end{enumerate}


En fait, on peut démontrer (cf \cite{Cormen} pp. 86-97) que les $O$ sont des
$\Theta$ et considérer des fonctions de reconstruction plus générales..




Pour revenir à l'algorithme de \begin{otherlanguage}{russian}
КАРАЦУБА
\end{otherlanguage}, $a=3$ et $b^α=2$ donc $T(n)=\Theta(n^{\log_23})$.





\begin{theoreme}[Master Theorem: totalement hors programme  mais qui sait  ce qui  peut se
  passer à l'X ou aux ENS...]
Soient $a  \geqslant 1$  et $b>1$ deux  constantes et $f(n)$  une fonction  et T
définie par:
$$T(n)=aT(n/b)+f(n)$$
  avec $n/b$ étant en fait $\lfloor n/b\rfloor$ ou $\lceil n/b\rceil$.

  \begin{enumerate}
  \item Si  $f(n)=O(n^{\log_ba -  ε})$ pour une  certaine constante  $ε>0$ alors
    $T(n)=\Theta(n\log_ba)$
\item Si $f(n)=\Theta(n^{\log_ba})$ alors $T(n)=\Theta(n^{\log_ba\log_bn})$
\item  Si  $f(n)=Ω(n^{\log_ba+ε})$  et  si  $af(n/b)\leqslant  cf(n)$  pour  une
  certaine constante $c<1$ pour $n$ suffisamment grand, alors $T(n)=\Theta(f(n))$.
  \end{enumerate}
\end{theoreme}



\subsection*{Arbre de récursion}

Il peut être utile de représenter la  récursion par un arbre pour avoir une idée
de la formule à démontrer par récurrence. Toujours avec \begin{otherlanguage}{russian}
КАРАЦУБА
\end{otherlanguage}:



\setindent{0mm}


\begin{center}

\begin{tikzpicture}[
level 1/.style = {sibling distance=5.5cm},
    level 2/.style = {sibling distance=2cm}, 
    level 3/.style = {sibling distance=0.5cm}, 
level 4/.style = {sibling distance=0.9cm} 
]
\node [rectangle, rounded corners = 1mm,draw, fill = black!10] (z){$cn$}
  child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (a) {$\frac{cn}{2}$}
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (b) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}
        child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (d) {$\frac{cn}{2^k}$}}
        child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (dd) {$\frac{cn}{2^k}$}}
        child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (e) {$\frac{cn}{2^k}$}}
      } 
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (g) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (gg) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
  }
 child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (aa) {$\frac{cn}{2}$}
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (bb) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}} 
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (gb) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (ggb) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
  }
  child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (j) {$\frac{cn}{2}$}
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (k) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
    child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (ggb) {$\frac{cn}{2^2}$}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
      child {node {$\vdots$}}
    }
  child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (l) {$\frac{cn}{2^2}$}
    child {node {$\vdots$}}
    child {node {$\vdots$}}
    child {node (c){$\vdots$}
      child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (o) {$\frac{cn}{2^k}$}}
      child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (oo) {$\frac{cn}{2^k}$}}
      child {node [rectangle, rounded corners = 1mm,draw, fill = black!10] (p) {$\frac{cn}{2^k}$}
        %child [grow=right] {node (q) {$=$} edge from parent[draw, fill = black!10=none]
          %child [grow=right] {node (q) {$O_{k = \lg n}(n)$} edge from parent[draw, fill = black!10=none]
            %child [grow=up] {node (r) {$\vdots$} edge from parent[draw, fill = black!10=none]
              %child [grow=up] {node (s) {$O_2(n)$} edge from parent[draw, fill = black!10=none]
                %child [grow=up] {node (t) {$O_1(n)$} edge from parent[draw, fill = black!10=none]
                  %child [grow=up] {node (u) {$O_0(n)$} edge from parent[draw, fill = black!10=none]}
                %}
              %}
            %}
            %child [grow=down] {node (v) {$O(n \cdot \lg n)$}edge from parent[draw, fill = black!10=none]}
          %}
        %}
      }
    }
  }
};
% \path (a) -- (j) node [midway] {+};
% \path (b) -- (g) node [midway] {+};
% \path (k) -- (l) node [midway] {+};
% \path (k) -- (g) node [midway] {+};
% \path (d) -- (e) node [midway] {+};
% \path (o) -- (p) node [midway] {+};
 % \path (o) -- (e) node (x) [midway] {$\cdots$}
 %  child [grow=down] {
 %    node (y) {$O\left(\displaystyle\sum_{i = 0}^k 2^i \cdot \frac{n}{2^i}\right)$}
 %    edge from parent[draw, fill = black!10=none]
 %  };
% \path (q) -- (r) node [midway] {+};
% \path (s) -- (r) node [midway] {+};
% \path (s) -- (t) node [midway] {+};
% \path (s) -- (l) node [midway] {=};
% \path (t) -- (u) node [midway] {+};
% \path (z) -- (u) node [midway] {=};
% \path (j) -- (t) node [midway] {=};
% \path (y) -- (x) node [midway] {$\Downarrow$};
% \path (v) -- (y)
%   node (w) [midway] {$O\left(\displaystyle\sum_{i = 0}^k n\right) = O(k \cdot n)$};
% \path (q) -- (v) node [midway] {=};
% \path (e) -- (x) node [midway] {+};
% \path (o) -- (x) node [midway] {+};
% \path (y) -- (w) node [midway] {$=$};
% \path (v) -- (w) node [midway] {$\Leftrightarrow$};
% \path (r) -- (c) node [midway] {$\cdots$};
\end{tikzpicture}


\end{center}

\setindent{\indentationcours}

\vfill

\eject



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
\section{RECHERCHES}


% \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}{entiers}
%  \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}$) sur un  ordinateur équipé d'un processeur
% 3GHz effectuant une opération arithmétique élémentaire en 100 cycles.


% \end{exercice}



% \vfill

% \eject




\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}[Point fixe]

On dispose  d'un tableau de N  entiers (relatifs) distincts rangés  dans l'ordre
croissant.

Déterminez un algorithme qui renvoie l'éventuel indice $\mathtt{i}$ tel que $\mathtt{a[i] = i}$

  % Hint: binary search. 
\end{exercice}

\begin{exercice}[Recherche en dent de scie]

Un tableau  est constitué  d'une suite  croissante d'entiers  directement suivie
d'une   suite   décroissante  d'entiers.   Tous   les   entiers  sont   supposés
distincts. Déterminez une fonction qui détermine  si un entier appartient ou non
à un  tableau en  dent de scie.  Votre programme doit  effectuer $\sim  3\log N$
comparaisons dans le pire des cas.

% Use a version of binary search, as in BitonicMax.java, to find the maximum (in ~ 1 lg N compares); then use binary search to search in each piece (in ~ 1 lg N compares per piece). 
  
\end{exercice}



\begin{exercice}[Écart mumixam]
  Étant donné un  tableau de N réels,  déterminez un algo en  temps linéaire qui
  détermine la valeur maximum de $\mathtt{a[j]-a[i]}$ pour $j \geqslant i$.

% double best = 0.0;
% double min = a[0];
% for (int i = 0; i < N; i++) {
%     min  = Math.min(a[i], min);
%     best = Math.max(a[i] - min, béat);
% }
\end{exercice}






\begin{exercice}[TP de physique]\label{exo::saut}
  Pour  illustrer les  lois de  la pesanteur,  messieurs \textsc{Alméras} et \textsc{Seigne}  (en
  s'inspirant de \citep{raw})
  préparent un  TP: ils  kidnappent un  nombre $k$  d'étudiant(e)s d'ECE  et les
  emmènent à  la Tour  de Bretagne  qui a $n$  étages, le  rez-de-chaussée étant
  l'étage 0.



%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{hudsucker}
\end{center}
%\end{figure}



  Le but du TP est de déterminer  l'étage à partir duquel lancer un(e) étudiante
  par la fenêtre lui est fatal.

  On suppose qu'un tel étage existe et que le rez-de-chaussée n'est pas fatal..

  On supposera que tant que l'étudiant(e) survit, on peut le(a) réutiliser. Pour
  économiser  le temps  des  expérimentateurs  (afin par  exemple  que
  M. \textsc{Alméras}  continue à corriger vos  copies dans la nuit)  et réduire
  l'empreinte carbone de l'expérience (aller-retours en ascenseur), on va chercher un algorithme qui
  minimise le  nombre d'éssais  effectués (et non  pas le  nombre d'étudiant(e)s
  détruit(e)s: ). 

  Déterminez dans chacun des cas suivants un tel algo:

  \begin{enumerate}
  \item en $O(\log_2(n))$  si $k \geqslant \lceil \log_2(n)\rceil$;
  \item en $O(k + n/2^{k-1})$ si $k < \lceil \log_2(n)\rceil$;
  \item en $O(\sqrt(n))$ si vous ne disposez plus que de 2 étudiant(e)s d'ECE.
  \end{enumerate}
\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}[Complément à 2 puissance n]\label{exo::comp2}
%     \begin{quote}
%       {\itshape
% Le monde se sépare en 10 catégories: ceux qui comprennent cette phrase
% et les autres.
% }
% \begin{flushright}
%   {\small Zorglub in \og Les aventures de Zorglub et Martine au Far-West\fg{}}
% \end{flushright}
%     \end{quote}

% Nous  allons,  pour  favoriser  la  compréhension  et  simplifier  les
% écritures,  travailler  sur 8  bits.  Cela  signifie que  nos  nombres
% entiers peuvent être codés avec 8 chiffres égaux à 0 ou 1 en base 2.

% \begin{enumerate}

% \item Écrivez les nombres de 0 à 17  en base 2. Quel est le plus grand
%   nombre que l'on peut écrire avec 8 bits?
  
% \item  En fait,  on aimerait  avoir des  entiers signés,  c'est-à-dire
%   pouvoir  représenter des  entiers  tant positifs  que négatifs  avec
%   cette contrainte.

%   On va donc réserver un bit (le plus à gauche) pour indiquer le signe
%   du nombre: on mettra un 0 s'il est positif et un 1 s'il est négatif.

 

% \item  Bon,  pas  de  problème...enfin  si  quand  même  un  peu.  Que
%   pensez-vous de ces deux nombres:

%   \begin{Verbatim}
%     00000000 10000000
%   \end{Verbatim}

% \item On voudrait additionner facilement  ces nombres. Une idée serait
%   d'utiliser l'addition  posée comme  à l'école primaire.  Par exemple
%   pour calculer $ 5 + 9$

%   \begin{Verbatim}
%     00000101
% +   00001001
% ------------
%     00001110
%   \end{Verbatim}

%   On trouve bien 14.
  
%   Et maintenant si on veut calculer $ 5 + (-9)$, qu'est-ce que cela donne avec ce système?

% \item  Considérez maintenant  le  nombre \lstinline{m  = 11111111}  et
%   ajoutez-lui 1  (vous n'avez que  8 bits  à disposition). Que  vaut $
%   m+1$? Que cela vous donne-t-il comme idée?

%   Considérez \lstinline{n=11111110} et calculez $ n+2$.

%   Considérez \lstinline{p=11111100} et calculez $ n+4$.

%   Considérez \lstinline{p=11111000} et calculez $ n+8$.

%   Considérez \lstinline{p=11111010} et calculez $ n+6$.

%   Des idées?

% \item Si l'on considère que $  2^8$ vaut 0 en \lstinline{Int8}, ce qui
%   est d'ailleurs le cas:
% \haskell
%   \begin{pythoncode}
% λ> let n = 256 :: Int8
% λ> n
% 0
%   \end{pythoncode}

% Que pensez-vous alors de $x$ et de $2^8-|x|$ si $ x$ est négatif?

% Comment s'écrit $2^8-|x|$ sur 8 bits?

% Bon, vous commencez à voir ce qui se passe?

% Alors expliquez ce qui se passe ici:

% \begin{pythoncode}
% λ> let n = 13 :: Int8
% λ> n * 2
% 26
% λ> n * 4
% 52
% λ> n * 8
% 104
% λ> n * 16
% -48
% λ> n * 32
% -96
% λ> n * 64
% 64
% \end{pythoncode}
% \pythonc
% Généralisez, énoncez votre  norme de représentation des  entiers sur 8
% bits,  énoncez un  \og truc\fg{}  pour trouver  facilement de  tête le
% complément à $ 2^8$.


% \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}
  \includegraphics[width=5cm]{rhind.jpg}
%\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}[Test aléatoire: produit de polynômes correct]
 On considère  deux polynômes écrits  différemment, par exemple l'un  sous forme
 factorisée, l'autre sous forme développée:  comment faire pour vérifier que les
 deux polynômes sont bien égaux?

Quelle est  la complexité en nombre  de calculs arithmétiques basiques  de votre
méthode?

Imaginons maintenant que les polynômes soient de degré $d$. On choisit un nombre
entier $n$ dans l'intervalle $[0,100d]$ selon une distribution uniforme et on calcule
l'image de  ce nombre par chacun  des polynômes: comment exploiter  le résultat?
Évaluer sa \og sûreté\fg{}? Complexité?

Que pensez-vous de  l'issue de l'algorithme par rapport  aux issues habituelles?
Pouvez-vous prouver que l'algorithme est correct?

Que  se passe-t-il  si  on  répète cette  expérience?  Soyez  précis(e) dans  la
description de votre tirage.
\end{exercice}

\begin{exercice}[Produit de matrices correct]
  
On a  deux matrices  A et B  dont on  a calculé  le produit. On  a trouvé  C. On
voudrait vérifier que le calcul a été bien mené.

Quelle est la complexité habituelle du calcul d'un produit de matrcies?

On  préfère  choisir  un  vecteur  $\mathbf{v}$  dans  $\bigl\{0,1\bigr\}^n$  et
effecteur le produit $D×\mathbf{v}$ en notant $D=A×B-C$.

D étant non nul, il a au moins un coefficient non nul. On peut se ramener au cas
$d_{11}\neq 0$.

Exprimer alors $v_1$ en fonction des autres $v_k$ et des $d_{1k}$.

En déduire que  si $D$ est non nulle, la  probabilité que $D×\mathbf{v}=0_n$ est
inférieure à 1/2.

Conclure en terme de vérification et de complexité.

\end{exercice}










\begin{exercice}[Algorithme de Strassen]
  \illmpl{En 1969 (\textit{\og Gaussian elimination is not optimal\fg{} in Nümerische mathematik}), Konrad \textsc{Strassen} propose un algorithme pour calculer
    le produit de deux matrices carrées de taille $n$.


Estimez  tout d'abord  la  complexité  en nombre  d'additions  et  en nombre  de
multiplications de la multiplication usuelle que vous avez vue en Sup.


Considérons à présent le produit de deux matrices de taille $2×2$:

$$
\begin{pmatrix}
  a&b\\
  c&d
\end{pmatrix}
\times
\begin{pmatrix}
  e&f\\
  g&h
\end{pmatrix}
=
\begin{pmatrix}
  w&x\\
  y&z
\end{pmatrix}
$$
}{Strassen}{0.75}{0.2}

On note:

$$
p_1=a(f-h),\    p_2=(a+b)h,\    p_3=(c+d)e,\    p_4=d(g-e),\    p_5=(a+d)(e+h),\
p_6=(b-d)(g+h), \ p_7=(c-a)(e+f)
$$

alors:

$$
\begin{cases}
  w = p_4 + p_5 + p_6 - p_2\\
  x = p_1 + p_2\\
  y = p_3 + p_4\\
  z = p_1 + p_5 - p_3 + p_7\\
\end{cases}
$$

Comparez le nombre d'opérations effectuées.

Considérez maintenant des  matrices carrées de taille $2^t$ (si ce
n'est pas le cas, que peut-on faire?).

On peut découper  nos matrices en quatre blocs de  taille $2^{t-1}$ et appliquer
récursivement notre algorithme:  il faut quand même vérifier  quelque chose pour
passer des  formules sur les  coefficients aux  formules sur les  matrices: quoi
donc?

Comptez le nombre de multiplications et d'additions nécessaires. 

C'est  une application  de  \textit{divide  et impera}:  pourquoi  alors ne  pas
diviser nos atrices en 9 blocs trois fois plus petits? 

\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{figure}
  \includegraphics[width=2.8cm]{Ruffini}
%\caption{Paolo \textsc{Ruffini}\\(1765 - 1822)}
\end{figure}
\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)$.  C'est  ce que  nous allons  (re)découvrir
aujourd'hui... 

\setindent{0cm}


\subsection*{Complexité}

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

\subsection*{Dérivées successives}

On note $P_n=a_0+a_1X+\cdots+a_nX^n$ un polynôme de degré $n$.

Déterminez le lien entre  l'algorithme de \textsc{Horner} et la division
euclidienne  de $P_n$  par $(X-t)$.  On utilisera  par la  suite la
notation suivante:

$$P_n=(X-t)(b_nX^{n-1}+b_{n-1}X^{n-2}+\cdots+b_1)+b_0$$


Comment calculer  les dérivées successives $\widetilde{P_n^{(j)}}(t)$
en  utilisant  uniquement  des  schémas  de  \textsc{Horner}?  Quel  est
l'intérêt informatique? Voici un peu d'aide...


Considérons le  développement de $P_n$ selon  les puissances croissantes
de $(X-t)$:

$$P_n=t_n(X-t)^n+t_{n-1}(X-t)^{n-1}+\cdots+t_0$$

Montrez que $\widetilde{P_n^{(j)}}(t)=(j!)×t_j$.  Quel est le lien
entre les $t_j$ et nos schémas de \textsc{Horner}?

\subsubsection*{Version récursive}

Déterminez une fonction récursive \texttt{der\_j(poly,j,t)} qui calcule
$\widetilde{P_n^{(j)}}(t)$ en utilisant le schéma de \textsc{Horner}.

Pour  cela, on  pourra  commencer par  modifier  légèrement la  fonction
\texttt{horner} pour récupérer le vecteur $\mathtt{[b_0 b_1 ... b_n]}$.

Créez ensuite \texttt{quotient\_horner(poly,t)} qui renvoie
le    quotient    de    \texttt{poly}    par    \texttt{(X-t)}    puis
\texttt{reste\_horner(poly,t)}. 

Déduisez-en une  fonction récursive  \texttt{jeme\_poly(poly,j,t)} qui
renvoie $\widetilde{P_n^{(j)}}(t)$. 


\subsubsection*{Version itérative}

Prenons par exemple le  polynôme $P_4=[6,-7,1,-5,2]$. Essayez de trouver
un algorithme simple pour remplir le tableau suivant:


\begin{center}
             \begin{tabularx}{\linewidth}{IZ|ZZZZZ|ZZI}
	     \whline
Restes & 0 & 1 & 2 & 3 & 4 & $j$ & \\
\whline
 / & 6 & $-7$ & 1 & $-5$ & 2 & $a_j$ & $P_4$ \\
$-12$ & $-9$ & $-1$ & $-1$ & 2 & / & $b_j$ & $Q_3$ \\
      & & & & & &$c_j$ & $Q_2$ \\
      & & & & & &$d_j$ & $Q_1$ \\
      & & & & & &$e_j$ & $Q_0$ \\
      & & & & &  & & \\
             \whline
             \end{tabularx}
             \end{center}

En     déduire     l'écriture     de     $P_4$     sous     la     forme
$R_4+R_3(X-2)+R_2(X-2)^2+R_1(X-2)^3+R_0(X-2)^4$  et faire  le  lien avec
les dérivées successives.


Écrivez  ensuite une  fonction  qui renvoie  un  tableau similaire  puis
transformez-la un peu pour obtenir les divisions successives en $t$.


\begin{lstlisting}[caption={}]
jeme_poly_mat([6 -7 1 -5 2],5,2)

    0.     6.  - 7.    1.  - 5.    2.  
  - 12.  - 9.  - 1.  - 1.    2.    0.  
    1.     5.    3.    2.    0.    0.  
    19.    7.    2.    0.    0.    0.  
    11.    2.    0.    0.    0.    0.  
    2.     0.    0.    0.    0.    0.  
\end{lstlisting}

  
\end{exercice}







%

\begin{exercice}[Complexité de l'algorithme d'Euclide et nombre d'or...]
On suppose dans toute la suite que $a$ et $b$ sont deux entiers naturels
tels que $a \geqslant b$.
  \begin{enumerate}
  \item Rappeler le principe de l'algorithme et de sa preuve.
  \item  Soit $r_n=a\wedge  b$ avec  les notations  habituelles: $r_0=b$
        puis      $r_1=a     \modu      b$,     $r_2=      r_1     \modu
        r_0$ et plus généralement:
$$r_{k+1}=r_kq_k+r_{k-1},\quad 0 \leqslant r_{k-1}<r_k$$ 

    Montrez que
        pour  tout entier  $k\in \bigl\{1,2,...,n\bigr\}$,  on  a $q_k
        \geqslant 1$ puis que $q_n \geqslant 2$.
  \item Notons $Φ=\frac{1+\sqrt{5}}{2}$.
    Comparez $\Phi$ et $1+\frac{1}{\Phi}$.
      \item Montrez  par récurrence que $r_k  \geqslant \Phi^{n-k}$ pour
            tout entier $k\in \bigl\{0,1,...,n\bigr\}$.
\item  Déduisez-en  que $b  \geqslant  \Phi^{n}$  puis  que le  nombre
      d'appels récursifs de 
      l'algorithme d'Euclide est au maximum de $\frac{\ln b}{\ln
      \Phi}$.

  \end{enumerate}
\end{exercice}





\modenormal

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyIPT2014_15"
%%% End: 
