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

\usepackage[beamer,utf8x,fourier]{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}
\input{patch-tkz-graph}
\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/}}




\newcommand\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\haskell{\lstset{numbers=none, escapeinside={(*@}{@*)},language=haskell,xleftmargin=10pt,%
keywordstyle =\footnotesize\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\footnotesize\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}
}


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

\begin{document}


\title[] % (optional, use only with long paper titles)
{Lois, structures, matrices en informatique}

\subtitle{INFO2 - Semaines 43 \& 45}

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


\haskell








\section{Loi de composition}

\subsection{Définitions}

%
\begin{frame}
  

\begin{definition}[Loi de composition interne (LCI)]
Une loi de composition interne définie sur un ensemble E est une fonction totale
(ou application) de $E\otimes E$ dans E.
On dit alors que E est un \textbf{magma}.
\end{definition}

\end{frame}

% 
\begin{frame}
  
\begin{definition}[Stabilité]
  Un ensemble E est stable par une opération $\star$ si, et seulement si:

$$\Bigl(\forall              \langle
x,y\rangle\Bigr)\Bigl(\bigl(\langle x,y\rangle \in E\otimes E\bigr)\limp \bigl(x\star y \in E\bigr)\Bigr)$$
\end{definition}


\end{frame}



%
\begin{frame}
  

\begin{definition}[Loi de composition externe (LCE)]
Une loi de composition externe définie sur un ensemble E et à opérateurs dans un
ensemble K est une fonction totale
(ou application) de $K\otimes E$ dans E.
  
\end{definition}

\end{frame}


%
\begin{frame}
  
\begin{definition}[Morphisme]

Soit  $\langle  E,\star\rangle $  et
$\langle F,\dagger\rangle $ deux magmas et $φ$ une fonction totale de $E$
dans $F$.
On dit que $φ$ est un morphisme de E dans F si, et seulement si:

$$\bigl(\forall x\bigr)\bigl(\forall y\bigr)\bigl(φ(x\star y) = φ(x)\dagger φ(y)\bigr)$$
\end{definition}

\end{frame}


%
\begin{frame}
  
\begin{definition}[Isomorphisme]
Soit  $\langle  E,\star\rangle $  et
$\langle F,\dagger\rangle$ deux magmas et $φ$ une fonction totale de $E$
dans $F$.
On dit  que $φ$  est un  morphisme de  E dans F  si, et  seulement si,  c'est un
morphisme BIJECTIF de E dans F.  
\end{definition}

\end{frame}



\subsection{Propriétés des lois (de composition interne)}

%
\begin{frame}
  
\begin{definition}[Commutativité]
  Une LCI $\star$ sur E est commutative si, et seulement si
$$(\forall x)(\forall y)(x\star y = y \star x)$$

\end{definition}


\end{frame}


%
\begin{frame}
  

\begin{definition}[Associativité]
  Une LCI $\star$ sur E est associative si, et seulement si
$$(\forall x)(\forall y)(\forall z)(x\star (y\star z) = (x\star y ) \star z)$$
Un magma muni  d'une loi associative est appelé... un
magma associatif.
\end{definition}

\end{frame}

%
\begin{frame}
  

\begin{definition}[Élément neutre]
 Un élément  neutre $e$  d'une LCI $\star$  sur E est  un élément  $e_\star$ qui
 vérifie:

$$(\forall x)(x\star e_\star = e_\star\star x = x)$$

Un  semi-groupe admettant  un  élément  neutre est  un  \textbf{monoïde} (ou un magma
associatif \textbf{unifère}).
\end{definition}


\pause

Pouvez-vous démontrer que si l'élément neutre existe, il est unique?


\end{frame}








%
\begin{frame}
  
\begin{definition}[Élément symétrisable]
  Soit $x$ un élément de E. Il est inversible
  (ou symétrisable) par $\star$ si, et seulement si, 

$$(\exists y)(x\star y =  y \star x = e_\star)$$
\end{definition}

\pause

Pouvez-vous démontrer que si $x$ admet un symétrique, alors ce symétrique est unique?

