\chapterimage{bourbaki_2}
\chaptertext{En 1934,  de jeunes mathématiciens  français se réunissent  dans un
  café du quartier latin.  Quatre ans plus tard, le groupe \textit{Bourbaki} publie le premier
  chapitre  des  \og  \textit{Éléments de  mathématique}\fg{}  qui  bouleversera
  l'enseignement de la mathématique au XX\eme siècle.
En    particulier,    dans    l'introduction,     le    groupe    précise    \og
\textit{qu'autrefois,  on  a pu  croire  que  chaque branche  des  mathématiques
  dépendait d'intuitions  particulières [...] ce  qui eût entraîné  pour chacune
  la  nécessité d'un  langage formalisé  qui lui  appartînt en  propre. On  sait
  aujourd'hui qu'il est possible, logiquement  parlant, de faire dériver presque
  toute   la  mathématique   d'une   source  unique,   le  \textbf{Théorie   des
    Ensembles}.}\fg{}

Ils introduisent ensuite ce qu'ils appellent \textit{la méthode axiomatique} qui
est \og \textit{l'art  de rédiger des textes dont la \textbf{ formalisation} est facile à
  concevoir.}\fg{}

Cette  méthode  \og \textit{permet  [alors]  lorsqu'on  a  affaire à  des  êtres
  mathématiques complexes,  d'en dissocier  les propriétés  et de  les regrouper
  autour d'un petit  nombre de notions, c'est-à-dire [...] de  les classer selon
  les \textbf{structures} auxquelles elles appartiennent.}\fg{}.

Dix ans plus  tard, les premiers ordinateurs apparaissent, dix  ans après,
le  premier  véritable  langage   \textit{structuré},  Fortran,  est  introduit,
notamment sous l'égide de  {\textbf{John Backus}} qui en fait vingt ans après une
sévère  critique  dans  un  célèbre   article  \og  \textit{Can  programming  be
  liberated from the  Von Neumann style? A \textbf{functionnal} style  and its \textbf{algebra} of
  programs}\fg{}.

Enfin, depuis une dizaine d'années, le  paradigme fonctionnel est en plein essor
car, comme  l'avait précisé {Backus}  dès 1978,  il permet de  combler de
grosses lacunes des langages traditionnels.

L'informatique a donc une histoire, fortement liée à celle de la mathématique et
c'est cette histoire commune que nous allons explorer à partir  d'aujourd'hui pour vous
permettre de devenir les informaticen(ne)s de demain...

}
\chapter{Ensembles}


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

Imaginons  que vous  effectuiez votre  stage au  service de  l'état civil  de la
mairie de Klow. On  vous demande de construire un logiciel  qui va permettre aux
employé(e)s de gérer les données de l'ancien fichier papier. 

Pour permettre de vous organiser, vous dressez des petits schémas du style:

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

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


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

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


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

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

Que  vous inspire  ces  différents  schémas ?  Leurs  différences? Leurs  points
communs?

Pour  régler ses  problèmes, l'informaticien(ne)  va devoir  \textit{formaliser,
  spécifier,    abstraire},    faire    appel    aux    notions    mathématiques
d'\textit{ensemble, produit cartésien, relation, fonction, composition, structure} et quand il sera
très fort il pourra parler de \textit{catégorie}.

Il faudra ensuite penser à une \textit{implémentation} dans un \textit{langage} donné, en
construisant au besoin des \textit{types}.

Il sera même utile de \textit{compter} les  données collectées et il ne faut pas
oublier que l'ordinateur est un \og \textit{computer}\fg{} pour qui tout est nombre...



Plus généralement, l'informatique est une science (jeune) et l'informaticien(ne) doit
donc  employer  une  \textit{démarche scientifique}  vis-à-vis  des  programmes,
algorithmes, etc.: la  mathématique, une science bien plus ancienne  et bien \og
rodée\fg{}, lui fournit un modèle utile et même indispensable.

\section{Tout est ensemble}


