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

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



\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph,tkz-berge}
\usepackage{circuitikz}
\usepackage{tikz-qtree}

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


\usepackage{media9}

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




\usepackage{algo}

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

\newcommand\nor{\downarrow}
\newcommand\nand{\uparrow}
\newcommand\xor{\oplus}

\newcommand\foncpart{\rightarrow\!\!\!\!\!\!\shortmid}
\newcommand\fonctot{\rightarrow}
\newcommand\injpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid}
\newcommand\injtot{\rightarrowtail}
\newcommand\surjpart{\twoheadrightarrow\!\!\!\!\!\!\!\shortmid}
\newcommand\surjtot{\twoheadrightarrow}
\newcommand\bijpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid\!\!\!\!\twoheadrightarrow}
\newcommand\bijtot{\rightarrowtail\!\!\!\!\!\!\!\!\!\twoheadrightarrow}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}

\graphicspath{{/home/moi/IUT/PolyINFO1}{/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/}}




\renewcommand\caml{\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\small\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\small\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\prolog{\lstset{numbers=none,language=prolog,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}{1} %\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}

\newcommand{\triangleup}{\Delta}













%%%%%%%%%%%%%%
%%% H A N O I
%%%%%%%%%%%% 
%\usepackage{scalefnt}
\usetikzlibrary{shadows,patterns,shapes}

\newcount\ndisques
\def\inittiges#1{
    \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{
    \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
\def\rhanoi#1#2#3#4{
    \ifnum#4>1
        {\advance#4 by -1 \rhanoi#1#3#2#4}
        \move{#1}{#3}
        {\advance#4 by -1 \rhanoi#2#1#3#4}
    \else
        \move{#1}{#3}
    \fi
}

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

% Define some colors, I don't like plain green and brown.
\definecolor{darkgreen}{rgb}{0.2,0.55,0}
\definecolor{darkbrown}{rgb}{0.375,0.25,0.125}

\newcommand{\tige}{
  \fill[darkbrown] (-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{Tour de Hanoi -- \the\ndisques\ Disque}
    \else
        \xdef\ftitle{Tour de Hanoi -- \the\ndisques\ Disques}
    \fi
    \gdef\fmsg{}
    % Starting frame.
    \drawtiges
    % Recursion draws a new frame for every step.
    \rhanoi{1}{2}{3}{\ndisques}
    % Final frame.
    \gdef\fmsg{\node[] at (3.8,2.5) {\Huge\scalefont{2}\color{darkgreen}OK};}
    \drawtiges
}









\begin{document}


\title[] % (optional, use only with long paper titles)
{Les ensembles en informatique}

\subtitle{INFO1 - Semaine 38}

\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{} à \now}
% - 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}
  \titlepage
\end{frame}

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

 
 \end{frame}


 \lstset{
    language=haskell,
    flexiblecolumns=false,
    escapeinside={(*@}{@*)},
    % numbers=left,
    basicstyle={\small\ttfamily},
    commentstyle={\small\itshape\color{pink!50!white}},
    keywordstyle={\ttfamily\bfseries\fontfamily{ul9}\selectfont\color{blue!50!white}},
    stringstyle={\small\ttfamily\color{gray!80!white}\itshape},
    breaklines=true,
    breakatwhitespace=true,
    showtabs=False,
    showspaces=False,
    showstringspaces=False,
    extendedchars=true,
    % aboveskip=1em,
    % belowskip=1em,
    rulecolor=\color{gray},
    % rulesepcolor=\color{gray},
    % frame=trBL,
    frame=single,
    frameround=tttt,
    framerule=0.3pt,
    framesep=4pt,
    belowcaptionskip=2.1pt,
    autogobble,
%    morecomment=[n][\bfseries\color{gray}]{λ>}{\ } ,
    title={{\setlength{\fboxsep}{1pt}\fcolorbox{blue}{gray!80}{\sffamily\scriptsize
          \textcolor{gray!10}{\ }Haskell \textcolor{gray!10}{\ }}}},
        literate= {*}{{$*$}}1 
         {\\ \ }{{$\lambda{} $}}1
        {\\\\}{{\char`\\\char`\\}}1
        {\ ->\ }{{$\rightarrow{}$}}2 {\ >=\ }{{${}\geq{}$}}2 {\ <-\ }{{${}\leftarrow{}$}}2
        {\ <=\ }{{${}\leq{}$}}2 {\ =>\ }{{${}\Rightarrow{}$}}2 
        % {\ .}{{$\circ$}}2 {\ .\ }{{$\circ$}}2
        {>>\ }{{>>}}2 {>>=\ }{{>>=}}2
        {|}{{$\mid$}}1
        {à}{{\`a}}1 {â}{{\^a}}1 %                         lettre a
        {À}{{\`A}}1 {Â}{{\^A}}1 %                         lettre A
        {ç}{{\c{c}}}1 %                                   lettre c
        {Ç}{{\c{C}}}1 %                                   lettre C
        {é}{{\'e}}1 {è}{{\`e}}1 {ê}{{\^e}}1 {ë}{{\"e}}1 % lettre e
        {É}{{\'E}}1 {È}{{\`E}}1 {Ê}{{\^E}}1 {Ë}{{\"E}}1 % lettre E
        {î}{{\^i}}1 {ï}{{\"i}}1 %                         lettre i
        {Î}{{\^I}}1 {Ï}{{\"I}}1 %                         lettre I
        {ô}{{\^o}}1 %                                     lettre o
        {Ô}{{\^O}}1 %                                     lettre O
        {œ}{{\oe}}1 %                                     lettre oe
        {Œ}{{\OE}}1 %                                     lettre OE
        {ù}{{\`u}}1 {û}{{\^u}}1 {ü}{{\"u}}1 %             lettre u
        {Ù}{{\`U}}1 {Û}{{\^U}}1 {Ü}{{\"U}}1 % lettre U
        {μ}{{$\mu $}}1
        {λ}{{$\lambda $}}1
        {°}{{\textdegree{}}}1
        {á}{{\'a}}1
        {ú}{{\'u}}1
}

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

 \end{frame}

 \begin{frame}

 {\itshape ...autrefois,  on  a pu  croire  que  chaque branche  des  mathématiques
  dépendait d'intuitions  particulières [...] ce  qui eût entraîné  pour chacune
  la  nécessité d'un  langage formalisé  qui lui  appartînt en  propre. On  sait
  aujourd'hui qu'il est possible, logiquement  parlant, de faire dériver presque
  toute   la  mathématique   d'une   source  unique,   la  \textbf{Théorie   des
    Ensembles}.}

 \end{frame}



\section{L'informaticien(ne) sur le terrain}

{\small
\begin{frame}
%\begin{figure}


\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=5cm,semithick]
\tikzstyle{every state}=[rectangle,rounded corners,fill=white,draw=black,text=black]
%\tikzstyle{accepting}=[fill=blue!30!20,draw=black,text=blue!30,accepting by arrow,double]
%\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial text=]
 

 \node[state] (A) {une personne};
 \node[state] (B) [ right of=A] {un homme};
 \node[state,node distance=2cm,] (C) [ below of=B] {une ville};
 
 \path (A) edge node[blue!30] {\small \textit{a un père}} (B)
       (B) edge node[blue!30] {\small \textit{vit dans}} (C)
       (A) edge node[blue!30] [pos=0.5, sloped, below]{\small \textit{vit dans}} (C);
\end{tikzpicture}
%\caption{Schéma 1}
%\label{Fig1}
%\end{figure}

\pause

%\begin{figure}
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=6cm,semithick]
\tikzstyle{every state}=[rectangle,rounded corners,fill=white,draw=black,text=black]
%\tikzstyle{accepting}=[fill=blue!30!20,draw=black,text=blue!30,accepting by arrow,double]
%\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial text=]
 

 \node[state] (A) {une personne};
 \node[state] (B) [ right of=A] {un couple $(f,h)$};
 \node[state,node distance=2cm,] (C) [ below of=B] {une femme};
 
 \path (A) edge node [blue!30,anchor=south, above] {\small \textit{a pour parents }} 
                node [blue!30,anchor = north, below] {\small \textit{biologiques}} (B)
       (B) edge node[blue!30,text width = 2.5cm] {\small \textit{a pour 1\ere\\ composante}} (C)
       (A) edge  node [blue!30,pos=0.5, sloped, below]{\small \textit{a  pour mère biologique}}(C);
%\node [below=0.5cm, align=flush center,text width=8cm] at (C) {Schéma 2};
\end{tikzpicture}
%\caption{Schéma 2}
%\label{Fig2}
%\end{figure}

\pause
%\end{frame}

%\begin{frame}

%\begin{figure}
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=6cm,semithick]
\tikzstyle{every state}=[rectangle,rounded corners,fill=white,draw=black,text=black]
%\tikzstyle{accepting}=[fill=blue!30!20,draw=black,text=blue!30,accepting by arrow,double]
%\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial text=]
 

 \node[state] (A) {une personne};
 \node[state] (B) [ right of=A] {une personne};
 %\node[state,node distance=2cm,] (C) [ below of=B] {une femme};
 
 \path (A) edge node [blue!30,anchor=south, above] {\small \textit{a pour enfant }}  (B);
\end{tikzpicture}
%\caption{Schéma 3}
%\label{Fig3}
%\end{figure}


\end{frame}
}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \begin{figure}
  \includegraphics[height=5cm]{Cantor}
\caption{Georg \textsc{Cantor} \\(1845 - 1918)}
\end{figure}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}[fragile]

\begin{lstlisting}
λ> :t 'a'
'a' :: Char
\end{lstlisting}

\pause

\begin{lstlisting}
λ> :t 2 + 2 == 4
2 + 2 == 4 :: Bool
\end{lstlisting}


\pause


\begin{lstlisting}
λ> :t 3
3 :: Num a => a
\end{lstlisting}


\end{frame}


\begin{frame} \frametitle{Environnement de travail}
  On considère un  \og tout\fg{} contenant des  \og objets\fg{}
distincts. On peut vérifier si certains  de ces \og objets\fg{} vérifient ou non
une \og propriété\fg{}.


\pause

$$G = \bigl\{\text{ étudiant} \mid \text{ (étudiant est en INFO1) ET (étudiant est un garçon)}\bigr\}$$

\pause

\begin{itemize}
\item \og Robert appartient à G\fg{}
\item  \og Robert  est un
élément de G\fg{}
\item \og G contient Robert\fg{}
\item \og Robert $\in G$\fg{}
\item \og $G \owns$ Robert\fg{}
\end{itemize}



\end{frame}

\begin{frame}[fragile]
 Entiers naturels pairs ?

\pause


\begin{lstlisting}
naturels = [0..]
pairs = [n | n <- naturels, mod n 2 == 0]
petits_pairs = [n | n <- [0..15], mod n 2 == 0]
petits_pairs_bis = [2*k | k <- [0..7]]
\end{lstlisting}

\pause


\begin{lstlisting}
λ> petits_pairs
[0,2,4,6,8,10,12,14]
\end{lstlisting}


\end{frame}


\begin{frame}
  \begin{itemize}
  \item $2\in\mathtt{pairs}$
\item $2\in \bigl\{x | (x\in\bbn) \land
P(x)\bigr\}$
\item $2\in \bigl\{t | (t\in\bbn) \land P(t)\bigr\}$
\item $P(2)$
\item $2\in \bigl\{x| x\text{ est un entier naturel et } x \text{ est pair}
\bigr\}$
\item $3\not\in\mathtt{pairs}$
\item $3\in \bigl\{x | (x\in\bbn) \land \lnot P(x)\bigr\}$
\item $3\not\in \bigl\{t | (t\in\bbn) \land P(t)\bigr\}$ 
\item  $\lnot P(3)$
  \end{itemize}
\end{frame}



\begin{frame}
  \begin{example}
    Un nombre $x$ \og vérifie R\fg{} si, et seulement si, son carré vaut 2.
  \end{example}

\pause

$$\forall x(x\in \bbn \wedge \lnot R(x))$$

\pause

\textit{für \textbf{A}lle}: 1934 par Gerhard \textsc{Gentzel}





\end{frame}





\begin{frame}

  \begin{example}
    Un nombre $x$ \og vérifie S\fg{} si, et seulement si,
son carré vaut 4.
  \end{example}

$$\exists x(x\in \bbn \wedge S(x))$$

\pause

\textit{\textbf{E}siste almeno uno}: 1897 Giuseppe
\textsc{Peano}

\pause

$$\exists ! x(x\in\bbn \wedge S(x))$$

\end{frame}




\begin{frame}
\begin{theorem}
\begin{itemize}
 \item  $\forall x(x\in E \limp P(x)) \equiv E = \bigl\{x\in E\mid P(x)\bigr\}$

\item   $\exists x(x\in E \limp P(x)) \equiv \bigl\{x\in E\mid P(x)\bigr\}\neq \emptyset$


\item  $\lnot\left(\forall x(x\in  E \limp  P(x))\right) \equiv\exists  x(x\in E
  \limp \lnot P(x)) $

\item  $\lnot\left(\exists x(x\in  E \limp  P(x))\right) \equiv\forall  x(x\in E
  \limp \lnot P(x)) $

\end{itemize}
\end{theorem}
\end{frame}










\begin{frame}[fragile]

\begin{lstlisting}
s :: (Num a, Eq a) => a -> Bool
s =                  \x -> x^2 == 4
\end{lstlisting}

\pause

\begin{lstlisting}
λ> s 2
True
λ> s 2.0
True
λ> s 3
False
λ> any s [0..]
True
λ> find s [0..]
Just 2
λ> filter s [0..100]
[2]
\end{lstlisting}


\end{frame}


\begin{frame}
  \begin{exercice}
    Dans une ville, il  n'y a qu'un barbier qui rase tous ceux  qui ne se rasent pas
eux-mêmes et uniquement ceux-ci: qui rase le barbier?...
  \end{exercice}
\end{frame}




\section{Types numériques}


\begin{frame}[fragile]\frametitle{Integer}
  
\begin{lstlisting}
λ> 2^1000
107150860718626732094842504906000181056140481170553360744375038837035105112493612249319
837881569585812759467291755314682518714528569231404359845775746985748039345677748242309
854210746050623711418779541821530464749835819412673987675591655439460770629145711964776
86542167660429831652624386837205668069376
\end{lstlisting}



\end{frame}

\begin{frame}[fragile]\frametitle{Int}


\begin{lstlisting}
λ> let n = 2^63 - 1 :: Int
λ> n
9223372036854775807
\end{lstlisting}

\pause


\begin{lstlisting}
λ> n * 2
-2
\end{lstlisting}


  
\end{frame}

\begin{frame}[fragile]


\begin{lstlisting}
λ> maxBound :: Int
9223372036854775807
λ> minBound :: Int
-9223372036854775808
\end{lstlisting}

  
\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
λ> [minBound :: Int8 ..]
[-128,-127,-126,-125,-124,-123,-122,-121,-120,-119,-118,-117,-116,-115,-114,-113,-112,
-111,-110,-109,-108,-107,-106,-105,-104,-103,-102,-101,-100,-99,-98,-97,-96,-95,-94,
-93,-92,-91,-90,-89,-88,-87,-86,-85,-84,-83,-82,-81,-80,-79,-78,-77,-76,-75,-74,-73,
-72,-71,-70,-69,-68,-67,-66,-65,-64,-63,-62,-61,-60,-59,-58,-57,-56,-55,-54,-53,-52,
-51,-50,-49,-48,-47,-46,-45,-44,-43,-42,-41,-40,-39,-38,-37,-36,-35,-34,-33,-32,-31,
-30,-29,-28,-27,-26,-25,-24,-23,-22,-21,-20,-19,-18,-17,-16,-15,-14,-13,-12,-11,-10,
-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,
52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,
81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,
107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,
126,127]
\end{lstlisting}


  
\end{frame}




\begin{frame}[fragile]
  \frametitle{Les booléens}
  
\begin{lstlisting}
λ> True && False
False
λ> False && False
False
λ> False || True
True
λ> not False
True
λ> 2 + 2 > 5
False
λ> 2 + 2 /= 5
True
λ> "Iut" == "Enfer"
False
λ> "Haskell" > "C"
True
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Char}
  
 
\begin{lstlisting}
λ> minBound :: Char
'\NUL'
λ> maxBound :: Char
'\1114111'
λ> take 130 [ minBound :: Char .. ]
"\NUL\SOH\STX\ETX\EOT\ENQ\ACK\a\b\t\n\v\f\r\SO\SI\DLE\DC1\DC2\DC3\DC4\NAK\SYN\ETB\CAN
\EM\SUB\ESC\FS\GS\RS\US !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\
\]^_`abcdefghijklmnopqrstuvwxyz{|}~\DEL\128\129"
\end{lstlisting}
 

\end{frame}








\section{Parties d'un ensemble}



\subsection{Notion d'égalité}


\begin{frame}[fragile]

\begin{definition}[Axiome d'extensionalité]
Deux ensembles  A et B sont  égaux si, et seulement  si, ils contiennent
les mêmes éléments. On écrit alors $A= B$.
\end{definition}

\pause


\begin{exercice}
   On note $E=\bigl\{x\mid x\in\bbz \wedge x^2=1\bigr\}$ et
  $F=\bigl\{x\mid x \in\bbr \wedge\left\lfloor x\right\rfloor=1\bigr\}$. 

Que pouvez-vous dire de $E$ par rapport à $F$? 
\end{exercice}

\pause


\begin{lstlisting}
λ> [1,2,3] == [1,3,2]
False
λ> 3 * 0.1 == 0.3
False
λ> 2 * 0.1 == 0.2
True
\end{lstlisting}




\end{frame}



\subsection{Inclusion}

\begin{frame}
  
\begin{definition}[inclusion]
  L'ensemble  $X$ est  inclus dans  l'ensemble  $Y$ si,  et seulement  si, tous  les
  éléments de $X$ sont des éléments de $Y$.
Cela se note 
$$(X \subseteq Y) \lequiv ((z \in X) \limp (z\in Y))$$

\end{definition}


\pause

On  dira  indifféremment  \og  \textit{$X$   est  contenu  dans  $Y$}\fg{},  \og
\textit{$Y$  contient  $X$}\fg{},  \og   \textit{$X$  est  un  sous-ensemble  de
  $Y$}\fg{}, \og \textit{$X$ est une partie de $Y$}\fg{}.

\pause



\begin{theorem}
Tout ensemble $E$ contient l'ensemble vide.
\end{theorem}

\pause

Démonstration?...

\pause

$$(\emptyset \subseteq E) \lequiv ((z \in \emptyset) \limp (z\in E)) \ ?...$$


\end{frame}






\begin{frame}
  \begin{alertblock}{DANGER!}
    Il faudra bien distinguer $\subset$, $\subseteq$ $\varsubsetneq$ et $\nsubseteq$.
  \end{alertblock}
\end{frame}


\begin{frame}[fragile]


\begin{theorem}[Axiome d'extensionalité version II]

$$(\forall X)(\forall Y)(((X \subseteq Y) \land (Y \subseteq X)) \limp (X=Y))$$
  
\end{theorem}


\pause

\begin{lstlisting}
est_inclus :: (Eq a) => Ens a -> Ens a -> Bool
est_inclus ens1 ens2 = pour_tout (contient ens2) ens1
\end{lstlisting}

\pause

\begin{lstlisting}
instance (Eq a) => Eq (Ens a) where
  ens1 == ens2 = (est_inclus ens1 ens2) && (est_inclus ens2 ens1)
\end{lstlisting}




\end{frame}





\subsection{Ensemble des parties d'un ensemble}



\begin{frame}
\begin{exercice}
  Montrez que $$\bigl\{a\bigr\}=\bigl\{b\bigr\}\lequiv a = b$$

puis  que $\emptyset  \neq \bigl\{\emptyset\bigr\}$  et $\bigl\{\emptyset\bigr\}
\neq \bigl\{\{\emptyset\}\bigr\}$.
\end{exercice}


\pause


\begin{theorem}
  Nous admettrons que si $E$ désigne un ensemble alors \textbf{l'ensemble
des parties de} $E$ est un ensemble  noté $\ P{}\left( E\right) $ 
$$
\ P{}\left( E\right) =\Bigl\{ X\mid X\subseteq E\Bigr\}
$$
\end{theorem}


\pause


\begin{exercice}
   Cet ensemble admet toujours au moins deux éléments: lesquels?
\end{exercice}

\end{frame}

\begin{frame}[fragile]
  \begin{example}
    $E=\Bigl\{ D,L,M\Bigr\} $
  \end{example}

\pause


\begin{lstlisting}
λ> let e1 = lit ['D','L','M']
λ> ens_parties e1
{ { } { 'M' } { 'L' } { 'L' 'M' } { 'D' } { 'D' 'M' } { 'D' 'L' } { 'D' 'L' 'M' } }
\end{lstlisting}

\pause

\begin{exercice}
  Que dire alors de $\ P{}\left( \ P{}\left( E\right) \right) $ ?
\end{exercice}


\end{frame}




\subsection{Construction récursive}


\begin{frame}[fragile]
  
\begin{lstlisting}
ens_parties ::  Eq a => Ens a -> Ens (Ens a)
ens_parties Vide = Ens (Vide,Vide)
ens_parties (Ens (t,q)) = union pq (applique (insere t) pq)
  where pq = ens_parties q
\end{lstlisting}
\end{frame}


\section{Algèbre des ensembles}




\subsection{Intersection}

\begin{frame}
\begin{definition}
L'\textbf{intersection} des ensembles $A$ et $B$ est l'ensemble $A\cap B$
constitué des éléments communs à $A$ et $B$.

$$
A\cap B=\Bigl\{ x\mid (x\in A)\land (x\in B)\Bigr\}
$$
\end{definition}
\pause

C'est une partie de $E$. De plus $(x\in A\cap B)\lequiv  ( x\in A\land x\in B)$.
\pause


% Definition of circles
\newcommand\A{(0,0) ellipse (0.75cm and 1.25cm)}
\newcommand\B{(0:1.375cm) ellipse (1.25cm and 0.75cm)}
\newcommand\Cc{(0.75cm,0.75cm) circle (0.75cm)}
\newcommand\Uni{(-1.5,-1.5) rectangle (3,1.5)}

\colorlet{circle edge}{pink!}
\colorlet{circle area}{pink!70}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}

% Set A and B
\begin{center}
\begin{tikzpicture}
    \begin{scope}
        \clip \A;
        \fill[filled] \B;
    \end{scope}
     \draw \Uni ;
    \draw[outline] \A node [above left] {$A$};
    \draw[outline] \B node [below right] {$B$};
 \node[anchor=north] at (current bounding box.south) {\textcolor{pink!50!red}{$A \cap B$}};
\end{tikzpicture}
\end{center}


\end{frame}

\begin{frame}

\begin{exercice}
Démontrez que  $(A\cap B=B)\lequiv (B\subseteq A)$.
\end{exercice}



\end{frame}




\subsection{Union}


\begin{frame}
\begin{definition}
L'\textbf{union} ou la \textbf{r\'{e}union }des ensembles $A$ et $B$ est
l'ensemble:%
$$
A\cup B=\Bigl\{ x\mid (x\in A)\lor (x\in B)\Bigr\}
$$
\end{definition}



\pause

C'est une partie de $E$. De plus $(x\in A\cup B)\lequiv ( x\in A\lor x\in B)$.

\pause

\og ou non exclusif\fg{} 

\pause

\newcommand\A{(0,0) ellipse (0.75cm and 1.25cm)}
\newcommand\B{(0:1.375cm) ellipse (1.25cm and 0.75cm)}
\newcommand\Cc{(0.75cm,0.75cm) circle (0.75cm)}
\newcommand\Uni{(-1.5,-1.5) rectangle (3,1.5)}

\colorlet{circle edge}{pink!}
\colorlet{circle area}{pink!70}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}
\begin{center}
\begin{tikzpicture}
  \draw \Uni ;
    \draw[filled] \A node[left] {$A$}
                  \B node [right] {$B$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{pink!50!red}{$A \cup B$}};
\end{tikzpicture}
\end{center}



\end{frame}



\begin{frame}
  \begin{exercice}
    Démontrez que  $(A\cup B=A)\lequiv (B\subseteq A)$.
  \end{exercice}
\end{frame}




\subsection{Différence}


\begin{frame}
  
\begin{definition}
La \textbf{diff\'{e}rence} des ensembles $A$ et $B$ est l'ensemble%
$$
A\setminus B=\Bigl\{ x\mid (x\in A)\land (x\notin B)\Bigr\}
$$
\end{definition}


\pause



\begin{center}




\newcommand\A{(0,0) ellipse (0.75cm and 1.25cm)}
\newcommand\B{(0:1.375cm) ellipse (1.25cm and 0.75cm)}
\newcommand\Cc{(0.75cm,0.75cm) circle (0.75cm)}
\newcommand\Uni{(-1.5,-1.5) rectangle (3,1.5)}

\colorlet{circle edge}{pink!}
\colorlet{circle area}{pink!70}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}

\begin{tikzpicture}
    \begin{scope}
        \clip \A;
        \draw[filled, even odd rule] \A node [left]{$A$}
                                     \B;
    \end{scope}
\draw \Uni;
  \draw[outline] \A
                   \B node [right] {$B$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{pink!50!red}{$A \setminus B$}};
\end{tikzpicture}
\end{center}


\end{frame}



\subsection{Différence symétrique}




\begin{frame}
  
\begin{definition}
La \textbf{diff\'{e}rence sym\'{e}trique} des ensembles $A$ et $B$ est
l'ensemble:%

\begin{eqnarray*}
A\triangleup B &=&\Bigl\{ x\mid (x\in A\setminus B)\lor (x\in
B\setminus A)\Bigr\}
=\left( A\setminus B\right) \cup \left( B\setminus A\right) \\
A\triangleup B &=&\Bigl\{ x\mid (x\in A\cup B)\land (x\notin A\cap
B)\Bigr\} =\left( A\cup B\right) \setminus \left( A\cap B\right)
\end{eqnarray*}
\end{definition}

\pause


\begin{center}

\newcommand\A{(0,0) ellipse (0.75cm and 1.25cm)}
\newcommand\B{(0:1.375cm) ellipse (1.25cm and 0.75cm)}
\newcommand\Cc{(0.75cm,0.75cm) circle (0.75cm)}
\newcommand\Uni{(-1.5,-1.5) rectangle (3,1.5)}

\colorlet{circle edge}{pink!}
\colorlet{circle area}{pink!70}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}

  \begin{tikzpicture}
\draw \Uni;
    \draw[filled, even odd rule] \A [left] node {$A$}
                                 \B [right] node{$B$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{pink!50!red}{$A \triangleup B$}};
\end{tikzpicture}
\end{center}

\end{frame}

\begin{frame}
\begin{alertblock}{Remarque}
  La différence symétrique correspond au \og ou exclusif\fg{}: fromage ou dessert...
\end{alertblock}



\end{frame}


\subsection{Complémentaire}



\begin{frame}
  

\begin{definition}
$A$ désignant une partie de $E,$ le \textbf{complémentaire} de $A$
par rapport \`{a} $E$ ou le complémentaire de $A$ dans $E$ est
l'ensemble noté $\complement_{E}A$ défini par 
$$
\complement_{E}A=E\setminus A=\Bigl\{ x\mid (x\in E)\land (x\notin A)\Bigr\}
$$
\end{definition}


\pause


\begin{center}

\newcommand\A{(0,0) ellipse (0.75cm and 1.25cm)}
\newcommand\B{(0:1.375cm) ellipse (1.25cm and 0.75cm)}
\newcommand\Cc{(0.75cm,0.75cm) circle (0.75cm)}
\newcommand\Uni{(-1.5,-1.5) rectangle (3,1.5)}

\colorlet{circle edge}{pink!}
\colorlet{circle area}{pink!70}

\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
    outline/.style={draw=circle edge, thick}}

\begin{tikzpicture}
    \begin{scope}
        \clip \Uni;
        \draw[filled, even odd rule] \Uni 
                                     \A  ;
    \end{scope}
  \draw[outline] \Uni
                   \A node {$A$};
    \node[anchor=north] at (current bounding box.south) {\textcolor{pink!50!red}{$\complement_EA$}};
\end{tikzpicture}
\end{center}


\pause

S'il n'y a pas d'ambigu\"{\i}té sur le référentiel $E$, $%
\complement _{E}A$ est noté $\overline{A}$ et $\overline{\overline{A}}=A$.%



\end{frame}







\begin{frame}
  \begin{exercice}
    $A\setminus B=A\cap \overline{B}$ et $A\triangleup B=\left( A\cap \overline{B}\right) \cup
\left( \overline{A}\cap B\right) .$
  \end{exercice}
\end{frame}


\subsection{Lois de \textsc{De Morgan}}









\begin{frame}
  \begin{theorem}[Lois de \textsc{De Morgan} ]
 $$ 
\overline{\left( \bigcup\limits_{i=1}^{n}A_{i}\right) }=\bigcap%
\limits_{i=1}^{n}\overline{A_{i}} \qquad \qquad\text{et}\qquad \qquad
\overline{\left( \bigcap\limits_{i=1}^{n}A_{i}\right) }=\bigcup%
\limits_{i=1}^{n}\overline{A_{i}}%
$$
\end{theorem}

\pause

Ça se démontre...

\end{frame}



\subsection{Dualité}\label{dualite}



\begin{frame}
\begin{center}
             \begin{tabularx}{\linewidth}{Y{1}}
	     \whline
             Idempotence & $A\cup A= A$ & $A\cap A = A$ \\
             \hline
             Associativité & $(A\cup B)\cup C=A\cup(B\cup C)$ & $(A\cap B)\cap C=A\cup(B\cap C)$\\
             \hline
             Commutativité & $A\cup B=B\cup A$& $A\cap B=B\cap A$\\
             \hline
             Distributivité & $A\cup(B\cap  C)= (A\cup B)\cap (A\cup C)$
             & $A\cap(B\cup C)= (A\cap B)\cup (A\cap C)$\\
             \hline
             Identité & $A\cup \emptyset=A$ & $A\cap E= A$\\
             \hline
             Involution & $\overline{\overline{A}}=A$& \\
             \hline
             Complémentaire & $A\cup \overline{A}=E$ & $A\cap
             \overline{A}=\emptyset$\\
             &                             $\overline{E}=\emptyset$&
             $\overline{\emptyset}=E$\\
             \hline
             De Morgan & $\overline{A\cup B} = \overline{A} \cap \overline{B}$& $\overline{A\cap B} = \overline{A} \cup \overline{B}$\\
             \whline
             \end{tabularx}
             \end{center}




\end{frame}

\begin{frame}
  \begin{exercice}
    Le \textit{principe de dualité} affirme que si $e$ est vérifiée pour tout
élément de $\P{}(E)$, alors sa duale $e^\star$ aussi: ça se démontre...

  \end{exercice}
\end{frame}



\section{Partition d'un ensemble}


\begin{frame}
  \begin{definition}
  

$E$ désignant ici un ensemble non vide. Soit $P$, une partie non vide de 
$\ P{}(E)$ (on a donc $P\subseteq \ P{}\left( E\right) $ et $%
P\neq \emptyset )$ $P$ est un ensemble non vide de parties de $E$. On dit
que $P$ est une \textbf{partition} de $E$ si, et seulement si,

\begin{enumerate}
\item tout élément de $P$ est non vide,

\item deux éléments distincts quelconques de $P$ sont disjoints,

\item tout élément de $E$ appartient \`{a} l'un des éléments
de $P.$
\end{enumerate}

\end{definition}

\end{frame}



\begin{frame}
  

%\begin{figure}
\begin{center}
  \includegraphics{CE1_partition}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}[fragile]

\begin{lstlisting}
λ> Data.List.partition (\x -> x < 0) [-1,5,-65,8,5,-12]
([-1,-65,-12],[5,8,5])
\end{lstlisting}

  
\end{frame}










\section{Produit cartésien}



\begin{frame}[fragile]
  
\begin{itemize}
\item l'ensemble des entrées: $$E=\bigl\{\text{Cuisses de sauterelles panées}, \text{ \oe uf mou},
  \text{ huîtres de l'Erdre}\bigr\}$$
\item  l'ensemble  des   plats  de  résistance:  $$P=\bigl\{\text{Turbot  à
    l'huile  de  ricin},  \text{  Chien  à  l'andalouse},  \text{  Soupe
    d'orties}\bigr\}$$
\item l'ensemble des desserts: $$D=\bigl\{\text{Pomme}, \text{Banane}, \text{Noix}\bigr\}$$
\end{itemize}

\end{frame}




\begin{frame}[fragile]


\begin{lstlisting}
data Entree  = Cuisses | Oeufs | Huitres
               deriving (Enum, Show)
data Plat    = Turbot | Chien | Soupe
               deriving (Enum, Show)
data Dessert = Pomme | Banane | Noix
               deriving (Enum, Show)

lesEntrees  = [Cuisses .. ]
lesPlats    = [Turbot .. ]
lesDesserts = [Pomme .. ]

lesMenus = [(e,p,d) | e <- lesEntrees, p <- lesPlats, d <- lesDesserts]
\end{lstlisting}

\end{frame}




\begin{frame}[fragile]


\begin{lstlisting}
λ> lesMenus
[(Cuisses,Turbot,Pomme),(Cuisses,Turbot,Banane),(Cuisses,Turbot,Noix),
 (Cuisses,Chien,Pomme),(Cuisses,Chien,Banane),(Cuisses,Chien,Noix),
 (Cuisses,Soupe,Pomme),(Cuisses,Soupe,Banane),(Cuisses,Soupe,Noix),
 (Oeufs,Turbot,Pomme),(Oeufs,Turbot,Banane),(Oeufs,Turbot,Noix),
 (Oeufs,Chien,Pomme),(Oeufs,Chien,Banane),(Oeufs,Chien,Noix),
 (Oeufs,Soupe,Pomme),(Oeufs,Soupe,Banane),(Oeufs,Soupe,Noix),
 (Huitres,Turbot,Pomme),(Huitres,Turbot,Banane),(Huitres,Turbot,Noix),
 (Huitres,Chien,Pomme),(Huitres,Chien,Banane),(Huitres,Chien,Noix),
 (Huitres,Soupe,Pomme),(Huitres,Soupe,Banane),(Huitres,Soupe,Noix) ]
λ> length lesMenus
27
λ> :t lesMenus
lesMenus :: [(Entree, Plat, Dessert)]
\end{lstlisting}

  
\end{frame}


\subsection{Paire ordonnée - Produit de deux ensembles}





\begin{frame}
  
\begin{definition}[Paire ordonnée]
On note $\langle a,b\rangle = \bigl\{\{a\},\{a,b\}\bigr\}$
\end{definition}

\pause

\begin{theorem}
$$(\bigl\{a,b\bigr\} =_{\text{ens}}\bigl\{x,y\bigr\}) \equiv  ((a=x \land b=y) \lor
(a=y \land b=x))$$ 
\end{theorem}

\pause

\begin{theorem}
  $$(\langle a,b\rangle =_{\text{paire}}\langle x,y\rangle) \equiv (a=x \land b=y)$$
\end{theorem}
\pause

\begin{definition}
 $$A\times B = \bigl\{(a,b)\mid (a\in A) \land (b\in B)\bigr\}$$ 
\end{definition}

\end{frame}


\begin{frame}
  \begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\otimes $ & $\bm{1}$ & $\bm{2}$ & $\bm{3}$ & $\bm{4}$ & $%
\bm{5}$ \\ \hline
$\bm{a}$ & $\left( a,1\right) $ & $\left( a,2\right) $ & $\left(
a,3\right) $ & $\left( a,4\right) $ & $\left( a,5\right) $ \\ \hline
$\bm{b}$ & $\left( b,2\right) $ & $\left( b,2\right) $ & $\left(
b,3\right) $ & $\left( b,4\right) $ & $\left( b,5\right) $ \\ \hline
$\bm{c}$ & $\left( c,1\right) $ & $\left( c,2\right) $ & $\left(
c,3\right) $ & $\left( c,4\right) $ & $\left( c,5\right) $ \\ \hline
\end{tabular}%
\end{center}
\end{frame}




\begin{frame}[fragile]

\begin{lstlisting}
λ> [(x,y) | x <- ['a','b','c'], y <- [1,2,3,4,5]]
[('a',1),('a',2),('a',3),('a',4),('a',5),
 ('b',1),('b',2),('b',3),('b',4),('b',5),
 ('c',1),('c',2),('c',3),('c',4),('c',5)]

λ> [(x,y) | x <- ['a','b','c'], y <- [1,2,3,4,5], mod y 2 == 0]
[('a',2),('a',4),('b',2),('b',4),('c',2),('c',4)]
\end{lstlisting}

  
\end{frame}
\subsection{n-uplets - Produit d'un nombre quelconque d'ensembles}


\begin{frame}
  
Définissons temporairement un triplet ordonné $\langle a,b,c\rangle$ par:
$
\langle a,b,c\rangle = \langle a, \langle b,c \rangle \rangle
$.

\pause

\begin{exercice}
  

Est-ce  que c'est  licite? C'est-à-dire  est-ce que  c'est une  définition...qui
définit vraiment  un triplet  ordonné? Qu'est-ce  que ça veut  dire en  fait \og
définit vraiment un triplet ordonné\fg{}?

Comment va-t-on faire alors pour un quadruplet? Un $n$-uplet?

Qu'est-ce que c'est que ça: $
E_{1}\times E_{2}\times \cdots \times
E_{n}=\prod\limits_{i=1}^{n}E_{i}$?
\end{exercice}



\end{frame}


\section{Notion de cardinal}\label{cardinal}


\begin{frame}
  


$
\card\left( E\right) \text{ ou }\left\vert E\right\vert \text{ ou }%
\#E
$


\end{frame}


\begin{frame}
  \begin{theorem}[Propriétés des cardinaux des ensembles finis]
    

  \begin{itemize}
  \item Si $A\subseteq B$ alors $\bigl| A\bigr| \leqslant \bigl| B\bigr| .$ Une cons\'{e}quence int\'{e}ressante est celle ci
: si $A\subseteq B$ avec $\bigl| A\bigr| =\bigl| B\bigr| $ alors $A=B.$

\item $\bigl| A-B\bigr| \leqslant \bigl| A\bigr| .$

\item $\bigl| A\cup B\bigr| =\bigl| A\bigr| +%
\bigl| B\bigr| -\bigl| A\cap B\bigr| $

\item \textbf{Si on a} $E_{i}\cap E_{j}=\emptyset $ \textbf{lorsque} $i\neq
j,$ alors $\left| \bigcup\limits_{i=1}^{n}E_{i}\right|
=\sum\limits_{i=1}^{n}\bigl| E_{i}\bigr| $.

\item $\bigl| E_{1}\times E_{2}\bigr| =\bigl|
E_{1}\bigr| .\bigl| E_{2}\bigr| $ et 
\begin{eqnarray*}
\bigl| E_{1}\times E_{2}\times \cdots \times E_{n}\bigr| &=&%
\bigl| E_{1}\bigr| .\bigl| E_{2}\bigr| .\cdots
.\bigl| E_{n}\bigr| \\
\bigl| E^{n}\bigr| &=&\bigl( | E|
\bigr) ^{n}
\end{eqnarray*}

\item La formule suivante est absolument \`{a} conna\^{\i}tre :%
$$
\bigl| \ P{}\left( E\right) \bigr| =2^{| E| }
$$
Nous la d\'{e}montrerons en exercice.
  \end{itemize}

  \end{theorem}
\end{frame}





\begin{frame}[fragile]
  
  \begin{exercice}
    Une petite question d'anglais de spécialité...: nos amis anglo-saxons appellent
$\P{}(E)$ \textit{power set of E}. Pourquoi?...
  \end{exercice}

\pause

\begin{exercice}
  Comment calculer récursivement le cardinal d'un ensemble?
\end{exercice}


\pause

\begin{lstlisting}
cardinal :: (Eq a) => Ens a -> Int
cardinal Vide = 0
cardinal (Ens (t,q)) = 1 + (cardinal q)
\end{lstlisting}
\end{frame}






\section{Fonction caractéristique (niveau II...)}\label{carac}



\begin{frame}
  

\begin{definition}
Soit $E$ un ensemble. Pour toute partie $A$ de $E$ on d\'{e}finit
la fonction caract\'{e}ristique $\indi{A}$ de $A$
dans $E$ par : 


$$
 \indi{A}\ \colon \begin{array}{rll} E & \to & \bigl\{0;1\bigr\}\\
   x & \mapsto &
   \begin{cases}
     1\quad \text{ si } x\in A\\
     0\quad \text{ si } x\not\in A
   \end{cases}
 \end{array}
 $$

\end{definition}

\pause

$$
\indi{A}=\indi{B}\Longleftrightarrow A=B
$$

\end{frame}








\begin{frame}[fragile]
  \begin{lstlisting}
module EnsembleCompréhension where

type Element  = Int
type Predicat = Element -> Bool
data Ensemble = Ens (Predicat)

contient :: Ensemble -> Element -> Bool
contient    (Ens f)     e       =  f e

insere :: Element -> Ensemble -> Ensemble
insere    e          ens      =  Ens (\x -> (x == e) || (ens `contient` x))

union ::  Ensemble -> Ensemble -> Ensemble
union     ens1        ens2     =  Ens (\x -> (ens1 `contient` x) || (ens2 `contient` x))

  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]

  \begin{lstlisting}
filtre :: Predicat -> Ensemble -> Ensemble
filtre    predic      ens      =  Ens (\x -> (ens `contient` x) && (predic x))

complementaire :: Ensemble -> Ensemble
complementaire    (Ens f)  =  (Ens (not . f))

difference :: Ensemble -> Ensemble -> Ensemble
difference    ens1        ens2     =  ens1 `inter` (complementaire ens2)
                          
estInclus :: Ensemble -> Ensemble -> Bool
estInclus    ens1        ens2     =  estVide (Ens (\x -> (ens1 `contient` x) &&  not (ens2 `contient` x)))

estEgal :: Ensemble -> Ensemble -> Bool
estEgal    ens1        ens2     =  (ens1 `estInclus` ens2) && (ens2 `estInclus` ens1)
    
pourTous :: Predicat -> Ensemble -> Bool
pourTous    predic      ens      =  (filtre predic ens) `estEgal` ens
  \end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
 -- Pour un joli affichage et le test de vacuité
                                        
    listeUnivers :: [Element]
    listeUnivers =  [mini .. maxi]

    listeVersEns :: Ensemble -> [Element]
    listeVersEns    (Ens f)  =  [x | x <- listeUnivers, f x]

    instance  Show Ensemble where
                        show = show . listeVersEns

    estVide :: Ensemble -> Bool
    estVide    ens      =  listeVersEns ens == []
  \end{lstlisting}
  
\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
mini,maxi  :: Element
(mini,maxi) = (-128,127)

univers :: Ensemble
univers =  Ens (\ n -> n >= mini && n <= maxi)
  \end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
λ> let e' = Ens (\ n ->  univers `contient` (n^2) )
λ> e'
[-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11]

λ> let naturels = filtre (> 0) univers

λ> ilExiste (\ n -> 2^11 - 1 `mod` n == 0) naturels
False
  \end{lstlisting}
  
\end{frame}

\section{C'est quoi une fonction?}



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


\begin{frame}[fragile]

  
\begin{lstlisting}
data Booleen = Faux | Vrai

non :: Booleen  -> Booleen
non    Vrai     =  Faux
non    Faux     =  Vrai
\end{lstlisting}
\end{frame}

\begin{frame}
  
\begin{definition}[Graphe d'une fonction]

Le graphe d'une fonction est l'ensemble de tous les couples:

$\langle$ élément du départ, son image dans l'arrivée $\rangle$

ou si vous préférez:

$$\GR(f) = \bigl\{\langle x,f(x)\rangle \mid x \in \text{départ} \bigr\}$$
  
\end{definition}
\end{frame}



\begin{frame}
  
$$f=\Big\langle Booleen, Booleen, \bigl\{\langle Vrai,Faux\rangle, \langle
Faux, Vrai \rangle\bigr\}\Big\rangle$$

\end{frame}


\begin{frame}
  \begin{alertblock}{ATTENTION!}
    Une fonction est donc un triplet $ \langle$ Départ, Arrivée, Graphe$ \rangle$
  \end{alertblock}
\end{frame}


\begin{frame}
 
%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{compris}
\end{center}
%\end{figure}
\end{frame}


\begin{frame}[fragile]
  
\begin{lstlisting}
et1 :: Booleen -> Booleen -> Booleen
et1    Vrai       Vrai    =  Vrai
et1    _          _       =  Faux
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
et2 :: Booleen -> Booleen -> Booleen
et2    Vrai       x       =  x
et2    Faux       x       =  Faux 
\end{lstlisting}

\end{frame}

\begin{frame}
  
$$
\text{et}\colon 
\begin{array}{rll}
 Booleen × Booleen & → & Booleen\\
 (x,y)& \mapsto &
 \begin{cases}
   \text{si } x == \text{ Vrai} \text{ alors } y\\
   \text{sinon Faux} 
 \end{cases}
\end{array}
$$
\end{frame}


\begin{frame}
  \begin{alertblock}{ATTENTION!}
     Sur  Haskell  , toutes les fonctions sont d'UNE SEULE VARIABLE!
  \end{alertblock}
\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
et3 :: Booleen -> (Booleen -> Booleen)
et3    Vrai       x       =  x
et3    Faux       x       =  Faux 
\end{lstlisting}


\pause


\begin{lstlisting}
λ> :t et3 Vrai
et3 Vrai :: Booleen -> Booleen
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]

\begin{lstlisting}
idem :: Booleen -> Booleen
idem    x       =  x
\end{lstlisting}

\pause

\begin{lstlisting}
tjsFaux :: Booleen -> Booleen
tjsFaux    _        = Faux
\end{lstlisting}

\pause

\begin{lstlisting}     


et4 :: Booleen -> Booleen -> Booleen
et4    Vrai    =  idem
et4    Faux    =  tjsFaux
\end{lstlisting}
  
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=3cm]{logoHS}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
et5 :: Booleen -> Booleen -> Booleen
et5    Vrai    =  \ x -> x
et5    Faux    =  \ x -> Faux
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]

\begin{lstlisting}
et6 :: Booleen -> Booleen -> Booleen
et6 y x = if y == Vrai
          then x
          else Faux
\end{lstlisting}

  
\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
placeDeCinema :: Int -> String
placeDeCinema age
    | age < 0   = "Euh, t'as bu quoi au petit déjeuner?"
    | age < 12  = "Pour toi c'est 2 euros et viens prendre un bonbon"
    | age < 18  = "Pour toi c'est 8 euros"
    | otherwise = "T'es pas un peu vieux pour aller voir Petit Poney?"
\end{lstlisting}


\end{frame}




\begin{frame}[fragile]

\begin{lstlisting}
et7 :: Booleen -> Booleen -> Booleen
et7 x y
    |x == Vrai = x
    |otherwise = Faux
\end{lstlisting}

\end{frame}



\section{Un exemple}


\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}[fragile]\frametitle{Spécification}
   \begin{lstlisting}
moyenne_olympique4 :: Float -> Float -> Float -> Float -> Float
-- renvoie la moyenne olympique de 4 flottants sous forme d'un flottant
  \end{lstlisting}

\end{frame}



\begin{frame}[fragile]\frametitle{Réalisation}
Nous allons par exemple additionner
  les quatre nombres, retirer le plus grand et le plus petit puis diviser par 2.


\pause

\begin{lstlisting}
λ> :t min
min :: Ord a => a -> a -> a
\end{lstlisting}


\pause

\begin{lstlisting}
λ> min 'a' 'b'
'a'
λ> min 5 3
3
λ> min "Tralala" "Pouet Pouet"
"Pouet Pouet"
λ> min True False
False
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]\frametitle{Réalisation}
\begin{lstlisting}
moyenne_olympique4 a b c d =
  (s - mini - maxi) / 2 -- l'expression correspondant à la méthode choisie
  where s = a + b + c + d -- la somme des 4 nombres
        mini = min a (min  b (min c d) ) -- le plus petit des 4
        maxi = max a (max  b (max c d) ) -- le plus grand des 4
\end{lstlisting}


\pause


\begin{lstlisting}
λ> moyenne_olympique4 10 8 12 14
11.0
\end{lstlisting}

\end{frame}

\section{Fonctions récursives}

\subsection{Un exemple simple}




\begin{frame}

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

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-0}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-1}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-2}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-3}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-4}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-5}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-6}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-0}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-1}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-2}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-3}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-4}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-5}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-6}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-0}
\end{center}
%\end{figure}

\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}[fragile]

$$S(n) = 0 + 1 + \cdots + (n - 1) + n  = S(n - 1) + n$$

\begin{lstlisting}
s :: Int -> Int
s n
    | n <  0    = error "l'argument doit être un entier naturel"
    | n == 0    = 0
    | otherwise = n + s (n -1)
\end{lstlisting}


\pause

\begin{lstlisting}
s' n = foldl (+) 0 [0 .. n]
\end{lstlisting}


\end{frame}



\subsection{Un jeu}


    \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}[fragile]
% \begin{lstlisting}
% hanoi ::  String -> String -> String -> Int -> String
% -- On nomme les trois piquets sous forme de chaînes. 
% -- On obtient la liste des mouvements sous forme d'une chaîne.
% -- On déplace n disques de dep vers but en se servant de piv comme pivot.
% hanoi dep but piv 1 = 
%   -- 1 disque : renvoie la chaîne décrivant le mvt de dep vers but
%   "De " ++ dep ++ " vers " ++ but ++ "\n"
% hanoi dep but piv n = 
%   -- n disques :
%   (hanoi dep piv but (n - 1)) ++ --  on bouge n-1 disques de dep vers piv
%   (hanoi dep but piv 1) ++ -- on bouge le gros disque de dep vers but
%   (hanoi piv but dep (n - 1)) -- on bouge le n-1 disques du piv vers but
% \end{lstlisting}

% \pause

% \begin{lstlisting}
% -- on affiche le résultat 
% tours_hanoi :: Int -> IO ()
% tours_hanoi n = putStrLn ( hanoi "Tige 1" "Tige 2" "Tige 3" n)
% \end{lstlisting}
      
%     \end{frame}



%     \begin{frame}[fragile]
% \begin{lstlisting}
% λ> tours_hanoi 3
% De Tige 1 vers Tige 2
% De Tige 1 vers Tige 3
% De Tige 2 vers Tige 3
% De Tige 1 vers Tige 2
% De Tige 3 vers Tige 1
% De Tige 3 vers Tige 2
% De Tige 1 vers Tige 2
% \end{lstlisting}
      
%     \end{frame}

 %\section{Une première approche des listes sur Haskell}

 \section{Définition récursive d'un type}




\begin{frame}
\begin{center}
  Qu'est-ce qu'un mot?
\end{center}
\end{frame}



\begin{frame}
  \og glop\fg{}

\pause

\begin{center}
\begin{tikzpicture}[sibling distance=50pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.:+ g
         [.:+ l
             [.:+ o
                 [.:+ p
                    Vide ] ] ] ];
\end{tikzpicture}
\end{center}
\end{frame}






\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
infixr :+

data Mot = 
  Vide 
  | Char :+ Mot 
\end{lstlisting}



\end{frame}





\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
infixr :+

data Mot = 
  Vide 
  | Char :+ Mot 
  deriving (Show)
\end{lstlisting}



\end{frame}





\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
infixr :+

data Mot = 
  Vide 
  | Char :+ Mot 
  deriving (Show, Eq)
\end{lstlisting}



\end{frame}




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

\begin{lstlisting}
λ> let m = 'g' :+ 'l'  :+ 'o' :+ 'p' :+ Vide
λ> m
'g' :+ ('l' :+ ('o' :+ ('p' :+ Vide)))
\end{lstlisting}

\pause


\begin{lstlisting}
λ> :t m
m :: Mot
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]\frametitle{Sélecteurs}


\begin{lstlisting}
tete :: Mot   -> Char
-- renvoie le premier caractère d'un mot avec un filtrage par motif
tete    Vide  =  error "Mot vide !"
tete (t :+ q) =  t
\end{lstlisting}


\pause

\begin{lstlisting}
λ> tete m
'g'
\end{lstlisting}

\pause 

Et la queue?

\end{frame}


\begin{frame}[fragile]{Testeurs}
  \begin{lstlisting}
estVide :: Mot -> Bool
estVide m = m == Vide
  \end{lstlisting}

\pause

$$
  \lnot  (\text{estVide }  m) \lequiv  \big(m  = (\text{tete  } m)  \text{ :+  }
  (\text{queue } m) \big)
$$



\end{frame}




\begin{frame}[fragile]{Construire une fonction définie sur un type récursif}

On voudrait compter le nombre de \og a\fg{} dans un mot.

\pause


\begin{lstlisting}
nba :: Mot -> Int
-- calcule le nombre de 'a' dans un mot
\end{lstlisting}

\end{frame}




\begin{frame}[fragile]
  \begin{itemize}
\item Si le mot est vide, alors son nombre de 'a' est 0.
\item Sinon, le mot est construit par \verb|t :+ q|.  

Si  $\mathtt{t}  =
  \mathtt{'a'}$, alors $\mathtt{nba\ mot} = 1 + \mathtt{nba\ q}$, sinon, $\mathtt{nba\ mot} = \mathtt{nba\ q}$.
\end{itemize}


\pause

\begin{lstlisting}
nba Vide     = 0
nba (t :+ q) = (nba q) + (if t == 'a' then 1 else 0)
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]\frametitle{Filtrage par motif}
  \begin{lstlisting}
nba2 Vide = 0
nba2 (t :+ q) 
  | t == 'a' = (nba2 q) + 1
  |otherwise =  nba2 q
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]\frametitle{Case}
\begin{lstlisting}
nba3 mot = case mot of Vide     -> 0
                       (t :+ q) -> (nba3 q) + (if t == 'a' then 1 else 0)
\end{lstlisting}
\end{frame}


\begin{frame}\frametitle{Pliage}




\begin{center}
\begin{multicols}{2}
\begin{tikzpicture}[sibling distance=20pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.:+ g
         [.:+ l
             [.:+ o
                 [.:+ p
                    Vide ] ] ] ];
\end{tikzpicture}
\begin{tikzpicture}[sibling distance=20pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.f [.f [.f [.f ini g ] l ] o ] p ];
\end{tikzpicture}
\end{multicols}
\end{center}

\end{frame}

\begin{frame}[fragile]\frametitle{Pliage}


\begin{lstlisting}
nba4 :: Mot -> Int
-- calcule le nombre de 'a' dans un mot par pliage
nba4 mot =
  pliage (\accu t -> accu + (if t == 'a' then 1 else 0)) 0 mot 
\end{lstlisting}


\end{frame}


\begin{frame}[fragile]\frametitle{Pliage}
  \begin{lstlisting}
pliage :: (a -> Char -> a) -> a -> Mot -> a
-- adapte foldl aux mots
pliage _    accu Vide     = accu
pliage fonc accu (t :+ q) = pliage fonc (fonc accu t) q
  \end{lstlisting}
\end{frame}




\begin{frame}[fragile]{Applique}

Mettre en majuscule.

\pause

\begin{lstlisting}
λ> import Data.Char
λ> toUpper 'g'
'G'
\end{lstlisting}



  
\end{frame}



\begin{frame}
  \begin{center}
    glop -> GLOP ?
  \end{center}
\end{frame}


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

\end{frame}





\begin{frame}[fragile]
  \frametitle{Maporum Leviosa}


  \begin{lstlisting}
applique :: (Char -> Char)  -> Mot    -> Mot
applique    _                 Vide    = Vide
applique    f                (t :+ q) = (f t) :+ (applique f q)
  \end{lstlisting}


\pause
  \begin{lstlisting}
toMaj :: Mot -> Mot
toMaj    m   =  applique toUpper m
  \end{lstlisting}

\pause

\begin{lstlisting}
λ> let m = 'g' :+ 'l'  :+ 'o' :+ 'p' :+ Vide
λ> toMaj m
'G' :+ ('L' :+ ('O' :+ ('P' :+ Vide)))
\end{lstlisting}



\end{frame}


\section{Composition de fonctions}

\begin{frame}[fragile]
\begin{lstlisting}
infixr 9 .
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
\end{lstlisting}

\pause

\begin{alertblock}{DANGER}
Il faut faire très attention à la signature de type des fonctions à composer!
\end{alertblock}

\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
λ> longMotPlusLong "Vos beaux yeux d'amour mourir me font Belle Marquise"
8
  \end{lstlisting}

\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
λ> words "vos beaux yeux d'amour belle mourir me font Marquise"
["vos","beaux","yeux","d'amour","belle","mourir","me","font","Marquise"]
\end{lstlisting}


\pause

\begin{lstlisting}
λ> :t words
words :: String -> [String]
λ> :t length
length :: [a] -> Int
λ> :t maximum
maximum :: Ord a => [a] -> a
\end{lstlisting}
  
\end{frame}


\begin{frame}
$$\mathtt{String}         \xrightarrow{\mathtt{words}}         \mathtt{[String]}
\xrightarrow{\mathtt{map\ length}} \mathtt{[Int]} \xrightarrow{\mathtt{maximum}} \mathtt{Int}$$

\pause

$$\mathtt{s} \xrightarrow{\mathtt{words}} \mathtt{words\ s}
\xrightarrow{\mathtt{map\    length}}    \mathtt{map\     length\    (words\    s)}
\xrightarrow{\mathtt{maximum}} \mathtt{maximum\ (map\ length\ (words\ s))}$$


\pause

$$\mathtt{String}   \xrightarrow{\mathtt{words \,  . \,  (map\  length\,   .\,   maximum)}}
\mathtt{Int}$$

\pause


$$\mathtt{String}   \xrightarrow{\mathtt{words \,  . \,  map\  length\,   .\,   maximum}}
\mathtt{Int}$$
\end{frame}



\begin{frame}[fragile]


\begin{lstlisting}
λ> let longMotPlusLong = maximum . map length . words
λ> :t longMotPlusLong
longMotPlusLong :: String -> Int
λ> longMotPlusLong "Vos beaux yeux d'amour mourir me font"
7
\end{lstlisting}

\pause

\begin{itemize}
\item \lstinline{maximum . map length . words} 

\item \lstinline{\s -> maximum (map length (words s))} 

\item \lstinline{\s -> maximum $ map length $ words s} 
\end{itemize}

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

\section{Prouver que deux fonctions sont équivalentes}

\begin{frame}[fragile]
\begin{lstlisting}
f1 :: [Int] -> [Int]
f1    []     = []
f1    (k:ks) = abs k : f1 ks

f2 :: [Int] -> [Int]
f2 = map abs
\end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}[caption={Extrait de Data.List}]
-- map f xs is the list obtained by applying f to each element of xs, i.e.,
-- map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
-- map f [x1, x2, ...] == [f x1, f x2, ...]
map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs
\end{lstlisting}
\end{frame}

\begin{frame}
\begin{itemize}

\item f1 []

 
\item  => []         {définition de f1}


\item  => map abs [] {définition de map}

\item  => f2 []      {défintion de f2}

\end{itemize}


\pause

\begin{itemize}
\item f1 (k:ks)

\item  => abs k : f1 ks      {définition de f1}

\item  => abs k : f2 ks      {hypothèse de récurrence}

\item  => abs k : map abs ks {définition de f2}

\item  => map abs (k:ks)     {définition de map}

\item  => f2 (k:ks)          {définition de f2}
\end{itemize}

\end{frame}

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