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

\usepackage[beamer,utf8x]{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/robinhoodtights
}
}

\usepackage{elephantbird}


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

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

\usepackage[detect-all]{siunitx}

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

\usepackage{scalefnt}

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

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


\usepackage{algo}

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


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}{/home/moi/PREPA/IPT/2014_15/Poly/}}




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


\newcommand{\triangleup}{\Delta}













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


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

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

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

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


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

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



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

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


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

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

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

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

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

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

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

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



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












\begin{document}


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

\subtitle{Informatique pour tou(te)s - semaines 40 \& 41}

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

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

%   \end{frame}
% }




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

  \end{frame}
}





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

  \end{frame}
}


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

\beamerdefaultoverlayspecification{<+->}




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


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

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

 
 \end{frame}


% \section{Un premier jeu}

\normalsize


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

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



\section{Fonctions pures}

\begin{frame}


Départ \pause DOMAINE

\pause

Arrivée \pause CODOMAINE 

\pause

Une fonction est une relation 

\pause

C'est donc une partie \pause (sous-ensemble) \pause de DOMAINE $⊗$ CODOMAINE

\pause

...mais il n'y a pas deux couples ayant le même premier élément

\end{frame}




\begin{frame}
  Donc   la  fonction   \textit{double}  de   domaine  $\bigl\{1,2,3,...\bigr\}$
  est\pause

$$\bigl\{(1,2),(2,4),(3,6),...\bigr\}$$
\end{frame}



\begin{frame}
  La  fonction   \textit{addition}  de   domaine  $\bigl\{1,2,3,...\bigr\}⊗\bigl\{1,2,3,...\bigr\}$
  est\pause

$$\bigl\{((1,1),2),((1,2),3),...((5,7),12),((5,8),13),...\bigr\}$$
\end{frame}


\begin{frame}
  Mais bon,  ça manque un peu de dynamisme.

\end{frame}


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


\begin{frame}
   \begin{center}
    $$\text{Départ }⟶\text{Arrivée}$$
  \end{center}


\pause



\end{frame}







% \begin{frame}
  
% \begin{example}
%     Décrire une fonction qui étant donnés quatre flottants leur associe la moyenne
%   des deux  nombres parmi les  quatre qui ne  sont ni le  plus grand ni  le plus
%   petit. Par exemple, la moyenne olympique de 10, 8, 12 et 14 est 11 et celle de
%   12, 12, 12 et 12 est 12.
%   \end{example}
  
% \end{frame}



\begin{frame}
  \begin{example}
    On veut mettre une chaîne de caractères en majuscules
  \end{example}

  \begin{itemize}
  \item On commence par  créer une fonction qui met une chaîne  de longueur 1 en
    majuscule.
  \item Cela ne concerne que les lettres minuscules.
  \item On manipule les unicodes correspondant.
  \item Les lettres minuscules ont un code entre 97 et $97 + 26$
  \item La majuscule correspondant a un code diminué de $2^5$
  \item La fonction doit retourner une chaîne de longueur 1
  \end{itemize}
\end{frame}







\begin{frame}[fragile]
  \begin{pythoncode}
In [62]: ?chr
Docstring:
chr(i) -> Unicode character

Return a Unicode string of one character with ordinal i; 0 <= i <= 0x10ffff.
Type:      builtin_function_or_method    
  \end{pythoncode}
  
\pause

\begin{pythoncode}
In [63]: ?ord
Docstring:
ord(c) -> integer

Return the integer ordinal of a one-character string.
Type:      builtin_function_or_method  
\end{pythoncode}

\pause

\begin{haskellcode}
Prelude Data.Char> :t chr
chr :: Int -> Char
Prelude Data.Char> :t ord
ord :: Char -> Int  
\end{haskellcode}

\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
def car_en_maj(car) :
    ascii = ord(car)
    if 97 <= ascii <= 97 + 26 :
        return chr(ascii - 32)
    else :
        return car 
\end{pythoncode}

\pause

\begin{pythoncode}
def car_en_maj(car) :
    ascii = ord(car)
    if 97 <= ascii <= 97 + 26 :
        return chr(ascii - 32)
    return car  