\end{frame}










%
\begin{frame}
  

\begin{definition}[Régularité]
Un élément $a$ de E est  dit \textbf{régulier à gauche} (ou \textbf{simplifiable
  à gauche}) si, et
seulement si:

$$\bigl(\forall x\bigr)\bigl(\forall y\bigr)\bigl((a\star x = a\star y)\limp (x=y)\bigr)$$

On a une définition similaire de la régularité à droite.

Un élément à la fois régulier à gauche et à droite est dit \textbf{régulier}.

Une loi telle que tout élément soit régulier est dite régulière.

\end{definition}

\pause

Un élément inversible est régulier (vérifiez-le). Un élément régulier est-il inversible?


\end{frame}





%
\begin{frame}
  
\begin{definition}[Distributivité]
  On dit que la loi $\star$ définie sur E est distributive sur $\dagger$ définie
  sur E si, et seulement si:

$$\Bigl(     \forall     x\Bigr)\Bigl(     \forall     y\Bigr)\Bigl(     \forall
z\Bigr)\Bigl( \bigl( x\star (y\dagger z) =  (x\star y) \dagger (x \star z)\bigr)
\land \bigl((y\dagger z)\star x = (y\star x) \dagger (z \star x)\bigr) \Bigr)$$
\end{definition}
\end{frame}














%
\begin{frame}
  

\begin{definition}[Élément absorbant]
 Un élément  absorbant  d'une LCI $\star$  sur E est  un élément  $a_\star$ qui
 vérifie:

$$(\forall x)(x\star a_\star = a_\star\star x = a_\star)$$

  
\end{definition}

\pause

Montrez que si un tel élément existe, il est unique.

\end{frame}












%
\begin{frame}
  
\begin{definition}[Élément involutif]
  Soit $\star$ une loi sur un ensemble E admettant un élément neutre $e_\star$.

Alors $x$ est \textbf{involutif} si, et seulement si, $x\star x=e_\star$.
\end{definition}

\pause

\begin{definition}[Élément idempotent]
  Soit $\star$ une loi sur un ensemble E.

Alors $x$ est \textbf{idempotent} si, et seulement si, $x\star x=x$.
\end{definition}



\end{frame}



\section{Groupes}





%
\begin{frame}
  \begin{figure}
  \includegraphics[height=0.8\textheight]{Evariste}
\caption{É.\textsc{Galois} (1811-1832)}
\end{figure}
\end{frame}









%
\begin{frame}
  

\begin{definition}[Groupe]
Un groupe est un monoïde tel que tout élément est inversible.
\end{definition}


\pause

\begin{definition}[Sous-groupe]
  $\langle  H,\star\rangle$  est  un
  sous-groupe       de      $\langle
  G,\star\rangle$ si, et seulement si, H est une
  partie de G et $\langle H,\star\rangle$ est un groupe.
\end{definition}


\end{frame}



\section{Anneaux et corps}

\subsection{Anneaux}

%
\begin{frame}
  \includegraphics[width=\linewidth]{lord_ring}
\end{frame}



%
\begin{frame}
  \begin{definition}[Anneau]
  Soit A un ensemble muni de deux lois $\boxdot$ et $\boxplus$. 

On dit que
$\langle A,\boxplus,\boxdot\rangle$ est un anneau si, et seulement si:
\begin{itemize}
\item $\langle A,\boxplus\rangle$ est un groupe commutatif;
\item $\boxdot$ est associative;
\item $\boxdot$ est distributive sur $\boxplus$.
\end{itemize}

\pause

Si   $\boxdot$   est  commutative,   alors  l'anneau   est  dit
\textit{commutatif}. 

\pause

Si  $\boxdot$  admet   un  élément  neutre,  l'anneau  est  dit
\textit{unitaire}. 

\pause

Les éléments d'un anneau unitaire qui admettent un symétrique par $\boxdot$
 sont dits  \textit{inversibles}. On note $A^\ast$ l'ensemble
des éléments 
inversibles de A.
\end{definition}

\end{frame}



