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

\usepackage[beamer,utf8,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}
\usepackage{circuitikz}


\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)
{Opérations, lois, structures en informatique}

\subtitle{INFO1 - 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{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}

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

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

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


\pause



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

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