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

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



\usepackage{iwona}


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

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
  \usefonttheme{progressbar}
%  \useoutertheme{progressbar}
  %\useinnertheme{progressbar}
 % \progressbaroptions{% titlepage=normal,
  %  imagename=/home/moi/Photos/Maths/prisoner
%}
}

%\usepackage{elephantbird}
\newcommand\MyBox[2][XXX]{%
  \fbox{\tabular[b]{C{#1}} #2 \endtabular}}

\setbeamertemplate{footline}[frame number]


%\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)
{Coder l'information}

\subtitle{Informatique pour tou(te)s - semaines 46 \& 47}

\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]{logoUNI}}

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

\date[] % (optional, should be abbreviation of conference name)
{novembre 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{L'information en informatique}

\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[width = \linewidth]{shannon2}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[width = \linewidth]{shannon}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}
  \begin{itemize}
  \item Claude \textsc{Shannon}
  \item 1916 - 2001
  \item MIT, Bell Labs
  \item Mathématiques, Électricité
  \item Master : liens entre algèbre de Bool et interrupteurs
  \item Théorie de l'information
  \end{itemize}
\end{frame}

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

\end{frame}

\begin{frame}
  \begin{itemize}
  \item fonction décroissante de la probabilité d'un évènement
\item La quantité d'information de deux  évènements indépendants est la somme de
  leurs quantités d'information
\item $I(B\cap C) = I(B)+I(C)$
\item $φ(b\cdot c)=φ(b)+φ(c)$
\item $φ$ continue de $[0,1]$ dans $[0,+\infty]$
\item $φ(Pr(E))=-\log_2(Pr(E))$
  \end{itemize}
\end{frame}


\begin{frame}
  \begin{block}{Quantité d'information: version pratique}
    Nombre de questions auxquelles on ne peut  répondre que par oui ou non qu'il
    faut poser pour être certain de retrouver les données.
  \end{block}
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.8\linewidth]{pick}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}
  \begin{itemize}
  \item 1 bit = 1 question
  \item Je choisis une lettre de l'alphabet: combien de questions?
  \item Je  choisis une lettre  au hasard  dans \textit{Notre-Dame de  Paris} de
    Victor \textsc{Hugo}?
  \end{itemize}
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{sudoku}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}\frametitle{sémantique}
  \begin{itemize}
  \item \textit{Quelque part sur la Terre}: 25 caractères soit environ 200 bits.
  \item \textit{À Nantes}: 8 caractères soit environ 64 bits.
  \end{itemize}
\end{frame}

\begin{frame}\frametitle{Les unités}

  \begin{itemize}
  \item Un octet (Byte) représente 8 bits (BInary digiT)
  \item Traditionnellement:
    \begin{itemize}
    \item un \textit{kilo}octet représente $2^{10}$ octets
    \item un \textit{méga}octet représente $2^{20}$ octets
    \item un \textit{giga}octet représente $2^{30}$ octets
    \item ...
    \item Depuis 1998, il fau\textit{drai}t utiliser les préfixes \textit{kibi},
      \textit{mébi}, \textit{gibi}...et garder les autres pour les puissances de
      10 par paquets de 3.
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{alertblock}{bit $\neq$ Byte}
    \begin{itemize}
    \item 1 Mb = 1 mégabit = $10^6$b
    \item 1 MB = 1 méga\textit{byte} = 1 mégaoctet = 8 Mb
    \end{itemize}
    
  \end{alertblock}
\end{frame}

\begin{frame}
  \frametitle{Numérique / Analogique}

%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{playwood}
\end{center}
%\end{figure}


\end{frame}


\begin{frame}\frametitle{Numérique / Analogique}
  \begin{description}
  \item[Échantillonnage] On découpe l'information (temps / espace)
  \item[Quantification]  Approximation  de  chaque échantillon  par  une  valeur
    choisie dans un ensemble fini
  \item[Encodage] On associe un nombre à chacune des valeurs
  \item[Options] compression, détection/correction d'erreurs
  \end{description}
  
\end{frame}



\section{Représenter les entiers}

\begin{frame}
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{gabuzo}
\end{center}
%\end{figure}
\end{frame}


\begin{frame}[fragile]
  \begin{itemize}
  \item Entier non signé sur 32 bits $⟶$ 8 paquets de 4 bits $⟶$ 4 octets 
  \item \verb+1001 0111 1110 1010 0011 1011 1111 0101+ 
  \item \verb+  9    7   E     A    3    B    F    5 +
  \end{itemize}

\end{frame}


\begin{frame}[fragile]\frametitle{Entiers signés}

  \begin{itemize}
  \item Le bit de poids fort est réservé pour le signe: 1 pour les négatifs, 0 pour les positifs.
  \item Mais cela pose des problèmes si on se contente de ce codage. Par exemple, sur quatre bits,  $3 + (-3)$ serait égal à...
    \begin{verbatim}
      0 0 1 1
    + 1 0 1 1
    ---------
      1 1 1 0
    \end{verbatim}
...$-6$
  \end{itemize}
\end{frame}



\begin{frame}[fragile]\frametitle{Complément à $2^n$}
  \begin{itemize}
  \item Sur un octet par exemple, $2^8$ est représenté par 8 zéros car on n'a pas la place pour écrire le \verb+1+ en neuvième position.
  \item Or $2^8-1$ s'écrit normalement \verb+1111 1111+
  \item Un nombre plus son complément à 1 s'écrit \verb+1111 1111+ avec l'algorithme usuel
  \item $\bigl(  b_7b_6b_5b_4b_3b_2b_1b_0 +  \bar{b_7}\bar{b_6}\bar{b_5}\bar{b_4}\bar{b_3}\bar{b_2}\bar{b_1}\bar{b_0}\bigr) + 1 = 1111\,1111 + 1 = (1)0000\,0000$
  \item donc  $ b_7b_6b_5b_4b_3b_2b_1b_0 +  \bigl( \bar{b_7}\bar{b_6}\bar{b_5}\bar{b_4}\bar{b_3}\bar{b_2}\bar{b_1}\bar{b_0} + 1\bigr) = 0$
  \item On choisira donc comme opposé d'un nombre son complément à 1 plus 1.
  \end{itemize}
  
\end{frame}


\begin{frame}[fragile]
  \begin{example}[$-27$ sur 8 bits]
    \begin{description}
    \item[Valeur absolue] $|-27|$ s'écrit \verb+00011011+
    \item[Complément à 1] \verb+11100100+
    \item[On ajoute 1] \verb+11100101+
    \item[Opposé?] on vérifie:
      \begin{verbatim}
        00011011
      + 11100101
      -----------
     (1)00000000
      \end{verbatim}

    \end{description}
  \end{example}
\end{frame}


\begin{frame}
  Avec $k$ bits, quels sont les entiers ainsi représentables?
\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.8\linewidth]{ariane}
\end{center}
%\end{figure}

\end{frame}


\section{IEEE754}


\begin{frame}
\begin{center}
  \includegraphics[width=0.7\textwidth]{patriot}
\end{center}
\end{frame}


\begin{frame}
\begin{center}
  \includegraphics[width=0.7\textwidth]{scud}
\end{center}
\end{frame}



\begin{frame}
\begin{center}
  \includegraphics[width=0.6\textwidth]{oups}
\end{center}
\end{frame}


\begin{frame}[fragile]

  
\begin{pythoncode}
In [1]: 3 * 0.1
.
.
.
\end{pythoncode}

\end{frame}



\begin{frame}[fragile]

  
\begin{pythoncode}
In [1]: 3 * 0.1
Out[1]: 0.30000000000000004
.
.
\end{pythoncode}

\end{frame}



\begin{frame}[fragile]

  
\begin{pythoncode}
In [1]: 3 * 0.1
Out[1]: 0.30000000000000004
In [2]: sum([0.1 for k in range(10000000)])
.
\end{pythoncode}

\end{frame}



\begin{frame}[fragile]

  
\begin{pythoncode}
In [1]: 3 * 0.1
Out[1]: 0.30000000000000004
In [2]: sum([0.1 for k in range(10000000)])
Out[2]: 999999.9998389754
\end{pythoncode}

\end{frame}

\begin{frame}

