%% Last modified: <Matrix_DUT2_13_operator.tex modifié par  Guillaume CONNAN le samedi 26 octobre 2013 à 20h 00min 51s>


\chapterimage{operator}
\chaptertext{Les langages  de programmation modernes sont  très algébriques: ils
  puisent  dans ce  domaine  mathématique,  développé surtout  depuis  la fin  du
  XIX\eme siècle, la  rigueur et les structures qui leur  permettent de créer des
  programmes sûrs et vérifiables a priori.
Les structures algébriques sont aussi les outils qui servent de base au codage
de l'information,  en cryptographie,
elles sont aussi le point de départ des outils de transformation en infographie, en
traitement d'image, elles offrent des outils indispensables à la théorie des langages, de la
compilation, des types.

Bref, elles sont un passage obligé pour bien saisir l'informatique moderne..}


\chapter{Opérations, lois et structures}


\section{Opération}


Une opération  est un concept à  la fois simple  (on l'utilise depuis le  CP) et
compliqué  : en  mathématique actuelle  et en  informatique théorique,  ce terme
recouvre des notions très abstraites.

Comme  nous  n'avons  guère  vu   que  des  ensembles,  nous  nous  contenterons
\textit{pour l'instant} de dire ici qu'il s'agit d'une \textbf{fonction} dont 
les paramètres seront appelés \textit{opérandes}.  On utilise le plus souvent un
symbole pour désigner cette fonction : c'est l'\textit{opérateur}.


\subsection{Opération unaire}

C'est simplement un autre nom d'une fonction d'un ensemble dans un autre...

On dit aussi dans ce cas que l'opération est d'\textbf{arité} 1.

Par exemple, la  négation d'une proposition sur l'ensemble  des propositions, la
fonction qui renvoie
l'opposé d'un  entier sur l'ensemble des  entiers mais on peut  imaginer tout ce
qu'on veut...

Considérons la  fonction \verb+vers_majuscule+ de  l'ensemble des
caractères dans lui-même qui à une  lettre minuscule renvoie la lettre majuscule
associée.


\begin{aparte}
Pourquoi le 'A' est codé 65 et le 'a' 97 en \textsc{Ascii}? 

Vous avez remarqué que $97-65=32=2^5$.

Mais il vaut mieux voir les choses ainsi:

'A' -> [1,0,0,0,0,0,1]

'a' -> [1,1,0,0,0,0,1]

'Z' -> [1,0,1,1,0,1,0]

'z' -> [1,1,1,1,0,1,0]

Qu'en pensez-vous?

\end{aparte}

En \HS :


\begin{lstlisting}
import qualified Data.Char as Car

versMaj :: Char                      -> Char 
versMaj    lettre 
  | (lettre < 'a') || (lettre > 'z')  =  error "Ce n'est pas une minuscule !!!" 
  | otherwise                         =  Car.chr (Car.ord lettre - 32)
\end{lstlisting}

On utilise  deux fonctions fondamentales  dont on aura besoin  en cryptographie,
\verb+chr+ et  \verb+ord+ du module \verb+Data.Char+  qui font le lien  entre un
caractère et son code \textsc{Ascii}.

\begin{lstlisting}
*Main> Car.ord 'a'
97
*Main> Car.ord 'A'
65
*Main> map Car.ord ['a'..'z']
[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]
*Main> map Car.ord ['A'..'Z']
[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]

*Main> Car.chr 97
'a'
*Main> map Car.chr [32 .. 126] 
" !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]
  ^_`abcdefghijklmnopqrstuvwxyz{|}~"
\end{lstlisting}

Par exemple:

\begin{lstlisting}
*Main> versMaj 'a'
'A'
*Main> map versMaj "tralalahop"
"TRALALAHOP"
\end{lstlisting}


Bon, cette fonction existait déjà...

\begin{lstlisting}
*Main> map Car.toUpper ['a'..'z']
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
\end{lstlisting}

mais fonctionne autrement:

\begin{lstlisting}
*Main> map Car.toUpper "Ho ! Tu vas te mettre en majuscule ! #@$ $ %*$"
"HO ! TU VAS TE METTRE EN MAJUSCULE ! #@$ $ %*$"
\end{lstlisting}

Comment   modifier  notre   \verb+versMaj+   pour   qu'elle  fonctionne   comme
\verb+to_Upper+?






\subsection{Opération binaire}

Une opération binaire  est une fonction de  signature $A\otimes B \to  C$. On dit
qu'elle est d'arité 2.

Par exemple, que pensez-vous de: 

\begin{lstlisting}
somCar :: (Char,Char) -> Char
somCar    (a   ,b)    =  Car.chr ((Car.ord a) + (Car.ord b)) 
\end{lstlisting}

dont voici des réalisations:

\begin{lstlisting}
*Main> somCar ('A','!')
'b'
*Main> somCar ('1','2')
'c'
\end{lstlisting}




On n'est pas obligé de travailler dans le même ensemble:

\begin{lstlisting}
estCode :: (Char,Int) -> Bool
estCode (car,nb) = (Car.ord car == nb)
\end{lstlisting}

Par exemple:

\begin{lstlisting}
*Main> estCode ('a', 97)
True
\end{lstlisting}


Mais  la \textit{curryfication}  nous permet  de transformer  toute fonction  de
plusieurs variables en une fonction d'une variable:

\begin{lstlisting}
estCode_c :: Char -> Int -> Bool
estCode_c    car     nb  =  Car.ord car == nb
\end{lstlisting}

Cette fonction curryfiée, donc d'une seule variable, sera malgré tout considérée
comme une opération binaire.

Ici, l'opérateur est placé avant ses arguments:  on dit qu'il est dénoté par une
notation \textbf{préfixée}.

D'habitude,   les   opérateurs   binaires   sont  dénotés   par   une   notation
\textbf{infixée}. C'est possible aussi en \HS:

\begin{lstlisting}
infix @+

(@+) a b = somCar (a,b)  
\end{lstlisting}

On peut maintenant utiliser une syntaxe plus habituelle:

\begin{lstlisting}
*Main> 'A' @+ '!'
'b'
\end{lstlisting}


On  peut  utiliser  une  notation  \textbf{postfixée}  comme  pour  la  \textit{Notation
Polonaise Inversée} utilisée en assembleur, en postscript,...

Par exemple, $3$ $2$ $+$ désigne la somme de 3 et de 2.



\subsection{Opération d'arité supérieure}

On peut continuer ainsi.

Prenons par exemple l'opération ternaire définie sur $\bbz$ par:


\begin{itemize}
\item Version non curryfiée:

\begin{lstlisting}
f :: (Int,Int,Int) -> Int
f    (a  ,b  ,c  ) =  a^2 + b^2 + c^2
\end{lstlisting}

\begin{lstlisting}
*Main> f (1,2,3)
14
\end{lstlisting}


\item Version curryfiée:

  \begin{lstlisting}
f :: Int -> Int -> Int -> Int
f    a      b      c   =  a^2 + b^2 + c^2
  \end{lstlisting}

  \begin{lstlisting}
*Main> f 1 2 3
14
  \end{lstlisting}


\end{itemize}


On  peut aussi  la  considérer  comme opération  d'arité  1  sur l'ensemble  des
triplets de $\bbz^3$...





\section{Loi de composition}

\subsection{Définitions}

Une loi est une opération d'arité 2 qui est une fonction totale. On distingue deux
cas:



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


Donnez vous-mêmes de nombreux exemples....


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




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




Donnez vous-mêmes de nombreux exemples....


Voici enfin une notion primordiale dont nous reparlerons souvent:

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

Pouvez-vous donner quelques exemples?


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


C'est une notion primordiale!!! Cela permet  de simplifier (si si) énormément de
situations  qui  paraissent  différentes  mais  qui  sont  les  mêmes  \textit{à
  isomorphisme près}...



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


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



\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{abel}
%\caption{N.\textsc{Abel} (1802-1829)}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.2cm}
\begin{minipage}[t]{\linewidth}
Un magma  muni d'une  loi commutative  est dit  \textit{abélien} (en  hommage au
mathématicien norvégien Niels Henrik \textsc{Abel} (1802 - 1829)).
\end{minipage}



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

\begin{aparte}
  Il  y a  une grosse  bataille franco-anglo-saxonne  au sujet  de ce  qu'est un
  semi-groupe ou un demi-groupe.
  Nous allons nous conformer à la dernière référence en date, même si elle n'est
  pas  française:  \og Homotopy  Type  Theory\fg{}  disponible à  cette  adresse
  \href{http://homotopytypetheory.org/book/}{http://homotopytypetheory.org/book/}.1
  Un magma associatif y est défini page 122 comme un semi-groupe.
\end{aparte}

Quand des lois sont associatives, on peut se passer de parenthèses et on peut noter plus simplement leurs
itérations.  

Par exemple,  depuis le collège, vous  notez $a^n$ la multiplication  itérée $n$
fois de $a$ par lui-même.







Certaines lois ne sont pas associatives mais on peut \textit{décider}, pour se simplifier
la  vie au  moment de  les  créer, qu'elles  sont  associatives à  droite (ou  à
gauche).

Sur  \HS par  exemple, l'opérateur  \verb+->+ entre  domaine et  codomaine d'une
fonction est  associatif à droite. En  effet, les concepteurs de  \HS ont décidé
que \verb+Char -> Int -> Bool+ signifie en fait \verb+Char -> (Int -> Bool)+.

On peut ainsi se passer de parenthèses mais il faudra bien garder à l'esprit que
l'associativité n'est effective qu'à droite.

Par exemple, commentez ce qui passe ici:

\begin{lstlisting}
estCode :: Char -> Int -> Bool
estCode car nb = Car.ord car == nb
\end{lstlisting}

\begin{lstlisting}
*Main> :t estCode 'a'
estCode 'a' :: Int -> Bool
*Main> :t Car.ord
Car.ord :: Char -> Int
*Main> :t estCode (Car.ord)

<interactive>:1:11:
    Couldn't match expected type `Char' with actual type `Char -> Int'
    In the first argument of `estCode', namely `(Car.ord)'
    In the expression: estCode (Car.ord)
\end{lstlisting}




\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 magma associatif admettant un élément neutre est un \textbf{monoïde} (ou un magma
associatif \textbf{unifère}).
\end{definition}

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



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

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

On note souvent ce symétrique $x^{-1_\star}$ ou bien ${-}_\star x$.


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


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


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

\begin{remarque}
  Une loi  de composition externe peut  être distributive par rapport  à une loi
  interne: cherchez un exemple...
\end{remarque}




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


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


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



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






\section{Groupes}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=2.6cm]{Evariste}
\caption{É.\textsc{Galois} (1811-1832)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.2cm}
\begin{minipage}[t]{\linewidth}


Mort dans un duel à l'âge  de vingt ans, Évariste \textsc{Galois} a tout
de même  eu le temps de  révolutionner la mathématique  et ses travaux
ont eu une très grande influence  sur le développement de nombreux domaines liés
à l'informatique: la théorie de
l'information, la spécification, la compilation,etc.



La notion  de groupe  puis d'anneau  et de corps  que nous  allons voir  dans ce
chapitre permettent également d'organiser  très efficacement notre programmation
et de nous initier aux notions de polymorphisme.


Nous    verrons    que   nous    pourrons    également    aborder   la    notion
d'\textit{instantiation} de classes en \HS et de \textit{surcharge} d'opérateur.

Il existe  également de nombreuses  applications en infographie, en  théorie des
langages formels, de la compilation...

\end{minipage}



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

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


Nous travaillerons souvent avec des groupes ayant seulement un nombre
fini d'éléments:


\begin{definition}[Ordre d'un groupe fini]
  Soit $G$ un groupe ayant un nombre fini d'éléments. Le cardinal de
  G est appelé l'\textbf{ordre du groupe} G.
\end{definition}

\section{Anneaux et corps}

\subsection{Anneaux}

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


\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3.2cm]{lord_ring}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{2.8cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

Avez-vous déjà rencontré un anneau dans ce cours?

Dans un anneau, est-ce que tout élément est inversible?


\subsection{Corps}


\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 
  unitaire;
\item                       $\langle
  \bbk\setminus\{e_\boxplus\},\boxdot\rangle$
  a une structure de groupe.
\end{itemize}
\end{definition}




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


Quand $\langle
  \bbk\setminus\{e_\boxplus\},\boxdot\rangle$
  est  un groupe  abélien, le  corps
  $\langle
  \bbk,\boxplus,\boxdot\rangle$  est
  dit commutatif.

En anglais, le terme mathématique pour désigner les corps est \textit{field}.

Il  existe  un   corps  très  important  en  théorie  de   l'information  et  en
cryptographie:  le  corps  $\ofr{\bbz}{2\bbz}$  muni  de  l'addition  et  de  la
multiplication modulaire. On le note
habituellement $\bbf_2$  en français
et $GF(2)$ en anglais.

Vérifiez  qu'il   s'agit  bien  d'un
corps muni des lois habituelles...



\subsection{La classes numériques sur Haskell}


La classe \verb+Num+ de \verb+Prelude+ regroupe les types numériques usuels (\verb+Int+,
\verb+Integer+, \verb+Float+ et \verb+Double+) mais avec des opérations basiques :

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


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

Il existe \og  au-dessus\fg{} une classe \verb+Fractional+ qui  est définie avec
les opérations suivantes:

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

sachant qu'un \verb+Rational+ est, comme son  nom l'indique un élément de $\bbq$
c'est-à-dire le rapport entre deux entiers.

\begin{lstlisting}
Prelude> toRational 1.25
5 % 4
\end{lstlisting}

Mais nous n'insisterons pas sur ce type de données car nous allons...le recréer nous-mêmes!

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

Voici enfin deux autres classes utiles:

\begin{lstlisting}
class  (Num a, Ord a) => Real a  where
    toRational ::  a -> Rational

class  (Real a, Enum a) => Integral a  where
    quot, rem, div, mod :: a -> a -> a
    quotRem, divMod     :: a -> a -> (a,a)
    toInteger :: a -> Integer

class  (Fractional a) => Floating a  where
    pi                  :: a
    exp, log, sqrt      :: a -> a
    (**), logBase       :: a -> a -> a
    sin, cos, tan       :: a -> a
    asin, acos, atan    :: a -> a
    sinh, cosh, tanh    :: a -> a
    asinh, acosh, atanh :: a -> a

class  (Real a, Fractional a) => RealFrac a  where
    properFraction   :: (Integral b) => a -> (b,a)
    truncate, round  :: (Integral b) => a -> b
    ceiling, floor   :: (Integral b) => a -> b
\end{lstlisting}

\subsection{Un nouveau type numérique}

Il  est  possible  de  créer  un nouveau  type  numérique.  Selon  sa  structure
algébrique, on en fera une instance de \verb+Num+ ou de \verb+Fractional+.



\section{Structure d'espace vectoriel}


\subsection{Un peu d'histoire}



%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3.2cm]{grassmann}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.375cm}
\begin{minipage}[t]{\linewidth}


Hermann \textsc{Gra\ss mann} (1809-1877) est un mathématicien allemand
hors du  commun. Il enseigna  principalement au lycée  des disciplines
aussi  diverses que  les  mathématiques, la  physique, l'allemand,  le
latin et la théologie. Il commence  à publier les fondements de ce qui
deviendra la théorie des espaces  vectoriels mais le rapporteur de ses
travaux les lit d'un \oe il distrait et passe totalement à côté.

\textsc{Gra\ss  mann}  persiste  et  publie en  1844  \og  \textit{Die
  lineale  Ausdehnungslehre,  ein  neuer  Zweig  der  Mathematik}\fg{}
(l'enseignement de  l'extension linéaire,  une nouvelle branche  de la
mathématique) qui passe encore inaperçu car \textsc{Gra\ss mann} n'est
pas un universitaire. Ses travaux  ne seront reconnus qu'après sa mort
lorsque  l'italien \textsc{Peano}  donne une  présentation axiomatique
des espaces vectoriels dérivée des travaux de \textsc{Gra\ss mann}.

Enfin c'est un  jeune polonais, Stefan \textsc{Banach},  qui, en 1920,
propulsa  les  espaces vectoriels  en  dehors  de la  sphère  purement
géométrique  et  en  fit  un   des  outils  majeurs  de  développement
scientifique.



\end{minipage}

\subsection{Vers une définition}


Considérons le vecteur Marylin et le
vecteur Albert. Voici trois nouveaux
vecteurs  obtenus   par  différentes
combinaisons: 
 $3\times      \text{Marylin}      +
 \text{Albert}$, 
       $   \text{Marylin}    +
      \text{Albert}$ et $ \text{Marylin} + 3\times\text{Albert}$
    

\setindent{0cm}

\begin{center}
\begin{multicols}{3}
  

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



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




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


\end{multicols}
\end{center}

\setindent{\indentationcours}


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3.2cm]{banach}
\caption{S. \textsc{Banach} (1892-1945)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.375cm}
\begin{minipage}[t]{\linewidth}


On voit clairement  apparaître la notion de produit externe  : ici les
vecteurs sont des  images qui peuvent être additionnées  et rester des
images. De  plus, on peut multiplier  une image par un  nombre et cela
reste une image.

On est souvent confronté à cette  situation: un groupe, un corps et un
produit externe des éléments du corps sur les éléments du groupe.

On peut par  exemple combiner des octets, des  fonctions...et même des
vecteurs du plan.

Mais il  ne faut pas lier  des opérations de manière  trop hasardeuse:
cela  pourrait  réserver de  fâcheuses  surprises.  C'est pourquoi  on
impose des  liens étroits  entre les deux  opérations, comme  pour les
corps.


Un \textbf{espace  vectoriel $V$  sur un corps  $\bbk$} est  un groupe
additif muni d'une loi de composition externe. 

Les  éléments  du  corps  sont  appelés  les  \textbf{scalaires},  les
éléments de $V$ sont appelés les \textbf{vecteurs}.


Bon, soyons plus formels:


\end{minipage}

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


On pourrait se  demander pourquoi on n'a pas poussé  $V$ jusqu'à avoir
une multiplication, tant qu'à  faire....Mouais...mais s'il est naturel
d'additionner des  images en leur  affectant des coefficients,  il est
moins naturel  d'imaginer une  multiplication d'images (et  c'est même
mathématiquement compromis).

Il est donc plus naturel de se contenter d'un groupe.

Souvent sur papier (mais pas sur machine :-) ), par paresse, on omet
les symboles de produit externe et  de produit interne, mais cela peut
prêter à confusion, surtout lors  de notre phase d'apprentissage, donc
nous n'en ferons rien.

\begin{remarque}
  Pour  obtenir  les  combinaisons d'images  précédentes,  nous  avons
  utilisé  \verb+NumPy+  et  la   syntaxe  est  très  orientée  espace
  vectoriel:


\pythonc

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

\haskell

\end{remarque}


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


On  considère l'ensemble $T$ des chaînes  de  3 bits  muni de  l'addition
canonique:

$$\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$$
avec $\oplus$ l'addition sur $\bbf_2$: 

$$0\oplus 0=1\oplus 1=0 \quad \text{et} \quad 0\oplus 1= 1\oplus 0 =1$$


On muni $\bbf_2$ de sa multiplication canonique:

$$0\odot 0=0\odot 1=1\odot 0 =0 \quad \text{et} \quad 1\odot 1= 1$$

Ainsi  $\langle \bbf_2,\oplus,\odot\rangle$  est un  corps, $\langle
T,\dagger\rangle$ est un groupe abélien.

Le produit externe est:
$$
 (\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}
 $$


Il reste à vérifier les quatre axiomes (faites-le...)

Sur \HS:


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


donne par exemple:

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



On peut alors tester l'axiome de distributivité scalaire par exemple :

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

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


Dans  un  espace vectoriel,  les  opérations  \og linéaires\fg{}  sont
l'addition du groupe et le produit externe.

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


Par exemple,  prenons le $\bbr$-espace  vectoriel $\bbr^2$ muni  de la
somme et du produit externe canonique.

On peut  dire que $\mathbf{v}=\langle 4,3\rangle$  est une combinaison
linéaire   de    $\mathbf{u_1}=\langle   2,1\rangle$    et   $\mathbf{u_2}=\langle
0,3\rangle$:

$$\mathbf{v}= 2\mathbf{u_1}+ \frac{1}{3} \mathbf{u_2}$$


On peut  alors légitimement se  demander ce que  représente l'ensemble
des combinaisons linéaires d'une famille fixée de vecteurs.

Par  exemple, travaillons  dans $\bbf_2^3$  en tant  que $\bbf_2$-espace
vectoriel  muni des  opérations  canoniques. Quelles  sont toutes  les
combinaisons linéaires des vecteurs $\langle 0,1,1\rangle$ et $\langle 1,0,1\rangle$?

Vérifiez les résultats  donnés par \HS avec  les fonctions introduites
précédemment:

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

Donne:

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

\subsection{Sous-espace vectoriel}

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



Il   serait   bête   de   vérifier   tous   les   critères   pour   un
sous-espace. Démontrez les caractérisations suivantes:

\begin{theoreme}[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{theoreme}


Démontrez qu'on peut être plus synthétique:

\begin{theoreme}[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{theoreme}




%%%%
%
%                                      E X E R C I C E S 
%
%%%%%%%%


\vfill

\eject

\modeexercice
\section{EXERCICES}

%
\subsection{LCI}
%




\begin{exercice}[Have  you  got  the
  power?]\label{exo::1}

On considère la LCI $\star$ définie sur
$\bbz$ par:

$$a\star b = a - b$$



L'écriture $a^3$ a-t-elle un sens?
\end{exercice}

\begin{exercice}[Have  you  got  the
  power now?]\label{exo::2}


On considère la LCI $\star$ définie sur
$\bbz$ par:

$$a\star b = a^b$$

L'écriture $a^3$ a-t-elle un sens?

\end{exercice}

\begin{exercice}[And now?]\label{exo::3}
  On considère la LCI définie sur $\bigl\{a,b,c,d\bigr\}$ par:

  \begin{center}
    \begin{tabularx}{0.5\linewidth}{Y{3}}
      \whline
      $\star$&$a$&$b$&$c$&$d$\\
      \whline
      $a$&$b$&$c$&$d$&$a$\\
      \hline
      $b$&$d$&$a$&$b$&$c$\\
      \hline
      $c$&$a$&$b$&$c$&$d$\\
      \hline
      $d$&$c$&$d$&$a$&$b$\\
      \whline
    \end{tabularx}
  \end{center}

L'écriture $a^3$ a-t-elle un sens?

\end{exercice}




\begin{exercice}[Avec Haskell]
On peut facilement  construire une classe définissant les magmas:  c'est un type
(qui  correspond pour  nous à  un ensemble)  qu'on notera  de manière  générique
\verb+t+,
muni d'une loi qu'on notera de manière
générique \verb|<+>|. 

\begin{lstlisting}
class Magma t where
  (<+>) :: t -> t -> t
\end{lstlisting}

Pour que notre ensemble  muni de sa loi soit un magma, il  faut et il suffit que
cette loi soit associative. On crée donc un test:

\begin{lstlisting}
isMagmaAssociatif :: (Magma t, Eq t) => (t,t,t) -> Bool
isMagmaAssociatif (a,b,c) = (a <+> b) <+> c == a <+> (b <+> c)
\end{lstlisting}

Comment fait un mathématicien pour vérifier  que \verb+Integer+ muni de la somme
\verb|+| a une structure de magma associatif? Il démontre que la loi est associative.

Que fait un informaticien qui a dormi en cours? Il fait des tests.

Il existe sur \HS un module \verb+QuickChek+ qui va nous aider ici:

\begin{lstlisting}
import Test.QuickCheck
\end{lstlisting}


On  commence  par   faire  de  \verb+Integer+  une  instance   de  notre  classe
\verb+Magma+ en prenant comme loi l'addition des entiers: 

\begin{lstlisting}
instance Magma Integer where
  (<+>) = (+)
\end{lstlisting}

Écrivons  notre  test (\verb+quickCheck+  fait  en  fait  100  tests sur  des  triplets
aléatoirement choisis selon une loi uniforme):

\begin{lstlisting}
test1 = quickCheck (isMagmaAssociatif :: (Integer,Integer,Integer) -> Bool)
\end{lstlisting}

C'est bon pour 100, c'est bon pour tous dit un apprenti informaticien:

\begin{lstlisting}
*Main> test1
+++ OK, passed 100 tests.
\end{lstlisting}

Mais, comme le disait Edsger \textsc{Dijkstra} (1930 - 2002), prix \textsc{Turing} 1972:

\begin{quote}
  {\itshape
Program testing can be used to show the presence of bugs, but never to show their absence! 
}
\end{quote}
\begin{flushright}
 in \og Notes On Structured Programming, corollary at the end of section 3, On The Reliability of Mechanisms\fg{} (EWD249).
\end{flushright}


Maintenant,  faites  un  \verb+quickCheck+  sur les  exercices  \ref{exo::1}  et
\vref{exo::2}.

Pour l'exercice \vref{exo::3}, on peut faire une preuve.

Définissons notre loi et son ensemble:

\begin{lstlisting}
data Truc = A | B | C | D deriving(Show,Eq)

lesTrucs = [A,B,C,D]

plus :: Truc -> Truc -> Truc
plus A A = A
plus A B = C
plus A C = D
plus A D = A
plus B A = D
plus B B = A
plus B C = B
plus B D = C 
plus C A = A
plus C B = B
plus C C = C 
plus C D = D
plus D A = C
plus D B = D
plus D C = A
plus D D = B

instance Magma Truc where
  (<+>) = plus
\end{lstlisting}


Maintenant, on peut tester toutes les possibilités:

\begin{lstlisting}
testa = all isMagmaAssociatif  [(a,b,c) | a <- lesTrucs, b <- lesTrucs, c <- lesTrucs]
\end{lstlisting}

Argh:

\begin{lstlisting}
*Main> testa
False
\end{lstlisting}

Quel est le premier cas qui pose problème?


\begin{lstlisting}
*Main> Data.List.find (not.isMagmaAssociatif)  [(a,b,c) | a <- lesTrucs, b <- lesTrucs, c <- lesTrucs]
Just (A,A,B)
\end{lstlisting}

\end{exercice}


\begin{exercice}
  On considère l'opération définie sur $\bbz$ par:
  $$a\top b = a + 2b$$
  Cette opération est-elle une LCI? Est-elle commutative? Associative? etc.

Même question avec la loi définie sur $\bbq$ par $a\dagger b = (a+b)/2$.
\end{exercice}


\begin{exercice}
  On considère l'opération $\nand$ définie sur $\bbn_1$ par:
  $$ a\nand 1 = a,\quad a\nand b = a \times (a \nand (b-1))$$
  Cette opération vous  rappelle-t-elle quelque chose? Est-ce  une LCI? Est-elle
  commutative? Associative? etc.

Cherchez un élément régulier à droite mais pas à gauche.
\end{exercice}


\begin{exercice}
  On considère l'opération  de concaténation de listes dont  l'opérateur sur \HS
  est \verb|++|. Est-elle commutative? Associative?
\end{exercice}

\begin{exercice}
  A, B et C étant des ensembles, que pensez-vous de $A \cap B \cup C$?
\end{exercice}

\begin{exercice}
  Que  pensez-vous de  la soustraction  des  entiers? Du  produit cartésien  des
  ensembles? De la composition des  relations? De la multiplication d'un vecteur
  du plan par un réel? etc.
\end{exercice}



\begin{exercice}
  On définit une opération sur les quadruplets de nombres réels:
  $$(a,b,c,d) \odot (α,β,γ,δ) = (aα + bγ,aβ+bδ,cα+dγ,cβ+dδ)$$
  Est-elle commutative? Associative? 
\end{exercice}


\begin{exercice}
  Donnez  des  exemples  de  couples
  $\langle E,\star\rangle $ avec $\star$ une application
  définie sur $E\otimes E$ telle que
  $\langle E,\star\rangle $ ne soit pas un magma.
\end{exercice}



\begin{exercice}
  Soit  $A=\bigl\{a_1,a_2,...,a_p\bigr\}$ un  ensemble  de  caractères. On  note
  $A^\star$  l'ensemble  des chaînes  de  caractères  construites à  partir  des
  caractères de A.
  \begin{enumerate}
  \item $A^\star$ muni de la concaténation des chaînes a-t-il 
    une structure de magma associatif? de monoïde?
  \item  Les ensembles
    suivants munis de la
    concaténation sont-ils des magmas associatifs?  Des monoïdes?
    \begin{enumerate}
    \item L'ensemble des chaînes de longueur paire;
    \item L'ensemble des chaînes de longueur impaire;
    \item $\bigl\{(a_1a_2)^n\quad\mid\quad  n\in \bbn\bigr\}$;
    \item $\bigl\{a_1^na_2^n\quad\mid\quad  n\in \bbn\bigr\}$;
    \item L'ensemble  des chaînes ne  contenant que $a_1$ et  $a_2$, ceux-ci
      apparaissant un nombre égal de fois.
    \end{enumerate}
  \end{enumerate}
\end{exercice}


\begin{exercice}
Soit $\bbb_2=\bigl\{0,1\bigr\}$ l'ensemble des  booléens. Est-ce que $\bbb_2$ muni
de NAND est un monoïde? Muni de NOR?
\end{exercice}


\begin{exercice}
  Soit l'opération  $\intercal$ définie  par $x\intercal y=  \sqrt{x^2+y^2}$. Est-ce
  que $\langle \bbr,\intercal\rangle
  $ est un magma associatif?  Un monoïde? Un monoïde simplifiable? Y a-t-il un élément absorbant?
\end{exercice}




\begin{exercice}[Curryfication, parenthèse et associativité]

On  considère  une fonction  

$$
 f\colon \begin{array}{rll} E\otimes F & \to & G\\
   \langle x,y\rangle & \mapsto & f(\langle x,y\rangle)
 \end{array}
 $$



Pour chaque $x$ de $E$, on peut donc définir une fonction $f_x$:

$$
f_x\colon \begin{array}{rll} F & \to & G\\
   y & \mapsto & f(\langle x,y\rangle)
 \end{array}
$$

Que pouvez-vous dire de la fonction: $\varphi : x \mapsto f_x$ (domaine, codomaine,lien avec $f$)?

Pouvez-vous, inversement, associer une fonction $f$ à une fonction du type $\varphi$?

Notons $C$ la fonction qui à une fonction $f$ de $E\otimes F$ dans $G$ associe la fonction $\varphi$ selon le mécanisme précédent.

Quelle est la signature de $C$? Quelle propriété intéressante possède $C$ concernant notre utilisation de \HS? 

On dit que $C(f)$ est la fonction currifiée de $f$

Ici, vous entamez un débat avec vos camarades et votre professeur au sujet de ces problèmes et vous les liez à votre cours :)

Notez pour finir que \HS a tout prévu...

\begin{lstlisting}
Prelude> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
Prelude> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c
\end{lstlisting}

\end{exercice}




\begin{exercice}[Notation polonaise]



%\piccaption{Jan \textsc{\L ukasiewicz} \\ (1878-1956)}

 \parpic{ \includegraphics[width=2.5cm]{lukasiewicz} }


En   1920,   le   mathématicien-logicien-philosophe  polonais   Jan   \textsc{\L
  ukasiewicz}  invente  la  notation  préfixée   alors  qu'il  est  ministre  de
l'éducation (on a le droit de rêver...).

35 ans  plus tard, le philosophe  et informaticien (!) australien  (!!!) Charles
\textsc{Hamblin} (1922 - 1985) s'en inspire.

Il a en effet en sa possession  l'un des deux ordinateurs présents à l'époque en
Australie. Il  se rend compte  que la saisie de  calculs avec les  opérateurs en
notation  infixée  induit   de  nombreuses  erreurs  de  saisie   par  oubli  de
parenthèses.  Il pense  aussi  à la  (très petite)  mémoire  des ordinateurs  de
l'époque.

% \end{minipage}
% \setindent{0cm}

%\piccaption{Charles \textsc{Hamblin} \\ (1922-1985)}
\parpic[r]{ \includegraphics[width=2.5cm]{hamblin}}



Il trouve alors  son inspiration dans le travail de  \textsc{\L ukasiewicz} pour
éviter les parenthèses et il
 pense à mettre les opérateurs en position préfixée:
ainsi  il   introduit  la   notion  de   \textit{pile}  (ou   \textit{stack}  ou
\textsc{Lifo}) qui économise le nombre d'adresses mémoire nécessaire.


C'est  la  naissance de  la  Notation  Polonaise  Inversée  (NPI ou  RPN).  Elle
économise également la taille des composants électroniques des portes logiques.

Son seul inconvénient:  les mauvaises habitudes prises  d'utiliser des notations
infixées.




Un autre grand avantage: il faut comprendre le calcul avant de l'exécuter :)

Ouvrez emacs  et tapez \verb+M-x  calc RET+.  Vous pouvez alors  faire n'importe
quel  calcul  arithmétique  en  voyant chaque  résultat  intermédiaire  et  sans
parenthèse.


\begin{multicols}{2}
Par exemple, la séquence
%\begin{center}
  \verb|2 3 4 + *|
%\end{center}
donne::

\emacs


\begin{lstlisting}[caption={}]
--- Emacs Calculator Mode ---
3:  2
2:  3
1:  4
--- Emacs Calculator Mode ---
2:  2
1:  7
--- Emacs Calculator Mode ---
1:  14
\end{lstlisting}

Mais 
%\begin{center}
  \verb|2 3 + 4 *|
%\end{center}
donne:

\begin{lstlisting}[caption={}]
--- Emacs Calculator Mode ---
2:  2
1:  3
--- Emacs Calculator Mode ---
2:  5
1:  4
--- Emacs Calculator Mode ---
1:  20
    .
\end{lstlisting}
\end{multicols}


Que donne \verb|10 4 3 + 2 * -|?


Entraînez-vous à passer de la notation infixe à la NPI et vice-versa. Donnez vos
exemples à votre voisin(ne) à titre d'exercice.


{\itshape
En \HS,  une machine  à calculer fonctionnant  en NPΙ se  programme en  5 lignes
comme vous pourrez  le voir sur le  tutoriel \og apprendre Haskell  vous fera le
plus grand bien\fg{}...
}
\haskell


\end{exercice}















%
\subsection{Groupes}
%



\begin{exercice}
\begin{enumerate}
\item   $\bbb_2$ muni des opérations suivantes est-il un groupe:

  \begin{multicols}{3}
    \begin{enumerate}
    \item $\land$? \item $\lor$? \item $\oplus$?
    \end{enumerate}
  \end{multicols}

\item Résoudre dans $\bbb_2$ l'équation $a\oplus x = b$.
\end{enumerate}
\end{exercice}

\begin{exercice}
  Soit $\langle G,\star\rangle $ un groupe et $a$ et $b$ deux éléments de $G$.  Exprimez
  l'inverse de $a\star b$ en fonction des inverses de $a$ et de $b$.
\end{exercice}






\begin{exercice}
  Les    tables    ci-dessous    définies   sur    $E=\bigl\{a,b,c\bigr\}$
  définissent-elles des magmas associatifs? des monoïdes?

  \begin{multicols}{2}
    \begin{tabularx}{0.7\linewidth}{Y{2}}
      \whline
      $\star$&$a$&$b$&$c$\\
      \whline
      $a$&$a$&$b$&$c$\\
      \hline
      $b$&$b$&$c$&$a$\\
      \hline
      $c$&$c$&$a$&$b$\\
      \whline
    \end{tabularx}
    
    \begin{tabularx}{0.7\linewidth}{Y{2}}
      \whline
      $\bot$&$a$&$b$&$c$\\
      \whline
      $a$&$a$&$c$&$c$\\
      \hline
      $b$&$b$&$c$&$a$\\
      \hline
      $c$&$c$&$a$&$a$\\
      \whline
    \end{tabularx}
  \end{multicols}
  
  Notons $A=\bigl\{a,b,c\bigr\}$.
  Montrez        que        $\langle
  A,\star\rangle $ a une structure de groupe. Comparer ce groupe
  avec 
  \begin{itemize}
  \item                $\left\langle
      \ofr{\Z}{3\Z},\overline{+}\right\rangle
    $ 
  \item $\left\langle \bigl\{1,\mathrm{e}^{\ofr{2\pi}{3}},\mathrm{e}^{\ofr{-2\pi}{3}}\bigr\},\times\right\rangle$.
  \end{itemize} 
\end{exercice}




\begin{exercice}[Avec Haskell]
  Comme nous l'avons fait avec les magmas et les monoïdes, on peut créer une classe
  \verb+Groupe+  dérivant de  \verb+Monoide+ et  créer  les tests  qui vont  bien:
  \verb+Just+ do it!
\end{exercice}







\begin{exercice}[Déplacement à partir du pavé numérique]

À  chaque  touche  du  pavé  numérique,  on  fait  correspondre  un  déplacement
élémentaire d'un point  sur l'écran: 6 pour un déplacement  unitaire à droite, 2
pour un déplacement unitaire vers le bas, etc.

On  note $D$  l'ensemble  de  ces dix  déplacements  et  $D^\star$ l'ensemble  des
séquences de déplacements.

Définir $D^*$ comme un monoïde. Montrez que c'est un groupe abélien.
  

Que se passe-t-il si  au lieu de déplacements on considère  la trace laissée par
ces déplacements? 
\end{exercice}


\begin{exercice}[Caractérisation d'un sous-groupe]

La programmation, c'est l'efficacité... La définition d'un sous-groupe n'est pas
efficace: pouvez-vous en donner une caractérisation plus synthétique?
  
\end{exercice}







\begin{exercice}
 Est-ce que l'ensemble $\bigl\{x+y \sqrt{2} \mid (x,y)\in \bbq^2\bigr\}$ muni de
 la multiplication des réels a une structure de groupe?
\end{exercice}


\begin{exercice}[Du CM1 à la 6\eme :-)]
  
%\begin{figure}
\begin{center}
  \includegraphics[scale=1.1]{groupe_cm1}
\end{center}
%\end{figure}


Adaptez le texte précédent aux notations introduites lors de l'étude des classes
d'équivalence..

Comment  généraliser les  résultats en  terme  de groupe?  (Attention, on  passe
maintenant au programme de 6\eme des années 1970...)


Nous en aurons besoin pour implémenter le calcul modulaire en \HS....


\end{exercice}





\begin{exercice}[Ordre d'un élément dans un groupe fini]
  \begin{enumerate}
\item Comment justifier que pour tout élément $g$ d'un groupe fini $(G,\cdot)$,
il existe  un plus petit  entier $n$ tel  que $g^n=1_G$? On  appelle $n$
l'ordre de $g$.
\item Déterminez l'ordre des éléments de $\left(\ofr{\bbz}{9\bbz}\right)^*$.
\item Calculez $2^{1200000000003000000000600000002000040000020}[7]$.
  \end{enumerate}
\end{exercice}




\begin{exercice}[Permutations]
\setindent{\indentationcours}
  \begin{definition}[Permutation]
    Soit  E  un ensemble.  Une  permutation  de  E est  une  application
    bijective  de E  sur  E. On  note  $\mathfrak{S}(E)$ l'ensemble  des
    permutations de E.
  \end{definition}
\setindent{0cm}

Généralement, on  note les permutations  sous forme d'une matrice  où la
première  ligne correspond aux  éléments de  E et  où la  deuxième ligne
correspond aux images des éléments de E.

Par exemple:


$$
\begin{pmatrix}
  1&2&3&4&5\\
3&1&2&5&4
\end{pmatrix}
$$

est une permutation de $E=\bigl\{1,2,3,4,5\bigr\}$.

\setindent{\indentationcours}
\begin{definition}
  Soit  $n\in\bbn$,   alors  $\mathfrak{S}_n$  désigne   l'ensemble  des
  permutations de $\bigl\{1,2,3,...,n\bigr\}$.
\end{definition}

\begin{theoreme}[Groupe des permutations]\label{th::groupe_perm}
  L'ensemble $\mathfrak{S}(E)$ des permutations  sur un ensemble E, muni
  de la loi $\circ$ de composition des applications, a une structure de groupe.
\end{theoreme}

\begin{theoreme}[Nombre de permutations]\label{th::nb_perm}
  Le groupe $\mathfrak{S}_n$ est d'ordre $n!$.
\end{theoreme}
\setindent{0cm}

\begin{enumerate}
\item Démontrez le théorème \vref{th::groupe_perm}.
\item Démontrez le théorème \vref{th::nb_perm}.  Vous pourrez procéder par
      récurrence.  Pour  l'hérédité,  distinguez  les  permutations  qui
      envoient 1 sur un élément quelconque $x$.
\item Décrivez explicitement les groupes $\mathfrak{S}_2$ et $\mathfrak{S}_3$.
\item    En    cryptographie,     on    travaillera    sur    l'alphabet
      $E=\bigl\{0,1\bigr\}^n$ et on  effectuera souvent des \textit{permutations
      de bits} : seuls les positions des bits sont permutées.

On formalise ces permutations ainsi:
$$
 f\colon \begin{array}{rll} \bigl\{0,1\bigr\}^n & \to & \bigl\{0,1\bigr\}^n\\
   b_1b_2\cdots b_n& \mapsto & b_{\pi(1)}b_{\pi(2)}\cdots b_{\pi(n)}
 \end{array}
 $$

avec $\pi\in \mathfrak{S}_n$.

Une \textit{permutation circulaire  gauche} \og décale\fg{} les éléments
d'un nombre fixé  de \og rangs\fg{}. Par exemple,  voici une permutation
circulaire gauche:

$$
\begin{pmatrix}
  1&2&3&4&5\\
  3&4&5&1&2
\end{pmatrix}
$$

Décrire $\pi(k)$ dans le cas d'une permutation circulaire de bits de $i$
rangs vers la gauche.

On définit de même des permutations circulaires droite.

Combien y a-t-il de permutations circulaires dans $\mathfrak{S}_n$?

\end{enumerate}

\end{exercice}




\begin{exercice}[\textsc{Hamilton} et les couples]
  
Le  mathématicien irlandais  William Rowan  \textsc{Hamilton}  (1805-1865) publie en
1837    \textit{Theory   of    Conjugate    Functions,   or    Algebraic
  Couples}                                                    :
   (\href{http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/PureTime/PureTime.pdf}{http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/PureTime/PureTime.pdf}).


En voici un extrait:


\begin{quote}
  {\itshape\small

\begin{center}
On the Addition, Substraction, Multiplication, and Division, of
Number-Couples, as
combined with each other.
\end{center}

%\nobreak\bigskip
6.
Proceeding to operations upon number-couples, considered in
combination with each other, it is easy now to see the
reasonableness of the following definitions, and even their
necessity, if we would preserve in the simplest way, the analogy
of the theory of couples to the theory of singles:
$$\langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  = \langle b_1 + a_1, b_2 + a_2\rangle ;
   \eqno ( 52.)$$
$$\langle b_1, b_2\rangle  - \langle a_1, a_2\rangle  = \langle b_1 - a_1, b_2 - a_2\rangle ;
   \eqno (53.)$$
$$\langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
    = \langle b_1, b_2\rangle  \cdot \langle a_1, a_2\rangle 
    = \langle b_1 a_1 - b_2 a_2, b_2 a_1 + b_1 a_2\rangle ;
   \eqno (54.)$$
$${\langle b_1, b_2\rangle  \over \langle a_1, a_2\rangle }
    = \left\langle 
         {b_1 a_1 + b_2 a_2 \over a_1^2 + a_2^2}, \,
         {b_2 a_1 - b_1 a_2 \over a_1^2 + a_2^2}
      \right\rangle .
   \eqno (55.)$$
Were these definitions even altogether arbitrary, they would at
least not contradict each other, nor the earlier principles of
Algebra, and it would be possible to draw legitimate conclusions,
by rigorous mathematical reasoning, from premises thus
arbitrarily assumed: but the persons who have read with attention
the foregoing remarks of this theory, and have compared them with
the Preliminary Essay, will see that these definitions are really
{\it not arbitrarily chosen}, and that though others might have
been assumed, no others would be equally proper.

With these definitions, addition and subtraction of
number-couples are mutually inverse operations, and so are
multiplication and division; and we have the relations,
$$\langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  = \langle a_1, a_2\rangle  + \langle b_1, b_2\rangle ,
   \eqno (56.)$$
$$\langle b_1, b_2\rangle  \cdot \langle a_1, a_2\rangle  = \langle a_1, a_2\rangle  \cdot \langle b_1, b_2\rangle ,
   \eqno (57.)$$
$$\langle b_1, b_2\rangle  ( \langle a_1', a_2'\rangle  + \langle a_1, a_2\rangle  )
   =  \langle b_1, b_2\rangle  \langle a_1', a_2'\rangle  + \langle b_1, b_2\rangle  \langle a_1, a_2\rangle :
   \eqno (58.)$$
we may, therefore, extend to number-couples all those results
respecting numbers, which have been deduced from principles
corresponding to these last relations.  For example,



$( \langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  ) \cdot
  ( \langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  )
   =  \langle b_1, b_2\rangle  \langle b_1, b_2\rangle 
    + 2 \langle b_1, b_2\rangle  \langle a_1, a_2\rangle \\
    + \langle a_1, a_2\rangle  \langle a_1, a_2\rangle ,
   \hfill (59.)$


in which


$$2 \langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
   =  \langle 2, 0\rangle  \langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
   =  \langle b_1, b_2\rangle  \langle a_1, a_2\rangle  + \langle b_1, b_2\rangle  \langle a_1, a_2\rangle ;
   \eqno (60.)$$
for, in general, we may {\it mix the signs of numbers with those
of number-couples}, if we consider every single number~$a$ as
equivalent to a pure primary number-couple,
$$a = \langle a, 0\rangle .
   \eqno (61.) $$
When the pure primary couple $\langle 1, 0\rangle $ is thus considered as
equivalent to the number~$1$, it may be called, for shortness,
the {\it primary unit\/}; and the pure secondary couple $\langle 0, 1\rangle $
may be called in like manner the {\it secondary unit}.

We may also agree to write, by analogy to notations already
explained,


\begin{eqnarray*}
  \langle 0, 0\rangle  + \langle a_1, a_2\rangle  &=& + \langle a_1, a_2\rangle ,\\
\langle 0, 0\rangle  - \langle a_1, a_2\rangle  &=& - \langle a_1, a_2\rangle ;
   \quad (62.)\\
\end{eqnarray*}


and then $+ \langle a_1, a_2\rangle $ will be another symbol for the
number-couple $\langle a_1, a_2\rangle $ itself, and $- \langle a_1, a_2\rangle $ will be a
symbol for the {\it opposite number-couple\/} $\langle - a_1, - a_2\rangle $.
The {\it reciprocal\/} of a number-couple $\langle a_1, a_2\rangle $ is this
other number-couple,
$${1 \over \langle a_1, a_2\rangle }
   =  {\langle 1, 0\rangle  \over \langle a_1, a_2\rangle }
   =  \left\langle 
         {a_1 \over a_1^2 + a_2^2},
         {- a_2 \over a_1^2 + a_2^2}
      \right\rangle 
   =  {\langle a_1, - a_2\rangle  \over a_1^2 + a_2^2}.
   \eqno (63.)$$
It need scarcely be mentioned that the insertion of the sign of
coincidence~$=$ between any two number-couples implies that those
two couples coincide, number with number, primary with primary,
and secondary with secondary; so that {\it an equation between
number-couples is equivalent to a couple of equations between
numbers}.

}
\end{quote}


Vous ferez de ce texte un commentaire composé :)




\end{exercice}





\begin{exercice}[\textsc{Hamilton} is back : ze quaternions]


\parpic{\includegraphics[width=7cm]{hamilton}}
Après avoir  travaillé, comme nous  l'avons vu,  sur les nombres  complexes, Sir
William (il a été anobli en 1835) voulut étendre ses travaux à la dimension 3. 
Il n'arrivait cependant pas à  imaginer une multiplication qui puisse satisfaire
des critères intéressants, notamment la conservation des normes.\\
Un  jour qu'il  se promenait  avec son  épouse dans  un parc  dublinois, il  eut
soudain un  éclair qu'il  s'empressa de  graver sur  la pierre  du pont  le plus
proche :

$${\rm i}^2 = {\rm j}^2={\rm k}^2= {\rm ijk} = -1$$

Remplissez alors la table de multiplication suivante:

\begin{center}
  \begin{tabularx}{0.4\linewidth}{Y{3}}
    \whline
    $\times$ & 1 & i & j & k \\
    \whline
    1        &  &  &  &  \\
    \hline
    i        &  &  &  &  \\
    \hline
    j        &  &  &  &   \\
    \hline
    k        &  &  &  &   \\
    \whline
  \end{tabularx}
\end{center}


\textsc{Hamilton} définit alors  un \textit{quaternion} par la  donnée de quatre
réels $a$,  $b$, $c$ et  $d$ car un quaternion  peut s'écrire de  manière unique
comme combinaison des quatre quaternions élémentaires:

$$q = a1 + b{\rm i} + c{\rm j} + d{\rm k}$$

Le nombre  $a$ est  la partie  scalaire et  le triplet  $(b,c,d)$ est  la partie
vectorielle  (c'est \textsc{Hamilton}  qui  a  en effet  introduit  le terme  de
\textit{vecteur} en mathématique).

Quelles propriétés possède ou ne possède pas la multiplication des quaternions?


{\itshape
  Il y a énormément  de choses à dire sur les quaternions  mais nous manquons un
  peu de recul mathématique...

  Point  de vue  informatique, il  faut  cependant noter  qu'ils sont  largement
  utilisés  en  infographie,  en  traitement  du signal  et  dans  tout  domaine
  utilisant des rotations et entraînant de nombreux calculs. 

  En  physique,  ces  calculs  sont traditionnellement  traités  par  du  calcul
  matriciel mais nous verrons bientôt  que celui-ci induit de nombreuses erreurs
  d'arrondis qui peuvent être atténuées en passant par les quaternions.


  Un site  à visiter :  \href{http://www.alcys.com/}{http://www.alcys.com/}. Les
  quaternions  apparaissent  sous  vos   yeux  ébaubis....
}


\end{exercice}



\subsection{Anneaux et corps}

\begin{exercice}[C'est fini]
  Soit $E=\bigl\{1,2,3,5,6,10,15,30\bigr\}$.

Pour tout couple $\langle a,b\rangle$ d'éléments de $E$, on note $a\wedge b$ le PGCD de $a$ et $b$ et $a\vee b$
le PPCM de $a$ et $b$. 

Quelle est la  structure de $\langle
E,\wedge,\vee\rangle $?  De $\langle
E,\vee,\wedge\rangle $?
\end{exercice}


\begin{exercice}[Les Bool]
Quelle    structure     possède    $
\left\langle \bigl\{\verb+True+ ,
  \verb+False+\bigr\},\land,\lor\right\rangle $ ? Et $ \left\langle\bigl\{\verb+True+ ,
  \verb+False+\bigr\},\lor,\land\right\rangle $
\end{exercice}

\begin{exercice}[Les parties]
  Soit $E$ un ensemble. Quelle structure possède $ \left\langle\PR(E),\cap,\cup\right\rangle 
$? $ \left\langle\PR(E),\cup,\cap\right\rangle 
$? 
\end{exercice} 

\begin{exercice}[Isomorphisme]
Montrez que $\langle \bbf_2,+\rangle $ et $\langle \ofr{\bbz}{4\bbz}^\star , \cdot\rangle $ sont isomorphes.

Est-ce que $\langle \ofr{\bbz}{4\bbz} , +\rangle $ et $\langle \ofr{\bbz}{5\bbz}^\star , \cdot\rangle $ sont
isomorphes?

Est-ce que $\langle \ofr{\bbz}{4\bbz} , +\rangle $ et $\langle \ofr{\bbz}{8\bbz}^\star , \cdot\rangle $ sont
isomorphes?

Est-ce que $\langle \bbf_2\otimes \bbf_2, +\rangle $ et $\langle \ofr{\bbz}{8\bbz}^\star , \cdot\rangle $ sont
isomorphes?
\end{exercice}



\begin{exercice}[Un type Rationnel sur Haskell]
 Qu'est-ce qu'un  rationnel? \textit{Ratio}  est un mot  latin, qui  désignait un
 calcul  mais  qui   a  donné  en  français  le  mot   \textit{raison}.  Le  mot
 \textit{ratio} est passé en anglais pour désigner un indice en comptabilité: le
 rapport entre deux quantités de même nature.
 Ce mot a été importé de l'anglais de spécialité par les financiers.

 En mathématique, un \textit{nombre rationnel} est \og \textbf{construit}\fg{} à partir d'un couple d'entiers
 relatifs, le deuxième étant non nul.  
 Le premier est appelé \textit{numérateur}, le second \textit{dénominateur}.
 
 Oui  mais  comment  s'effectue  cette  \og construction\fg{}?  On  a  une  idée
 intuitive  de  la réponse:  on  veut  qu'un \textit{ratio}nnel  représente  une
 proportion. Par exemple, si  Daniel a 5 billes bleues parmi ses  8 billes et si
 Fabienne a 10 billes  bleues parmi ses 16 billes, les deux  enfants ont la même
 proportion  de billes  bleues.  On  voudrait alors  que  cette proportion  soit
 désignée par le même nombre rationnel.

On voudrait donc  mettre en \textit{relation} tous les  couples $\langle$ nombre
de billes bleues, nombre total de  billes $\rangle$ qui \og représentent\fg{} la
même proportion de billes bleues.

On va donc modéliser cela en considérant la relation:

$$                 \Big(\forall                  \langle                 a,b\rangle{}
\in\bbz\otimes(\bbz\setminus\left\{0\right\})\Big)\Big(\forall    \langle    c,d\rangle{}
\in\bbz\otimes(\bbz\setminus\left\{0\right\})\Big)\Big(        \langle        a,b\rangle
\,\mathcal{R}\,\langle c,d\rangle \lequiv ad=bc\Big) $$


Il est facile de vérifier que $\RR$ est une relation d'équivalence.

Une proportion est alors une classe modulo cette relation d'équivalence.


 On désigne par $\bbq$ l'ensemble quotient de $\bbz\otimes (\bbz\setminus\{0\})$
 modulo $\RR$.

 Cette notation a été
 introduite par  le mathématicien  italien Guiseppe  \textsc{Peano} en  1895 car
 c'est l'initiale du mot italien \og \textit{quoziente}\fg{}.

 $$ \bbq = \ofr{\bbz\otimes (\bbz\setminus\{0\})}{\RR} =
 \bigl\{\big[\langle n, d\rangle\big]_\RR\ |\ \langle n, d\rangle \in \bbz\otimes
 (\bbz\setminus\{0\}) \bigr\}$$

Un nombre rationnel est donc une classe d'équivalence, c'est-à-dire un ensemble!!!


 Sur  \HS,  on  pourrait  garder  telle quelle  cette  idée  et  construire  les
 rationnels à  partir d'ensembles  infinis, mais  c'est informatiquement  un peu
 dangereux.

 On va plutôt adapter cette idée en commençant par \textit{construire} un rationnel à partir d'un
 couple $\langle$ \verb+Integer+, \verb+integer+ $\rangle$. 

Pour ne pas  trop perturber nos habitudes, nous allons  utiliser un constructeur
infixe:

\begin{lstlisting}
data Rationnel =  Integer :/ Integer
\end{lstlisting}

Ici, \verb+:/+ est le \textit{constructeur}  du type \verb+Rationnel+: c'est en
fait une fonction (bien sûr !!):

\begin{lstlisting}
Prelude> :t (:/)
(:/) :: Integer -> Integer -> Rationnel
\end{lstlisting}


 On  aura  souvent besoin  d'utiliser  le  numérateur  ou le  dénominateur  d'un
 rationnel.  

Remarquons tout d'abord que dans chaque classe, il y a un élément plus intéressant que les autres:
lequel? Comment l'obtenir? Comment pensez-vous définir le signe d'un rationnel?




On va donc créer deux fonctions \verb+num+ et
\verb+den+ qui, pour un rationnel donné, vont renvoyer le numérateur et le
dénominateur simplifiés.



Ainsi, on voudrait que le numérateur de \verb+10 :/ 8+ soit 5
et son numérateur soit...?

On dispose de quelques fonctions  utiles définies dans la classe \verb+Integral+
dont voici un extrait de la documentation:

\begin{lstlisting}
Integral numbers, supporting integer division.

Methods

quot :: a -> a -> a
  integer division truncated toward zero

rem :: a -> a -> a
  integer remainder, satisfying (x `quot` y)*y + (x `rem` y) == x

div :: a -> a -> a
  integer division truncated toward negative infinity

mod :: a -> a -> a
  integer modulus, satisfying (x `div` y)*y + (x `mod` y) == x

quotRem :: a -> a -> (a, a)
  simultaneous quot and rem

divMod :: a -> a -> (a, a)
  simultaneous div and mod

toInteger :: a -> Integer
  conversion to Integer 
\end{lstlisting}

\verb+Prelude+ dispose également de la fonction suivante:

\begin{lstlisting}
gcd             :: (Integral a) => a -> a -> a
gcd x y         =  gcd' (abs x) (abs y)
                   where gcd' a 0  =  a
                         gcd' a b  =  gcd' b (a `rem` b)
\end{lstlisting}


Complétez alors les pointillés:

\begin{lstlisting}
num :: Rationnel -> Integer 
num    (x :/ 0)  = error "divide by zero"
num    (x :/ y)  = (...) * (...)


den :: Rationnel -> Integer 
den    (x :/ 0)  = error "divide by zero"
den    (x :/ y)  = ... (...)
\end{lstlisting}

Par exemple, désignons par \verb+x+ le rationnel $\langle 5,3,\rangle$:

\begin{lstlisting}
Prelude> let x = 10 :/ 8
Prelude> num x
5
Prelude> den x
4
\end{lstlisting}


Cependant, on  est un  peu embêté si  l'on veut savoir  si deux  rationnels sont
égaux, c'est-à-dire deux classes d'équivalence sont égales:

\begin{lstlisting}
Prelude> let x = 10 :/ 8
Prelude> let y = 20 :/ 16
Prelude> x == y

<interactive>:31:3:
    No instance for (Eq Rationnel)
      arising from a use of `=='
    Possible fix: add an instance declaration for (Eq Rationnel)
    In the expression: x == y
    In an equation for `it': it = x == y
\end{lstlisting}

Le débugueur de \HS  a été conçu par des gens  tellement intelligents et gentils
qu'il nous  explique comment  faire: on  va faire  du type  \verb+Rationnel+ une
\textit{instance} de la classe de type \verb+Eq+ qui contient tous les types
qui sont des classes d'équivalence.

\begin{lstlisting}
Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool
\end{lstlisting}

Pour cela, on utilise la fonction \verb+instance+:


\begin{lstlisting}
instance Eq Rationnel where
   f1 == f2 = (num f1) * (den f2) == (den f1) * (num f2)
\end{lstlisting}

Maintenant, on peut tester si deux rationnels sont égaux ou non:

\begin{lstlisting}
Prelude> 10 :/ 8 == 20 :/ 16
True
\end{lstlisting}

Pour  améliorer notre  confort  d'utilisation  de GHCi,  nous  allons créer  une
fonction  d'affichage  des rationnels  (un  \og  \textit{pretty print}\fg{})  et
instancier   \verb+Rationnel+  dans   la  classe   \verb+Show+  des   types  \og
montrables\fg{}...


\begin{lstlisting}
instance Show Rationnel where
  show f  
     |den f == 0 = error "divide by zero" 
     |den f == 1 = show (num f) 
     |otherwise  = (show (num f)) ++ "/" ++ (show (den f))
\end{lstlisting}

Par exemple:

\begin{lstlisting}
*Main> 10 :/ (-8)
-5/4
*Main> 10 :/ (-5)
-2
\end{lstlisting}


Il ne reste plus qu'à donner une structure algébrique à \verb+Rationnel+: est-ce
que $\langle \bbq,+,\times\rangle$ a une structure d'anneau? De corps?

Commençons par la structure d'anneau.

Il faut définir une addition et une multiplication: complétez les pointillés...

\begin{lstlisting}
r_plus :: Rationnel -> Rationnel -> Rationnel
r_plus    f1           f2        =  ... :/ ...

r_mult :: Rationnel -> Rationnel -> Rationnel
r_mult    f1           f2        =  ... :/ ...
\end{lstlisting}

Nous pouvons à présent faire de \verb+Rationnel+ une instance de \verb+Num+

Comme évoqué en cours, il nous faut donc définir le sept fonctions de la classe \verb+Num+

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

avec \verb+a+ notre type \verb+Rationnel+ pour que celui-ci en fasse partie.

Complétez alors les pointillés:

\begin{lstlisting}
instance Num Rationnel where
  (+) = ...
  (*) = ...
  negate f =  ... :/ ...
  fromInteger k = ... :/ ...
  abs f = ... :/ ...
  signum f = ... :/ ...
\end{lstlisting}

Alors, par exemple:

\begin{lstlisting}
*Main> 5 :/ 3 + 1 :/ 2
13/6
*Main> 5 :/ 3 - 1 :/ 2
7/6
*Main> 5 :/ 3 * 1 :/ 2
5/6
\end{lstlisting}

Bon, que pensez-vous de l'inverse d'un \verb+Rationnel+?

\begin{lstlisting}
r_inv :: Rationnel -> Rationnel
r_inv f
  |num f == 0 = ...
  |otherwise  = ...
\end{lstlisting}

On peut donc instancier \verb+Fractional+ avec notre \verb+Rationnel+:

\begin{lstlisting}
instance Fractional Rationnel where
  (/) f1 f2 = ...
  fromRational r = (Ratio.numerator r) :/ (Ratio.denominator r)
\end{lstlisting}

La dernière ligne est un peu bizarre: en fait, il existe déjà dans \verb+Prelude+ un type pour les rationnels...
Cette ligne permet donc de passer d'un \verb+Rational+ de \verb+Prelude+ à un élément de type \verb+Rationnel+.

\begin{lstlisting}
*Main> (5 :/ 3) / (7 :/ 6)
10/7
\end{lstlisting}

Reprenons  maintenant nos  classes \verb+Magma+,  \verb+Monoide+, \verb+Groupe+:
qu'elles nous  inspirent pour  créer des  classes \verb+Anneau+  et \verb+Corps+
avec les  tests qui vont avec.  Est-ce qu'on peut faire  de \verb+Rationnel+ une
instance de \verb+Anneau+?  De \verb+Corps+?

\end{exercice}



\begin{exercice}[Anneau des booléens]
  Pouvez-vous faire de \verb+Bool+ une instance de \verb+Num+? de \verb+Rational+?
\end{exercice}

















\subsection{Espaces vectoriels}


\begin{exercice}[Espaces vectoriels pour les nuls]

Avec les notations usuelles, que pensez-vous des égalités suivantes:

\begin{enumerate}
\item $0_\oplus \cdot \mathbf{u} =\mathbf{0}$
\item $λ\cdot \mathbf{0}=\mathbf{0}$
\item $(λ\cdot \mathbf{u} = \mathbf{0})\limp (λ=0 \lor \mathbf{u}=\mathbf{0})$
\end{enumerate}

  
\end{exercice}


\begin{exercice}[R-espaces vectoriels?]
  Déterminez si les ensembles  suivants munis des opérations indiquées
  ont une structure de $\bbr$-espace vectoriel:
  \begin{enumerate}
  \item   Soit  $V=\bigl\{\langle   a,b,c,0\rangle  \mid   \langle  a,
    b,c\rangle  \in \bbr^3\bigr\}$  muni de  l'addition canonique  des
    quadruplets et du produit canonique d'un quadruplet par un réel.
  \item Soit  $V=\bigl\{\langle   a,b,c,2\rangle  \mid   \langle  a,
    b,c\rangle  \in \bbr^3\bigr\}$  muni de  l'addition canonique  des
    quadruplets et du produit canonique d'un quadruplet par un réel.
  \item On munit $V=\bbr^\star_+$ de  l'addition définie par $a\oplus b=a\times
    b$ et  $\bbr$ opère  sur le groupe  $\langle V,\oplus\rangle$
    par  le   produit  externe  défini  par   $λ\otimes  \mathbf{x}  =
    \mathbf{x}^λ$.
  \item        $V=\bigl\{\langle       a,b,c\rangle\mid        \langle
    a,b,c\rangle\in\bbr^3 \land  a\cdot b\cdot  c =0\bigr\}$  avec les
    opérations canoniques.
\item $V$ est l'ensemble des fonctions dérivables sur $\bbr$.
\item $V$ est l'ensemble des suites arithmétiques réelles.
  \end{enumerate}
\end{exercice}


\begin{exercice}[K-espaces vectoriels?]
Les exemples suivants permettent-ils de définir des $\bbk$-espaces vectoriels?
  \begin{enumerate}
  \item $\bbk=\bbc$, l'ensemble des  nombres complexes, $V=\bbc$
    muni de l'addition habituelle des complexes, et le produit externe
    est défini par:
$$
 (\star)\ \colon \begin{array}{rll} \bbc\otimes \bbc& \to & \bbc\\
   \langle λ,\mathbf{z}\rangle& \mapsto & λ^2\cdot \mathbf{z}
 \end{array}
 $$

\item Soit $\bbk$ un corps quelconque et $V=\bbk^2$ muni de l'addition
  canonique des couples. On définit le produit externe ainsi:

$$
 (\star)\ \colon \begin{array}{rll} \bbk\otimes \bbk^2& \to & \bbk^2\\
   \big\langle λ,\langle x,y\rangle\big\rangle& \mapsto & \langle λ x,0\rangle
 \end{array}
 $$

\item $\bbk=\bbq$ et $V=\bbr$ munis des opérations canoniques.

  \end{enumerate}
\end{exercice}



\begin{exercice}[RVB/CJMN]
  Comment modéliseriez-vous les systèmes RVB et CJMN en terme d'espace vectoriel?
\end{exercice}



\begin{exercice}[A bit of dice]
On voudrait dessiner ce dé:
\drawdie{8}


Pour cela, on dispose de 6 dés un peu spéciaux:

\drawdie{1}
\drawdie{2}
\drawdie{3}
\drawdie{4}
\drawdie{5}
\drawdie{6}


On peut les additionner selon la  règle suivante: on superpose les dés
et un  point apparaît  si, et seulement  si, un et  un seul  point est
présent par position.

Par exemple, 1\drawdie{1} + 1\drawdie{2}=\fancydie{0}{0}{1}{1}{0}{0}

Quel  est le  rapport avec  notre cours?  Dessinez le  dé demandé.  Et
celui-ci \drawdie{7}? Et celui-là \fancydie{1}{0}{0}{0}{0}{0}?

Pour aller plus loin, aller jouer au \textit{Lights Out} : \href{http://www.jaapsch.net/puzzles/lights.htm}{http://www.jaapsch.net/puzzles/lights.htm}

\end{exercice}

\begin{exercice}
 Démontrez les théorèmes \ref{sev1} et \vref{sev2}
\end{exercice}


\begin{exercice}
Soit $V$ un espace vectoriel muni de tout ce qu'il faut.

Soit  $\langle \mathbf{u_i}\rangle_{0  \leqslant i  \leqslant p}$  une
famille  de  vecteurs  de $V$.  Montrez  que  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$ a une structure d'espace vectoriel.

Voilà pourquoi on appellera maintenant  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$  le \textbf{sous-espace  vectoriel  engendré} par  la
famille $\langle \mathbf{u_i}\rangle_{0 \leqslant i \leqslant p}$.

On dit  que $\langle \mathbf{u_i}\rangle_{0 \leqslant  i \leqslant p}$
est une \textbf{famille génératrice} de  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$.
\end{exercice}












 \begin{exercice}
     On travaille dans l'ev $\mathbb{R}^{2}$ :
\begin{enumerate}
\item $u=\langle  6,-9\rangle  $\ et $v=\langle  -10,15\rangle  .$\ Donner des CL
de la famille $\langle  u\rangle  ,$\ de la famille $\langle  u,v\rangle  .$

\item Que représente $\sev{\mathcal{F}} $\ avec $%
\mathcal{F}=\langle  u,v\rangle  $ ?

\item Démontrer que $w=\langle  2,-3\rangle  \in \sev{\mathcal{F}}  .$

\item $u$\ et $v$\ sont-ils colinéaires ?

%\item $\mathcal{F}$\ est-elle libre ou liée ?

\item Démontrer que $\sev{\FR}  =\sev{\langle  w\rangle}  .$

\item Démontrer que $\langle  1,2\rangle  \notin \sev{\mathcal{F}}.$

% \item $t=\langle  1,2\rangle  ,$\ et $\mathcal{F}^{\prime }=\langle  w,t\rangle  $%
% \ ; démontrer que ${\rm Vect}\langle  \mathcal{F}^{\prime }\rangle  =%
% \mathbb{R}^{2}.$
\end{enumerate}

   \end{exercice}



   \begin{exercice}
      On note $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
x+2y+3z=0\right\} ,$\ démontrer que $H$\ est un sev de $\mathbb{R}^{3}$
en déterminant $u$\ et $v,$\ deux vecteurs de $\mathbb{R}^{3},$\ de
sorte que $H=\sev{\langle  u,v\rangle}  .$


On note $w=(1,2,3)$. Est-ce que $w\in H$?
   \end{exercice}

  \begin{exercice}
    \begin{enumerate}
    \item Démontrer que $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
        x-z=0\right\} $ est un sev de $\mathbb{R}^{3}$.
    \item Démontrer que $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
        x=0\right\} $ est un sev de $\mathbb{R}^{3}$.
    \item   $H=\left\{   \langle   x,y,z\rangle    \in   \mathbb{R}^{3}\mid
          ax+by+cz=0\right\} $ o\`{u} $a$, $b$ et $c$ sont des réels
          fixés.  
          Démontrer que $H$ est un sev de $\mathbb{R}^{3}$.  
    \end{enumerate}
  \end{exercice}

% \begin{exercice}[ A bit of game]
  
% \end{exercice}

 \begin{exercice}
    On travaille dans $\mathbb{R}^{3}$ et on note $u=\langle  1,2,2\rangle 
    $ et $v=\langle -2,1,2\rangle $. 


Déterminer des réels $a$, $b$
    et                   $c$                  pour                   que
    $\sev{\langle   u,v\rangle} =\left\{  \langle   x,y,z\rangle   \in
    \mathbb{R}^{3}\mid ax+by+cz=0\right\}$. 
  \end{exercice}

\modenormal

%%% Local Variables: 
%%% TeX-master: "Poly_Matrix_DUT2_13.tex"
%%% End: 
