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

\usepackage[beamer,utf8x,russe]{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=/home/moi/Photos/Maths/estimation
}
}

\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}
\setbeamertemplate{theorems}[numbered]

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


\usepackage{algo}

\renewcommand{\algocommentfont}{\tiny\ttfamily\itshape}
\renewcommand{\algokeywordfont}{\small\ttfamily}
\renewcommand{\algotextfont}{\footnotesize\ttfamily}
\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}












\begin{document}


\title[]% (optional, use only with long paper titles)
{Étude d'algorithmes}

\subtitle{Informatique pour tou(te)s - semaines 42 \& 43}

\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{Lycée Clemenceau - MP / MP$^{\star}$}% (optional, but mostly needed)

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

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

\date[] % (optional, should be abbreviation of conference name)
{octobre 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{<+->}


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

\normalsize


% début




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



\begin{frame}
  \begin{block}{Le problème}
\begin{center}

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

\end{center}
    
  \end{block}
\end{frame}



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


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


\begin{frame}[fragile]
\begin{pythoncode}
from time import perf_counter
from math import log2

def temps(xs):
    debut = perf_counter()        # on déclenche le chrono
    trois_sommes(xs)              # on lance le calcul
    return perf_counter() - debut # on arrête le chrono quand c'est fini

# on fabrique une liste contenant les temps de calcul pour des longueurs de 100, 200, 400 et 800
t = [temps(range(100 * 2**k)) for k in range(4)]

# on forme la liste des ratios 
ratio = [t[k + 1] / t[k] for k in range(3)]

# on applique la fonction log2 aux éléments de la liste des ratios
logratio = [log2(r) for r in ratio]
\end{pythoncode}
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [4]: ratio
Out[4]: [7.523860206447286, 9.118789882406599, 8.5098312160934]

In [5]: logratio
Out[5]: [2.940628541715559, 3.133284732580891, 3.128693841844642]  
\end{pythoncode}
\end{frame}



\begin{frame}[fragile]


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

\pause


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

\pause


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



\begin{frame}[fragile,fragile]\frametitle{En C}
  \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}
 
On a la même évolution en $N^3$ avec  un rapport de 8 entre chaque doublement de
taille \pause 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}$

 
\end{frame}





\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}
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}
  \begin{block}{Loi de Brooks}
     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}$
  \end{block}
\end{frame}

\begin{frame}

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

\end{frame}

\begin{frame}


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

\begin{frame}


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


\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}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{ZeArt}
\end{center}
%\end{figure}

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



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


\begin{frame}
  \begin{block}{Calcul}
    Que valent  $S_1$ et $S_2$? 
  \end{block}
\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}        \qquad
(\text{avec } i'=N-(i+1))$$

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

\end{frame}


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

\pause
Le temps d'exécution vérifie:

\begin{center}
\begin{multline}
  \tau(N) \leqslant (2d+3d+3a+a) + (d+a+x+d+s+a)N+\\
              \hspace{2cm}   (d+a+x+s+d+s+a)S_1 +(x+s+c+s)S_2
\end{multline}
\end{center}
\pause
Or $S_1\sim N^2$ et $S_2\sim N^3$ quand $N$ est \og grand\fg{}.

\pause
Finalement... \pause $$\tau(N)=O{N^3}$$
\end{frame}




\section{Algorithme de Karatsouba}

\begin{frame}
  Addition de deux entiers de $n$ chiffres: $O{n}$

\pause
Multiplier un entier de $n$ chiffres par un entier de 1 chiffre: $O{n}$

\pause

Algorithme de l'école  primaire pour multiplier deux  nombres de
$n$ chiffres: \pause $n$ multiplications d'un nombre de $n$ chiffres par un
nombre de 1 chiffre puis une addition des $n$ nombres obtenus:\pause $O{n^2}$

\end{frame}


\begin{frame}
  $O{n^2}$: multiplication de nombres deux fois plus petits $⟶$ quatre fois plus rapide ?
\end{frame}


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



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

Les divisions et  les multiplications par des  puissances de 10 ne  sont que des
décalages effectués en temps constant.
\pause
L'addition finale est en $\lambda n$ \pause donc le temps d'exécution est défini par:

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

\pause

 $$n=2^k \pause \qquad T(n)=T(2^k)=x_k$$

\pause


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





\end{frame}




\begin{frame}
  \begin{eqnarray*}
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_k n \log n \\
&=& Θ(n^2)    
  \end{eqnarray*}
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{kolmogorov}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.6\textheight]{karatsouba}
\end{center}
%\end{figure}
  \pause


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

\end{frame}




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






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


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

\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}
%  孙子兵法
% \end{CJK}
de Sun Zi (VI\eme siècle avant JC)
  \end{flushright}
\end{quote}


\end{frame}




\begin{frame}
  

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. \pause Le coût de l'algorithme est alors:

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

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



