\documentclass[10pt,a4paper,chinois,russe,biblio]{article}
\usepackage{etex}
\usepackage[euler,utf8x]{preambuleTrm}
\usepackage{geometry}
\geometry{papersize={21cm,29.7cm}}
\geometry{margin=1cm,top=1.5cm,bottom=2cm}

\usepackage{textcomp}
\usepackage{ mathtools,xlop,longtable}

\hypersetup{
pdftitle={Repère - Dichotomie}, pdfauthor ={ Guillaume CONNAN}}


\title{ La complexité c'est simple comme la dichotomie (Lycée Maths/ISN)
}

\author{ Guillaume \textsc{Connan}\footnote{\url{Guillaume.Connan@univ-nantes.fr}} - \textsc{Irem} de Nantes}

\date{\today}


\usepackage{algo,bclogo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}


% \newcounter{definit}\newcounter{propri}
% \newcounter{theor}\newcounter{retenir}
% \newcounter{remar}


% \newenvironment{Definition}[1][]{%
% \refstepcounter{definit}
% \begin{bclogo}[ombre=true,logo=\bcbook,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont    D\'efinition  \thedefinit\ : #1}}
% {\end{bclogo}}



% \newenvironment{Remarque}[1][]{%
% \refstepcounter{remar}
% \begin{bclogo}[logo=\bcnote,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont  Remarque   \theremar\ : #1}}
% {\end{bclogo}}



% \newenvironment{Propriete}[1][]{%
% \refstepcounter{propri}
% \begin{bclogo}[ombre=true,logo=\bccoeur,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont    Propri\'et\'e  \thepropri\ : #1}}
% {\end{bclogo}}




% \newenvironment{Theoreme}[1][]{%
% \refstepcounter{theor}
% \begin{bclogo}[ombre=true,logo=\bctrefle,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont Th\'eor\`eme
%     \thetheor\ : #1}}
% {\end{bclogo}}



% \newenvironment{Retenir}[1][]{%
% \refstepcounter{retenir}
% \begin{bclogo}[logo=\bcnote,arrondi=0.05,couleur=white]{\color{black}\bfseries\small\fontfamily{ugq}\selectfont    \`A retenir (\theretenir)\ : #1}}
% {\end{bclogo}}


\newtheorem{Definition}{Définition}
\newtheorem{Theoreme}{Théorème}
\newtheorem{Remarque}{Remarque}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/PREPA/IPT/2014_15/Poly/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}} 

\usepackage[figurename=,labelformat=empty]{caption}



\begin{document}

\maketitle


\begin{Abstract}
La dichotomie,  c'est couper un  problème en  deux. On ne  la présente
  souvent au
  lycée que dans le cadre restreint  de la recherche dichotomique de la solution
  réelle d'une  équation du  type $f(x)=0$ et  on la dénigre  car elle  est bien
  plus lente que la fulgurante méthode de Heron d'Alexandrie. Pourtant, elle est bien
  plus  riche  que  son  utilisation  dans  ce  contexte  étroit  le  laisserait
  penser.  Nous  en   profiterons  pour  introduire  la   notion  de  complexité
  algorithmique.

Il ne s'agit  pas d'une activité \og clé en  main\fg{}. L'orientation est plutôt
vers la formation continue car nous avons besoin d'en savoir un peu plus que nos
élèves avant  de leur introduire  une notion. Cependant,  comme cela a  déjà été
évoqué  (\cite{germoni}) dans  cette revue,  l'étude  de la  complexité peut  être
abordée au lycée et les auteurs de cet article avaient proposé de nombreux exemples.

Nous proposons ici des  approches théoriques et expérientales de ce
problème. On  met ainsi en  évidence qu'une notion mathématique  importante (les
suites numériques) peut
être  illustrée   par  un  problème   informatique  théorique  et   pratique  et
inversement, en cours  d'ISN par exemple, on fait prendre  conscience aux élèves
que l'informatique, ce n'est pas taper sur des touches, c'est surtout noircir du
papier avec des raisonnements très proches des mathématiques.


Nous avons du  mal en français à  trouver des termes pour  désigner les domaines
gravitant autour  de l'informatique. Ce  dernier mot est souvent  remplacé par
\textsc{Tice}  (  avec  un  T  comme  \textit{technologie}...cela  restreint  le
domaine  et permet  de  comprendre pourquoi  pendant  si longtemps  informatique
rimait avec bureautique) ou bien
par \textit{numérique} et  la dernière mode est de parler  de \textit{code}. Les
anglo-saxons parlent de \textit{Computer  Science}, désignation qui a l'avantage
de comporter le  mot \textit{science}. \textit{Computer Science}  est \textbf{en relation
avec}   les   domaines   \textit{Scientific   Computing}   et   \textit{Computer
Engineering} mais n'est pas du tout réduit à ces deux composantes proches.

Le département de \textit{Computer Science}  de l'Université de Boston s'adresse
ainsi                     à                    ses                     futur(e)s
étudiant(e)s (\cite{boston}):

\begin{quote}
  \og \textit{Computer Science is about problem solving. Thus, the qualities of a good computer scientist include a passion for
finding elegant solutions, an ability to use mathematical analysis and logical rigor to evaluate such solutions, creativity
in modeling complex problems through the use of abstractions, attention to details and hidden assumptions, an ability to
recognize variants of the same problem in different settings, and being able to retarget known efficient solutions to
problems in new settings. If you like to solve puzzles, then computer science is for you!}\fg{}
\end{quote}

Cela ressemble beaucoup à ce que l'on attend d'élèves étudiant les mathématiques!...

\end{Abstract}

\setlength{\parindent}{0mm}

\section{Le lancer d'\oe uf ou comment faire de l'informatique sans ordinateur...}

\subsection{L'expérience}

Un groupe  d'élèves a fabriqué  des \oe ufs synthétiques  dans le cadre  des TPE
(très transversal : biologie, physique, mathématique et informatique) et voudrait
étudier sa solidité et en particulier sa resistance en cas de chute. 

Il mettent au point un protocole d'expérimentation.

Ils  acheminent $k$ \oe ufs
en bas du bâtiment principal de leur lycée qui a $N=2^n$ étages, le rez-de-chaussée
portant le numéro 0.

Le but de l'expérimentation est de  déterminer l'étage à partir duquel lancer un
\oe uf par la fenêtre lui (l'\oe uf..) est fatal.

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

On  suppose également  que  tant que  l'\oe uf  survit au  lancer,  on peut  le
réutiliser.  Pour économiser  le temps  et le  souffle des  expérimentateurs, on  va
chercher un algorithme qui minimise le  nombre d'essais effectués (et non pas le
nombre d'\oe ufs détruits).


Une première idée serait de commencer au premier étage et de lancer un \oe uf
de chaque étage jusqu'à atteindre l'étage  fatal. Si jamais l'étage fatal est le
dernier, cela nécessitera d'effectuer $N-2$ essais: c'est le pire cas.

Si l'on considère  que tous les étages sont potentiellement  fatals avec la même
probabilité, on effectuera avec cette méthode $(N-2)/2$ essais en moyenne.

Mais on peut faire mieux...

\subsection{Diviser pour régner}


\begin{flushleft}
\begin{minipage}[t]{3.5cm}
\begin{figure}
  \includegraphics[width=3.5cm]{sunzi}
\caption{\begin{CJK}{UTF8}{song}{\large 孫子}\end{CJK}\\
(544–496 av. J.-C.)
}
\end{figure}
\end{minipage}
\end{flushleft}
\vspace{-3.6cm}
\begin{flushright}
\begin{minipage}[t]{0.75\linewidth}


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

\end{minipage}
\end{flushright}
\vspace{1.6cm}

Nous allons diviser l'immeuble en deux  parties égales en considérant l'étage du
milieu:  si  cet  étage  est  fatal,  il suffira  de  chercher  dans  la  moitié
inférieure, sinon,  dans la  moitié supérieure de  l'immeuble. Nous  allons donc
effectuer une \textbf{recherche dichotomique} de l'étage fatal.


\begin{algo}
\STATE{inf\recoit{}Étage inférieur}
\STATE{sup\recoit{}Étage supérieur}
\STATE{milieu\recoit{} $({\rm inf} + {\rm sup})/2$}
\IF{estFatal(milieu)}
\STATE{ChercherEntre(inf,milieu)}
\ELSE
\STATE{ChercherEntre(milieu, sup)}
\ENDIF 
\end{algo}


Quand  va-t-on  s'arrêter  de  découper  l'immeuble?  Lorsqu'il  n'y  aura  plus
d'ambiguité, c'est-à-dire lorsque l'étage supérieur sera directement au-dessus de l'étage
inférieur.
La fonction devient:


\begin{algo}
 \FUNC{ChercherEntre}{\pfarg{inf, sup}{Entiers}}{Entier}
\COMMENT{pré-condition: il existe au moins un étage fatal entre inf et sup, inf n'est pas fatal et inf < sup}
\COMMENT{invariant: le plus petit étage fatal est entre inf (non compris) et sup}
\COMMENT{post-condition: la valeur retournée est le plus petit étage fatal}
\IF{sup == inf + 1}
\RETURN{sup}
\ELSE
\STATE{milieu\recoit{} $({\rm inf} + {\rm sup})/2$}
\IF{estFatal(milieu)}
\STATE{ChercherEntre(inf,milieu)}
\ELSE
\STATE{ChercherEntre(milieu, sup)}
\ENDIF
\ENDIF 
\end{algo}

On peut  donner une version non  récursive équivalente mais moins  naturelle: se
dire  \og  je  recommence  l'expérience  dans  la  moitié  supérieure\fg{}  fait
clairement penser à un processus récursif.
 

\begin{algo}
\FUNC{ChercherEntre}{\pfarg{N}{Entier}}{Entier}
\COMMENT{pré-condition: il existe au moins un étage fatal entre inf et sup, inf n'est pas fatal et inf < sup}
\COMMENT{invariant: le plus petit étage fatal est entre inf (non compris) et sup}
\COMMENT{post-condition: la valeur retournée est le plus petit étage fatal}
\STATE{inf \recoit{} 0}
\STATE{sup \recoit{} N}
\WHILE{sup > inf + 1}
\COMMENT{le  plus petit étage  fatal est  entre inf (non  compris) et
  sup et sup > inf + 1}
\STATE{milieu\recoit{} $({\rm inf} + {\rm sup})/2$}
\IF{estFatal(milieu)}
\STATE{sup = milieu}
\ELSE
\STATE{inf = milieu}
\ENDIF
\ENDWHILE
\COMMENT{le plus petit étage  fatal est entre inf (non compris) et  sup et sup =
  inf + 1}
\RETURN{sup}
\COMMENT{ la valeur retournée est le plus petit étage fatal}
\end{algo}


Qu'a-t-on gagné?  Mais d'abord, est-ce  que notre fonction nous  renvoie l'étage
attendu? Et d'abord, renvoie-t-elle quelque chose?

Déterminer   les  réponses   à  ces   questions  constitue   les  trois   étapes
indispensables de l'étude d'un algorithme:

\begin{enumerate}
\item étude de  la\textit{ terminaison} de l'algorithme: est-ce  que la fonction
  renvoie effectivement une valeur?
\item étude  le la \textit{correction}  de l'algorithme: est-ce que  la fonction
  renvoie la valeur attendue?
\item  étude  de la  \textit{complexité}  de  l'algorithme: peut-on  estimer  la
  vitesse d'exécution de cet algorithme?
\end{enumerate}


\begin{enumerate}
\item Pour  répondre à  la première  question, il  suffit de  remarquer qu'au  départ,
l'intervalle d'étude  est l'ensemble $\bigl\{0,1,...,N-1\bigr\}$ de  longueur $N$. Après
chaque appel récursif, la longueur de l'intervalle est divisée par deux. 

Notons $\ell_i$ cette  longueur après $i$ appels récursifs. La  suite $\ell$ est
géométrique de raison $1/2$ et de premier terme $N$.

On a donc $\ell_i=\frac{N}{2^i}=\frac{2^n}{2^i}=2^{n-i}$. Ainsi $\ell_n=1$ et
l'algorithme s'arrête. 

\item Vérifions d'abord que l'invariant est valide à chaque appel récursif:
  c'est  vrai  au départ  car  on  précise qu'un  étage  fatal  existe entre  le
  rez-de-chaussée et le dernier étage.

  Par construction, on choisit inf et sup pour que le plus petit reste entre inf
  et sup et que la borne inférieure ne soit pas fatale.

  Quand la  récursion s'arrête,  l'intervalle est en  fait $\bigl\{\mathrm{inf},
  \mathrm{inf} + 1\bigr\}$ et inf
  n'est pas fatal donc $\mathrm{inf} + 1$ l'est et est la valeur cherchée.

\item Combien  de temps nous a-t-il  fallu? Mais d'abord comment  mesure-t-on le
  temps?

  Nous ne sommes pas sur machine mais dans les bâtiments d'un lycée. Il faut
  compter le temps de chute, le temps  de remontée des \oe ufs encore en état, le
  temps  de manipulation  pour passer  les \oe ufs  par la  fenêtre, l'examen  de
  l'état de l'\oe uf ayant chu.  Selon
  l'efficacité des muscles
  et l'état  de santé  des expérimentateurs,  nous pouvons poser  que ces  temps sont
  proportionnels  au nombre  d'étages, mis  à part  le temps  de passage  par la
  fenêtre   qui   est   constant   ainsi   que  l'examen   de  l'\oe uf   par   un
  expert\footnote{C'est  ce  qui correspondra  par  exemple  en informatique  au
    parcours d'une liste chaînée.}.


  ...Mais  c'est   un  peu  compliqué...On   va  supposer  que   l'ascenseur  est
  ultra-performant et que  les \oe ufs sont très légers ce  qui entraîne que tous
  ces temps  sont à peu  près constants, quelque soit  l'étage\footnote{C'est ce
    qui  correspondra  par exemple  en  informatique  au parcours  d'un  tableau
    statique.}.

  Il suffit donc de compter combien de lancers ont été effectués. La réponse est
  dans l'étude faite  pour prouver la terminaison: c'est à  l'étape $n$ que l'on
  atteint la condition de sortie de l'algorithme.

  Que vaut $n$? On  a posé au départ que le nombre  d'étages était une puissance
  de 2: $N=2^n$. Ainsi, $n=\log_2N$.

  Finalement, le nombre de tests effectués est égal au logarithme en base 2 du
  nombre d'étages. Et  le temps? Et bien,  ce n'est pas ce  qui nous intéressait
  puisqu'on nous  demandait de mesurer  le nombre  de tests effectués  mais cela
  nous a  permis d'introduire la  notion de \textit{complexité}  d'un algorithme
  dont la mesure va dépendre de l'unité  choisie et sera plus ou moins difficile
  à déterminer.


  Si notre  immeuble a  1024 étages,  nous sommes  donc passés  de 1022  tests au
  maximum à 10 tests  ce qui n'est pas négligeable, surtout  pour les jambes des
  expérimentateurs.


\end{enumerate}


\subsection{Le bug de Java}

Pendant 9  ans, jusqu'en 2006, les  fonctions de recherche dichotomique  en Java
cachaient un bug...

Voici      ce     que      l'on      trouvait      dans     la      bibliothèque
\Colorbox{blue!10}{\lstinline{java.util.Arrays}}:


\begin{javacode}
public static int binarySearch(int[] a, int key) {
         int low  = 0;
         int high = a.length - 1;

         while (low <= high) {
             int mid    = (low + high) / 2;
             int midVal = a[mid];

             if (midVal < key)
                 low = mid + 1
             else if (midVal > key)
                 high = mid - 1;
             else
                 return mid; // key found
         }
         return -(low + 1);  // key not found.
     }  
\end{javacode}

Regardez la ligne 6: \mintinline{java}{int mid    = (low + high) / 2;}.

Tout va bien...mais en fait il faut se souvenir que les entiers sont codés en général
sur 64  bits et  que le  successeur de  $2^{63}-1$ n'est  pas $2^{63}$  mais son
opposé car on représente les nombres relatifs sur machine d'une manière spéciale
\footnote{Voir      par     exemple      le      bug      de     l'an      2038:
  \href{https://fr.wikipedia.org/wiki/Bug\_de\_l\%27an\_2038}{https://fr.wikipedia.org/wiki/Bug\_de\_l\%27an\_2038}}. Étudier
la manière de représenter les relatifs  sur machine est un problème intéressant:
un exemple de recherche sur ce thème est donné en \vref{exo::comp2}.

Le bug a été corrigé\footnote{\href{http://bugs.java.com/bugdatabase/view\_bug.do?bug\_id=5045582}{http://bugs.java.com/bugdatabase/view\_bug.do?bug\_id=5045582}} en remplaçant cette ligne par:

\mintinline{java}{ int mid = low + ((high - low) / 2);}


Il faudra faire de même dans nos fonctions!




\subsection{Questions subsidiaires}
\begin{enumerate}
\item  \textbf{Que  se  passe-t-il  si   nous  avons  moins  de}  $\mathbf{n=  }$
  \textbf{log}$\mathbf{_2}$\textbf{(N) \oe ufs pour
    tester?}

 Aïe! Notre  dichotomie ne peut aller  jusqu'au bout. L'idée est  de l'appliquer
 $k-1$ fois ($k$  étant le nombre de  \oe ufs à diposition). Il se  peut que nous
 n'ayons pas abîmé de \oe uf. Il se peut aussi que nous ayons cassé un \oe uf à
 chaque fois si  l'étage fatal est très  petit. Il nous reste donc  \textit{dans le pire
 des cas} un \oe uf et $N/2^{k-1}$ étages non testés. 

 On  va  donc partir  du  plus  bas et  remonter  jusqu'à  casser notre  dernier
 \oe uf. \textit{Dans le pire des cas}, ce sera le dernier testé.

 Ainsi, s'il nous reste  assez de \oe ufs (si l'étage fatal  n'est pas trop bas),
 nous pourrons appliquer  la dichotomie jusqu'au bout. Dans le  pire des cas, il
 faudra effectuer $k-1+\frac{N}{2^{k-1}}-1$ tests.

 \item \textbf{Que se passe-t-il si nous n'avons que 2 \oe ufs et que n est pair?}
   
 Si l'on applique une fois la dichotomie, il nous restera N/2 tests à effectuer.

 On peut faire mieux...
 
 Il suffit  de découper l'immeuble  en $\sqrt{N}=2^{n/2}$ paquets  de $\sqrt{N}$
 étages.

 On  commence par  tester  l'étage $\sqrt{N}$  puis éventuellement  $2\sqrt{N}$,
 etc. Bref, on effectue une recherche séquentielle du paquet fatal.

 Ensuite, il  suffit d'utiliser  le deuxième  \oe uf (le  premier est  cassé pour
 déterminer  le paquet  fatal) afin  d'effecteur une  recherche séquentielle  de
 l'étage  fatal  cette  fois. Dans  le  pire  des  cas,  cela va  nous  demander
 $\sqrt{N}-1$ tests. 

 Bref, dans le pire des cas, nous effectuerons $2\sqrt{N}-1$ tests.


 \item \textbf{Que se passe-t-il quand N n'est pas une puissance de 2?}

   Ce  n'est   pas  grave  car  le   nombre  de  tests  croît   avec  le  nombre
   d'étages dans limmeuble. Or, pour tout  entier naturel N, il existe un entier
   $n$ tel que: 

   $$2^n \leqslant N < 2^{n+1}$$

   Si on  appelle T la  fonction qui, au nombre  d'étages, associe le  nombre de
   tests par la méthode dichotomique, alors:

   $$T(2^n)=n \leqslant T(N) < n+1$$
   
   donc $T(N)=n=\lfloor \log_2(N)\rfloor$.

   \item \textbf{Et si nous avions fait de la trichotomie}


     On  pourrait penser  que diviser  notre immeuble  en 3  pourrait être  plus
     efficace  car   on  divise  la   taille  de  l'intervalle  suivant   par  3
     \textit{mais} on effectue au pire deux tests à chaque fois.

     Ainsi, dans  le pire  des cas  on effectuera  (en supposant  que N  est une
     puissance                               de                               3)
     $2\log_3(N)=2\frac{\ln(N)}{\ln(2)}\times\frac{\ln(2)}{\ln(3)}\simeq
     1,3\log_2(N)$ tests donc ce n'est pas mieux  et ça ne fera qu'empirer si on
     augmente le nombre de divisions...

     La division par 2 serait-elle magique?

\end{enumerate}


\section{Diviser ne permet pas toujours de régner}

Considérons un problème mathématique simple: la multiplication de deux entiers.

Vous savez additionner deux entiers de $n$ chiffres: cela nécessite $\lambda_1 n $ additions
de nombres de un chiffre compte-tenu des retenues avec $\lambda_1$ une constante positive.

Multiplier un entier de $n$ chiffres par un entier de 1 chiffre prend $\lambda_2 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 $\lambda_3 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 $\lambda n$ donc le temps d'exécution est défini par:

$$T(n)=4T(\lfloor n/2\rfloor) +\lambda 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.

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





Alors la relation de récurrence devient:

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

On obtient:


$$x_k=4(4x_{k-2}+\lambda'  2^{k-1})+\lambda  2^k  =  4^kx_0+\sum_{i=1}^k\Lambda_k  2^k
=4^k+k\Lambda_k 2^k =n^2 + \Lambda_kn \log
n \sim n^2 $$

Car nous  verrons que l'on  peut encadrer  ce $\Lambda_k$ entre  deux constantes
positives dans la dernière section.


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




\section{Et la recherche dichotomique d'une solution d'une équation réelle?}


Quel rapport entre la recherche dichotomique dans un tableau (ou un immeuble) et
la recherche des solutions d'une équation $f(x)=0$ dans $\bbr$?

Pour mettre en \oe  uvre une telle méthode, il faut donner  une précision. On ne
travaille que sur  des approximations décimales ou plutôt à  l'aide de nombres à
virgule flottante en base 2.

Par exemple, si nous cherchons une approximation de $x^2-2=0$ par la méthode de dichotomie avec
une précision de  $2^{-10}$ entre 1 et  2, il va falloir chercher  un nombre (un
étage) dans un tableau (un immeuble) de $2^{10}$ nombres (étages):


\begin{center}
\begin{tabular}[!h]{|c|c|c|c|c|c|}
  \hline
$1$      &      $1+2^{-10}$      &     $1+2\times      2^{-10}$&      $1+3\times
2^{-10}$&$\cdots$&$1+2^{10}\times 2^{-10}$\\
\hline
\end{tabular}
\end{center}


Notre  fonction  booléenne  \og  estFatal\fg{}  est alors  le  test  $x  \mapsto
\mathtt{x*x <= 2}$ et l'on va chercher  une cellule de ce tableau par dichotomie
comme on cherchait un étage dans un immeuble.

\begin{pythoncode}
  def racineDicho(prec):
    cpt = 0
    inf = 1
    sup = 2
    while (sup - inf > prec):
        m = inf + (sup - inf) / 2
        cpt += 1
        if m*m <= 2:
            inf = m
        else:
            sup = m
    return sup,cpt
\end{pythoncode}


Nous obtenons:

\begin{pythoncode}
In [1]: racineDicho(2**(-10))
Out[1]: (1.4150390625, 10)

In [2]: racineDicho(2**(-15))
Out[2]: (1.414215087890625, 15)

In [3]: racineDicho(2**(-20))
Out[3]: (1.4142141342163086, 20)

In [4]: racineDicho(2**(-30))
Out[4]: (1.4142135623842478, 30)

In [5]: racineDicho(2**(-50))
Out[5]: (1.4142135623730958, 50)
\end{pythoncode}


Attention!  Il  faudra  s'arrêter  à  la précison  $2^{52}$  compte-tenu  de  la
représentation des nombres sur machine. N'hésitez pas à parcourir 

 \href{http://download.tuxfamily.org/tehessinmath/les\%20pdf/JA2014.pdf}{http://download.tuxfamily.org/tehessinmath/les\%20pdf/JA2014.pdf}

ou 

\href{http://download.tuxfamily.org/tehessinmath/les\%20pdf/PolyAnalyse14.pdf}{
http://download.tuxfamily.org/tehessinmath/les\%20pdf/PolyAnalyse14.pdf}

pour plus de précisions ;-)


On \og voit\fg{} que le nombre de tests correspond à la longueur de l'intervalle
exprimé  en  \og logarithme  de  la  précision\fg{}:  ici, l'intervalle  est  de
longueur 1.




\section{La complexité sur machine: approche expérimentale et théorique}

\subsection{Le problème}


  \textit{On dispose  d'une  liste  de  N nombres.  Déterminez  les
  triplets dont la somme est nulle}.

Ici,  diviser va  difficilement  nous permettre  de régner.  Intuitivement, on  peut
facilement diviser notre liste en 2  et rechercher les triplets annulateurs dans
chaque moitié  mais il faudra recommencer  sur toute la liste  pour chercher des
triplets  d'éléments appartenant  à des  moitiés différentes  donc on  a peu  de
chance de gagner du temps.



\subsection{Méthode expérimentale}


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 [1]: %timeit trois_sommes([randint(-10000,10000) for k in range(100)])
10 loops, best of 3: 27.5 ms per loop

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

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


On aurait plus être plus concis en utilisant des listes par compréhension:

\begin{pythoncode}
def trois_sommes_comp(xs):
    n = len(xs)
    return len([(i,j,k) 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 ])  
\end{pythoncode}


Mais les temps sont les mêmes:

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

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

In [26]: %timeit trois_sommes_comp([randint(-10000,10000) for k in range(400)])
1 loops, best of 3: 1.85 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

def temps(xs):
    debut = perf_counter()
    trois_sommes(xs)
    return perf_counter() - debut

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 [4]: ratio
Out[4]: [7.523860206447286, 9.118789882406599, 8.5098312160934]

In [5]: list(logratio)
Out[5]: [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 [6]: temps(range(400))
Out[6]: 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 [7]: temps(range(1000))
Out[7]: 68.54615448799996  
\end{pythoncode}

Presque...




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



En Haskell:


\begin{haskellcode}
import Criterion.Main

-- La fonction
troisSommes :: [Int] -> [(Int,Int,Int)]
troisSommes xs =
    let inds = [0 .. (length xs -1)]
    in [(xs!!i , xs!!j , xs!!k) | i <- inds, j <- drop i inds, k <- drop j inds, xs!!i + xs!!j + xs!!k == 0]

-- Le "benchmarking" avec le module Criterion
main :: IO()
main = defaultMain [
        bgroup "TroisSommes" [ bench "3som 100"  $ whnf troisSommes [-50..49]
                             , bench "3som 200"  $ whnf troisSommes [-100..99]
                             , bench "3som 400"  $ whnf troisSommes [-200..199]
                             , bench "3som 800"  $ whnf troisSommes [-400..399]
                             , bench "3som 1600"  $ whnf troisSommes [-800..799]
                             , bench "3som 3200"  $ whnf troisSommes [-1600..1599]
                       ]
       ]  
\end{haskellcode}


et on observe:

\begin{bashcode}
$ ./TroisSom --output troisSom.html
benchmarking TroisSommes/3som 100
time                 640.9 μs   (636.3 μs .. 645.0 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 640.4 μs   (637.6 μs .. 644.4 μs)
std dev              11.88 μs   (9.047 μs .. 15.88 μs)

benchmarking TroisSommes/3som 200
time                 4.322 ms   (4.305 ms .. 4.344 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 4.358 ms   (4.342 ms .. 4.384 ms)
std dev              65.63 μs   (42.33 μs .. 119.0 μs)

benchmarking TroisSommes/3som 400
time                 31.72 ms   (31.43 ms .. 32.08 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 31.58 ms   (31.50 ms .. 31.75 ms)
std dev              239.8 μs   (83.75 μs .. 368.0 μs)

benchmarking TroisSommes/3som 800
time                 261.7 ms   (259.7 ms .. 263.6 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 262.8 ms   (262.0 ms .. 263.2 ms)
std dev              758.8 μs   (95.48 μs .. 967.9 μs)
variance introduced by outliers: 16% (moderately inflated)

benchmarking TroisSommes/3som 1600
time                 2.318 s    (2.289 s .. 2.339 s)
                     1.000 R²   (NaN R² .. 1.000 R²)
mean                 2.320 s    (2.314 s .. 2.323 s)
std dev              4.803 ms   (0.0 s .. 4.834 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking TroisSommes/3som 3200
time                 16.47 s    (15.00 s .. 17.51 s)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 17.33 s    (16.82 s .. 17.64 s)
std dev              471.1 ms   (0.0 s .. 535.4 ms)
variance introduced by outliers: 19% (moderately inflated)
\end{bashcode}


Encore un rapport de 8 pour chaque doublement de taille mais Haskell est 60 plus
rapide que Python.

\textbf{Conclusion}: {\bfseries Python, Haskell 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 quand on parlera
de complexité)
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}

% \begin{center}
%   %\begin{figure}
%   \includegraphics[width=3cm]{hackers}
% %\end{figure}
% \end{center}



\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{}.
Rappelons une définition pour plus de clarté:

\medskip

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

\medskip


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

\medskip


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


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:

\medskip


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

\begin{flushleft}
\begin{minipage}[t]{2.25cm}
\begin{figure}
  \includegraphics[width=2.25cm]{knuth}
\caption{
D. E. Knuth \\
Né en 1938
}
\end{figure}
\end{minipage}
\end{flushleft}
\vspace{-4.6cm}
\begin{flushright}
\begin{minipage}[t]{0.85\linewidth}


Une   bonne  lecture   de   chevet   est  le   troisième   volume   de  \og   The
Art\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.

\end{minipage}
\end{flushright}
\vspace{1.6cm}





\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 echelle log-log')
plt.xlabel('Taille des listes')
plt.ylabel('Temps en s')
\end{pythoncode}



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

C'est assez rectiligne.

Regardons  de  nouveau   le  code  des  trois  sommes  et   comptons  le \textbf{ nombre
d'opérations  élémentaires}:  ces  opérations  élémentaires  représentent  notre
\textbf{unité de  temps théorique}. Dans certains  cas, il est difficile  de les
distinguer.

Ici,  notre algorithme  est  suffisamment basique  pour  pouvoir distinguer  des
opérations que nous  considèrerons à coût constant: une  déclaration de variable
($d$ unités de temps),
une affectation  ($a$ unités de  temps), l'accès à  un élément d'une  liste ($x$
unités de temps), une somme d'entiers ou un
incrément ($s$ unités de temps), une  comparaison entre deux entiers ($c$ unités
de temps).

Chacune de  ces actions  va compter  pour un nombre  constant d'unités  de temps
qu'on ne connait pas  a priori, qui dépendra du système  sur lequel on travaille
mais on verra que leur valeur réelle ne nous intéresse pas. 

Il ne reste plus qu'à
déterminer leurs fréquences dans l'algorithme.


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



\begin{center}

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


\end{center}


Que valent  $S_1$ et $S_2$?  Pour $S_1$ il s'agit  du nombre d'itérations  de la
boucle incrémentée par $j$ et
pour $S_2$ ce sera $k$. 

Cela implique un petit travail classique sur les sommes voire les doubles sommes d'entiers.

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


\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' \qquad (j'=N-(j+1))\\
     &=&\sum_{i=0}^{N-2}\frac{(N-(i+2))(N-(i+1))}{2} \\
     &=&\sum_{i'=1}^{N-2}\frac{i'(i'+1)}{2}\qquad (i'=N-(i+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!


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




\section*{Annexe 1: Plus fort que la dichotomie...l'algorithme de Héron et sa complexité}

\textbf{La dichotomie  est peu  efficace\footnote{Pour visualiser  un algorithme
    dichotomique très efficace, on peut regarder le tri rapide dansé: \href{https://www.youtube.com/watch?v=ywWBy6J5gz8}{https://www.youtube.com/watch?v=ywWBy6J5gz8}...} pour trouver la solution d'une équation numérique
par rapport à  l'algorithme de Héron. Pour démontrer cette  supériorité du point
de vue de la complexité, il nous faut introduire aux élèves quelques outils mathématiques.}


Le mathématicien \textsc{Héron} d'Alexandrie n'avait pas attendu \textsc{Newton} et le
calcul différentiel  pour trouver  une méthode permettant  de déterminer
une approximation de la racine carrée d'un nombre entier positif puisqu'il a
vécu seize siècles avant Sir Isaac.


Si  $x_n$  est une  approximation  strictement  positive  par défaut  de
$\sqrt{a}$, alors $a/x_n$ est  une approximation par excès de $\sqrt{a}$
 et vice-versa.

La    moyenne   arithmétique    de   ces    deux    approximations   est
$\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$  et constitue  une meilleure
approximation que les deux précédentes.

On  peut  montrer c'est  une  approximation  par  excès (en  développant
$\left(x_n-\sqrt{a}\right)^2$ par exemple).


En voici deux versions, une récursive et une itérative.  

%\begin{multicols}{2}
\begin{pythoncode}
def heron_rec(a,fo,n):
       if n == 0:
              return fo
       return heron_rec(a,(fo + a / fo) / 2, n - 1)

def heron_it(a,fo,n):
       app = fo
       for k in range(n):
              app = (app + a / app) / 2
       return app
\end{pythoncode}

Ce qui donne par exemple:

\begin{pythoncode}
In [12]: heron_rec(2,1,6)
Out[12]: 1.414213562373095

In [13]: heron_it(2,1,6)
Out[13]: 1.414213562373095

In [14]: from math import sqrt

In [15]: sqrt(2)
Out[15]: 1.4142135623730951

\end{pythoncode}




\paragraph{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:  Banach,   Borel,  Brouwer,  Kakutani,
Kleene,…Celui  qui nous  intéresserait  le  plus en  informatique  est celui  de
Knaster-Tarski.  Ils donnent tous des conditions d'existence
de points  fixes (des solutions  de $f(x)=x$  pour une certaine  fonction). Nous
nous contenterons de la version light abordable au lycée.  


\begin{Theoreme}[Un théorème light du point fixe]
  Soit I un intervalle fermé de $\mathbb R$, soit $f$ une fonction continue 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Ν 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$. On peut alors démontrer par récurrence que

\begin{enumerate}

   \item  pour tout entier naturel non nul $n$, on a $r_n \geqslant \sqrt{2}$;
    \item la suite est décroissante;
    \item $\sqrt{2}$ est l'unique point fixe positif de $f$.
\end{enumerate}


On peut alors conclure et être assuré que notre algorithme va nous permettre d'approcher $\sqrt{2}$.




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


Déterminons  l'ordre  et la  constante  asymptotique  d'erreur  de la  suite  de
Babylone donnant une approximation de $\sqrt{2}$. 
 On  démontre   que  $$
\left|r_{n+1} - \sqrt{2}\right| = \left| \frac{(r_n-\sqrt{2})^2}{2r_n}\right| $$

Ainsi   la   suite   est   d'ordre   2  et   sa   constante   asymptotique   est
$\frac{1}{2\sqrt{2}}$. Ici, on peut même avoir une idée de la vitesse sans étude
asymptotique.  

En  effet,  on  a  $r_n \geqslant  1$  donc  $$  \left|r_{n+1}  -
  \sqrt{2}\right| \leqslant \left| (r_n-\sqrt{2})^2\right| $$ 

Le nombre de  décimales d'un
nombre   positif   plus    petit   que   1   est    $-\log_{10}x$.   En   posant
$d_n=-\log_{10}|r_n-\sqrt{2}|$ on  obtient donc que $d_{n+1}  \geqslant 2d_n$: à
chaque tour de boucle, on double au minimum le nombre de bonnes décimales.


 La
précision de  la machine  étant de  16 décimales  si les  nombres sont  codés en
binaires sur 64 bits, \textbf{il faut au  maximum 6 itérations pour obtenir la précision
maximale}.  






\section*{Annexe 2: un exemple de TP sur les relatifs et le 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 Anonyme}
\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.

  Écrivez en compréhension l'ensemble des  nombres que l'on peut ainsi
  représenter et qui se note sur Haskell \lstinline{Int8}.

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



  \begin{haskellcode}
> let n = 256 :: Int8
> n
0
  \end{haskellcode}

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 (illustration  en Haskell  pour faciliter
l'utilisation d'enteirs 8 bits):

\begin{haskellcode}
> let n = 13 :: Int8
> n * 2
26
> n * 4
52
> n * 8
104
> n * 16
-48
> n * 32
-96
> n * 64
64
\end{haskellcode}

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}


  









%%% biblio et fin 
\renewcommand{\bibname}{Lectures recommand\'ees pour aller plus loin}
\nocite{*}
\bibliography{DichoRepere}


   \end{document}

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