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

\usepackage[beamer,utf8,fourier]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}
\usepackage{tkz-graph,tkz-berge}
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning}
\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

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

\usepackage{algo}

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

\newcommand\nor{\downarrow}
\newcommand\nand{\mid}

\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}


\graphicspath{{/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/}}




\newcommand\caml{\lstset{numbers=none,language=Caml,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\ada{\lstset{numbers=none,language=ada,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}
}





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


\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


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

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



\begin{document}


\title[] % (optional, use only with long paper titles)
{Récursion et programmation fonctionnelle}

\subtitle{INFO1 - Semaine 36}

\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{IUT} de Nantes - Dpt d'informatique }% (optional, but mostly needed)

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

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

\date[] % (optional, should be abbreviation of conference name)
{Dernière mise à jour: \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{ }


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




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


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

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

 
 \end{frame}




\section{Un petit jeu pour commencer}

\caml

\begin{frame}[fragile]
  
\begin{lstlisting}[caption={mouvement élémentaire}]
let mvt depart arrivee=
print_string
("Déplace un disque de la tige "^depart^" vers la tige "^arrivee);
print_newline();;
\end{lstlisting}

\pause


\begin{lstlisting}[caption={résolution récursive du problème des tours de Hanoï}]
let rec hanoi a b c= function
   | 0 -> ()  (*0 disque : on ne fait rien*)
   | n -> hanoi a c b (n-1); (*n-1 disques sont déplacés de a vers b*)
          mvt a c; (*on déplace le disque restant en a vers c*)
          hanoi b a c (n-1) (*n-1 disques sont déplacés de b vers c*);;
\end{lstlisting}


\end{frame}






\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
# hanoi "A" "B" "C" 3;;
Déplace un disque de la tige A vers la tige C
Déplace un disque de la tige A vers la tige B
Déplace un disque de la tige C vers la tige B
Déplace un disque de la tige A vers la tige C
Déplace un disque de la tige B vers la tige A
Déplace un disque de la tige B vers la tige C
Déplace un disque de la tige A vers la tige C
- : unit = ()
  \end{lstlisting}
\end{frame}




\begin{frame}[fragile]
\begin{lstlisting}
# hanoi "A" "B" "C" 4;;
Déplace un disque de la tige A vers la tige B
Déplace un disque de la tige A vers la tige C
Déplace un disque de la tige B vers la tige C
Déplace un disque de la tige A vers la tige B
Déplace un disque de la tige C vers la tige A
Déplace un disque de la tige C vers la tige B
Déplace un disque de la tige A vers la tige B
Déplace un disque de la tige A vers la tige C
Déplace un disque de la tige B vers la tige C
Déplace un disque de la tige B vers la tige A
Déplace un disque de la tige C vers la tige A
Déplace un disque de la tige B vers la tige C
Déplace un disque de la tige A vers la tige B
Déplace un disque de la tige A vers la tige C
Déplace un disque de la tige B vers la tige C
- : unit = ()
\end{lstlisting}
\end{frame}




\section{Fonction}

\subsection{Souvenirs du lycée}


\begin{frame}
  \og \textit{Soit $f$ la fonction qui à un entier $k$ associe l'entier naturel
  $k^2$. Calculer $f(2)$ et $f(2-3)$}\fg{}.

\end{frame}

\begin{frame}[fragile]
\ada
\begin{lstlisting}[caption={}]
function F (X: in INTEGER) return INTEGER is
begin
   return X*X;
end F;
\end{lstlisting}

\pause

\caml



\begin{lstlisting}[caption={}]
let f = fun x -> x*x ;;
\end{lstlisting}

  
\end{frame}



\begin{frame}
$$\text{puissance}(x,n)=\underbrace{x\times x \times \cdots\times x}_{n \text{ fois}}$$
\end{frame}


\begin{frame}


{\small
$$\text{puissance}=\left[f\mid \forall x \ (x\in\bbr \wedge f(x,0)=1) \wedge \forall
x\forall n\ ((x,n)\in \bbr\times\bbn \wedge f(x,n+1)=x\times f(x,n))\right]$$
}


\end{frame}


\subsection{Langage des expressions}

\begin{frame}
  \texttt{2*(3+4)}


\pause

 \texttt{a*(b+c)}

\end{frame}




\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
let f = fun k -> k*k;;
\end{lstlisting}


\pause
\begin{lstlisting}[caption={}]
val f : int -> int = <fun>
\end{lstlisting}


\pause

\begin{lstlisting}[caption={}]
# let g = fun x -> x *. x;;
val g : float -> float = <fun>
\end{lstlisting}

\pause

\begin{lstlisting}[caption={}]
# f(3);;
- : int = 9
\end{lstlisting}

\pause


\begin{lstlisting}[caption={}]
# f(1.2);;
Characters 1-6:
  f(1.2);;
   ^^^^^
Error: This expression has type float but an expression was expected of type int
\end{lstlisting}


\end{frame}





\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
# let h = fun a b -> f (b-a);;
val h : int -> int -> int = <fun>
# h 7 3;;
- : int = 16
\end{lstlisting}


\pause

Comment a été calculé $h$ 7 3 ?



\end{frame}




\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
let hh a b =
  let ff k =
    fun k -> k*k
  in
  ff (b-a);;
\end{lstlisting}
\end{frame}


\section{Récursion}

\subsection{Récursion, récurrence, induction}

\begin{frame}
  \begin{itemize}
  \item induction
  \item induction mathématique (raisonnement par récurrence)
  \item fonction récursive, type récursif
  \end{itemize}
\end{frame}




\subsection{Induction mathématique}




%\subsubsection{Jouons aux cubes}


\begin{frame}
  

\begin{center}
\includegraphics[height=4cm]{mp-tex-cubes-0}
\end{center}


\end{frame}


\begin{frame}
  

$$n!=1\times 2\times 3 \times\cdots\times (n-1)\times n$$

\pause
\begin{center}
\texttt{fac(n): si n=1 alors 1 sinon n*(fac (n-1))}
\end{center}
\end{frame}



\begin{frame}
  \begin{exercice}
    Pour  la  factorielle,  on  prouve par  récurrence  que  \texttt{fac(n)}
calcule bien $n!$ et que  le nombre d'appels de la fonction \texttt{fac}
engendrés par le calcul de \texttt{fac(n)} est égal à $n-1$: faites-le!
  \end{exercice}
\end{frame}



\begin{frame}
  \begin{center}
    \texttt{fac(n): si n=1 alors 1 sinon (fac (n+1))/(n+1)}
  \end{center}
\end{frame}





\begin{frame}[fragile]

\begin{lstlisting}[caption={}]
let rec fac = function
  |1 -> 1
  |n -> n*fac(n-1);;

let rec fac n =
  if n = 1 then 1 else n*fac(n-1);;

let rec fac n =
  match n with
    |1 -> 1
    |_ -> n*fac (n-1);;

let fac n =
  let rec temp = function
    |1,acc -> acc
    |n,acc -> temp(n-1 , n*acc)
  in
  temp(n,1);;
\end{lstlisting}

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