\pause


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



\begin{frame}
  \begin{eqnarray*}
T(n)&=&aT(n/b)+cn^α\\\pause
&=&a^2T(n/b^2)+ac(n/b)^α+cn^α\\\pause 
&=&\cdots\\\pause
&=&a^kT(n/b^k)+∑_{i=0}^{k-1}a^ic(n/b^i)^α 
  \end{eqnarray*}
\pause
$n=b^{k_n}$ 
\pause

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


\end{frame}



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

\pause



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

\end{frame}


\begin{frame}


En fait, on peut démontrer (cf \textsc{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})$.


\end{frame}


\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}[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, 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}
\RETURN{sup}
\ELSE
\STATE{milieu\recoit{} $(\text{inf} + \text{sup})/2$}
\IF{estFatal(milieu)}
\STATE{ChercherEntre(inf,milieu)}
\ELSE
\STATE{ChercherEntre(milieu, sup)}
\ENDIF
\ENDIF 
\end{algo}

\end{frame}


\begin{frame}[fragile]

\begin{algo}
%\FUNC{ChercherEntre}{\pfarg{N}{Entier}}{Entier}
\COMMENT{pré-cond.: il existe 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,sup \recoit{} 0, 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}  
\end{frame}



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





\begin{frame}
\begin{itemize}
\item TERMINAISON: \pause $\ell_i=\frac{N}{2^i}=\frac{2^n}{2^i}=2^{n-i}\pause \quad \ell_n=1$
  \item CORRECTION:\pause l'invariant est vérifié à chaque itération
  \item COMPLEXITÉ: \pause 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.
\pause

  Que vaut $n$? \pause 

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

  
  \end{itemize}

  
\end{frame}


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



\begin{frame}
  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. \pause Il va falloir chercher:

  \begin{itemize}
  \item un nombre \pause (un étage)
  \item dans un tableau\pause (un immeuble)
  \item de $2^{10}$ nombres \pause (étages)
  \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}

\pause


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


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

\subsection{L'algo}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{heron}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.6\textheight]{babylone}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  \begin{quote}
« Puisque alors les 720 n'ont pas le côté exprimable, nous prendrons le côté avec une très petite différence ainsi. Puisque le carré le plus voisin de 720 est 729 et il a 27 comme côté, divise les 720 par le 27 : il en résulte 26 et deux tiers. Ajoute les 27 : il en résulte 53 et deux tiers. De ceux-ci la moitié : il en résulte 26 2' 3'. Le côté approché de 720 sera donc 26 2' 3'. En effet 26 2' 3' par eux-mêmes : il en résulte 720 36', de sorte que la différence est une 36e part d'unité. Et si nous voulons que la différence se produise par une part plus petite que le 36', au lieu de 729, nous placerons les 720 et 36' maintenant trouvés et, en faisant les mêmes choses, nous trouverons la différence qui en résulte inférieure, de beaucoup, au 36'. »
\end{quote}
\begin{flushright}
Héron d'Alexandrie, Metrica, tome I, 8
\end{flushright}
\end{frame}


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

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

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

  \end{itemize}
\end{frame}



\begin{frame}[fragile]
  
\begin{algo}
\FUNC{heron\_rec}{\pfarg{a,fo}{Réels} \pfarg{n}{Entier}}{Réel}
\IF{n = 0}
\RETURN{0}
\ELSE
\RETURN{heron\_rec(a,(fo + a / fo) / 2, n - 1)}
\ENDIF


\FUNC{heron\_it}{\pfarg{a,fo}{Réels} \pfarg{n}{Entier}}{Réel}
\STATE{app \recoit{} 0}
\FOR{k}{0}{n - 1}
\STATE{app\recoit{} (app + a / app) / 2}
\ENDFOR
\RETURN{app}
\end{algo}
\end{frame}


\subsection{Est-ce que la suite des valeurs calculées par la boucle converge vers $\sqrt{2}$?}

\begin{frame}
  \begin{block}{Théorème de la limite monotone}
    Toute suite croissante majorée (ou décroissante minorée) converge.
  \end{block}
\pause

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


\end{frame}


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

\pause

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




\subsection{Quelle est la vitesse de convergence?}






\begin{frame}
  \begin{block}{Définition: ordre d'une suite}
   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$. \pause

On dit que $(r_n)$ est d'ordre $k$ et que C est la constante
   asymptotique d'erreur.    
  \end{block}

\pause
 $$
\left|r_{n+1} - \sqrt{2}\right| = \left| \frac{(r_n-\sqrt{2})^2}{2r_n}\right| $$
\pause
 $$  \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 \qquad d_{n+1}  \geqslant 2d_n$$


\end{frame}


\begin{frame}
\begin{center}
Prochaine étape: les tris
  
\end{center}
\end{frame}





















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