\end{pythoncode}


\end{frame}




\section{Fonctions impures}



\begin{frame}[fragile]
  \frametitle{Print}
Et pourquoi pas \mintinline{python}{print}?

\pause

\mintinline{python}{ord} prend un argument de type \mintinline{python}{string}, retourne un argument de type \mintinline{python}{int} \pause ET NE FAIT QUE ÇA.


\pause

C'est une fonction PURE


\end{frame}


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

\end{frame}



\begin{frame}[fragile]
  \frametitle{Print}
  \begin{pythoncode}
In [34]: type(print(2))
2
Out[34]: NoneType

In [35]: print(print(2))
2
None

In [36]: print(print(2),print('GNU'))
2
GNU
None None    
  \end{pythoncode}

\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
In [37]: [ print(a) for a in range(5) ]
0
1
2
3
4
Out[37]: [None, None, None, None, None]  
\end{pythoncode}


\end{frame}



\begin{frame}[fragile]

\begin{pythoncode}
In [38]: b = [ print(a) for a in range(5) ]
0
1
2
3
4

In [39]: b
Out[39]: [None, None, None, None, None]  
\end{pythoncode}

\pause

\mintinline{python}{print} est IMPURE!

\end{frame}



\begin{frame}

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



\begin{frame}[fragile]
  \mintinline{python}{print} renvoie  toujours \mintinline{python}{None}  mais a
  un EFFET SECONDAIRE (\textit{side effect}) qui affiche quelque chose dans le
  monde extérieur.


\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
def plus_chaine(x) :
    global a
    return x + ' ' + a
\end{pythoncode}

  
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [102]: a = 'Dave'

In [103]: plus_chaine('Bonjour')
Out[103]: 'Bonjour Dave'

In [104]: a = 'HAL'

In [105]: plus_chaine('Bonjour')
Out[105]: 'Bonjour HAL'
\end{pythoncode}

\pause


%\begin{figure}
\begin{center}
  \includegraphics[height=.45\textheight]{HAL}
\end{center}
%\end{figure}
  


\end{frame}







\begin{frame}

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


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=.6\textheight]{go}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=.9\linewidth]{rust}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}[fragile]
Comment expliquer:

\begin{pythoncode}
In [1]: L = [1, 2, 3]

In [2]: type(L)
Out[2]: list

In [3]: L = L.append(4)

In [4]: L

In [5]: type(L)
Out[5]: NoneType  
\end{pythoncode}


\end{frame}



\begin{frame}[fragile]
Comment expliquer:

\begin{pythoncode}
In [6]: L = L.append(5)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-6-1cadcf93bdc1> in <module>()
----> 1 L = L.append(5)

AttributeError: 'NoneType' object has no attribute 'append'
\end{pythoncode}


\end{frame}








\begin{frame}[fragile]
Comment expliquer:

\begin{pythoncode}
In [7]: L = [1, 2, 3]

In [8]: L = L.pop()

In [9]: L = L + [4]
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-9-fa09307a637a> in <module>()
----> 1 L = L + [4]

TypeError: unsupported operand type(s) for +: 'int' and 'list'
\end{pythoncode}

\end{frame}




\section{lambda expressions}

\begin{frame}[fragile]
%  \frametitle{Lambda expressions}

Les fonctions sont des expressions comme les autres.
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def transforme_une_lettre(transformation, lettre) :
    return transformation(lettre)  
\end{pythoncode}

\pause

\begin{pythoncode}
In [119]: transforme_une_lettre(car_en_maj, 'g')
Out[119]: 'G'  
\end{pythoncode}

\pause

\begin{pythoncode}
def cesar(lettre) :
    return chr( ord(lettre) + 3 )  
\end{pythoncode}

\pause

\begin{pythoncode}
In [120]: transforme_une_lettre(cesar, 'g')
Out[120]: 'j'  
\end{pythoncode}

\end{frame}


\begin{frame}
\frametitle{$λ$-expressions}


%\begin{figure}
\begin{center}
  \includegraphics[height=.8\textheight]{knightsLambda}
\end{center}
%\end{figure}

  
\end{frame}


