\documentclass[xcolor=hyperref,hyperef={naturalnames,pdfpagelabels},french]{beamer}
\usepackage{etex}
\usepackage[beamer]{preambule}
\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark}
\usepackage{movie15}
%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}


\setlength{\columnseprule}{0pt}

\graphicspath{{/home/moi/Lycee/2nde/2009_10/}{/home/moi/Photos/Maths/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Figures/figuresTS/}{/home/moi/Lycee/TDmaple/2007_8/}{/home/moi/IREM/IREM10_06_09/}}



\newcommand\xc{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
keywordstyle =\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\caml{
\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}
\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}

\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}

\title[] % (optional, use only with long paper titles)
{Définitions algorithmiques d'outils mathématiques basiques}

\subtitle{ Programmes avec XCAS et CAML}

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

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

\logo{\includegraphics[scale=0.15]{logoirem}}

\date[] % (optional, should be abbreviation of conference name)
{\today}
% - 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{Définitions algorithmiques d'outils mathématiques basiques}


\beamerdefaultoverlayspecification{<+->}

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

  \end{frame}
}




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\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{<+->}









\begin{document}


\begin{frame}
  \titlepage
\end{frame}

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

 
 \end{frame}


\section{Valeur absolue}\label{abs}

\subsection{Algorithme}

\begin{frame}[fragile]
              
On peut définir la valeur absolue  d'un réel $x$ de la manière suivante,
même si ce n'est pas l'usage en seconde~:

\begin{algorithm}[H]
  \caption{valeur absolue}
\Entree{$x$(un réel)}
\Deb{
\eSi{x positif}{\Retour{x}}{\Retour(-x)}
}
\end{algorithm}

\end{frame}


\subsection{Traduction XCAS}



\begin{frame}[fragile]
             \xc
              

\begin{lstlisting}[caption={valeur absolue}]
va(x):={
  si x>0 alors 
    return(x) sinon  
    return(-x) 
  fsi;  
}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
             \xc
 en anglais~:

\begin{lstlisting}[caption={valeur absolue (VO)}]
va(x):={
  if(x>0){return(x)}
  else{return(-x)}
}
\end{lstlisting}             
\end{frame}


\subsection{En CAML}




\begin{frame}[fragile]
             \caml
              
\begin{lstlisting}[caption={valeur absolue (OCAML)}]
# let va(x)=
    if x>0 then x else -x;;
\end{lstlisting}

\end{frame}


\section{Partie entière}

\subsection{Intérêt}


\begin{frame}
  
La partie entière  n'est pas explicitement au programme  de seconde mais
sa  détermination  algorithmique   enrichit  l'étude  des  ensembles  de
nombres.

On peut  définir la  partie entière  d'un réel $x$  comme étant  le plus
grand entier inférieur à $x$.

\end{frame}



\subsection{Algorithme récursif}

\begin{frame}
  
On part du fait que la  partie entière d'un nombre appartenant à $[0;1[$
est nulle.

\pause

Ensuite, on \og  descend \fg{} de $x$ vers  0 par pas de 1  si le nombre
est positif en montant que $\lfloor x\rfloor=1+\lfloor x-1\rfloor$.


\pause

Si le nombre est négatif, on \og monte\fg{} vers 0 en montrant que $\lfloor x\rfloor=-1+\lfloor x+1\rfloor$.

\end{frame}


\subsubsection{Avec XCAS}\label{per}




\begin{frame}[fragile]
             \xc
              
\begin{lstlisting}[caption={partie entier en récursif}]
partie_entiere_rec(r):={
  si(r>=0) et (r<1) 
      alors 0
      sinon si r>0
            alors 1+partie_entiere_rec(r-1)
            sinon -1+partie_entiere_rec(r+1)
            fsi       
      fsi
}:;
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
             \xc
              
En anglais~:

\begin{lstlisting}[caption={partie entière en récursif (VO)}]
partie_entiere_rec(r):={
  if((r>=0) and (r<1)){0}
  else{if(r>0){1+partie_entiere_rec(r-1)}
       else{-1+partie_entiere_rec(r+1)}       
      }
}:;
\end{lstlisting}


\end{frame}

\subsubsection{Avec CAML}

\begin{frame}[fragile]
             \caml
\begin{lstlisting}[caption={partie entière en récursif (OCAML)}]
# let rec partie_entiere (r)
        =
        if r >= 0. && r < 1.
         then 0.
         else if r > 0.
               then   1. +. partie_entiere (r -. 1.) 
	       else -.1. +. partie_entiere (r +. 1.)

\end{lstlisting}             
\end{frame}



\subsection{Algorithme impératif}


\begin{frame}
  
On peut  commencer par se restreindre  aux nombres positifs.  On part de
0.  Tant qu'on  n'a  pas dépassé  $x$,  on avance  d'un  pas. La  boucle
s'arrête dès  que $k$ est strictement  supérieur à $x$.  La partie entière
vaut donc $k-1$.

\end{frame}



\begin{frame}[fragile]
              

\begin{algorithm}[H]
\caption{partie entière d'un nombre positif}
\Entree{$x$(réel positif)}
\Ini{k \aff 0}
\Deb{
\Tq{k<=x}{k\aff k+1}
\Retour{k-1}
}
\end{algorithm}
\end{frame}



\begin{frame}
  
Dans le  cas d'un réel  négatif, il faut  cette fois reculer d'un  pas à
chaque tour de boucle et la partie entière est la première valeur de $k$
à être inférieure à $x$~:

\end{frame}



\begin{frame}[fragile]
              
\begin{algorithm}[H]
\caption{partie entière d'un réel quelconque}
\Entree{$x$(réel)}
\Ini{k \aff 0}\;
\Deb{
eSi{
\Tq{k<=x}{k\aff k+1}
\Retour{k-1}
}{
\Tq{k>x}{k\aff k-1}
\Retour{k}
}
}
\end{algorithm}
\end{frame}




\subsubsection{Traduction XCAS}


\begin{frame}[fragile]
             \xc
              
\begin{lstlisting}[caption={partie entière en impératif}]
pe(x):={
local k;
k:=0;
si x>=0 alors
   tantque k<=x faire
      k:=k+1;
   ftantque;
   return(k-1);
sinon 
   tantque k>x faire
      k:=k-1;
   ftantque;
   return(k); 
fsi;  
}:;
\end{lstlisting}

\end{frame}






\begin{frame}[fragile]
             \xc
              
\begin{lstlisting}[caption={partie entière en impératif (VO)}]
pe(x):={
local k;
k:=0;
if(x>=0){
   while(k<=x){k:=k+1};
   return(k-1);
        }
else{
   while(k>x){k:=k-1};
   return(k); 
    } 
}:;
\end{lstlisting}
\end{frame}



\section{Arrondis}



\begin{frame}

On veut arrondir un nombre réel à $10^{-2}$ près par défaut.  

\end{frame}


\subsection{Algorithme}


\begin{frame}[fragile]
              
On va
prendre la partie entière (avec l'algorithme créé précédemment) du nombre multiplié par $10^2$ puis le
rediviser par $10^{2}$~:

\begin{algorithm}[H]
              \caption{arrondi}
              \Entree{$x$(réel)}
              \Deb{
\Retour{(partie entière de $100x$) divisée par 100}
} 
               \end{algorithm}

\end{frame}


\subsection{Traduction XCAS}



\begin{frame}[fragile]
             \xc
              
\begin{lstlisting}[caption={arrondi au centième}]
arrondi(x):={
return(pe(100*x)/100.0)
}
\end{lstlisting}
             
\end{frame}




\subsection{Traduction CAML}


\begin{frame}[fragile]
             \caml
              
\begin{lstlisting}[caption={arrondi au centième avec OCAML}]
let arrondi_au_100_eme_par_defaut (r)
    =
    partie_entiere (100. *. r) /. 100.
\end{lstlisting}
\end{frame}


\subsection{Variante}



\begin{frame}
  
On veut arrondir  à $10^{-2}$ près par défaut si  la partie décimale est
strictement inférieure à 0,5 et à $10^{-2}$ près par excès si la partie décimale est
 supérieure à 0,5.

\end{frame}


\begin{frame}[fragile]
              
La recherche de la partie décimale peut poser des problèmes. On commence
donc par traiter le cas des nombres positifs~:

\pause

\begin{algorithm}[H]
              \caption{arrondi au plus proche}
              \Entree{$x$(réel positif)}
             
\Ini{deci\aff  ($x$ $-$  partie entière de $x$)}
 \Deb{
\eSi{deci < 0,5}{\Retour{(partie entière de $100x$) divisée par 100}}{
\Retour{0,01+(partie entière de $100x$) divisée par 100}
}
} 
               \end{algorithm}


\pause

On peut  ensuite chercher à généraliser à  un réel quelconque~:~beaucoup
d'élèves devraient se tromper ici...ce qui est formateur~!

\end{frame}


\section{Calculs de sommes}


\begin{frame}
  
On veut par exemple calculer la somme des entiers de 1 à n.

\end{frame}



\subsection{Algorithme récursif}

\subsubsection{Avec XCAS}


\begin{frame}[fragile]
             \xc
              

\begin{lstlisting}[caption={somme des entiers en récursif}]
som_ent(n):={
if(n==0){0}
else{n+som_ent(n-1)}
}:;
\end{lstlisting}
             

\end{frame}



\subsubsection{Avec CAML}


\begin{frame}[fragile]
             \caml
              

\begin{lstlisting}[caption={somme des entiers en récursif avec OCAML}]
# let rec som_ent(n)=
     if n=0 then 0
     else n+som_ent(n-1);;
\end{lstlisting}
 
\end{frame}

\begin{frame}[fragile]
             \caml
              

Par exemple~:

\begin{lstlisting}
# som_ent(100000);;
- : int = 705082704
\end{lstlisting}


\end{frame}





\begin{frame}
  
On pense bien sûr à généraliser cette procédure à n'importe quelle somme
du type $\ds\sum_{k=k_0}^nf(k)$~:

\end{frame}


\begin{frame}[fragile]
             \caml
              

\begin{lstlisting}[caption={somme des images des entiers par une fonction (CAML)}]
# let rec som_rec(f,ko,n)=
     if n=ko then f(ko)
     else f(n)+som_rec(f,ko,n-1);;
\end{lstlisting}
\end{frame}



\subsection{Algorithme impératif}



\begin{frame}[fragile]
              

\begin{algorithm}[H]
\caption{somme des entiers de 1 à n}
\Entree{$n$(entier naturel)}
\Ini{S\aff 0\tcp{la somme est nulle au départ}}
\Deb{
\Pour{k de 1 à n}{S\aff S+k}
\Retour{S}
 } 
\end{algorithm}
\end{frame}




\subsubsection{Avec XCAS}

\begin{frame}[fragile]
             \xc
              
             

\begin{lstlisting}[caption={somme des entiers en impératif}]
som(n):={
local S;
S:=0;
pour k de 1 jusque n faire
  S:=S+k;
fpour;
return(S)
}
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
             \xc
              
             
\begin{lstlisting}[caption={somme des entiers en impératif (VO)}]
som(n):={
local S;
S:=0;
for(k:=1;k<=n;k:=k+1){S:=S+k};
return(S)
}
\end{lstlisting}
\end{frame}





\section{Mini et maxi}

\subsection{Maximum de deux nombres}


\begin{frame}[fragile]
  On peut utiliser un test~:

\begin{algorithm}[H]
\caption{maxi(x,y)}
\eSi{x>y\;}
    {x}
    {y}
\end{algorithm}

\end{frame}


\begin{frame}[fragile]
             \xc
              
             
\begin{lstlisting}[caption={}]
maxi(x,y):={
if(x>y)then{x}else{y}
}:;                         
\end{lstlisting}
\end{frame}



\begin{frame}[fragile]
             \caml
     
\begin{lstlisting}[caption={}]
               
# let maxi(x,y)=
    if x>y
    then x
    else y ;;
\end{lstlisting}

\end{frame}




\begin{frame}
 
Un   petit    travail   sur    les   valeurs   absolues    définies   au
paragraphe~\vref{abs} permet de montrer que~:

\[{\rm max}(x,y)=\frac{x+y+|x-y|}{2}\qquad {\rm min}(x,y)=\frac{x+y-|x-y|}{2}\]

\end{frame}


\subsection{Maximum d'une liste de nombres}

\subsubsection{Version récursive}



\begin{frame}[fragile]
              

\begin{algorithm}[H]
\caption{maxi(liste)}
\eSi{liste n'a que deux éléments}
    {max(les deux éléments)}
    {max(tête de liste,maxi(liste sans sa tête))}
\end{algorithm}


\end{frame}


\begin{frame}[fragile]
             \caml
              

\begin{lstlisting}
# let rec maxilist = function
        | x::y::[] -> maxi(x,y)
        | x::queue -> maxi(x,maxilist(queue));;
\end{lstlisting}

Quand  on écrit  \verb+x::y::[]+,  CAML comprend  qu'on  a rajouté  deux
éléments à la liste vide~:~il s'agit donc d'une liste de deux éléments...

\end{frame}


\begin{frame}[fragile]
             \caml
              

Voici  une variante  sans utiliser  \texttt{maxi}  et en  créant un  \og
garde-fou\fg{}~:

\begin{lstlisting}[caption={maximum d'une liste en récursif (3)}]
# exception Liste_vide;;

# let rec maxbis = function
  | [] -> raise Liste_vide
  | x::[] -> x
  | x::y::queue -> if x>y then maxbis(x::queue)
                          else maxbis(y::queue);;
\end{lstlisting}

\end{frame}






\begin{frame}[fragile]
             \xc
              
Avec XCAS



\begin{lstlisting}
maxlist(lx):={
 if(size(lx)==2)
   then{maxi(lx[0],lx[1])}
   else{maxi(lx[0],maxlist(tail(lx)))}
}:;
\end{lstlisting}

\end{frame}



\subsection{Version impérative}


\begin{frame}[fragile]
              

\begin{algorithm}[H]
\caption{maximum : version impérative}
\Entree{liste}
\Ini{maxloc\aff tête de la liste}
\Deb{
\Pour{k de 1 jusqu'à la taille de la liste}
     {maxloc\aff le plus grand entre maxloc et k-eme élément de la liste}
 }
\Retour{maxloc} 
\end{algorithm}

\end{frame}



\begin{frame}[fragile]
             \xc
              

\begin{lstlisting}[caption={maximum d'une liste en impératif}]
maxlist_imp(lx):={
local maxloc,k;
maxloc:=lx[0];
  for(k:=1;k<size(lx);k:=k+1){
    maxloc:=maxi(maxloc,lx[k])
  }
return(maxloc)
}:;
\end{lstlisting}
             
\end{frame}



\end{document}

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