\subsection{Corps}


%
\begin{frame}
  \begin{definition}[Corps]
Soit $\bbk$ un ensemble muni de deux LCI $\boxplus$ et $\boxdot$.
Le  triplet  $\langle  \bbk,\boxplus,\boxdot\rangle$ possède  une  structure  de
\textbf{corps} si, et seulement si, 
\begin{itemize}
\item                       $\langle
  \bbk,\boxplus,\boxdot\rangle$    a
  une structure  d'anneau commutatif
  unitaire;
\item                       $\langle
  \bbk\setminus\{e_\boxplus\},\boxdot\rangle$
  a une structure de groupe.
\end{itemize}
\end{definition}


\pause




Combien d'éléments a au minimum un corps?


\end{frame}


\subsection{La classes numériques sur Haskell}


%
\begin{frame}[fragile]

\begin{lstlisting}
class  (Eq a, Show a) => Num a  where
    (+), (-), (*)  :: a -> a -> a
    negate         :: a -> a
    abs, signum    :: a -> a
    fromInteger    :: Integer -> a
\end{lstlisting}

\pause

À quelle structure algébrique peut-on associer la classe \verb+Num+?

\end{frame}


%
\begin{frame}[fragile]
\begin{lstlisting}
class  (Num a) => Fractional a  where
    (/)          :: a -> a -> a
    recip        :: a -> a
    fromRational :: Rational -> a
\end{lstlisting}

\pause


À quelle structure algébrique peut-on associer la classe \verb+Frational+?


\end{frame}

\section{Aparté: ze Haskell Touch}



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

John \textsc{Backus} (1924 - 2007)

\pause

 {\itshape 
Much of my work has come from being lazy
}
\end{center}
%\end{figure}



\end{frame}


\subsection{Les fonctions}


\begin{frame}[fragile]\frametitle{Spécifier}
SPÉCIFIER la  fonction: c'est-à-dire parfois (on  peut effectivement s'en
  passer au besoin) la nommer, donner son \textit{type}, i.e. son domaine et son
  codomaine: on  parle de \textit{signature de  type} et on explique  ce qu'elle
  fait.

\pause

 \begin{lstlisting}
double :: Int -> Int
-- calcule le double d'un entier : le résultat est un entier
  \end{lstlisting}


\end{frame}






\begin{frame}[fragile]\frametitle{Réaliser}
RÉALISER la  fonction  c'est  associer   à  la  fonction  spécifiée  une
  expression. 

 Pour cela, on utilise des \textit{paramètres formels} qui font
  \textit{abstraction} des valeurs particulières qui leur seront ensuite \textit{substituées}.

\pause

  \begin{lstlisting}
double n = 2 * n
  \end{lstlisting}


\end{frame}




\begin{frame}[fragile]\frametitle{Utiliser}
UTILISER a  fonction   dans  une   expression  en   lui  donnant   des
  \textit{paramètres effectifs} (arguments), c'est-à-dire liés à l'application particulière
  de la fonction:

\pause

  \begin{lstlisting}
*Main> (double 3) + (double 7)
20
  \end{lstlisting}


\end{frame}




\subsection{Curryfication}


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

Haskell \textsc{Curry} (1900 - 1982)

\end{center}
%\end{figure}



\end{frame}


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

\end{frame}




\begin{frame}
 Une \textbf{fonction curryfiée} est une fonction de
plusieurs  variables transformée  en une  fonction d'une  seule variable
qui renvoie une fonction ayant une variable de moins...


\pause


Cela permet de créer des fonctions partielles.




\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
plus x y = x + y
\end{lstlisting}


\pause

\begin{lstlisting}
plus :: Integer -> Integer -> Integer
plus    x          y       =  x + y
\end{lstlisting}

\pause

Associativité

\pause

\begin{lstlisting}
f = plus 3
\end{lstlisting}


\pause

Que vaut \verb+f(5)+?

\pause

\begin{lstlisting}
*Main> f 5
8
\end{lstlisting}

\pause