\begin{frame}[fragile]
  $$x\mapsto 2x+1$$

\pause

$$λx\cdot 2x+1$$

\pause

\begin{pythoncode}
     lambda              x          :           2*x + 1
"Une fonction qui    prend x   et retourne      2*x + 1"
\end{pythoncode}


\pause

\begin{pythoncode}
In [121]: (lambda x : 2*x + 1)(5)
Out[121]: 11  
\end{pythoncode}



\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
In [1]: transforme_une_lettre(lambda c : chr( ord(c) + 5 ), 'a')
Out[1]: 'f'  
\end{pythoncode}

  
\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
def cesar(decalage) :
    return lambda lettre : chr( ord(lettre) + decalage )  
\end{pythoncode}

\pause

\begin{pythoncode}
In [127]: cesar(3)
Out[127]: <function __main__.cesar.<locals>.<lambda>>  
\end{pythoncode}

\pause

\begin{pythoncode}
In [128]: cesar(3)('a')
Out[128]: 'd'

In [129]: cesar(5)('a')
Out[129]: 'f'  
\end{pythoncode}



  
\end{frame}


\section{Composition}


\begin{frame}[fragile]
  \frametitle{Composition de fonctions}

Défi ISI \no 1:

\shell

\begin{lstlisting}
 echo $@ | tr " " "\n" | nl | sort -nr | cut -f2- | tr "\n" " " | cat ; echo
\end{lstlisting}

\pause

\begin{lstlisting}
 echo $@ | tr " " "\n" | tac | tr "\n" " " | cat ; echo
\end{lstlisting}

\pause

\begin{lstlisting}
 $ ./defi2.sh un deux trois quatre
quatre trois deux un 
$ 
\end{lstlisting}


\end{frame}



\begin{frame}[fragile]
  Dans un vrai langage de programmation:


\begin{haskellcode}
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)  
\end{haskellcode}


\end{frame}



\begin{frame}[fragile]
  \frametitle{Défi}
Écrire une fonction qui renvoie la longueur  du mot le plus long d'une chaîne de
caractères donnée
en argument.

\begin{pythoncode}
In [1]: long_mot_plus_long("Vos beaux yeux d'amour mourir me font Belle Marquise")
Out[1]: 8
\end{pythoncode}
\end{frame}



\begin{frame}
  \begin{itemize}
  \item Il faudrait une fonction qui éclate la phrase en liste de mots 
  \item Il faudrait une fonction qui renvoie la liste des longueurs de ces mots
  \item Il faudrait une fonction qui calcule le maximum des éléments d'une liste
  \end{itemize}
\end{frame}



\begin{frame}
$$\mathtt{String}         \xrightarrow{\mathtt{eclate}}         \mathtt{[String]}
\xrightarrow{\mathtt{longueurs}} \mathtt{[Int]} \xrightarrow{\mathtt{maximum}} \mathtt{Int}$$

\pause
{\scriptsize
$$\mathtt{s} \xrightarrow{\mathtt{eclate}} \mathtt{eclate\ s}
\xrightarrow{\mathtt{longueurs}}    \mathtt{longueurs\    (eclate\    s)}
\xrightarrow{\mathtt{maximum}} \mathtt{maximum\ (longueurs\ (eclate\ s))}$$
}

\pause

$$\mathtt{String}            \xrightarrow{\mathtt{maximum}{}\           \circ{}\
  \mathtt{longueurs}{}\ \circ{}\ \mathtt{eclate}}
\mathtt{Int}$$

\pause


$$\mathtt{String}  \xrightarrow{\mathtt{eclate}{}\ \mid{}\  \mathtt{longueurs}{}\
  \mid{}\ \mathtt{maximum}}
\mathtt{Int}$$
\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
 def long_mot_plus_long(cs) :
    return maximum( longueurs( eclate( cs ) ) ) 
\end{pythoncode}

\end{frame}

\begin{frame}[fragile]


\begin{pythoncode}
In [14]: eclate("Vos beaux yeux")
Out[14]: ['Vos', 'beaux', 'yeux']  
\end{pythoncode}


\pause