{\huge
\bfseries   

{LES NOMBRES RÉELS N'EXISTENT PAS.

\bigskip

\pause

 TOUT CE QUE VOUS AVEZ VU 


EN MATHS N'EST 

\medskip

QU'ILLUSION!}
}
\end{frame}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{francois_magie}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
\begin{figure}
\begin{center}
  \includegraphics[width=0.6\textwidth]{kahan}
\end{center}
\caption{William \textsc{Kahan} (1933)}
\end{figure}
\end{frame}

\begin{frame}

$$v = (-1)^s\times m\times 2^E$$

\pause


\begin{itemize}
\item      un bit de signe $s$ qui vaut 0 si le nombre est positif, 1 sinon ;
  \item   11 bits d'exposant décalé $e$ ;
 \item 53  bits de  mantisse (ou  « significande »  en franglais)  $ m,  \quad 1
   \leqslant m $. 
\end{itemize}


\pause


\begin{itemize}
\item \textit{binary32} \pause $(\#
E,\# m)=(8,24)$  \pause 

\item \textit{binary64} \pause  $(\#
E,\# m)=(11,53)$. \pause 


\item \textit{toy7} \pause $(\#
E,\# m)=(3,4)$. \pause 


\end{itemize}




\end{frame}





\begin{frame}
  

Oups!  $1 +  11 +  53 =  65$...En  fait, on  représente un  nombre de  ${\mathbb
  V}_{64}$ sous  \textbf{forme normale}  : $$v =  (-1)^s\times 1,f  \times 2^E$$
\end{frame}







\begin{frame}
 

Sur $\# E$ bits on peut coder $2^{\# E}$ nombres.

\pause

La première moitié va donc de 0 à $2^{\# E - 1} - 1$.

\pause

Elle correspond aux exposants réels de $E_{\min}$ jusqu'à 0.

\pause

La deuxième de $2^{\# E - 1}$ à $2^{\# E} - 1$.

\pause

Elle correspond aux exposants de 1 jusqu'à $E_{\max}$.

\pause

Il suffit donc de translater les exposants réels de $2^{\# E - 1} - 1$...


\pause

$$
e_{\text{stocké}} = E_{\text{réel}} + 2^{\# E - 1} - 1
$$
\end{frame}




\begin{frame} \frametitle{0,75 en toy7}
  $0,75_{10}$ en \textit{toy7}.\pause

$$0,75_{10} = \frac{3_{10}}{2_{10}^{2}}=11_2\times 2^{-2}=1,100_2\times2^{-1}$$\pause

$$e - \left(2^{3-1}-1\right)=E\pause =-1 \pause \lequiv e=-1+3=2=10_2
$$\pause



\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&0&1&0&1&0&0\\
    \hline
  \end{tabular}
\end{center}

\end{frame}









\begin{frame} \frametitle{0,75 en toy7}
  $0,75_{10}$ en \textit{toy7}.


$$0,75_{10} = \frac{3_{10}}{2_{10}^{2}}=11_2\times 2^{-2}=1,\textcolor{blue}{100}_2\times2^{-1}$$

\bigskip

$$e - \left(2^{3-1}-1\right)=E =-1  \lequiv e=-1+3=2=10_2
$$

\bigskip


\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&0&1&0&\textcolor{blue}{1}&\textcolor{blue}{0}&\textcolor{blue}{0}\\
    \hline
  \end{tabular}
\end{center}

\end{frame}








\begin{frame} \frametitle{0,75 en toy7}
  $0,75_{10}$ en \textit{toy7}.


$$0,75_{10} = \frac{3_{10}}{2_{10}^{2}}=11_2\times 2^{-2}=1,\textcolor{blue}{100_2}\times2^{-1}$$

\bigskip

$$e - \left(2^{3-1}-1\right)=E =-1  \lequiv e=-1+3=2=\textcolor{blue!40!blue}{10_2}
$$

\bigskip


\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&\textcolor{blue!40!blue}{0}&\textcolor{blue!40!blue}{1}&\textcolor{blue!40!blue}{0}&\textcolor{blue}{1}&\textcolor{blue}{0}&\textcolor{blue}{0}\\
    \hline
  \end{tabular}
\end{center}

\end{frame}





\begin{frame} \frametitle{0,75 en toy7 : méthode générale}


Comment écrire en base 2 la partie fractionnaire d'un nombre en base 10?

\pause

$$
0,75 = b_1\times 2^{-1} + b_2\times 2^{-2} + \cdots
$$

\pause

$$
2\times 0,75 = b_1 + b_2\times 2^{-1} + \cdots
$$



\pause

On voit poindre un bel algo...


\end{frame}




\begin{frame}

\begin{exercice}

  Pourquoi le \textit{Patriot} a raté son \textit{Scud} de 600m?

Représentez 1/10 avec une mantisse de 24 bits et tronquez le résultat.

Calculez l'erreur en seconde puis  après 100 heures d'utilisation. Sachant qu'un
Scud vole à $\SI{1676}{m.s^{-1}}$, quelle est environ l'erreur commise en mètres?

Et si on avait arrondi au plus proche?


\end{exercice}

\end{frame}





\begin{frame}
\begin{center}
  \includegraphics[width=0.9\textwidth]{alien}
\end{center}
\end{frame}



\begin{frame}
\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&0&0&0&0&0&0\\
    \hline
  \end{tabular}
\end{center}


\pause

\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    1&0&0&0&0&0&0\\
    \hline
  \end{tabular}
\end{center}


\end{frame}







\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

.
.
.
.
.
.
.
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
.
.
.
.
.
.
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
.
.
.
.
.
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
.
.
.
.
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
.
.
.
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
.
.
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
Out[4]: 0.0
.
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
Out[4]: 0.0
In [5]: 4 - x
.
\end{pythoncode}



  
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
Out[4]: 0.0
In [5]: 4 - x
Out[5]: -inf
\end{pythoncode}



  
\end{frame}





\begin{frame}[fragile]

$$
\displaystyle\lim_{x\to +\infty}x^2 -x
$$

\pause



\begin{pythoncode}
In [9]: x**2 - x
.
\end{pythoncode}





\end{frame}



\begin{frame}[fragile]

$$
\displaystyle\lim_{x\to +\infty}x^2 -x
$$

\pause



\begin{pythoncode}
In [9]: x**2 - x
Out[9]: nan
\end{pythoncode}





\end{frame}






\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{nan}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
In [10]: x
Out[10]: inf

In [11]: x - x
Out[11]: nan

In [12]: x / x
Out[12]: nan

In [13]: x - x == x - x
Out[13]: False

In [14]: x**2 - x
Out[14]: nan

In [15]: x * (x - 1)
Out[15]: inf

In [16]: x * (x - 1) == x**2 - x
Out[16]: False
  \end{pythoncode}
  
\end{frame}


\begin{frame}[fragile]

\begin{exercice}
\begin{enumerate}

\item   Comment expliquer les résultats suivants:

  \begin{pythoncode}
*Main> let f(x) = x^2 / sqrt(x^3 + 1)
*Main> f(1e100)
1.0e50
*Main> f(1e150)
0.0
*Main> f(1e200)
NaN
  \end{pythoncode}

\item Comment éviter le dernier NaN?



\end{enumerate}



\end{exercice}


  
\end{frame}



\begin{frame}[fragile]
  \begin{pythoncode}
In [16]: f = lambda x: x**2 / sqrt(x**3 + 1)

In [17]: f(1e100)
Out[17]: 1e+50

In [18]: f(1e150)
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-18-79775d85f31a> in <module>()
----> 1 f(1e150)

<ipython-input-16-eed0b81ef932> in <lambda>(x)
----> 1 f = lambda x: x**2 / sqrt(x**3 + 1)

OverflowError: (34, 'Numerical result out of range')

In [19]: f(1e200)
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-19-c1d077e9d28e> in <module>()
----> 1 f(1e200)

<ipython-input-16-eed0b81ef932> in <lambda>(x)
----> 1 f = lambda x: x**2 / sqrt(x**3 + 1)

OverflowError: (34, 'Numerical result out of range')
  \end{pythoncode}
  
\end{frame}




\begin{frame}[fragile]
  \begin{pythoncode}
In [53]: x = 1e-500

In [54]: x
Out[54]: 0.0

In [55]: x / x
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-55-fd52a7f8b5f1> in <module>()
----> 1 x / x

ZeroDivisionError: float division by zero
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
  \begin{pythoncode}
In [56]: sqrt(-1.0)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-56-d1c09f21b443> in <module>()
----> 1 sqrt(-1.0)

ValueError: math domain error

  \end{pythoncode}

\end{frame}



\begin{frame}[fragile]
  \begin{haskellcode}
*Main> let x = 1e500
*Main> x - x
NaN
*Main> x / x
NaN
*Main> sqrt(-1)
NaN
*Main> 0 / 0
NaN    
  \end{haskellcode}
\end{frame}



\begin{frame} \frametitle{Arbre de lecture}
\begin{center}


  \begin{tabular}[h]{|c||c||c|}
    \hline
    $s$&$e$&$f$\\
    \hline
  \end{tabular}
\pause

  \begin{tabular}[h!]{llcl}

\hline
$e=0...0$ & $f=0$ & $\rightarrow$ & $v=(-1)^s\times 0.0$  \\
$e=0...0$ & $f\neq  0$ & $\rightarrow$ & $v=(-1)^s\times  0.f \times 2^{1-E_{\max}}$\\
$e=1...1$ & $f=  0$ & $\rightarrow$ & $v=(-1)^s\times \infty$\\
$e=1...1$ & $f\neq 0$ & $\rightarrow$ & $\text{NaN}$\\
$0...0<e<1...1$ & $f\neq  0$ & $\rightarrow$ & $v=(-1)^s\times  1.f \times 2^{e-E_{\max}}$\\
\hline

  \end{tabular}

\end{center}

\end{frame}




\begin{frame}\frametitle{Successeur}
$$n=\# f$$

\pause

 \textit{toy7}, \pause $n=3$


\pause

\textit{binary32}, \pause $n=23$

\pause

 \textit{binary64}, \pause $n=52$


\pause

$$v=M(v)\times 2^{E(v)-n}$$


\pause

$$\operatorname{succ} (v) = (M(v)+1)\times 2^{E(v)-n} = v +  2^{E(v)-n}$$


\end{frame}



\begin{frame} \frametitle{Tableau récapitulatif}


  \begin{itemize}
  \item On notera $ε_m$ l'\textit{epsilon} de  la machine, c'est-à-dire le successeur de
1

\item On notera $λ$ le plus petit VF normal positif



\item On notera $μ$ le plus petit VF sous-normal positif


\item On notera $Ω$ le plus grand VF normal.
  \end{itemize}


\pause

 Quelle relation existe-t-il entre $μ$, $ε_m$ et $λ$?


  
\end{frame}



\begin{frame}

 {\tiny
  \begin{tabular}{|*{9}{l|}}
\hline
    Nom & $\# E$ & $\# f$ & $E_{\min}$ & $E_{\max}$ & $ε_m$ & $λ$ & $μ$ & $Ω$ \\
\hline
\textit{toy7} & 3 & 3 & $-2$& $3$ & $2^{-3}=1/8$ & $2^{-2}=1/4$ & $2^{-5}=1/32$ & $1,111\times 2^3=15$ \\
\textit{bin32} & 8 & 23 & $-126$ &$127$ &$2^{-23}$  &$2^{-126}$ & $2^{-126-23}$&  $(2^{24}-1)\times 2^{127-23}$\\
                  &  &    &         &       & $\approx 1,2\times 10^{-7}$ & $\approx 1,2\times 10^{-38}$  & $\approx 1,4\times 10^{-45}$ &$\approx 3,4\times 10^{38}$ \\
\textit{bin64} & 11 & 52 & $-1022$&$1023$ & $2^{-52}$ & $2^{-1022}$& $2^{-1074}$& $(2^{53}-1)2^{1023-52}$\\
                  & &  & & &  $\approx 2,2\times 10^{-16}$ &  $\approx 2,2\times
                  10^{-308}$ &$\approx 5\times 10^{-324}$ & $\approx 1,8\times 10^{308}$\\
\hline
  \end{tabular}\label{tab::reca}
}

\end{frame}

\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
.
.
.
.
.
.
.
.
.
.
.
.
  \end{pythoncode}
\end{frame}
\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True
.
.
.
.
.
.
.
.
.
.
.
  \end{pythoncode}
\end{frame}
\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16
.
.
.
.
.
.
.
.
.
  \end{pythoncode}
\end{frame}
\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
.
.
.
.
.
.
.
  \end{pythoncode}
\end{frame}
\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

.
.
.
.
.
  \end{pythoncode}
\end{frame}
\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
.

.
.
  \end{pythoncode}
\end{frame}
\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
Out[4]: 0.9999999999999999

.
.
  \end{pythoncode}
\end{frame}
\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
Out[4]: 0.9999999999999999

In [5]: 1e-16 + 1e-18
.
  \end{pythoncode}
\end{frame}


\begin{frame}[fragile]
  \begin{pythoncode}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
Out[4]: 0.9999999999999999

In [5]: 1e-16 + 1e-18
Out[5]: 1.01e-16
  \end{pythoncode}
\end{frame}










\subsection{Algèbre des nombres VF}






\begin{frame}

$$\bbv_b$$

\pause

 $$\overline{\bbv_{b}}$$




\end{frame}


\begin{frame} \frametitle{Comparaison}
  Il  est  très  simple  et  rapide  de  comparer  deux  VF:  comment  la  machine
procède-t-elle? Quel est l'avantage de ce stockage des VF?
\end{frame}


\begin{frame} \frametitle{Addition}


\begin{enumerate}
\item on commence par ramener les deux nombres au même exposant, en l'occurrence
  le plus grand des deux;
\item on ajoute les deux mantisses \textit{complètes} en tenant compte du signe;
\item on renormalise le nombre obtenu.
\end{enumerate}

  
\end{frame}




\begin{frame} \frametitle{Addition}

En \textit{toy7}: $1,1 + 0,0111\ $ \pause $\ \rightarrow \ \ 1,1\times
2^{0} + 1,11\times 2^{-2}$ 

\pause

\medskip

1,1:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    0&0&1&1&1&0&0\\
    \hline
  \end{tabular}
\pause
  \hfill 0,0011:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
   \hline
    0&0&0&1&1&1&0\\
    \hline
  \end{tabular}

\pause

\vfill

1,100

\pause

0,001\textcolor{blue}{\itshape 11}

$----$

\pause

1,101\textcolor{blue}{\itshape 11}


\end{frame}


\begin{frame} \frametitle{Les arrondis}
  \begin{definition}
\begin{enumerate}
\item l'arrondi au plus proche (RN) qui  arrondit au VF...le plus proche. En cas
  d'égalité,  on choisit  la valeur  paire  (donc qui  se  termine par  un 0  en
  binaire);
\item l'arrondi  vers 0  (RZ) qui  arrondit à  la valeur  de plus  petite valeur
  absolue: c'est la troncature;
\item l'arrondi vers $+\infty$ (RU) qui  arrondit à la valeur supérieure la plus
  petite;
\item l'arrondi vers $-\infty$ (RD) qui arrondit à la valeur inférieure la plus grande.
\end{enumerate}
\pause
Le mode d'arrondi par défaut est le premier.
\end{definition}
\end{frame}


\begin{frame}



1,100


0,001\textcolor{blue}{\itshape 11}

$----$



1,101\textcolor{blue}{\itshape 11}


\pause


\bigskip



   $x=1,101\textcolor{blue}{\mathit{11}}$ \pause VF en \textit{toy7}?


\pause

$$
1,101\textcolor{blue}{ \mathit{00}} \leqslant \underbrace{1,101\textcolor{blue}{ \mathit{11}}}_x \leqslant 1,110\textcolor{blue}{ \mathit{00}}
$$

\pause

$$
\underbrace{1,100+ \textcolor{blue}{\mathit{1,00}}ulp(x)}_v \leqslant  \underbrace{1,100+ \textcolor{blue}{ \mathit{1,11}}ulp(x)}_{x} \leqslant \underbrace{1,100+ \textcolor{blue}{\mathit{10,00}}ulp(x)}_{\operatorname{succ}(v)}
$$

$|x-v|=0,11ulp(x) $ \pause $\ |x- \operatorname{succ}(v)|=0,01ulp(x)$ \pause donc $RN(x)=\operatorname{succ}(v)$

\pause


$$ 1,1 \oplus 0,00111 = 1,110$$

\end{frame}






\begin{frame}
  


%\begin{figure}
\begin{center}
  \includegraphics{DrapeauFloat.5}
\end{center}
%\end{figure}


\end{frame}









\begin{frame}[fragile]
\begin{enumerate}
\item Est-ce que l'addition des VF est associative? 

\pause

  \begin{pythoncode}
In [14]: (1 + 1e-16) + 1e-16
Out[14]: 1.0

In [15]: 1 + (1e-16 + 1e-16)
Out[15]: 1.0000000000000002
  \end{pythoncode}
\pause
  
\item   Est-on sûr de l'ordre dans le quel un compilateur calcule $a+b+c+d$?

\end{enumerate}
\end{frame}


\begin{frame} \frametitle{Multiplication}
  \begin{enumerate}
\item on \og xore\fg{} les bits de signe;
\item on additionne les exposants réels et on décale ou plutôt on additionne les
  exposants décalés et on retire la valeur d'un décalage;
\item on multiplie les mantisses;
\item on normalise.
\end{enumerate}
\end{frame}


\begin{frame}
 $101,1 \times (-10,01)$

\pause

101,1:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    0&1&0&1&0&1&1\\
    \hline
  \end{tabular}
  \hfill -10,01:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
   \hline
    1&1&0&0&0&0&1\\
    \hline
  \end{tabular}


\pause

  \begin{enumerate}
  \item 0 xor 1 donne 1: le bit de signe est 1;
  \item $101 +  100 - 11 = 1001 -  11 = 110 $: l'exposant décalé  est $110$ donc
    l'exposant est 3;
  \item $1,011\times 1,001=1,011 + 1,011\times 0,001=1,011 + 0,001011=1,100011$;
\item le produit est donc $1,100011\times 2^3$. Le passage à la forme normale va
  arrondir le produit. On a \pause
$$1,100<x<1,101$$

\pause

avec   $|x-1,100| =\pause 0,011ulp(x)$   et  $|x-1,101|= \pause 0,101ulp(x)$   \pause
donc   $$RN(101,1\times
(-10,01))=-1,100\times 2^3$$

\end{enumerate}

\begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    1&1&1&0&1&0&0\\
    \hline
  \end{tabular}


\end{frame}

\begin{frame}[fragile]
\begin{enumerate}
\item  Est-ce que la multiplication des VF est associative? 

\pause

\begin{pythoncode}
In [1]: (1.00000001 * 1e-15) * 1e15
Out[1]: 1.0000000100000002

In [2]: 1.00000001 * (1e-15 * 1e15)
Out[2]: 1.00000001
\end{pythoncode}

\pause

\item Est-ce que la multiplication des VF est distributive sur l'addition?

\pause



\begin{pythoncode}
In [3]: 1e15 * (1e-16 + 1)
Out[3]: 1000000000000000.0

In [4]: (1e15 * 1e-16) + (1e15 * 1)
Out[4]: 1000000000000000.1
\end{pythoncode}


\end{enumerate}
\end{frame}



\subsection{Réels, arrondis et flottants}




\begin{frame}[fragile]

  \begin{pythoncode}
def base1(a):
    if (a + 1.0) - a != 1.0:
        return a
    else:
        return base1(2.0 * a)

def base2(a, b):
    if (a + b) - a == b:
        return b
    else:
        return base2(a, b + 1.0)
  \end{pythoncode}


\pause

????!!!!???? !!???



  
\end{frame}




\begin{frame}



\begin{quote}
  {\itshape
    95 \% of the folks out there are completely clueless about floating-point
}
\begin{flushright}
  James \textsc{Gosling} (M. Java) - 28 février 1998
\end{flushright}
\end{quote}


\end{frame}


\begin{frame}
 \begin{description}
\item[Précision]  (\textit{precision}): c'est  le nombre  de bits  utilisés pour
  représenter un nombre. La précision concerne  donc le format utilisé pour écrire ou
  stocker  ou   arrondir  un  nombre. \pause  Par   exemple  \texttt{3},  \texttt{3.0},
  \texttt{3.0000},  \texttt{3.0e0} n'ont  pas la  même précision,  précision qui
  dépend en plus du langage. \pause
\item[Exactitude] (\textit{accuracy}): c'est ce qui  relie un nombre au contexte
  dans lequel il est employé. 
\end{description}

\pause

$3,177777777777777$  est une  approximation plutôt  précise (16  décimales) mais
inexacte (2 décimales) de $\pi$.

\end{frame}


\begin{frame}
  Soit $x$ un nombre et $\widehat{x}$ le nombre qui le représente. On distingue:\pause
  \begin{description}
  \item[l'erreur absolue] $|x - \widehat{x}|$
  \item[l'erreur relative] $η=\frac{x-\widehat{x}}{x}$\pause alors $\widehat{x}=x(1+η)$
  \end{description} \pause
commise en prenant $\widehat{x}$ à la place de $x$.
\end{frame}






% \begin{frame}
%   $r=f(d)$

% \begin{definition}
%   \begin{itemize}
%   \item   L'erreur  \textit{aval} (\textit{forward  error}) est  la différence  entre le
%   résultat mesuré $\widehat{r}$ et le résultat théorique $r$.

% \item L'erreur \textit{amont}, ou erreur \textit{inverse} (\textit{backward error})
% est le plus petit $|Δ d|$ tel que $f(d + Δ d ) = \widehat{r}$.
% \end{itemize}
% \end{definition}

% \end{frame}







\begin{frame}
\begin{quote}
  {\itshape
   Feel nervous, but feel in control.
It’s not dark magic, it’s science.
}
\begin{flushright}
  Florent \textsc{de Dinechin}
\end{flushright}
\end{quote}



%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{AS400}
\end{center}
%\end{figure}



\end{frame}






\begin{frame}\frametitle{Précision machine}
$$M\times 2^{E-n}\leqslant  x < (M+1)\times 2^{E-n}\pause =M\times 2^{E-n} +2^{E-n}$$

\pause

$$|x-\widehat{x}|\leqslant \frac{1}{2}2^{E-n}$$


\pause

$$\left|\frac{x-\widehat{x}}{x}\right|\leqslant
\left|\frac{x-\widehat{x}}{m\times 2^E}\right|\pause \leqslant
\frac{1}{2}\frac{2^{E-n}}{m\times 2^E}\pause =\frac{1}{2}\frac{2^{-n}}{m}\pause =\frac{1}{2}\frac{ε_M}{m}$$

\pause

\begin{enumerate}
\item Si $\widehat{x}$ VF alors  l'\textbf{erreur relative} est majorée $\left|\frac{x-\widehat{x}}{x}\right|\leqslant\frac{1}{2}ε_M$

\item  Si $\widehat{x}$ est sous-normal, alors l'\textbf{erreur absolue} est majorée \pause $|x-\widehat{x}|\leqslant \frac{1}{2}2^{E_{\min}-1-n}$
\end{enumerate}


\end{frame}




\begin{frame}
  \begin{center}
    \huge
NE  FAITES  PAS  DES  TESTS  D'ÉGALITÉ  MAIS  DES  TESTS  D'APPARTENANCE  À  DES
INTERVALLES DE LARGEUR L'$ε$ MACHINE!

  \end{center}
\end{frame}


\begin{frame}\frametitle{Précision machine}
$$\widehat{x}=x(1+η_1)+η_2$$

avec:

\begin{itemize}
\item si $\widehat{x}$ est normal $|η_1|\leqslant \frac{1}{2}ε_M$ et $η_2=0$
\item si $\widehat{x}$ est sous-normal $η_1=0$ et $|η_2|\leqslant  \frac{1}{2}2^{E_{\min}-1-n} $
\end{itemize}



\pause

Mouais...


\end{frame}

\begin{frame} \frametitle{Élimination}
 $\widehat{a}=a(1+η_a)$,\pause
$\widehat{b}=b(1+η_b)$,\pause $x=a-b$ \pause et $\widehat{x}=\widehat{a-b}\pause
=\widehat{a}-\widehat{b}$.

\pause


$$
\left|\frac{x-\widehat{x}}{x}\right|=\left|\frac{-a    η_a+b    η_b}{a-b}\right|
\pause \leqslant \max(|η_a|,|η_b|)\frac{|a|+|b|}{|a-b|}
$$

\end{frame}


% dérivation approchée

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{pythoncode}
def deriv(f,h,x):
    return (f(x+h) - f(x)) / h
  \end{pythoncode}

\pause

\begin{pythoncode}
def derivn(f,x,h,n):
    if n == 0:
        return f(x)
    else:
        return derivn(lambda x: deriv(f,h,x),x,h,n-1)
\end{pythoncode}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{pythoncode}
In [1]: [derivn(lambda x: x**4,1,1e-7,k) for k in range(5)]
Out[1]: 
[1,
 4.000000601855902,
 12.012613126444194,
 -222044.6049250313,
 2220446049250.313]
  \end{pythoncode}

\pause

\begin{pythoncode}
In [2]: [derivn(lambda x: x**4,1,1e-8,k) for k in range(5)]
Out[2]: [1, 4.000000042303498, 11.102230246251565, 0.0, 2.220446049250313e+16]
\end{pythoncode}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{pythoncode}
In [3]: [derivn(lambda x: x**4,1,1e-9,k) for k in range(5)]
Out[3]: [1, 4.000000330961484, 0.0, 0.0, 0.0]
  \end{pythoncode}

\pause

\begin{pythoncode}
In [4]: [derivn(lambda x: x**4,1,1e-3,k) for k in range(6)]
Out[4]: 
[1,
 4.006004000999486,
 12.024014000244776,
 24.03599941303014,
 24.001245435556484,
 -2.4424906541753444]
\end{pythoncode}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{pythoncode}
In [5]: [derivn(lambda x: x**4,1,2**-10,k) for k in range(6)]
Out[5]: [1, 4.005863190628588, 12.02345085144043, 24.03515625, 24.0, 0.0]
  \end{pythoncode}

\pause

 
\begin{pythoncode}
In [6]: [derivn(lambda x: x**4,1,1.0/1026.,k) for k in range(6)]
Out[6]: 
[1,
 4.005851753982072,
 12.023405112200917,
 24.035087928668187,
 23.999573957547014,
 0.755876563500351]
\end{pythoncode}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{pythoncode}
In [7]: [derivn(lambda x: x**4,1,2**-20,k) for k in range(6)]
Out[7]: [1, 4.000005722045898, 12.0, 0.0, 268435456.0, -844424930131968.0]
  \end{pythoncode}
\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{pythoncode}
In [7]: [derivn(exp,0,2**-5,k) for k in range(10)]
Out[7]: 
[1.0,
 1.0157890399712883,
 1.0318273737254913,
 1.0481189373895177,
 1.0646677284967154,
 1.081477828323841,
 1.0985534191131592,
 1.1158447265625,
 1.1376953125,
 0.953125]
  \end{pythoncode}
\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{pythoncode}
In [8]: [derivn(exp,0,2**-20,k) for k in range(10)]
Out[8]: [1.0, 1.0000004768371582, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  \end{pythoncode}
\end{frame}


\begin{frame}
  \begin{center}
    \huge 
TROP DE PRÉCISION TUE LA PRÉCISION!

\pause


DIVISEZ PAR DES PUISSANCES DE 2...\pause PAS DES PUISSANCES DE 10!

  \end{center}
\end{frame}




\begin{frame}
\footnotesize
\begin{exercice}\label{ex::delta}
  Vous savez résoudre  une équation du type $ax^2+bx+c=0$ avec
  $a\neq 0$...

Les  racines, si  elles  existent,  sont données  par  une  formule bien  connue
dépendant de $a$, $b$ et $c$:

$$r=\frac{-b\pm     \sqrt{b^2-4ac}}{2a}=\frac{-b\pm      \sqrt{Δ}}{2a}     \quad
\text{avec}\quad Δ = b^2-4ac$$





Où peuvent se cacher d'éventuelles  annulations catastrophiques? Étudiez ces cas
avec attention, voyez si vous pouvez éviter les éliminations catastrophiques en
réécrivant   les   formules   un   peu   dans   l'esprit   de   la   \og   levée
d'indétermination\fg{}.

\begin{enumerate}
\item Que  se passe-t-il lorsque  $b^2 \gg |4ac|$?  En quoi la  formule $\frac{-
    \left(b+\operatorname{signe}(b)\sqrt{Δ}\right)}{2a} $ peut aider? 
\item  Que se  passe-t-il  lorsque  $b^2\approx 4ac$?  Peut-on  y remédier?  Que
  peut-on dire de $Δ$ par rapport à $b^2$? Y a-t-il élimination catastrophique?
\item  Que  se  passe-t-il  dans   le  cas  de  l'équation  $10^{200}x^2-3\times
  10^{200}x+2\times 10^{200}=0$?
\item Et dans le cas de $10^{-200}x^2-3x+2\times 10^{200}=0$?
\item Moralité?


\end{enumerate}



\end{exercice}


\end{frame}




\begin{frame}[fragile]\frametitle{Élimination}
  \begin{pythoncode}
def expn(n):
    return (1. + 1./n)**n
  \end{pythoncode}
\end{frame}

\begin{frame}[fragile]\frametitle{Élimination}
\begin{multicols}{2}
  \begin{pythoncode}
In [1]: [(exp(1) - expn(10.0**k)) for k in range(20)]
Out[1]: 
[0.7182818284590451,
 0.12453936835904278,
 0.01346799903751661,
 0.0013578962234515046,
 0.000135901634119584,
 1.359126674760347e-05,
 1.359363291708604e-06,
 1.3432696333026684e-07,
 3.011168736577474e-08,
\end{pythoncode}

\begin{pythoncode}
 -2.2355251516614771e-07,
 -2.2477574246337895e-07,
 -2.248980650598753e-07,
 -0.00024166757819266138,
 0.002171794372144209,
 0.0021717943720220845,
 -0.31675337809021675,
 1.718281828459045,
 1.718281828459045,
 1.718281828459045,
 1.718281828459045]
  \end{pythoncode}
\end{multicols}
\end{frame}


\begin{frame}[fragile]\frametitle{Élimination}
\begin{multicols}{2}
  \begin{pythoncode}
In [2]: [(exp(1) - expn(2.0**(3*k))) for k in range(20)]
Out[2]: 
[0.7182818284590451,
 0.1524973145086972,
 0.020936875893946105,
 0.0026498282900537795,
 0.0003317472693793455,
 4.147652875108321e-05,
 5.1846929989274315e-06,
 6.480886076687398e-07,
 8.101110671177025e-08,
\end{pythoncode}

\begin{pythoncode}
 1.0126388616527038e-08,
 1.2657985770658797e-09,
 1.582245445774788e-10,
 1.977795704988239e-11,
 2.4722446312352986e-12,
 3.090860900556436e-13,
 3.863576125695545e-14,
 4.884981308350689e-15,
 4.440892098500626e-16,
 1.718281828459045,
 1.718281828459045]
  \end{pythoncode}
\end{multicols}
\end{frame}



\begin{frame}[fragile]
  \begin{pythoncode}
In [89]: [2.0**53 + k for k in range(10)]
Out[89]: 
[9007199254740992.0,
 9007199254740992.0,
 9007199254740994.0,
 9007199254740996.0,
 9007199254740996.0,
 9007199254740996.0,
 9007199254740998.0,
 9007199254741000.0,
 9007199254741000.0,
 9007199254741000.0]
  \end{pythoncode}

\end{frame}

\begin{frame}[fragile]
  \begin{pythoncode}
In [91]: [2.0**55 + k for k in range(10)]
Out[91]: 
[3.602879701896397e+16,
 3.602879701896397e+16,
 3.602879701896397e+16,
 3.602879701896397e+16,
 3.602879701896397e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16]
  \end{pythoncode}
\end{frame}





\begin{frame}
  \begin{alertblock}{Attention!}
     Pour  éviter de  déduire des  lemmes suivants  des théorèmes  totalement faux,
  n'oubliez pas que \textbf{DANS CE QUI SUIT X ET Y SONT DES NOMBRES À VIRGULE FLOTTANTE}!
  \end{alertblock}
\end{frame}




\begin{frame}
 
\begin{lemma}[Majoration de l'erreur d'une somme]\label{lemme::majSom}
Posons $x\oplus y =  x + y + \operatorname{err}(x\oplus y)$. Alors, s'il  n'y a pas de
dépassement de capacité, 

$$\left|\operatorname{err}(x\oplus y)\right| \leqslant \min  \left(|x|,|y|\right) 
$$

On a bien sûr un résultat analogue pour la différence

  
\end{lemma}

\end{frame}




\begin{frame}
  \begin{itemize}
  \item $x\oplus y = x + y + \operatorname{err}(x\oplus y)$
  \item $x\textcolor{black}{\oplus y} = x + y + (-y)$
  \item $x$ est un VF situé à la distance $|y|$ de $x+y$
  \item $x\oplus  y$ le VF le plus  proche de $x+y$
  \item $\left|\operatorname{err}(x\oplus y)\right| \leqslant |y|$
  \item de même  $\left|\operatorname{err}(x\oplus y)\right| \leqslant |x|$
  \end{itemize}


\pause


\begin{alertblock}{À noter}
    De l'importance de disposer avec la IEEE 754 de la \textbf{meilleure approximation}!
\end{alertblock}


\end{frame}


\begin{frame}

\begin{corollary}[M\o ller, Knuth, Dekker]
  L'erreur commise $\left|\operatorname{err}(x\oplus y)\right|$ peut être exprimée
  exactement sur $p$ bits.
\end{corollary}

\pause

\begin{itemize}
\item $|x| \geqslant |y|$
\item $x$ et $y$ sont des VF\pause : le  plus petit bit significatif de $\operatorname{err}(x\oplus y)$ est
au moins de magnitude celle de ulp($y$)

\pause

$x$\hspace{1em} \MyBox[mmmmmmmmm]{$x_1$}
\MyBox[mmmm]{$x_2$}

\pause

$+y$ \hspace{9.5em}\MyBox[mmmm]{$y_1$}
\MyBox[mmmmmmmm]{$y_2$}

\pause

$=$   \hspace{1em}\MyBox[mmmmmmmmm]{$x_1$}
\MyBox[mmmm]{$x_2+y_1$} \ $\operatorname{err}(x\oplus y)$

\pause

\item  $\left|\operatorname{err}(x\oplus y)\right| \leqslant |y|$\pause  donc la mantisse
entière de $\operatorname{err}(x\oplus y)$ a une longueur inférieure à $p$ bits
\end{itemize}

\end{frame}


\begin{frame}
\begin{lemma}\label{lemme::plusExact}
  Supposons que $|x+y|\leqslant \min(|x|,|y|)$, alors $x\oplus y = x + y$.

On obtient un résultat analogue pour la soustraction.
\end{lemma}

\begin{enumerate}
\item Supposons, sans perdre de généralité, que $|x| \geqslant |y|$
\item Le  plus petit bit significatif de $x+y$ est
au moins de magnitude celle de $\operatorname{ulp}(y)$
\item  $|x+y| \leqslant |y|$ donc la mantisse
entière de $x+y$  a une longueur inférieure à $p$ bits


\end{enumerate}

\end{frame}


\begin{frame}[fragile]
  \begin{alertblock}{DANGER}
  Nous avons démontré nos lemmes en considérant des VF $x$ et $y$.

  Est-ce que le résultat suivant contredit notre dernier lemme?

  \begin{pythoncode}
In [86]: 1 - 0.9
Out[86]: 0.09999999999999998
  \end{pythoncode}

  \end{alertblock}
\end{frame}





\begin{frame}
\begin{lemma}[Lemme de \textsc{Sterbenz} (1973)]
  Soit $(x,y)\in \bbv^2$ vérifiant $\dfrac{x}{2} \leqslant y \leqslant 2x$ alors $$x\ominus y=x-y$$
La différence de deux VF suffisamment proches est donc exacte.
\end{lemma}

\pause


\begin{enumerate}
\item  $\mathbf{x <  y}$:  alors  $x <  y  \leqslant  2x$ donc  $0
  < y-x \leqslant x \leqslant y$;
\item $\mathbf{x  \geqslant y}$: alors  $ \frac{x}{2} \leqslant y  \leqslant x$
  donc $ -\frac{x}{2} \leqslant y-x \leqslant 0$ et par suite $0 \leqslant x - y
  \leqslant \frac{x}{2} \leqslant y \leqslant x$.
\end{enumerate}


\pause


\textcolor{white}{Dans tous les cas $|x-y| \leqslant \min(|x|,|y|)$ et on peut utiliser le lemme 
\vref{lemme::plusExact}.}


\end{frame}






\begin{frame}
  \begin{itemize}
  \item   Concrètement, à quoi correspond cette condition $\dfrac{x}{2} \leqslant y \leqslant 2x$?

\item  Demandez-vous ce que l'on peut dire de l'écart maximum entre les exposants de $x$ et $y$.
  \end{itemize}
\end{frame}






\begin{frame}[fragile]
\begin{pythoncode}[Python3]
In [9]: 2.**53
Out[9]: 9007199254740992.0

In [10]: 2.**53 + 1
Out[10]: 9007199254740992.0

In [11]: 2.**53 + 2
Out[11]: 9007199254740994.0

In [12]: 2.**53 + 3
Out[12]: 9007199254740996.0

In [13]: 2.**53 + 4
Out[13]: 9007199254740996.0

In [14]: 2.**53 + 5
Out[14]: 9007199254740996.0
\end{pythoncode}
\end{frame}

\begin{frame}[fragile]
$$2^{53} = (-1)^0\times 1,000...000 \times 2^{53+1023}$$ 

\pause

\footnotesize{
\begin{Verbatim}
0 10000110100 0000000000000000000000000000000000000...00000 
\end{Verbatim}
}

\pause


$$ 1=(-1)^0\times 1,000...000 \times 2^{0+1023} $$ 


\pause

{\footnotesize
\begin{Verbatim}
0 01111111111 0000000000000000000000000000000000000...00000 
\end{Verbatim}
}

\pause

  $$1=0,\underbrace{000...000}_{\rm   52  bits}\  1  \times
2^{53}$$

\pause

{\footnotesize
\begin{Verbatim}
1,0000000000000000000000000000000000000000000000000000|
0,0000000000000000000000000000000000000000000000000000|1
--------------------------------------------------------
1,0000000000000000000000000000000000000000000000000000|1 
\end{Verbatim}
}


\end{frame}




\begin{frame}
 
%\begin{figure}
\begin{center}
  \includegraphics[width=0.7\linewidth]{drapeau}
\end{center}
%\end{figure}


\pause

 \textit{Unit in the Last Place}


\pause

\begin{description}
\item[Mauvaise nouvelle]: une addition entre deux
nombres flottants peut donc, dans certains cas, créer une erreur.
\item[Bonne nouvelle]: on peut récupérer cette erreur. 
\end{description}


\end{frame}












\begin{frame}
  

\begin{theorem}[Fast2Sum - \textsc{Dekker} \& \textsc{Kahan}]\label{th::Fast2Sum}
On considère  deux VF $x$  et $y$ tels que  $|x| \geqslant |y|$  et l'algorithme
suivant:

\begin{algo}[numbered]
\STATE{$s$ \recoit{} $x\oplus y$ }
\STATE{$y_v$\recoit{} $s\ominus x$}
\STATE{$d$ \recoit{} $y \ominus y_v$}
\RETURN{$(s,d)$}
\end{algo}
  
Alors $x+y=s+d$ avec $s=x\oplus y$ et $d={\rm err}(x\oplus y)$. De plus $s$ et $d$ ne se chevauchent pas.

\end{theorem}

\pause


\begin{itemize}
\item  \textbf{si} $\mathbf{x}$  \textbf{et} $\mathbf{y}$  \textbf{sont de  même
    signe    OU    si}    $\mathbf{|y|    \leqslant    \frac{|x|}{2}}$:    alors
  $\frac{x}{2}\leqslant s \leqslant 2x$ et on peut appliquer le lemme;
\item \textbf{sinon}:  on a $x$ et  $y$ de signes opposés  ET $y> \frac{|x|}{2}$
  alors si $y$  est négatif $x/2 < -y  < x$ et sinon $-x/2<y<-x$.  Dans les deux
  cas, d'après  le lemme  de \textsc{Sterbenz}, $s$  est calculée  exactement et
  alors $y_v=y$.
\end{itemize}



\end{frame}

\begin{frame}\frametitle{Somme compensée}


\color{white}

\begin{tabular}[!h]{rp{5em}p{2.7em}p{4.5em}p{2.5em}l}
  $x$ & \fbox{ $x_1$\hspace{4.1em}} & \fbox{$x_2$\hspace{2.2em}} & & & \\
  $+y$ & & \fbox{$y_1$\hspace{2.2em}} & \fbox{$y_2$\hspace{4em}} & & \\
  $=s$ & \fbox{$x_1 \textcolor{black}{y_1}$\hspace{3.4em}} & \fbox{$x_2+y_1$} & \ $y_2$ perdu & & \\
  $-x=y_v$ & &\fbox{$y_1$\hspace{2.2em}} & \fbox{$0\textcolor{black}{x_1}$\hspace{3.2em}} & & \\
  $-y=-d$ & & & \fbox{$-y_2$\hspace{3.2em}} & \fbox{$0\textcolor{black}{x_1}$\hspace{1em}} & on récupère l'erreur
\end{tabular}

\end{frame}












\begin{frame}[fragile]

  \begin{pythoncode}
def fast2sum(x,y):
    if abs(x) >= abs(y):
        s  = x + y
        yv = s - x
        d  = y - yv
        return (s,d)
    else:
        return fast2sum(y,x)
\end{pythoncode}
\end{frame}



\begin{frame}[fragile]

  \begin{pythoncode}
In [100]: fast2sum(2.0**54,1.0)
Out[100]: (1.8014398509481984e+16, 1.0)
\end{pythoncode}
\pause
\begin{pythoncode}
In [101]: fast2sum(2.0**54,2.0)
Out[101]: (1.8014398509481984e+16, 2.0)
\end{pythoncode}
\pause
\begin{pythoncode}
In [102]: fast2sum(2.0**54,3.0)
Out[102]: (1.8014398509481988e+16, -1.0)
\end{pythoncode}
\pause
\begin{pythoncode}
In [103]: fast2sum(2.0**54,4.0)
Out[103]: (1.8014398509481988e+16, 0.0)
\end{pythoncode}
\pause
\begin{pythoncode}
In [104]: fast2sum(2.0**54,5.0)
Out[104]: (1.8014398509481988e+16, 1.0)
  \end{pythoncode}
  
\end{frame}



\begin{frame}
\begin{theorem}[2Sum - \textsc{Knuth} ]\label{th::2Sum}
On considère  deux VF $x$  et $y$   et l'algorithme
suivant:

\begin{algo}[numbered]
\STATE{$s$ \recoit{} $x\oplus y$ }
\STATE{$y_v$\recoit{} $s\ominus x$}
\STATE{$x_v$\recoit{} $s\ominus y_v$}
\STATE{$y_a$\recoit{} $y\ominus y_v$}
\STATE{$x_a$\recoit{} $x\ominus x_v$}
\STATE{$d$ \recoit{} $x_a \oplus y_a$}
\RETURN{$(s,d)$}
\end{algo}
  
Alors $x+y=s+d$ avec $s=x\oplus y$ et $d={\rm err}(x\oplus y)$. De plus $s$ et $d$ ne se chevauchent pas.

\end{theorem}

\end{frame}




\begin{frame} \frametitle{Somme compensée d'un nombre quelconque de flottants}
  \small
\begin{center}
\tikzstyle{int}=[draw, fill=blue!20, minimum size=2em]
\tikzstyle{init} = [pin edge={<-,thin,white}]
\tikzstyle{fin} = [pin edge={->,thin,white}, pin position = below]
\tikzstyle{sort} = [pin edge={->,thin,white}, pin position = right]
\tikzstyle{entre} = [pin edge={<-,thin,white}, pin position = left]

\begin{tikzpicture}[node distance=2.9cm,auto,>=latex']
  \node [int, pin={[init]$x_1$}, pin={[fin]$e_1$},pin={[sort]$s_1$}] (a) {\textcolor{blue}{\texttt{twoSum}}}; %bloc 1
  \node (b) [left of=a,node distance=1.5cm, coordinate] {a}; % noeud d'entrée
  \node [int,pin={[entre]}, pin={[init]$x_2$}, pin={[fin]$e_2$},pin={[sort]$s_2$}] (c) [right of=a] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 2
  \node [int,pin={[entre]}, pin={[init]$x_3$}, pin={[fin]$e_3$},pin={[sort]$s_3$}] (d) [right of=c] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 3
  \node [int,pin={[entre]}, pin={[init]$x_4$}, pin={[fin]$e_4$}] (e) [right of=d] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 4
  \node [coordinate] (end) [right of=e, node distance=1.5cm]{}; % noeud fin
  \draw[->] (b)node[left] {$x_0$} --(a) ; % entrée
  \draw[->] (e) --(end)node[right] {$s$} ; % fin
 \end{tikzpicture}

\end{center}


\end{frame}


\begin{frame}[fragile] \frametitle{Somme compensée d'un nombre quelconque de flottants}
\begin{pythoncode}
def sommeKahan(liste):
    (s,c) = (0.,0.)
    for x in liste:
        (s,c) = fast2sum(s, x + c)
    return s
\end{pythoncode}

\pause

\begin{pythoncode}
def sommePichat(liste):
    s,e = 0.,0.
    for x in liste:
        (s,c) = fast2sum(s, x)
        e += c
    return s + e
\end{pythoncode}

\end{frame}











\begin{frame}
$x_0=2^{53}-1$, $x_1=2^{53}$ et $x_2=-(2^{54}-2)$


\pause


\begin{center}
\tikzstyle{int}=[draw, fill=blue!20, minimum size=2em]
\tikzstyle{init} = [pin edge={<-,thin,white}]
\tikzstyle{fin} = [pin edge={->,thin,white}, pin position = below]
\tikzstyle{sort} = [pin edge={->,thin,white}, pin position = right]
\tikzstyle{entre} = [pin edge={<-,thin,white}, pin position = left]

\begin{tikzpicture}[node distance=3.1cm,auto,>=latex']
  \node [int, pin={[init]$2^{53}$}, pin={[fin]$-1$},pin={[sort]$2^{54}$}] (a) {\textcolor{blue}{\texttt{twoSum}}}; %bloc 1
  \node (b) [left of=a,node distance=1.5cm, coordinate] {a}; % noeud d'entrée
  \node [int,pin={[entre]}, pin={[init]$-(2^{54}-2)$}, pin={[fin]$0$}] (c) [right of=a] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 2
  \node [coordinate] (end) [right of=c, node distance=1.5cm]{}; % noeud fin
  \draw[->] (b)node[left] {$2^{53}-1$} --(a) ; % entrée
  \draw[->] (c) --(end)node[right] {$2$} ; % fin
 \end{tikzpicture}
\end{center}

\begin{exercice}\label{exo::2sum}
  Expliquez les résultats trouvés. Que va faire l'algorithme de somme compensée?
  Et celui de somme en cascade?
\end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{pythoncode}
In [105]: sommePichat([1. / n for n in range(1,100001)])
Out[105]: 12.090146129863427

In [106]: sommeKahan([1. / n for n in range(1,100001)])
Out[106]: 12.090146129863427

In [107]: sum([1. / n for n in range(1,100001)])
Out[107]: 12.090146129863335

In [108]: sum([1. / n for n in range(100000,0,-1)])
Out[108]: 12.090146129863408
  \end{pythoncode}

\pause

\begin{pythoncode}
sage: sum(1. / n, n , 1 , 100000).n(64)
12.0901461298634279
\end{pythoncode}

\end{frame}











\begin{frame}[fragile]\frametitle{Banque chaotique}

Exemple dû à Jean-Michel Muller.

\pause

{\itshape 
M. X a récemment été à sa banque (Chaotic Bank Society), pour connaître les nouvelles offres proposées aux
meilleurs clients. Son banquier lui propose l'offre suivante: \og vous déposez tout d'abord e - 1 euros sur votre compte
(où e = 2.7182818... est la base du logarithme népérien). La première année, nous prenons 1 euro sur votre compte de
frais de gestion. Par contre, la deuxième année est plus intéressante pour vous, car nous multiplions votre capital restant
par 2 et prenons 1 euro de frais de gestion. La troisième année est encore plus intéressante, car nous multiplions votre
capital par 3 et prenons 1 euro de frais de gestion. Et ainsi de suite : la n-ième année, nous multiplions votre capital par n
et prenons 1 euro de frais de gestion. Intéressant, non? \fg{} Pour prendre sa décision, M. X décide de demander l'aide
d'un informaticien et se retourne vers vous.
}

\end{frame}



\begin{frame}[fragile]

  \begin{pythoncode}
def chaotic(n):
    cpt = exp(1) - 1
    for i in range(1,n + 1):
        cpt = i*cpt - 1
    return cpt
  \end{pythoncode}

\pause

\begin{align*}
c_n&=&n!\times \left(c_0-1- \frac{1}{2!} - \frac{1}{3!} -\cdots - \frac{1}{n!} \right) \\
&=&n!\times(c_0-({\rm e}-1)+ \frac{1}{(n+1)!} + \frac{1}{(n+2)!}+\cdots )
\end{align*}

\end{frame}



\section{Codage des caractères}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{martine_utf8}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}\frametitle{ASCII}
  \begin{itemize}
  \item \textbf{American} Standard Code for Information Interchange
  \item 128 caractères pour la langue anglaise
  \item sur combien de bits?
  \end{itemize}
\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{minitel}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{netscape}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{ascii}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}\frametitle{ISO-8859-1 / Latin-1}
  \begin{itemize}
  \item International Organization for Standardization
  \item 8 bits pour les langues d'Europe de l'Ouest
  \end{itemize}
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{latin1}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}\frametitle{Unicode}
  
  Espace pouvant contenir $0x10ffff$ soit $1\,114\,112$ codes différents.
 
\end{frame}

\begin{frame}\frametitle{UTF-8}
  \begin{itemize}
  \item Unicode  Transformation Format: un  standard pour encoder les  points de
    code. 
\item Peut représenter tous les points de code de l'Unicode
\item Un caractère est représenté sur 1 à 4 octets
\item Les caractères  les plus fréquents sont représentés sur  les codes de plus
  petite taille
\item compatible avec les caractères ASCII
  \end{itemize}
\end{frame}




\begin{frame}\frametitle{Fonctionnement de l'UTF-8}
  %\begin{table}[!h]
    %\centering
{\tiny 
    \begin{tabular}[!h]{|l|l|l|l|l|l|}
      \hline
De& à&1\up{er} octet& 2\up{ème} octet& 3\up{ème} octet& 4\up{ème} octet\\
\hline
$0x0$ & $0x7F$&{\color{blue} $0$}$b_7b_6b_5b_4b_3b_2b_1$&/&/&/\\
$0x80$                         &                         $0x7FF$&{\color{blue}
  $110$}$b_{11}b_{10}b_9b_8b_7$&{\color{blue}$10$}$b_6b_5b_4b_3b_2b_1$&/&/\\
$0x800$                        &                        $0xFFFF$&{\color{blue}
  $1110$}$b_{16}b_{15}b_{14}b_{13}$&{\color{blue}$10$}$b_{12}b_{11}b_{10}b_9b_8b_7$&{\color{blue}$10$}$b_6b_5b_4b_3b_2b_1$&/\\
$0x10000$                      &                      $0x10FFFF$&{\color{blue}
  $11110$}$b_{21}b_{20}b_{19}$&{\color{blue} $10$}$b_{18}b_{17}b_{16}b_{15}b_{14}b_{13}$&{\color{blue}$10$}$b_{12}b_{11}b_{10}b_9b_8b_7$&{\color{blue}$10$}$b_6b_5b_4b_3b_2b_1$\\
\hline
}
    \end{tabular}
  %\end{table}
\end{frame}


\begin{frame}[fragile]
Point  de  code  $0x3B1$  $⟶$  caractère  $α$  $⟶$  ${\color{blue}  110}01110\
{\color{blue}10}110001$


\pause

\begin{pythoncode}
In [4]: chr(0x3b1)
Out[4]: 'α'

In [5]: ord('é')
Out[5]: 233
\end{pythoncode}




\end{frame}

\section{Compression}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{techno}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
\only<1>{\includegraphics{step0.pdf}}
\only<2>{\includegraphics{step1.pdf}}
\only<3>{\includegraphics{step2.pdf}}
\only<4>{\includegraphics{step3.pdf}}
\only<5>{\includegraphics{step4.pdf}}
\only<6>{\includegraphics{step5.pdf}}
\only<7>{\includegraphics{step6.pdf}}
\only<8>{\includegraphics{step7.pdf}}
\only<9>{\includegraphics{step8.pdf}}
\only<10>{\includegraphics{step9.pdf}}
\only<11>{\includegraphics{step10.pdf}}
\only<12>{\includegraphics{step11.pdf}}
\only<13>{\includegraphics{step12.pdf}}
\only<14>{\includegraphics{step13.pdf}}
\only<15>{\includegraphics{step14.pdf}}
\only<16>{\includegraphics{step15.pdf}}
\only<17>{\includegraphics{step16.pdf}}
\only<18>{\includegraphics{step17.pdf}}
\only<19>{\includegraphics{step18.pdf}}
\only<20>{\includegraphics{step19.pdf}}
\only<21>{\includegraphics{step20.pdf}}
\only<22>{\includegraphics{step21.pdf}}
\only<23>{\includegraphics{step22.pdf}}
\only<24>{\includegraphics{step23.pdf}}
\only<25>{\includegraphics{step24.pdf}}
\only<26>{\includegraphics{step25.pdf}}
\end{frame}

\begin{frame}
  
\begin{tikzpicture}
\node at (2,0) {\includegraphics[width=2cm]{zip.png}};
\node at (3,3.5) {\includegraphics[width=2cm]{zipb.png}};
\node at (8,0.5) {\includegraphics[width=2cm]{rar.png}};
\node at (4,1) {\includegraphics[width=2cm]{divx.png}};
\node at (6,3) {\includegraphics[width=2cm]{mp3.jpg}};
\end{tikzpicture}

\end{frame}


\begin{frame}
  Sujet des Mines 2015...hors programme...Codage de \textsc{Huffman}
\end{frame}


\begin{frame}
  \begin{figure}[ht]
    \centering
    \includegraphics[height=0.9\textheight]{huffman}
    \caption{\label{fig:huffman} David \textsc{Huffman (1925 - 1999)}}
  \end{figure}

\end{frame}


\frame{
\frametitle{Principe de l'algorithme de Huffman}

\begin{block}{Principe}
\begin{itemize}
\item Les symboles (e.g octets) sont recodés avec des tailles variables : plus un symbole est fréquent, plus le mot de code le représentant sera court
\item Pour permettre la décompression, une table (en fait un arbre) de correspondance entre les symboles et les mots de code correspondants est transmise avec la donnée compressée
\end{itemize}
\end{block}

\pause

\begin{alertblock}{Apport principal de Huffman (1952)}
Une manière judicieuse de choisir quel mot de code associer à chaque symbole
\end{alertblock}

}

\frame{
\frametitle{Caractéristiques de l'algorithme de Huffman}

\begin{block}{Un code préfixe (\textcolor{red}{quel intérêt ?})}
Aucun mot de code n'est le préfixe (le début) d'un autre mot de code.
\end{block}

\begin{exampleblock}{Code préfixe ou non pour trois caractères}
\centering
\begin{tabular}{|c|ccc|}
\hline
            & a  & b  & c  \\
\hline
Préfixe     & 0  & 10 & 11 \\
Non préfixe & 0  & 1  & 11 \\
\hline
\end{tabular}
\end{exampleblock}

\pause

\begin{block}{Un code optimal}
En encodant les symboles séparément on ne peut pas compresser plus que par l'algorithme de Huffman !
\end{block}

}

\frame{
\frametitle{L'algorithme de Huffman en trois étapes}

\begin{block}{Étape 1 : fréquence des symboles}
On calcule la fréquence de chaque symbole de la donnée à compresser
\end{block}

\begin{exampleblock}{Exemple}
\begin{center}
{\it J'erre près des berges de l'Elster.}\\

\vspace{0.3cm}

\only<2>{
\begin{tabular}{c|ccccccccccccccc}
$x$ & J & ' & e & r & sp & p & è & s & d & b & g & l & E & t & .\\
\hline
$f_x$ & 1 & 2 & 7 & 5 & 5  & 1 & 1 & 4 & 2 & 1 & 1 & 2 & 1 & 1 & 1\\
\end{tabular}
}
\only<3->{
\begin{tabular}{c|ccccccccccccccc}
$x$ & J & p & è & b & g & E & t & . & ' & d & l & s & r & sp & e\\
\hline
$f_x$ & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 4 & 5 & 5  & 7\\
\end{tabular}
}
\end{center}
\end{exampleblock}

\only<4>{
\begin{block}{Remarque}
On peut utiliser des tables de fréquences pré-existantes, mais le code n'est alors plus optimal
\end{block}
}

}

\frame{
\frametitle{L'algorithme de Huffman en trois étapes}

\begin{block}{Étape 2}
On construit un arbre à partir des fréquences, qui déterminera le mot de code correspondant à chaque symbole
\end{block}

%\vspace*{-0.8cm}

\begin{columns}[t]
\begin{column}{6cm}
\begin{alertblock}{Construction de l'arbre}
{\bf tant que} il reste plus d'un symbole\\
~~~~~~{\bf choisir} $x$ minimisant $f_x$\\
~~~~~~{\bf choisir} $y\!\neq\!x$ minimisant $f_y$\\
~~~~~~{\bf détruire} $x$ et $y$\\
~~~~~~{\bf créer} $\hat{xy}$ de fréquence $f_x+f_y$\\
{\bf fin tant que}\\
{\bf retourner} le symbole restant
\end{alertblock}
\end{column}
\begin{column}{5.5cm}
\begin{exampleblock}{Exemple}
{\it J'erre près des berges de l'Elster.}\\
%\only<1>{
\vspace{0.3cm}

\begin{tabular}{c|cccccccc}
$x$ & J & p & è & b & g & E & t \\
\hline
$f_x$ & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{tabular}

\vspace{0.5cm}

\begin{tabular}{cccccccc}
. & ' & d & l & s & r & sp & e\\
\hline
1 & 2 & 2 & 2 & 4 & 5 & 5  & 7\\
\end{tabular}
%}
%% \only<2>{
%% \scalebox{0.7}{\input{huffman.pgf}}
%% }
\end{exampleblock}
\end{column}
\end{columns}

}

\frame{
\frametitle{Construction de l'arbre}

\begin{center}
\input{hs0.pgf}
\end{center}

}

\frame{
\frametitle{L'algorithme de Huffman en trois étapes}

\begin{block}{Étape 2}
On construit un arbre à partir des fréquences, qui déterminera le mot de code correspondant à chaque symbole
\end{block}

%\vspace*{-0.8cm}

\begin{columns}[t]
\begin{column}{6cm}
\begin{alertblock}{Construction de l'arbre}
{\bf tant que} il reste plus d'un symbole\\
~~~~~~{\bf choisir} $x$ minimisant $f_x$\\
~~~~~~{\bf choisir} $y\!\neq\!x$ minimisant $f_y$\\
~~~~~~{\bf détruire} $x$ et $y$\\
~~~~~~{\bf créer} $\hat{xy}$ de fréquence $f_x+f_y$\\
{\bf fin tant que}\\
{\bf retourner} le symbole restant
\end{alertblock}
\end{column}
\begin{column}{5.5cm}
\begin{exampleblock}{Exemple}
{\it J'erre près des berges de l'Elster.}\\
%\only<1>{
%% \vspace{0.3cm}

%% \begin{tabular}{c|cccccccc}
%% $x$ & J & p & è & b & g & E & t \\
%% \hline
%% $f_x$ & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
%% \end{tabular}

%% \vspace{0.5cm}

%% \begin{tabular}{cccccccc}
%% . & ' & d & l & s & r & sp & e\\
%% \hline
%% 1 & 2 & 2 & 2 & 4 & 5 & 5  & 7\\
%% \end{tabular}
%}
%% \only<2>{
\scalebox{0.7}{\input{huffman.pgf}}
%% }
\end{exampleblock}
\end{column}
\end{columns}

}

\frame{
\frametitle{L'algorithme de Huffman en trois étapes}

\begin{block}{Étape 3}
On utilise l'arbre pour coder, la branche qui mène à un symbole donne directement le mot de code pour ce symbole
\end{block}

\begin{exampleblock}{Exemple}
\begin{columns}
\begin{column}{5cm}
\only<1>{
\scalebox{0.7}{\input{huffman.pgf}}
}
\only<2->{
\scalebox{0.7}{\input{huffman2.pgf}}
}
\end{column}
\begin{column}{5.5cm}
{\it J'erre près des berges de l'Elster.}\\

\vspace*{0.3cm}

\only<1-9>{
\uncover<1->{J : \textcolor{blue}{11}\textcolor{red}{0000},}
\uncover<2->{' : \textcolor{blue}{1}\textcolor{red}{000},}
\uncover<3->{e : \textcolor{red}{00},\\}
\uncover<4->{r : \textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{1},}
\uncover<5->{sp : \textcolor{blue}{111},}
\uncover<6->{p : \textcolor{blue}{11}\textcolor{red}{000}\textcolor{blue}{1},}
\uncover<7->{etc\\}

\vspace*{0.3cm}
}

\uncover<1->{\textcolor{blue}{11}\textcolor{red}{0000}%
\uncover<2->{\textcolor{blue}{1}\textcolor{red}{000}%
\uncover<3->{\textcolor{red}{00}%
\uncover<4->{\textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{1}%
\uncover<5->{\textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{1}%
\uncover<6->{\textcolor{red}{00}%
\uncover<7->{\textcolor{blue}{111}%
\uncover<8->{\textcolor{blue}{11}\textcolor{red}{000}\textcolor{blue}{1}
\uncover<9->{\textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{1%
11}\textcolor{red}{00}\textcolor{blue}{1}\textcolor{red}{0%
0}\textcolor{blue}{11%
111%
1}\textcolor{red}{00}\textcolor{blue}{1}%
\textcolor{red}{00%
0}\textcolor{blue}{11%
111%
11} \textcolor{red}{00}\textcolor{blue}{11}%
\textcolor{red}{00}%
\textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{1}%
\textcolor{red}{0}\textcolor{blue}{1}\textcolor{red}{000%
00%
0}\textcolor{blue}{11%
111%
1}\textcolor{red}{00}\textcolor{blue}{1}%
\textcolor{red}{00}%
\textcolor{blue}{1 11%
11}\textcolor{red}{0}\textcolor{blue}{1%
1}\textcolor{red}{000%
0}\textcolor{blue}{1}\textcolor{red}{00}\textcolor{blue}{1%
11}\textcolor{red}{0}\textcolor{blue}{1}%
\textcolor{red}{0}\textcolor{blue}{11}%
\textcolor{red}{0}\textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{1}\textcolor{red}{0%
00}
\textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{1}%
\textcolor{red}{0}\textcolor{blue}{1}\textcolor{red}{0}\textcolor{blue}{11}}}}}}}}}}

\uncover<10->{
\vspace*{0.3cm}

124 bits pour 35 symboles dont 15 différents}

\end{column}
\end{columns}
\end{exampleblock}

}

\frame{
\frametitle{Décodage}

\begin{block}{Étape 3b}
On utilise l'arbre pour décoder, on suit les branches correspondant aux bits lus, quand on arrive à une feuille on a décodé le symbole correspondant
\end{block}

\begin{exampleblock}{Exemple}
\begin{columns}[c]
\begin{column}{5.5cm}
\textcolor<2>{green}{1}\textcolor<3>{green}{1}\textcolor<4>{green}{0}\textcolor<5>{green}{0}\textcolor<6>{green}{0}\textcolor<7>{green}{0}\textcolor<8>{green}{1}\textcolor<9>{green}{0}\textcolor<10>{green}{0}\textcolor<11>{green}{0}\textcolor<12>{green}{0}\textcolor<13>{green}{0}\textcolor<14>{green}{1}\textcolor<15>{green}{0}\textcolor<16>{green}{1}\textcolor<17>{green}{1}\textcolor<18>{green}{0}\textcolor<19>{green}{1}\textcolor<20>{green}{0}\textcolor<21>{green}{0}\textcolor<22>{green}{1}\textcolor<23>{green}{1}\textcolor<24>{green}{1}\textcolor<25>{green}{1}\textcolor<26>{green}{1}\textcolor<27>{green}{0}\textcolor<28>{green}{0}\textcolor<29>{green}{0}\textcolor<30>{green}{1}
10111001001111110010001111111
00110010101000000111111001001
11110110000100111010110101000
10101011\\

\vspace*{0.5cm}

{\it \uncover<7->{J}\uncover<11->{'}\uncover<13->{e}\uncover<16->{r}\uncover<19->{r}\uncover<21->{e}\uncover<24->{ }\uncover<30->{p}\uncover<31>{rès des berges de l'Elster.}}\\
\end{column}
\begin{column}{5cm}
\scalebox{0.7}{\input{huffman2.pgf}}
\end{column}
\end{columns}
\end{exampleblock}

}


\frame{
\frametitle{Utilisation pratique de Huffman}

\begin{block}{Compression sans perte d'information}
Plusieurs méthodes de compression sans perte utilisent l'algorithme de Huffman, souvent en combinaison avec d'autres algorithmes \only<2->{(\textcolor{red}{si Huffman est optimal, pourquoi faire ça ?})}
\end{block}

\begin{exampleblock}{Exemple}
Zip : LZ77 suivi de Huffman
\end{exampleblock}

\begin{block}{Support à la compression avec perte d'information}
Après avoir utilisé des techniques de compression détruisant de l'information on peut toujours ajouter une passe de compression sans perte d'information
\end{block}

}

\begin{frame}
  Merci à Loïg \textsc{Jézéquel}
\end{frame}







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