\begin{lstlisting}
*Main> :t f
f :: Integer -> Integer
\end{lstlisting}

\end{frame}



\begin{frame}
 $\FR(D,A)$ 

\pause

 $\mathtt{plus}\in\FR
\bigl( \bbn, \FR(\bbn,\bbn) \bigr)$
\end{frame}



\subsection{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}
*Main> :t min
min :: Ord a => a -> a -> a
\end{lstlisting}


\pause

\begin{lstlisting}
*Main> min 'a' 'b'
'a'
*Main> min 5 3
3
*Main> min "Tralala" "Pouet Pouet"
"Pouet Pouet"
*Main> 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}
*Main> moyenne_olympique4 10 8 12 14
11.0
\end{lstlisting}

\end{frame}



\subsection{Polymorphisme - abstraction - récursion - listes}

\begin{frame}
  \begin{example}
    Décrire une fonction qui étant donnée une liste d'au moins quatre nombres leur associe la moyenne
  des nombres parmi ceux de la liste qui ne sont ni le plus grand ni le plus
  petit. Par exemple, la moyenne olympique de 15, 7, 10, 8, 12 et 14 est 11.
  \end{example}
\end{frame}

\begin{frame}[fragile]\frametitle{Min et Max polymorphes}

\begin{lstlisting}
minListe :: (Ord a) => [a] -> a
-- renvoie le mini d'une liste d'éléments ordonnables 
\end{lstlisting}

\pause


\begin{lstlisting}
maxListe :: (Ord a) => [a] -> a
-- renvoie le maxi d'une liste d'éléments ordonnables 
\end{lstlisting}

\pause


\begin{lstlisting}
extr_liste :: (Ord a) => (a -> a -> a) -> [a] -> a
-- renvoie le mini ou le maxi (on choisit en mettant la nature de l'extremum en paramètre) d'une liste d'éléments ordonnables 
\end{lstlisting}



\end{frame}



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

\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
m_o4 :: (Fractional t, Ord t) => t -> t -> t -> t -> t 
m_o4               a    b    c    d =
  (s - mini - maxi) / 2
  where {
    s    = a + b + c + d ;
    mini = min d (min c (min a b)) ;
    maxi = max d (max c (max a b))
        }
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
som_liste :: (Num typ) => [typ]                               -> typ
som_liste                 []                                  =  
    error "Ta liste est vide !!"
som_liste                 (tete_de_liste : [])                =  
     tete_de_liste  
som_liste                 (tete_de_liste : liste_décapitée)   =  
     (+) tete_de_liste (som_liste liste_décapitée) 
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
minListe :: ( Ord t) => [t]                      -> t
minListe                []                       =  
    error "Ta liste est vide !!"
minListe                (tete : [])              =  
    tete
minListe                (tete : liste_décapitée) =  
    min tete (minListe liste_décapitée)
  \end{lstlisting}
  

\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting} maxListe :: (Ord t) => [t]                      -> t
maxListe               []                       =  
    error "Ta liste est vide !!"
maxListe               (tete : [])              =  
    tete
maxListe               (tete : liste_décapitée) =  
    max tete (maxListe liste_décapitée)
  \end{lstlisting}
\end{frame}



\begin{frame}

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

\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
op_liste = foldl1
  \end{lstlisting}

\pause 

\verb+fold+ comme...

\pause

\verb+l+ comme...

\end{frame}


\begin{frame}
\begin{center}
\begin{multicols}{2}
\begin{tikzpicture}[sibling distance=20pt ]
\Tree [.: 4 
        [.: 2
            [.: 3
               [.: 2.5
                   [.: 7
                       Vide ] ] ] ]];
\end{tikzpicture}
\begin{tikzpicture}[sibling distance=20pt ]
\Tree [.min [.min [.min [.min 7 2.5 ] 3 ] 2 ] 4 ];
\end{tikzpicture}
\end{multicols}
\end{center}
\end{frame}









\begin{frame}[fragile]

  \begin{lstlisting}
*Main> :t opListe
opListe :: (a -> a -> a) -> [a] -> a