\begin{pythoncode}
def eclate(chaine) :
    return chaine.split()  
\end{pythoncode}


  
\end{frame}


\begin{frame}[fragile]
 \begin{pythoncode}
In [15]: longueurs(['Vos', 'beaux', 'yeux'])
Out[15]: [3, 5, 4]   
 \end{pythoncode}
 

\pause

\begin{pythoncode}
def longueurs(xs) :
    return [ len(x) for x in xs ]
\end{pythoncode}


 
\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
def maximum(xs) :
    maxi = xs[0]
    for elmt in xs[1:] :
        if elmt > maxi :
            maxi = elmt
    return maxi  
\end{pythoncode}

  
\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
def eclate(chaine) :
    return chaine.split()

def longueurs(xs) :
    return [ len(x) for x in xs ]

def maximum(xs) :
    maxi = xs[0]
    for elmt in xs[1:] :
        if elmt > maxi :
            maxi = elmt
    return maxi

def long_mot_plus_long(cs) :
    return maximum(longueurs(eclate(cs)))  
\end{pythoncode}

  
\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
def compose2(f,g) :
    return lambda x: f(g(x))
\end{pythoncode}


\pause

\begin{pythoncode}
compose2 = lambda f,g : lambda x : f(g(x)) 
\end{pythoncode}

\pause

\begin{pythoncode}
In [28]: compose2(longueurs,eclate)("un deux trois")
Out[28]: [2, 4, 5]  
\end{pythoncode}

\pause

\begin{pythoncode}
long_mot_plus_long = compose2( maximum, compose2(longueurs, eclate) )
\end{pythoncode}




\end{frame}



\section{Récursion}


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

  \multido{\i=0+1}{7}{%
    \begin{frame}
      \begin{center}
        \includegraphics[height=0.9\textheight]{hasselhoff-\i}
      \end{center}
    \end{frame}
  }

\multido{\i=0+1}{7}{%
    \begin{frame}
      \begin{center}
        \includegraphics[height=0.9\textheight]{hasselhoff-\i}
      \end{center}
    \end{frame}
  }

\multido{\i=0+1}{7}{%
    \begin{frame}
      \begin{center}
        \includegraphics[height=0.9\textheight]{hasselhoff-\i}
      \end{center}
    \end{frame}
  }

\multido{\i=0+1}{7}{%
    \begin{frame}
      \begin{center}
        \includegraphics[height=0.9\textheight]{hasselhoff-\i}
      \end{center}
    \end{frame}
  }

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




\begin{frame}
  \frametitle{Le retour de Max}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{madmax}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def max2(a,b) :
    return a if a >= b else b  
\end{pythoncode}

\pause

\begin{pythoncode}
def maxi(xs) :
    assert xs != [], "Liste vide !"
    if len(xs) == 1 :
        return xs[0]
    return max2( xs[0], maxi(xs[1:]) ) 
\end{pythoncode}



\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [54]: maxi("agfdjuol")
maxi <- ('agfdjuol',)
 maxi <- ('gfdjuol',)
  maxi <- ('fdjuol',)
   maxi <- ('djuol',)
    maxi <- ('juol',)
     maxi <- ('uol',)
      maxi <- ('ol',)
       maxi <- ('l',)
       maxi -> l
      maxi -> o
     maxi -> u
    maxi -> u
   maxi -> u
  maxi -> u
 maxi -> u
maxi -> u
Out[54]: 'u'  
\end{pythoncode}

              
\end{frame}




\begin{frame}
$$a^n=\underbrace{a×a×\cdots×a}_{n\text{ facteurs } a}$$

\pause

$$\cdots\ \ \ ???$$

\pause

$$a^0 = 1,\quad \pause a^n=a×a^{n-1}$$ 
\end{frame}





\begin{frame}[fragile]
\begin{pythoncode}
def pow1(a, n) :
    assert n >= 0, "L'exposant doit être entier naturel"
    if n == 0 :
        return 1
    else :
        return a * pow1(a, n - 1)  
\end{pythoncode}


  
\end{frame}


\begin{frame}[fragile]
\verb+pow1(2, 3)+

\pause

