%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8x,chinois]{preambuleTrm}



\usepackage{iwona}


\mode<presentation>
{
  %\usetheme{Bergen}%Montpellier}
  % or ...Frankfurt, 
  \usetheme[secheader]{Madrid}

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
  \usefonttheme{progressbar}
  \useoutertheme{progressbar}
  %\useinnertheme{progressbar}
  \progressbaroptions{% titlepage=normal,
    imagename=images/logoirem}

}
\usepackage{elephantbird}


%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}

\ifpdf \DeclareGraphicsRule{*}{mps}{*}{} \fi
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes,arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap,shadows,patterns}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}
\hypersetup{pdfpagemode=FullScreen}

\usepackage[detect-all]{siunitx}

\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

\usepackage{scalefnt}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage[square]{daedale}
\bibliographystyle{cyclope}


\usepackage{algo}

\renewcommand{\algocommentfont}{\tiny\ttfamily\itshape}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/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/}{/home/moi/PREPA/IPT/2014_15/Poly/}}




\setcounter{tocdepth}{2} %\setcounter{page}{0}


\newcommand{\triangleup}{\Delta}













%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%            T O U R S     D E     H A N O I
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% The logic for Hanoi, we record the disques at every tige
% as a comma separated list ending with a '.'; i.e. the
% starting list for 4 disques would be 1,2,3,4,.
\newcount\ndisques

\newcount\nmv
\def\inittiges#1{
    \nmv=0
    \def\disquelist{}
    \foreach \n in {1,...,#1} {
        \xdef\disquelist{\disquelist\n,}
    }
    \expandafter\xdef\csname tige 1\endcsname{\disquelist.}
    \expandafter\gdef\csname tige 2\endcsname{.}
    \expandafter\gdef\csname tige 3\endcsname{.}
}

% Delimited macro; #1 is everything up to the first ',' and
% #2 everything after it.
\def\head#1,#2.{#1}
\def\tail#1,#2.{#2}