*Main> :t opListe min
opListe min :: Ord a => [a] -> a

*Main> opListe min [4, 2, 3, 2.5, 7]
2.0

*Main> opListe max [4, 2, 3, 2.5, 7]
7.0

*Main> opListe (+) [4, 2, 3, 2.5, 7]
18.5

*Main> opListe (*) [4, 2, 3, 2.5, 7]
420.0
  \end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]

Longueur d'une liste ? 

\pause

\begin{lstlisting}
*Main> length [2,3,6,7]
4
\end{lstlisting}

  
\end{frame}



\begin{frame}[fragile]

  \begin{lstlisting}
*Main> (opListe (+) [2,3,6,7]) / (length [2,3,6,7])
  \end{lstlisting}

\pause

\begin{lstlisting}
<interactive>:27:25:
    No instance for (Fractional Int)
      arising from a use of `/'
    Possible fix: add an instance declaration for (Fractional Int)
    In the expression:
      (opListe (+) [2, 3, 6, 7]) / (length [2, 3, 6, 7])
    In an equation for `it':
        it = (opListe (+) [2, 3, 6, ....]) / (length [2, 3, 6, ....])
\end{lstlisting}



\end{frame}






\begin{frame}[fragile]

  \begin{lstlisting}
*Main> :t length
length :: [a] -> Int

*Main> :t (/)
(/) :: Fractional a => a -> a -> a
  \end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
*Main> :t foldl1
foldl1 :: (a -> a -> a) -> [a] -> a
*Main> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
longListeFrac :: (Fractional nb) => [patates] -> nb 
longListeFrac                       xs       =  foldl (\acc patate -> 1 + acc) 0 xs
  \end{lstlisting}


\pause


\begin{lstlisting}
*Main> longListeFrac ['a'..'z']
26.0
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  Alternative récursive:

  \begin{lstlisting}
LongListeFrac :: Fractional nb => [patates] -> nb 
LongListeFrac                      []        =  0
LongListeFrac      (tete : liste_décapitée) =  1 + (LongListeFrac liste_décapitée)
  \end{lstlisting}
\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
m_o :: (Ord t, Fractional t) => [t] -> t
m_o     liste_notes      =
                        if nb_notes <= 0 then error "Liste trop courte !"
                        else 
                          (som_notes - note_mini - note_maxi) / nb_notes
  where {
    som_notes =  som_liste  liste_notes ;
    note_mini =  minListe  liste_notes ;
    note_maxi =  maxListe  liste_notes ;
    nb_notes  =  (LongListeFrac liste_notes) - 2
    }
  \end{lstlisting}
\end{frame}




\subsection{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}
data Mot = 
  Vide 
  | Char :+ Mot 
\end{lstlisting}



\end{frame}





\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
data Mot = 
  Vide 
  | Char :+ Mot 
  deriving (Show)
\end{lstlisting}



\end{frame}





\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
data Mot = 
  Vide 
  | Char :+ Mot 
  deriving (Show, Eq)
\end{lstlisting}



\end{frame}



\begin{frame}[fragile]

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


\pause


\begin{lstlisting}
*Main> let m = 'g' :+ 'l'  :+ 'o' :+ 'p' :+ Vide