\verb+2 * pow1(2, 2)+

\pause

\verb+2 * (2 * pow1(2, 1))+

\pause

\verb+2 * (2 * (2 * pow1(2 , 0)))+

\pause

\verb+2* (2 * (2 * 1))+

\pause

\verb+2 * (2 * 2)+

\pause

\verb+2 * 4+

\pause

\verb+8+

\pause

\vfill

Expansion \pause Réduction

              
\end{frame}


\begin{frame}[fragile]
 \begin{pythoncode}
 def pow2(a, n) :
    assert n >= 0, "L'exposant doit être entier naturel"
    def accumule(k, acc) :
        if k == 0 :
            return acc
        else :
            return accumule(k - 1, a*acc)
    return accumule(n, 1)  
 \end{pythoncode}
 
 
\end{frame}

\begin{frame}[fragile]
\verb+pow2(2, 3)+

\pause

\verb+accumule(3, 1)+

\pause

\verb+accumule(2, 2)+

\pause

\verb+accumule(1,4)+

\pause

\verb+accumule(0,8)+

\pause

\verb+8+

              
\end{frame}



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

\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [24]: pow1(2,3)
pow1 <- (2, 3)
 pow1 <- (2, 2)
  pow1 <- (2, 1)
   pow1 <- (2, 0)
   pow1 -> 1
  pow1 -> 2
 pow1 -> 4
pow1 -> 8
Out[24]: 8  
\end{pythoncode}

              
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [27]: pow2(2,3)
pow2 <- (2, 3)
accumule <- (3, 1)
 accumule <- (2, 2)
  accumule <- (1, 4)
   accumule <- (0, 8)
   accumule -> 8
  accumule -> 8
 accumule -> 8
accumule -> 8
pow2 -> 8
Out[27]: 8  
\end{pythoncode}


\end{frame}

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

\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def pow3(a, n) :
    assert n >= 0, "L'exposant doit être entier naturel"
    accu = 1
    k = 0
    while k < n :
        accu *= a
        k += 1
    return accu  
\end{pythoncode}


\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def pow4(a, n) :
    assert n >= 0, "L'exposant doit être un entier naturel"
    accu = 1
    for k in range(n) :
        accu = a*accu
    return accu  
\end{pythoncode}


\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
from functools import reduce

def pow5(a, n):
    return reduce(lambda accu, k : a*accu, range(n), 1)
\end{pythoncode}  
\end{frame}


\begin{frame}


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

  
\end{frame}



\begin{frame}
  \frametitle{Le secret de la réduction}

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


\begin{frame}[fragile]
\frametitle{Le secret de la réduction}

$$f(f(f(\cdots f(f(accu0, x_0),x_1)\cdots),x_{n-1}),x_n)$$

\pause

\begin{pythoncode}
def reduit(f, xs, accu0) :
    accu = accu0
    for x in xs :
        accu = f(accu, x)
    return accu    
\end{pythoncode}

\pause

\begin{pythoncode}
reduce(f, xs, accu0) 
\end{pythoncode}



              
\end{frame}



\begin{frame}
  \frametitle{Le retour de Max}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.8\linewidth]{madmax2}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}[fragile]


\begin{pythoncode}
maxi = lambda xs: reduce(lambda max_tmp, x: x if x > max_tmp else max_tmp, xs) 
\end{pythoncode}

\pause

\begin{pythoncode}
max2 = lambda a, b: a if a >= b else b

maxi = lambda xs: reduce(max2, xs) 
\end{pythoncode}


\pause


\begin{pythoncode}
def max2(a,b) :
    return a if a >= b else b

def maxi(xs) :
    return reduce(max2, xs)
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
In [23]: maxi([1,12,5,47,86,9,4])
Out[23]: 86

In [24]: maxi([])
TypeError: reduce() of empty sequence with no initial value
\end{pythoncode}



              
\end{frame}





\begin{frame}[fragile]
  \begin{block}{Défi}
    Construisez une fonction prend une liste d'entiers et renvoie le produit des
    carrés des nombres pairs de cette liste.
    Une réponse en une petite ligne serait appréciée...
  \end{block}

\pause