% This macro updates the disque lists, its arguments are the name
% names of the macro's corresponding to the tiges, for example
% 'tige 1' and 'tige 3'.
\def\movedisque#1#2{
    \edef\lista{\csname #1\endcsname}
    \edef\listb{\csname #2\endcsname}
    \expandafter\xdef\csname #2\endcsname{\expandafter\head\lista,\listb}
    \expandafter\xdef\csname #1\endcsname{\expandafter\tail\lista.}
}


% Updates the lists and then draws a new frame.
\def\move#1#2#3{
    \movedisque{tige #1}{tige #2}
    \gdef\fmsg{\node[anchor=north] at (3.8,-.5)  {On d\'eplace le disque
        de la 
        tige #1 vers la tige #2.};}
    \drawtiges
}

% This macro boils down to a well-known recursive solution, as given
% here for example: http://en.wikipedia.org/wiki/Towers_of_Hanoi#Recursive_solution
%
% #1 Tige to move from
% #2 Tige to move to
% #3 Tige to use as scratch
% #4 Number of disks #5 mvts
\def\rhanoi#1#2#3#4#5{
    \ifnum#4>1
        {\advance#5 by \the#5\advance#4 by -1 \advance#5 by 1\rhanoi#1#3#2#4#5}
        {\move{#1}{#3}{#5}}
        {\advance#5 by \the#5 \advance#5 by 1\advance#4 by -1 \rhanoi#2#1#3#4#5}
    \else
        {\move{#1}{#3}{#5}}
    \fi
}



% Below is the TikZ code to draw the towers:
\tikzset{
    disque/.style={shade, shading=radial, rounded rectangle,minimum height=.5cm,
        inner color=#1!20, outer color=#1!60!purple, text=sislyellow!0!black},
    disque 1/.style={disque=sislcyan, minimum width=15mm},
    disque 2/.style={disque=sislorange, minimum width=20mm},
    disque 3/.style={disque=sislred, minimum width=25mm},
    disque 4/.style={disque=black, minimum width=30mm},
    disque 5/.style={disque=purple, minimum width=35mm},
    disque 6/.style={disque=sislyellow, minimum width=40mm},
}

% Define some colors, I don't like plain green and brown.


\newcommand{\tige}{
  \fill[sislcyan] (-1.6cm, 0) rectangle (1.6cm,0.25cm)
    (-1.25mm,2.5mm) rectangle (1.25mm,4.25cm);
}

% Because the list starts with the topmost disque, we
% use two recursive macro's to invert the drawing process.
\newcount\curlevel

% This macro checks whether the list is empty, if not,
% it calls \rdrawdisques which removes one element and
% calls this one again.
\def\drawdisques#1.{
    % If #1 is empty, this expands to \if.. which is true, otherwise
    % we're safe to assume there's at least one element.
    \expandafter\if#1..\else
        \rdrawdisques#1.
        \advance\curlevel by 1\relax
    \fi
}

\def\rdrawdisques#1,#2.{
    \drawdisques#2.
    {\edef\n{\the\curlevel}
        % Draw the actual disk.
        \node[disque #1,yshift={\n*5mm}] {#1};
    }
}

\def\disques#1{
    \curlevel=1
    \expandafter\drawdisques#1
}

% Draws the whole situation based on the lists.
\def\drawtiges{
    \begin{frame}{\ftitle}
    \begin{tikzpicture}
        \foreach \n/\x in {1/0cm,2/3.8cm,3/7.6cm} {
            \begin{scope}[xshift=\x]
                \tige
                \expandafter\disques\csname tige \n\endcsname
            \end{scope}
        }
        % Macro that either contains something like OK or
        % the last move.
        \fmsg
        % We use this to prevent the picture from jumping between
        % frames.
        \useasboundingbox (-1.6cm,-1.2cm) rectangle (9.2cm,4.25cm);
    \end{tikzpicture}
    \end{frame}
}

% Main macro, inits the lists for the current number, sets a title
% for the frame and starts the recursion.

\def\hanoi#1{
    \ndisques=#1
    \inittiges{#1}
    \ifnum\ndisques=1
        \xdef\ftitle{Tours de Hanoi -- \the\ndisques\ Disque}
    \else
        \xdef\ftitle{Tours de Hanoi -- \the\ndisques\ Disques}
    \fi
    \gdef\fmsg{}
    % Starting frame.
    \drawtiges
    % Recursion draws a new frame for every step.
    \rhanoi{1}{2}{3}{\ndisques}{\nmv}
    % Final frame.
    \gdef\fmsg{\node[] at (3.8,2.5) {\Huge\scalefont{2}\color{sislyellow}OK};}
    \drawtiges
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   fin Hanoi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%












\begin{document}


\title[] % (optional, use only with long paper titles)
{Calcul de complexité}

\subtitle{Journées \textsc{Irem} 2015}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{Irem} de Nantes}% (optional, but mostly needed)

%\logo{\includegraphics[width=0.1\textwidth]{logoirem}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{8 et 9 avril 2015}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

% \AtBeginSubsubsection[]
% {
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\scriptsize
% \begin{multicols}{2}
%     \tableofcontents[currentsection,currentsubsection]
%        \end{multicols}
% }

%   \end{frame}
% }




\AtBeginSubsection[]
{\scriptsize
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\tiny
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
%\ThisCenterWallPaper{1}{logoiremBigInv}
 \Large \titlepage 
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}


\section{Un premier jeu}




    \hanoi{1}
    \hanoi{2}
    \hanoi{3}
    \hanoi{4}
    \hanoi{5}

    % For 5 disques we don't show everything (although it could be done).
    \ndisques=6
    \inittiges{6}
    \def\ftitle{Tour de Hanoi -- \the\ndisques\ Disques}
    \def\fmsg{\node[cloud, draw, fill=gray, aspect=2] at (3.8,2.5) {\Huge\scalefont{2}?};}
    \drawtiges





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

\subsection{L'expérience}


\begin{frame}
  
\begin{figure}[ht]
  \centering
  \includegraphics[height=5cm]{hudsucker}
  \caption{Expérience informatique\label{fig:piano} }
\end{figure}
\end{frame}







\begin{frame}
  \begin{itemize}
  \item $k$ actionnaires
  \item $N=2^n$ étages
  \item RDC $ = 0$
  \item Il existe un étage fatal
  \item RDC non fatal
  \item Minimiser le nombre d'essais
  \end{itemize}
\end{frame}



\begin{frame}
  \begin{itemize}
  \item  Première idée:  on commence  au  rez-de-chaussée et  on progresse  d'un
    étage.
  \item Combien d'essais au pire?
  \item En moyenne
  \end{itemize}

\end{frame}



\subsection{Diviser pour régner}


\begin{frame}
  \begin{figure}
  \includegraphics[width=3.5cm]{sunzi}
\caption{\begin{CJK}{UTF8}{song}{\large 孫子}\end{CJK}\\
(544–496 av. J.-C.)
}
\end{figure}

\pause


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






\begin{frame}[fragile]
  
\begin{algo}
\STATE{inf\recoit{}Étage inférieur}
\STATE{sup\recoit{}Étage supérieur}
\STATE{milieu\recoit{} $(\text{inf} + \text{sup})/2$}
\IF{estFatal(milieu)}
\STATE{ChercherEntre(inf,milieu)}
\ELSE
\STATE{ChercherEntre(milieu + 1, sup)}
\ENDIF 
\end{algo}

\end{frame}




\begin{frame}[fragile]
  

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

\end{frame}



\begin{frame}
  \begin{itemize}
  \item terminaison
  \item correction
  \item complexité
  \end{itemize}
\end{frame}


\begin{frame}
\begin{itemize}
  \item terminaison $$\ell_i=\frac{N}{2^i}=\frac{2^n}{2^i}=2^{n-i}$$
  \item correction $$\bigl\{\text{inf},
  \text{inf} + 1\bigr\}$$
  \item complexité
    \begin{itemize}
    \item Liste chaînée
    \item tableau statique
    \item $n$? \pause $\log_2(N)$
    \end{itemize}
  \end{itemize}

  
\end{frame}


\begin{frame}[fragile]
  
\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}


\end{frame}







\begin{frame}[fragile]
  $$2^{63}-1 + 1= \pause -2^{63}$$


\pause

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


\end{frame}



\subsection{Questions subsidiaires}


\begin{frame}
  \begin{itemize}
  \item \textbf{Que  se  passe-t-il  si   nous  avons  moins  de}  $\mathbf{n=  }$
  \textbf{log}$\mathbf{_2}$\textbf{(N) actionnaires pour
    tester?}
\item \textbf{Que se passe-t-il si nous n'avons que 2 actionnaires et que n est pair?}

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



\begin{frame}
  
Trichotomie?

\pause


     \begin{figure}[ht]
       \centering
       \includegraphics[height=4cm]{tricot}
       \caption{Trichotomie manuelle\label{fig:tricot} }
     \end{figure}

\pause

$$2\log_3(N)=2\frac{\ln(N)}{\ln(2)}\times\frac{\ln(2)}{\ln(3)}\simeq
     1,3\log_2(N)$$ 

\end{frame}


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

\begin{frame}


  La multiplication de deux entiers de l'école primaire: complexité?

  \begin{itemize}
  \item Additions de deux entiers de $n$ chiffres?
  \item Multiplication d'un nombre de $n$ chiffres par un nombre de 1 chiffre?
  \item Multiplication de deux nombres de $n$ chiffres?
  \item Diviser pour régner?
  \end{itemize}

\end{frame}



\begin{frame}[fragile]



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


  
\end{frame}





\begin{frame}
  
$$T(n)=4T(\lfloor n/2\rfloor) +\lambda n \qquad T(1)=1$$


\pause

$$n=2^k$$

\pause


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



\pause




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

\pause

$$ T(n)\sim n^2 $$


\end{frame}




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


\begin{frame}
  $x^2-2=0$ précision $2^{-10}$


\pause

  \begin{itemize}
  \item solution $\ \longrightarrow$ étage
  \item tableau $\ \ \longrightarrow$ immeuble
  \item précision $\ \longrightarrow$ nombre d'étages
  \item \texttt{estFatal} $\longrightarrow$ $\mathtt{x} \mapsto \mathtt{x*x <= 2}$
  \end{itemize}
\end{frame}


\begin{frame}
  

\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}
\end{frame}


\begin{frame}[fragile]
\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}

\end{frame}


\begin{frame}[fragile]
\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}

\pause

\begin{pythoncode}
In [6]: sqrt(2)
Out[6]: 1.4142135623730951  
\end{pythoncode}



\end{frame}










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


\begin{frame}
  \begin{block}{Le problème}
    On dispose d'une liste L de N nombres.  Déterminez les
  triplets d'éléments de L tous distincts dont la somme est nulle
  \end{block}
\end{frame}


\subsection{Mesures expérimentales}



\begin{frame}[fragile]
\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}
\end{frame}




\begin{frame}[fragile]
\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}
\end{frame}




\begin{frame}[fragile]
\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}
\end{frame}



\begin{frame}[fragile]
\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}


\end{frame}

\begin{frame}[fragile]
  $aN^3$ \pause $a$?


\pause


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


\pause

$4,00 = a\times 400^3 $

\pause


$a\approx 6,25\times 10^{-8}$




\end{frame}


\begin{frame}[fragile]
   $N=1000$ \pause $6,25\times 10^{-8}\times10^9=62,5$

\pause


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

\end{frame}


\begin{frame}[fragile]
  \begin{ccode}
#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;
}
  \end{ccode}