<interactive>:44:9:
    Couldn't match expected type `Char' with actual type `Mot'
    In the first argument of `(:+)', namely 'g' :+ 'l' :+ 'o' :+ 'p'
    In the expression: 'g' :+ 'l' :+ 'o' :+ 'p' :+ Vide
    In an equation for `m': m = 'g' :+ 'l' :+ 'o' :+ 'p' :+ Vide
\end{lstlisting}
\end{frame}



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

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

\pause

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

\end{frame}


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

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

\pause


\begin{lstlisting}
*Main> :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}
*Main> 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}[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 fonc ini Vide     = ini
pliage fonc ini (t :+ q) = pliage fonc (fonc ini t) q
  \end{lstlisting}
\end{frame}




\begin{frame}[fragile]{Applique}

Mettre en majuscule.

\pause

\begin{lstlisting}
*Main> import Data.Char
*Main 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]
  \begin{lstlisting}
applique :: (Char -> Char) -> Mot     -> Mot
applique    f                 Vide    =  Vide
applique    f                (t :+ q) =  (f t) :+ (applique f q) 
  \end{lstlisting}


\pause


\begin{lstlisting}
*Main> applique Data.Char.toUpper m
'G' :+ ('L' :+ ('O' :+ ('P' :+ Vide)))
\end{lstlisting}



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

\end{frame}
\section{Structure d'espace vectoriel}

%
\begin{frame}
\begin{figure}
   \includegraphics[height=0.8\textheight]{grassmann}
\caption{Hermann \textsc{Gra\ss mann} (1809-1877)}
 \end{figure}
\end{frame}


%
\begin{frame}
  \begin{figure}
  \includegraphics[width=3.2cm]{banach}
\caption{Stefan \textsc{Banach} (1892-1945)}
\end{figure}
\end{frame}




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

\pause

$3\times      \text{Marylin}      +
 \text{Albert}$

\end{frame}

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

\pause

$   \text{Marylin}    +
      \text{Albert}$

\end{frame}




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


\pause

$ \text{Marylin} + 3\times\text{Albert}$
\end{frame}


%
\begin{frame}[fragile]
  \begin{definition}[$\bbk$-espace vectoriel]
Un $\bbk$-espace vectoriel $V$ sur un corps commutatif $\langle \bbk,\oplus,\odot\rangle$ est un groupe
abélien  $\langle V,\dagger\rangle$  muni  d'une  loi de  composition
\textit{externe}  $\cdot$  de  $\bbk\otimes V$  dans  $V$  vérifiant
les  quatre  axiomes  suivant,  $λ$ et  $μ$  désignant  des  scalaires
quelconques, $\mathbf{u}$ et $\mathbf{v}$  des vecteurs quelconques et
$1_\odot$ l'élément neutre de la loi $\odot$ sur $\bbk$:

\begin{tabular}{ll}
  $(λ\oplus μ)\cdot \mathbf{u}=λ\cdot\mathbf{u}\dagger μ\cdot\mathbf{u}$ &(distributivité
    vectorielle);\\
  $λ\cdot(\mathbf{u}\dagger\mathbf{v})=λ\cdot\mathbf{u}\dagger λ\cdot\mathbf{v}$ &(distributivité
    scalaire);\\
 $(λ\odot μ)\cdot\mathbf{u}=λ\cdot(μ\cdot\mathbf{u})$ &(associativité);\\
 $1_\odot\cdot\mathbf{u}=\mathbf{u}$ &(axiome d'identité)\\
\end{tabular}

On dit que le corps $\bbk$ \textit{opère} sur le groupe  $\langle V,\dagger\rangle$.
 
\end{definition}



\pause



\begin{lstlisting}
imshow(3 * marilyn + einstein, cmap = cm.gray)
\end{lstlisting}

\end{frame}


\subsection{Un exemple de F$_{\text 2}$-espace vectoriel}


%
\begin{frame}

$$\langle b_1,b_2,b_3\rangle  \dagger \langle  b'_1,b'_2,b'_3\rangle =
\langle b_1\oplus b'_1,b_2\oplus b'_2,b_3\oplus b'_3\rangle$$

\pause
$$
 (\cdot)\ \colon \begin{array}{rll} \bbf_2\otimes T& \to & T\\
   \big\langle  λ,\langle   b_1,b_2,b_3\rangle\big\rangle&  \mapsto  &
   \langle λ\odot b_1,λ\odot b_2,λ\odot b_3\rangle
 \end{array}
 $$



\end{frame}




%
\begin{frame}[fragile]
  \begin{lstlisting}
data BoolInt = O | I deriving(Show,Read,Eq)

type BitChaine = [BoolInt]

bPlus :: BoolInt -> BoolInt -> BoolInt
bPlus    b1         b2 
  |b1 == b2                 = O
  |otherwise                = I
               
bFois :: BoolInt -> BoolInt -> BoolInt
bFois    I          I       =  I
bFois    _          _       =  O
         
cPlus :: BitChaine -> BitChaine -> BitChaine
cPlus    c1           c2        =  zipWith bPlus c1 c2

prodExt :: BoolInt -> BitChaine -> BitChaine
prodExt    b          c         =  map (\x -> bFois b x) c
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]



\begin{lstlisting}
*Main> bPlus O I
I
*Main> cPlus [O,O,I] [I,O,I]
[I,O,O]
*Main> prodExt I [O,O,I]
[O,O,I]
*Main> prodExt O [O,O,I]
[O,O,O]
\end{lstlisting}



\end{frame}










%
\begin{frame}[fragile]


\begin{lstlisting}
lesBits = [O,I]

lesTrios = [[x,y,z] | x <- lesBits, y <- lesBits, z <- lesBits]

and [prodExt (bPlus b1 b2) t == cPlus (prodExt b1 t) (prodExt b2 t) 
    | b1 <- lesBits, b2 <- lesBits, t <- lesTrios ]
\end{lstlisting}



  
\end{frame}




\subsection{Ensemble des combinaisons linéaires d'une famille de vecteurs}




%
\begin{frame}
  \begin{definition}[Combinaison linéaire de vecteurs]
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit   $\langle   \mathbf{u_0},\mathbf{u_1},\cdots,\mathbf{u_p}\rangle$   une
famille de vecteurs de $V$.


Un  vecteur $\mathbf{v}$  de $V$  est une  combinaison linéaire  de la
famille des $\langle \mathbf{u_i}\rangle_{0 \leqslant i \leqslant p}$ si, et
seulement si, il existe une famille 
$\langle λ_0,λ_1,\cdots,λ_p\rangle$ de  scalaires
de $\bbk$ vérifiant:

$$
\mathbf{v}            =            \displaystyle\daggersum_{i=0}^{i=p}λ_i\bullet
\mathbf{u_i}=λ_0\bullet\mathbf{u_0}\dagger
λ_1\bullet\mathbf{u_1}\dagger\cdots\dagger λ_p\bullet\mathbf{u_p}
$$


L'ensemble de ces combinaisons linéaires est noté:

$$\sev{\mathbf{u_0},\mathbf{u_1},\cdots,\mathbf{u_p}}$$
  
\end{definition}


\end{frame}




%
\begin{frame}[fragile]

\begin{lstlisting}
u = [O,I,I]
v = [I,O,I]
vect = [cPlus (prodExt b1 u) (prodExt b2 v) | b1 <- lesBits, b2 <- lesBits]
\end{lstlisting}

\pause


\begin{lstlisting}
*Main> vect
[[O,O,O],[I,O,I],[O,I,I],[I,I,O]]
\end{lstlisting}

  
\end{frame}

\subsection{Sous-espace vectoriel}







%
\begin{frame}
  \begin{definition}[Sev]
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit $W$ un sous-ensemble de $V$.

Si,  muni  des mêmes  opérations  que  $V$,  $W$  a une  structure  de
$\bbk$-espace   vectoriel,    alors   on   dit   que    $W$   est   un
\textbf{sous-espace vectoriel} de $V$.
  
\end{definition}

\end{frame}





%
\begin{frame}
  \begin{theorem}[Caractérisation (1) des sous-espaces vectoriels]\label{sev1}
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit $W$ un sous-ensemble de $V$.

$W$ est un sous-espace vectoriel (sev) de $V$ si, et seulement si:

\begin{itemize}
\item $W\neq \emptyset$
\item      $(\forall      \mathbf{u})(\forall      \mathbf{v})(\langle
  \mathbf{u},\mathbf{v}\rangle   \in    W^2   \limp   \mathbf{u}\dagger
    \mathbf{v}\in W)$
\item $(\forall λ)(\forall      \mathbf{u})(\langle
  λ,\mathbf{u}\rangle \in \bbk\otimes W \limp λ\bullet \mathbf{u} \in W)$
\end{itemize}
  
\end{theorem}

\end{frame}






%
\begin{frame}
  \begin{theorem}[Caractérisation (2) des sous-espaces vectoriels]\label{sev2}
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit $W$ un sous-ensemble de $V$.

$W$ est un sous-espace vectoriel (sev) de $V$ si, et seulement si:

\begin{itemize}
\item $\mathbf{0}\in W$

\item $(\forall λ)(\forall      \mathbf{u})(\forall      \mathbf{v})(\langle
  λ,\mathbf{u},\mathbf{v}\rangle   \in  \bbk\otimes   W\otimes  W\limp
  \mathbf{u}\dagger λ\bullet \mathbf{v} \in W)$
\end{itemize}
  
\end{theorem}
\end{frame}




\section{Les matrices}


\subsection{Histoire}

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

 \end{frame}



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

 \end{frame}


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

 \end{frame}



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

 \end{frame}





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

 \end{frame}


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

 \end{frame}

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

 \end{frame}



\subsection{Retour sur les vecteurs}





  


\begin{frame}

Nous  appellerons \textit{vecteur}  une liste  d'éléments  d'un ensemble
$\bba$. Cet  ensemble  $\bba$  est   muni  de  deux  opérations,  $\boxplus$  et
$\boxdot$, qui lui confèrent une structure d'\textbf{anneau}:

\pause

\begin{itemize}
\item $(\bba,\boxplus)$ a une structure de groupe commutatif;
\item $(\bba,\boxdot)$ a une structure de monoïde;
\item $\boxdot$ est distributive sur $\boxplus$.
\end{itemize}


\pause

On désigne souvent  par $0_{\bba}$ l'élément neutre de  $\boxplus$ et par
$1_{\bba}$ l'élément neutre de $\boxdot$.

\pause

$(\bba,\boxdot)$ n'étant pas forcément  un groupe, tout le monde n'admet
pas forcément un inverse par $\boxdot$. 

\end{frame}

\begin{frame}
  \begin{exercice}
    Quels sont les éléments inversibles de $(\bbz,\cdot)$?
  \end{exercice}
\end{frame}





\begin{frame}[fragile]
  \begin{lstlisting}
class  (Eq a, Show a) => Num a  where
    (+), (-), (*)  :: a -> a -> a
    negate         :: a -> a
    abs, signum    :: a -> a
    fromInteger    :: Integer -> a
\end{lstlisting}

\end{frame}



\begin{frame}


On notera $\bba^p$ l'ensemble des vecteurs à coefficients dans $\bba$ de
\textit{taille} $p$.


\pause

$$u\boxplus v=[a_1\boxplus b_1,a_2\boxplus b_2,...,a_n\boxplus b_n]$$

\pause

$$k u =[k\boxdot a_1,k \boxdot a_2,...,k\boxdot a_p]$$


\pause

$$u\boxdot v = [a_1\boxdot b_1,a_2 \boxdot b_2,...,a_p\boxdot b_p]$$




\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
*Main> let u = [1, 2, 5, 4]
*Main> let v = [3, 4, 2, 3]
*Main> import Data.List
*Main Data.List> zipWith (*) u v
[3,8,10,12]
  \end{lstlisting}
\end{frame}



\subsection{Matrice}




\begin{frame}


 $\bba^{n\times p}$: ensemble des matrices de $n$
lignes et $p$ colonnes à coefficients dans $\bba$. 

\pause

$$
\bordermatrix{
  &        &        &        &  j     &        &        \cr
  & a_{1,1} & a_{1,2} & \cdots & a_{1,j} & \cdots & a_{1,p} \cr
  & \vdots & \vdots &        & \vdots &        &  \vdots \cr
i & a_{i,1} & a_{i,2} & \cdots & a_{i,j} & \cdots & a_{i,p} \cr
  & \vdots & \vdots &        & \vdots &        &  \vdots \cr
  & a_{n,1} & a_{n,2} & \cdots & a_{n,j} & \cdots & a_{n,p} \cr
}
$$
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
data Matrice a = Mat [[a]] 
  \end{lstlisting}
\end{frame}

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