\begin{block}{Défi}
Construisez  une  fonction  compose  qui  renvoie la  composée  d'une  suite  de
fonctions:

\begin{pythoncode}
In [35]: compose(maximum,longueurs,eclate)("Trois deux un")
Out[35]: 5  
\end{pythoncode}


\end{block}




\end{frame}



\begin{frame}[fragile]

\begin{pythoncode}
In [29]: %timeit pow5(17,100)
100000 loops, best of 3: 12.3 µs per loop

In [30]: %timeit pow4(17,100)
100000 loops, best of 3: 6.67 µs per loop

In [31]: %timeit pow3(17,100)
100000 loops, best of 3: 9.24 µs per loop

In [32]: %timeit pow2(17,100)
10000 loops, best of 3: 18.6 µs per loop

In [33]: %timeit pow1(17,100)
10000 loops, best of 3: 17.8 µs per loop  
\end{pythoncode}


  
\end{frame}

\begin{frame}[fragile]

\begin{pythoncode}
def pow6(a, n):
    if n == 0 :
        return 1
    if n == 1 :
        return a
    if n % 2 == 0 :
        return pow6(a*a, n//2)
    return a * pow6(a, n-1) 
\end{pythoncode}

\pause

\begin{pythoncode}
In [42]: %timeit pow6(17,100)
100000 loops, best of 3: 2.35 µs per loop  
\end{pythoncode}


  
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [45]: pow6(2,10)
pow6 <- (2, 10)
 pow6 <- (4, 5)
  pow6 <- (4, 4)
   pow6 <- (16, 2)
    pow6 <- (256, 1)
    pow6 -> 256
   pow6 -> 256
  pow6 -> 256
 pow6 -> 1024
pow6 -> 1024
Out[45]: 1024
\end{pythoncode}

              
\end{frame}


\begin{frame}
  \begin{block}{Défi}
 Dérécursifiez la fonction \mintinline{python}{pow6} 

  \end{block}
\end{frame}




\begin{frame}

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








\begin{frame}[fragile]
\frametitle{OCaml}
 \begin{ocamlcode}
let rec pow a = function
    | 1 -> 1
    | n -> a * (pow a (n - 1)) ;; 
 \end{ocamlcode}

 \begin{ocamlcode}
let powt a n = 
   let rec pow_iter acc k =
       if k == 0 then acc
       else pow_iter (a*acc) (k-1)
   in pow_iter 1 n ;; 
 \end{ocamlcode}
 
 
\end{frame}


\begin{frame}[fragile]
  
  \begin{ocamlcode}
# pow 17 100_000;;
Stack overflow during evaluation (looping recursion?).

# powt 17 100_000;;
- : int = -573761023    
  \end{ocamlcode}

\end{frame}





\section{Raisonnement par récurrence}


\begin{frame}
Pour prouver qu'une  propriété $\PR_n$  dépendant uniquement
d'un paramètre $n$ est vraie pour tout $n \geqslant n_0$, il faut
vérifier que:

\begin{itemize}
\item $\PR_{n_0}$ est vraie (on parle parfois d'initialisation);
\item  pour tout  $n \geqslant  n_0$, $\PR_n  \limp \PR_{n+1}$
  (on parle parfois d'hérédité).
\end{itemize}
\end{frame}




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

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



\begin{frame}
  \begin{block}{Défi}
Déterminez le nombre de mouvements effectués pour déplacer $n$ disques des Tours
de Hanoï.
  \end{block}

\pause

  \begin{block}{Défi}
Créez  une fonction  qui  affiche  les mouvements  effectués  pour déplacer  $n$
disques des Tours 
de Hanoï.
  \end{block}

\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [52]: hanoi(3)
On déplace le disque de la tige 1 vers la tige 3
On déplace le disque de la tige 1 vers la tige 2
On déplace le disque de la tige 3 vers la tige 2
On déplace le disque de la tige 1 vers la tige 3
On déplace le disque de la tige 2 vers la tige 1
On déplace le disque de la tige 2 vers la tige 3
On déplace le disque de la tige 1 vers la tige 3
\end{pythoncode}

  
\end{frame}

















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