\end{frame}

\begin{frame}[fragile]
  \begin{ccode}
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{ccode}
\end{frame}



\begin{frame}[fragile]
  \begin{ccode}
$ 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{ccode}
\end{frame}



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

\pause

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


\pause

Rappel Python: $a\approx 6,25\times 10^{-8}$

\pause

 \textbf{ORDRE DΕ CROISSANCE}

\end{frame}




\subsection{Analyse mathématique}



\begin{frame}
  \begin{figure}
  \includegraphics[height=0.5\textheight]{knuth}
\caption{
D. E. Knuth \\
Né en 1938
}
\end{figure}
\end{frame}


\begin{frame}
\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}


\pause

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

\end{frame}



\begin{frame}[fragile]
\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}

\end{frame}



\begin{frame}[fragile]

\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}
\end{frame}



\begin{frame}[fragile]

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

\end{frame}







\begin{frame}
  

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







\begin{frame}
  

\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
\end{tabular}
\end{center}
\end{frame}




\begin{frame}
  

\begin{center}

\begin{tabular}[!h]{|l|c|}
\hline
OPÉRATION & FRÉQUENCE\\
\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}
\end{frame}




\begin{frame}

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

\end{frame}


\begin{frame}
  
\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*}

\end{frame}



\begin{frame}
  