\begin{flushright}
  \begin{quote}
{\itshape
Tous ensemble, tous ensemble, hé, hé\\
Tous ensemble, tous ensemble, hé, hé\\
Tous ensemble, tous ensemble, hé, hé\\
}
  \end{quote}
Nantes, Rue de Strasbourg,13 Mai 2003
\end{flushright}


\subsection{Une définition?}


La   notion   d'ensemble   peut   paraître   évidente:   le
dictionnaire parle de \og  groupe, assemblage d'éléments formant un tout
ou ayant les mêmes  caractéristiques\fg{}.  Les mathématiques du XX \eme
siècle ont pour  base la \textit{théorie des ensembles}:  il s'agit donc
d'un concept  de base et  même DU concept  de base, encore  plus basique
que  la  notion de  nombre  car nous  verrons  que  les nombres  entiers
peuvent être définis et construits à l'aide d'ensembles.



%\vspace{-1.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{4cm}
\begin{figure}
  \includegraphics[width=2.8cm]{Cantor}
\caption{Georg \textsc{Cantor} \\(1845 - 1918)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

Pourtant, une  définition correcte  est très délicate  à donner:  comme souvent,
plus la notion paraît simple, plus il est compliqué de la définir.  L'adage \og
\textit{plus c'est simple, plus c'est compliqué}\fg{} est
d'ailleurs une des  grandes frustrations en informatique: il  faut expliquer des
choses qui paraissent évidentes à  des machines stupides...Pourtant, c'est aussi
une chance: réfléchir et bien définir chaque notion est une contrainte mais cela
permet à l'informaticien(ne) de pouvoir avancer avec confiance.

La définition usuelle due à \textsc{Zermelo} et \textsc{Fraenkel} (début du XX\eme siècle) est bien trop compliquée à notre
niveau  et  nous utiliserons  plutôt  la  \textit{théorie naïve}  introduite  de
manière révolutionnaire à la fin du XIX\eme par\textsc{ Cantor}.

\subsection{Kit de survie logique}

Pour construire  notre théorie mathématique,  il faut  passer par tout  un stade
assez aride  de mise  au point des  \og briques\fg{} sur  lesquelles tout  va se
construire, sachant qu'on  ne part de rien: les  premiers circuits électroniques
de l'ordinateur...

Nous passerons cette étape fondamentale mais difficile: il faudra cependant être
conscient de son existence.

Nous allons  voir rapidement
quelques notions simples de logique en avant-première dont nous avons besoin tout
de suite.

Au  tout début  du  début,  une théorie  mathématique  comporte  des règles  qui
permettent de dire  si des assemblages de signes sont  des relations, des termes
ou des théorèmes de la théorie...Mmmmouais...

Bon, disons  que l'on considère un  \og tout\fg{} contenant des  \og objets\fg{}
distincts. On peut vérifier si certains  de ces \og objets\fg{} vérifient ou non
une \og propriété\fg{}.

Par  exemple \og  être  un  garçon\fg{} est  une  propriété  vérifiable si  l'on
considère l'amas d'étudiant(e)s d'INFO  1: on peut répondre par oui  ou non à la
question \og truc est un garçon\fg{}.

On peut  alors former l'ensemble G  des garçons d'INFO 1:  ses \textit{éléments}
sont ceux qui vérifient la propriété. On peut noter alors:

$$G = \bigl\{\text{ étudiant} \mid \text{ étudiant est un garçon}\bigr\}$$

On notera  indistinctement \og  Robert appartient  à G\fg{},  \og Robert  est un
élément de G\fg{}, \og G contient Robert\fg{}, \og Robert $\in G$\fg{}.


\begin{exemple}
Par exemple \og \textit{est un entier pair}\fg{} est une propriété définie sur
l'ensemble  $\bbn$  des entiers  naturels  que  nous  noterons P.  Alors
$P(2)=VRAI$ et $P(3)=FAUX$.

Ces notions s'introduiront naturellement sur  notre futur ami \HS dont nous
parlerons bientôt:

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

Alors on obtient par exemple:

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

\end{exemple}

%%% Local Variables: 
%%% TeX-master: "PolyMD1_13"
%%% End: 