Notons 
\begin{itemize}
\item $a$ le temps constant d'affectation
\item   $d$  le   temps  constant  de
déclaration
\item $x$ le temps constant d'accès à une cellule
\item  $s$ le temps constant
d'une somme
\item  $c$ le temps constant d'une comparaison.
\end{itemize}

\pause

{\small
$$\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$$
}
\pause

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

\end{frame}


\section{Plus fort que la dichotomie: l'algorithme de Héron}

\begin{frame}
  \begin{figure}[ht]
    \centering
    \includegraphics[height=0.5\textheight]{baby}
    \caption{Ordinateur Babylonien\label{fig:label} }
  \end{figure}

\end{frame}

\begin{frame}

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.

\pause

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.

\pause

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

\end{frame}


\begin{frame}[fragile]

%\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}
\end{frame}



\begin{frame}[fragile]
\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}
\end{frame}




\begin{frame}
$r_{n+1}= f(r_n)=\frac{r_n + \frac{2}{r_n}}{2}$ et $r_0=1$

\pause

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

\end{Theorem}


\pause



\begin{Theorem}[Un théorème light du point fixe]
  Soit I un intervalle  fermé de $\bbr$, soit $f$ une fonction  de Ι vers I
  et soit $(r_n)$ une suite d'éléments de I telle que $r_{n+1}=f(r_n)$ pour tout
  entier naturel  $n$. SI $(r_n)$ est  convergente ALORS sa limite  est UΝ point
  fixe de $f$ appartenant à I.  
\end{Theorem}


\end{frame}



\begin{frame}

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

\end{frame}





\begin{frame}
 $r_n \geqslant  1$  donc  $$  \left|r_{n+1}  -
  \sqrt{2}\right| \leqslant \left| (r_n-\sqrt{2})^2\right| $$ 

\pause

$d_n=-\log_{10}|r_n-\sqrt{2}|$

\pause

$$d_{n+1}  \geqslant 2d_n$$
\end{frame}

\section{Quelques exercices}


\begin{frame}[fragile]


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


\end{frame}

\begin{frame}[fragile]



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





\end{frame}




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

\end{frame}







\begin{frame}[fragile]

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

\end{frame}






\begin{frame}[fragile]


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


\end{frame}

\begin{frame}[fragile]

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

\end{frame}

\begin{frame}[fragile]

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

\end{frame}



\begin{frame}[fragile]
  
\begin{algo}
  \FOR{i}{1}{n}
  \FOR{j}{1}{i}
  \FOR{k}{1}{j}
  \STATE{op}
  \ENDFOR
  \ENDFOR
  \ENDFOR
\end{algo}

\end{frame}


\begin{frame}[fragile]

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


\end{frame}










\begin{frame}[fragile]

\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}
\end{frame}



\begin{frame}[fragile]

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


\begin{frame}
  


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.


\begin{center}
  \includegraphics[height=0.5\textheight]{rhind.jpg}
\end{center}

\end{frame}




\begin{frame}[fragile]
\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}
\end{frame}



\begin{frame}[fragile]
\begin{itemize}  
\item Que vaut \mintinline{python}{acc} au départ?



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

\item Écrivez une version impérative de cet algorithme.

\item Prouvez la correction de cet algorithme.

\item Étudiez sa complexité.

\end{itemize}
\end{frame}

\begin{frame}[fragile]

En python, \mintinline{python}{x  >> 1} décale l'entier  $x$ d'un bit
vers la doite et \mintinline{python}{x << 1} décale $x$ d'un bit vers
la gauche en complétant par  un zéro à droite, \mintinline{python}{x& y}
renvoie  l'entier  obtenu en  faisant  la  conjonction  logique  bit à  bit  des
représentations  binaires de  $x$ et  $y$ et  \mintinline{python}{~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{frame}

\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
