% \documentclass[xcolor=hyperref,hyperef={naturalnames,pdfpagelabels},french,envcountsect
% ]{beamer}
\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}
\usepackage[beamer,utf8,fourier]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark}
\usepackage{xlop}
%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}

\usepackage{Karnaugh}
\usepackage{algo}

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

\newcommand\nor{\downarrow}
\newcommand\nand{\mid}

\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}


\graphicspath{{/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/}{/home/moi/Photos/Maths/}}




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





\newcommand\lat{
\lstset{numbers=none,language=[LaTeX]{TeX},xleftmargin=10pt,%
keywordstyle =\color{yellow!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!yellow},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}





\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}



\begin{document}


\title[] % (optional, use only with long paper titles)
{Timide introduction aux mathématiques discrètes}

\subtitle{ }

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN \& Thierry BRUGÈRE}
% - 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]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{\today}
% - 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[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\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{<+->}







\begin{frame}
  \titlepage
\end{frame}

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

 
 \end{frame}



%  \begin{frame}

% Pendant  30  ans,  les   mathématiques  à  l'IUT  d'informatique  furent
% passionnément enseignées par Thierry \textsc{Brugère}:


% %\begin{figure}
% \begin{center}
%   \includegraphics[width=0.6\linewidth]{thierry}
% \end{center}
% %\end{figure}

% Le cours  qui vous sera proposé cette  année lui doit beaucoup  et on le
% retrouvera souvent désigné comme \og Le Maître\fg{}...



%  \end{frame}












% %
% \section{Des mathématiques en informatique?...}

% %

%  \begin{frame}
%    $$3\times 0,1=?$$
%  \end{frame}

% %

%  \begin{frame}[fragile]
% avec OCAML
% \caml
% \begin{lstlisting}
% # 3.*.0.1-.0.3;;
% - : float = 5.5511151231257827e-17
% \end{lstlisting}
% \end{frame}

% %

% \begin{frame}[fragile]
% avec Python
% \sage
% \begin{lstlisting}
% >>> 3*0.1-0.3
% 5.551115123125783e-17
% \end{lstlisting}
% \end{frame}

% %

% \section{Comment raisonner?...}

% \subsection{Récurrence, récursion, récursivité, induction \& Co.}

% %

% \begin{frame}
% \begin{center}
%   \includegraphics[angle=-1,scale=1.8]{hanoi3}
% \end{center}
% \end{frame}

% %

% \begin{frame}
% \begin{quote}
%   \textit{N. Claus de Siam a vu, dans ses voyages pour la publication des écrits
% de  l'illustre  Fer-Fer-Tam-Tam,  dans   le  grand  temple  de  Bénarès,
% au-dessous du  dôme qui  marque le centre  du monde, trois  aiguilles de
% diamant,  plantées  dans une  dalle  d'airain,  hautes  d'une coudée  et
% grosses comme  le corps  d'une abeille. Sur  une de ces  aiguilles, Dieu
% enfila au commencement  des siècles, 64 disques d'or  pur, le plus large
% reposant  sur  l'airain,  et  les  autres,  de  plus  en  plus  étroits,
% superposés  jusqu'au sommet.  C'est la  tour sacrée  du Brahmâ.  Nuit et
% jour, les  prêtres se  succèdent sur les  marches de l'autel,  occupés à
% transporter  la tour  de la  première  aiguille sur  la troisième,  sans
% s'écarter des  règles fixes que nous  venons d'indiquer, et  qui ont été
% imposées  par Brahma.  Quand  tout sera  fini,  la tour  et les  brahmes
% tomberont, et ce sera la fin des mondes !}
% \end{quote}
% \end{frame}








% %

% \begin{frame}
%   \begin{alertblock}{C.N.S. et théorème}
%     On  considère P  et Q  deux propositions  (des énoncés,  des  faits, des
% formules).

% \begin{itemize}
% \item Q est une \textbf{condition nécessaire} pour avoir P si, dès que P
%   est  vraie,  alors nécessairement,  forcément,  obligatoirement, Q  est
%   vraie. On note souvent $P \Longrightarrow Q$.
% \item Q est  une \textbf{condition suffisante} pour avoir  P s'il suffit
%   que  Q  soit  vraie  pour  que  P soit  vraie.   On  note  souvent  $P
%   \Longleftarrow Q$.
% \item  Lorsque  P  est  à  la fois  condition  nécessaire  et  condition
%   suffisante de Q, on dit  que P est une \textbf{condition nécessaire et
%     suffisante} de Q ou encore  que P est vraie \textbf{si, et seulement
%     si,} Q est vraie. On note souvent $P \Longleftrightarrow Q$.

% \item Lorsque qu'une \og affirmation\fg{} du  type $P \Longrightarrow Q$ ou $P
% \Longleftrightarrow Q$ est vraie, on dit que c'est un \textbf{théorème}.
% \end{itemize}

%   \end{alertblock}
% \end{frame}


% %

% \begin{frame}
%   \begin{alertblock}{Contre-exemple}
% Pour prouver qu'une proposition
% n'est pas un théorème, il suffit d'exhiber un \textbf{contre-exemple}.
% \end{alertblock}
% \end{frame}


% %


% \begin{frame}
%   \begin{alertblock}{Récurrence}
% Pour prouver qu'une  propriété $\PR_n$  dépendant uniquement
% d'un paramètre $n$ est vraie pour tout $n \geqslant n_0$, il faut
% vérifier que:

% \begin{itemize}
% \item $\PR_{n_0}$ est vraie (on parle parfois d'initialisation);
% \item  pour tout  $n \geqslant  n_0$, $\PR_n  \Longrightarrow \PR_{n+1}$
%   (on parle parfois d'hérédité).
% \end{itemize}
%   \end{alertblock}
% \end{frame}


% %

% \caml

% \begin{frame}[fragile]
% \begin{lstlisting}[caption={mouvement élémentaire}]
% let mvt depart arrivee=
% print_string
% ("Déplace un disque de la tige "^depart^" vers la tige "^arrivee);
% print_newline();;
% \end{lstlisting}
% \end{frame}


% \begin{frame}[fragile]
% \begin{lstlisting}[caption={résolution récursive du problème des tours de Hanoï}]
% let rec hanoi a b c= function
%    | 0 -> ()  (*0 disque : on ne fait rien*)
%    | n -> hanoi a c b (n-1); (*n-1 disques sont déplacés de a vers b*)
%           mvt a c; (*on déplace le disque restant en a vers c*)
%           hanoi b a c (n-1) (*n-1 disques sont déplacés de b vers c*);;
% \end{lstlisting}
% \end{frame}



% \begin{frame}[fragile]
% \begin{lstlisting}
% # hanoi "A" "B" "C" 4;;
% Déplace un disque de la tige A vers la tige B
% Déplace un disque de la tige A vers la tige C
% Déplace un disque de la tige B vers la tige C
% Déplace un disque de la tige A vers la tige B
% Déplace un disque de la tige C vers la tige A
% Déplace un disque de la tige C vers la tige B
% Déplace un disque de la tige A vers la tige B
% Déplace un disque de la tige A vers la tige C
% Déplace un disque de la tige B vers la tige C
% Déplace un disque de la tige B vers la tige A
% Déplace un disque de la tige C vers la tige A
% Déplace un disque de la tige B vers la tige C
% Déplace un disque de la tige A vers la tige B
% Déplace un disque de la tige A vers la tige C
% Déplace un disque de la tige B vers la tige C
% - : unit = ()
% \end{lstlisting}
% \end{frame}


% \lat
% \begin{frame}[fragile]
% \begin{lstlisting}[caption={}]
% % #1 Tige source
% % #2 Tige but
% % #3 Tige intermédiaire
% % #4 Nombre de disques
% \def\rhanoi#1#2#3#4{
%     \ifnum#4>1
%         {\advance#4 by -1 \rhanoi#1#3#2#4}
%         \move{#1}{#3}
%         {\advance#4 by -1 \rhanoi#2#1#3#4}
%     \else
%         \move{#1}{#3}
%     \fi
% }
% \end{lstlisting}
% \end{frame}

% %


% \subsection{Théorèmes}

% %

% \begin{frame}
%   \begin{example}
%     $f$ d\'{e}rivable en $x_{0}\Rightarrow f$ continue en $x_{0}$
%   \end{example}
% \end{frame}




% \begin{frame}
%   \begin{example}
%  Si $x^{2}=4$ et $x<0$ alors forc\'{e}ment on a $x=-2$
%   \end{example}
% \end{frame}

% \begin{frame}
%   \begin{alertblock}{Techniques de démonstrations}
% Pour d\'{e}montrer un th\'{e}or\`{e}me $P\Rightarrow Q$ on
% peut utiliser les techniques suivantes :

% \begin{itemize}
% \item Supposer que $P$ est vraie et, en utilisant des r\'{e}sultats prouv%
% \'{e}s ou d\'{e}finitions ou .... , arriver \`{a} prouver que $Q$ est vraie.
% C'est ce qu'on appelle une d\'{e}monstration directe.

% \item Supposer que $Q$ est fausse et, en utilisant des r\'{e}sultats prouv%
% \'{e}s ou d\'{e}finitions ou des calculs ou ...., arriver \`{a} prouver que $%
% P$ est fausse. Ce type de raisonnement est un \textbf{raisonnement ou d\'{e}%
% monstration par contraposition}.

% \item Supposer simultan\'{e}ment que $P$ est vraie et $Q$ fausse et, en
% utilisant des r\'{e}sultats prouv\'{e}s ou d\'{e}finitions ou des calculs ou
% ...., arriver \`{a} une contradiction flagrante ou un r\'{e}sultat
% manifestement impossible qui peut \^{e}tre $2=-2$ dans $\mathbb{R}$ ou $x\in
% A$ et $x\notin A$ ou .... Ce type de raisonnement est un \textbf{%
% raisonnement ou d\'{e}monstration par l'absurde}.
% \end{itemize}
%   \end{alertblock}
% \end{frame}


% \section{Théorie naïve des ensembles}




% \subsection{Éléments}


% \begin{frame}
% Une promotion est constituée...

% \begin{itemize}
% \item ...d'étudiant(e)s?
% \item ...de groupes ?
% \end{itemize}
% \end{frame}


% \begin{frame}
% «L'objet de la philosophie, c'est de partir d'une chose si simple que ça ne vaut pas la peine d'en parler et d'arriver à une chose si compliquée que personne n'y comprend plus rien.»
% \end{frame}

% \begin{frame}

% %\begin{figure}
% \begin{center}
%   \includegraphics[scale=1.5]{Russell}
% \end{center}
% %\end{figure}

% \end{frame}

% \begin{frame}
% Dans  une ville,  il  existe deux  types  d'hommes: ceux  qui se  rasent
% eux-mêmes  et les  autres. Pour  ces derniers,  la mairie  a  désigné un
% barbier, chargé de tous les raser, et eux seulement: qui rasera le barbier?...
% \end{frame}



% \begin{frame}
%   $$\text{La bonne, Papa }\bigr\}$$


% \pause


% $$\text{Familles}=\bigl\{\text{   Chaprot,   Dugland,   Du  Fermoir   de
%   Monsac }\bigr\}$$

% \end{frame}



% \begin{frame}

% Compréhension:\pause

% $$
% B =\left\{ x\in A:\mathcal{P}\right\} =\left\{ x\in A\text{ };\mathcal{P}%
% \right\} =\left\{ x\in A\mid \mathcal{P}\right\} =\left\{ x\in A\diagup 
% \mathcal{P}\right\}
% $$

%  \pause 

%  ou encore

% \pause

% $$B =\left\{ x:x\in A\text{ et }\mathcal{P}\right\} =\left\{ z\text{ };z\in A%
% \text{ et }\mathcal{P}\right\} =\left\{ u\mid u\in A\text{ et }\mathcal{P}%
% \right\} =\left\{ x\diagup x\in A\text{ et }\mathcal{P}\right\}
% $$

% \end{frame}


% \begin{frame}
%   \begin{example}
%     Écrire en compréhension l'ensemble des carrés des entiers 2, 10 et 12.
%   \end{example}
% \end{frame}

% \sage
% \begin{frame}[fragile]
% Avec \textsf{Sage}:

% \begin{lstlisting}[caption={}]
% sage: E=Set([2,10,12])
% sage: E
% {2, 12, 10}
% sage: 2 in E
% True
% sage: F=Set(k**2 for k in E)
% sage: F
% {144, 100, 4}
% sage: 2 in F
% False
% sage: G=Set([2,10,2,12])
% sage: G
% {2, 12, 10}
% sage: G==E
% True
% \end{lstlisting}

  
% \end{frame}




% \subsection{Ensembles égaux}


% \begin{frame}

% \begin{example}
%   On       note      $E=\bigl\{x\in\bbz\,|\,       x^2=1\bigr\}$      et
%   $F=\bigl\{x\in\bbr\,|\, \left|x\right|=1\bigr\}$. Que pouvez-vous dire
%   de $E$ et $F$? 
% \end{example}
% \end{frame}




% \subsection{Inclusion}


% \begin{frame}
%   $$A \subseteq B$$
% \end{frame}

% \begin{frame}[fragile]
%   \begin{lstlisting}[caption={}]
% sage: A=Set([1,3,8,7])
% sage: B=Set([2**3,14/2])
% sage: B.issubset(A)
% True
%   \end{lstlisting}


% \pause


% Quels sont les autres sous-ensembles (ou parties) de A?

% \pause

% \begin{lstlisting}[caption={}]
% sage: list(A.subsets())
% [{}, {8}, {1}, {3}, {7}, {8, 1}, {8, 3}, {8, 7}, {1, 3}, {1, 7}, {3, 7}, {8, 1, 3}, {8, 1, 7}, {8, 3, 7}, {1, 3, 7}, {8, 1, 3, 7}]
% \end{lstlisting}


% \end{frame}





% \begin{frame}
%   \begin{example}
%     \begin{itemize}
%       \item I est l'ensemble des entiers impairs;
% \item  J  l'ensemble des  entiers
%     pairs;
% \item K l'ensemble des entiers qui ne sont pas pairs;
% \item  L l'ensemble
%     des entiers premiers;
% \item M l'ensemble des entiers premiers supérieurs à 3.
%     \end{itemize}

% \pause

% \begin{enumerate}
%   \item $L \subseteq I$? 
% \item $M \subseteq I$?
% \item Montrer que $I=K$.
% \end{enumerate}


%   \end{example}
% \end{frame}












% % Definition of circles
% \def\firstcircle{(0,0) ellipse (2.5cm and 1.5cm)}
% \def\secondcircle{(0,0) circle (.75cm)}

% \colorlet{circle edge}{blue}
% \colorlet{circle area}{blue!60}

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

% \setlength{\parskip}{5mm}
% % Set A and B


% \begin{frame} \frametitle{Diagramme d'\bsc{Euler-Venn}}
%   \begin{center}
% \begin{tikzpicture}
%     \begin{scope}
%         \clip \firstcircle;
%         \fill[filled] \secondcircle;
%     \end{scope}
%     \draw[outline] \firstcircle node {$A$};
%     \draw[outline] \secondcircle node  {};
%     \node[anchor=south] at (current bounding box.north) {$A \subseteq B$};
% \end{tikzpicture}
% \end{center}
% \end{frame}



% \subsection{Parties d'un ensemble}




% \begin{frame}
  
% $$
% \mathcal{P}\left( E\right) =\Bigl\{ X\mid X\subseteq E\Bigr\}
% $$

% \pause


% $$
% X\in \mathcal{P}\left( E\right) \Leftrightarrow X\subseteq E\vspace{0.2cm}
% $$


% \pause


% $$
% \mathcal{P}(E)=\Bigl\{ \emptyset ,\ldots ,E\Bigr\}
% $$





% \end{frame}




% \begin{frame}
%   \begin{example}
%     Soit $X=\bigl\{1,2\bigr\}$.\pause

% Écrire en extension:

% \begin{enumerate}
% \item $\PR(X)$;
% \item $ \PR(\PR(X))$
% \end{enumerate}
%   \end{example}
% \end{frame}



% \begin{frame}[fragile]
%   \begin{lstlisting}[caption={}]
% sage: X=Set([1,2])
% sage: P=X.subsets()
% sage: P
% Subsets of {1, 2}
% sage: P=Set(X.subsets())
% sage: P
% {{1, 2}, {2}, {}, {1}}
% sage: PP=Set(P.subsets())
% sage: PP
% {{{1, 2}, {2}, {}, {1}}, {{2}, {}, {1}}, {{1, 2}, {1}}, {{2}}, {{1, 2}, {2}}, {}, {{}, {1}}, {{2}, {}}, {{1, 2}, {2}, {}}, {{1}}, {{1, 2}, {}, {1}}, {{}}, {{1, 2}, {}}, {{2}, {1}}, {{1, 2}, {2}, {1}}, {{1, 2}}}
%   \end{lstlisting}
  
% \end{frame}





% \subsection{Op\'{e}rations}

% \subsubsection{Intersection}






% \begin{frame}
%   \begin{definition}
% $$
% A\cap B=\Bigl\{ x\in E\mid x\in A\text{ et }x\in B\Bigr\}
% $$
%   \end{definition}
% \end{frame}









% \begin{frame}

%   Loi  de composition  interne,\pause  associative, \pause  commutative,
%   \pause élément neutre.

% \pause

% Élément idempotent


% \pause


% Ensembles disjoints

% \end{frame}


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

% \colorlet{circle edge}{blue}
% \colorlet{circle area}{blue!50}

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

% \setlength{\parskip}{5mm}
% % Set A and B

% \begin{frame}
  
% \begin{center}
% \begin{tikzpicture}
%     \begin{scope}
%         \clip \A;
%         \fill[filled] \B;
%     \end{scope}
%      \draw \Uni ;
%     \draw[outline] \A node [above left] {$A$};
%     \draw[outline] \B node [below right] {$B$};
%     \node[anchor=east] at (current bounding box.base) {\textcolor{blue!10}{$A \cap B$}};
% \end{tikzpicture}
% \end{center}
% \end{frame}



% \begin{frame}
%   \begin{example}
%     $$A\cap B=B\Leftrightarrow B\subseteq A$$
%   \end{example}
% \end{frame}








% \subsubsection{Union}




% \begin{frame}
%   \begin{definition}
%     $$
% A\cup B=\Bigl\{ x\in E\mid x\in A\text{ ou }x\in B\Bigr\}
% $$
%   \end{definition}

% \pause


% OU

% \pause


% Propriétés?
% \end{frame}


% \begin{frame}
  
% \begin{center}
% \begin{tikzpicture}
%   \draw \Uni ;
%     \draw[filled] \A node[left] {$A$}
%                   \B node [right] {$B$};
%     \node[anchor=north] at (current bounding box.south) {\textcolor{blue!20}{$A \cup B$}};
% \end{tikzpicture}
% \end{center}

% \end{frame}




% \subsubsection{Différence}



% \begin{frame}
%   \begin{definition}
%     $$
% A-B=\Bigl\{ x\in E\mid x\in A\text{ et }x\notin B\Bigr\}
% $$
%   \end{definition}
% \end{frame}

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






% \subsubsection{Différence symétrique}


% \begin{frame}
%   \begin{definition}
%     \begin{eqnarray*}
% A\bigtriangleup B &=&\Bigl\{ x\in E\mid x\in A-B\text{ ou }x\in B-A\Bigr\}
% =\left( A-B\right) \cup \left( B-A\right) \\
% A\bigtriangleup B &=&\Bigl\{ x\in E\mid x\in A\cup B\text{ et }x\notin A\cap
% B\Bigr\} =\left( A\cup B\right) -\left( A\cap B\right)
% \end{eqnarray*}
%   \end{definition}

% \pause


% OU?


% \end{frame}






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






% \begin{frame}
  
% \begin{center}
%   \begin{tikzpicture}
% \draw (-3,-3) rectangle (6,3.5);
% \draw[filled, even odd rule] \A [left] node {$A$}
%                                \B [right] node {$B$}
%                                  \Cc [above] node{$C$};
%     \node[anchor=north]     at      (current     bounding     box.south)
%     {\textcolor{blue}{$A \bigtriangleup B \bigtriangleup C$}};
% \end{tikzpicture}
% \end{center}

% \end{frame}




% \subsubsection{Complémentaire}


% \begin{frame}
%   \begin{definition}
%     $$
% \complement_{E}A=E-A=\Bigl\{ x\in E\mid x\notin A\Bigr\}
% $$
%   \end{definition}
% \end{frame}

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



% \subsubsection{Lois de \textsc{De Morgan}}





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

% \end{frame}


% \subsection{Partition d'un ensemble}

% \begin{frame}
%   \begin{definition}
%     On dit
% que $P$ est une \textbf{partition} de $E$ si, et seulement si,

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

% \item deux \'{e}l\'{e}ments distincts quelconques de $P$ sont disjoints,

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



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



% \subsection{Produit cart\'{e}sien}







% \begin{frame} \frametitle{$ n$-uplets}
%   $$
% \bigl( a_{1},a_{2},\cdots ,a_{n}\bigr) =\left( a_{1}^{\prime
% },a_{2}^{\prime },\cdots ,a_{n}^{\prime }\right) \Leftrightarrow
% a_{i}=a_{i}^{\prime }\text{ pour tout }i
% $$

% \end{frame}



% \begin{frame}
%   \begin{definition}
    
% $$
% E_{1}\times E_{2}\times \cdots \times
% E_{n}=\prod\limits_{i=1}^{n}E_{i}=\bigl\{ \left( a_{1},a_{2},\cdots
% ,a_{n}\right) \mid a_{i}\in E_{i}\bigr\}
% $$
%   \end{definition}
% \end{frame}





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

% \pause

% Combien de menus?
% \end{frame}


% \tikzstyle{lien}=[->,>=stealth,rounded corners=5pt,thick]
% \tikzset{individu/.style={draw,thick,fill=#1!25!black},
% individu/.default={green}}


% \begin{frame}
  
% {\scriptsize
% \begin{tikzpicture}
% [level 1/.style={sibling distance=4cm},
% level 2/.style={sibling distance=1.25cm},
% level 3/.style={sibling distance=0.36cm}]
% \node [individu=gray] {Menus}
% child{ node [individu=blue]{Cuisses}
%        child{ node [individu=red]{Turbot}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%        child{ node [individu=red]{Chien}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%        child{ node [individu=red]{Soupe}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%      }
% child{ node [individu=blue]{\OE uf}
%        child{ node [individu=red]{Turbot}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%        child{ node [individu=red]{Chien}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%        child{ node [individu=red]{Soupe}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%      }
% child{ node [individu=blue]{Huîtres}
%        child{ node [individu=red]{Turbot}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%        child{ node [individu=red]{Chien}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%        child{ node [individu=red]{Soupe}
%             child{ node [individu=green]{P}
%                  }
%             child{ node [individu=green]{B}
%                  }
%             child{ node [individu=green]{N}
%                  }
%             }
%      };
% \end{tikzpicture}


% }

% \end{frame}







% \caml
% \begin{frame}[fragile]
%   \begin{lstlisting}[caption={}]
% # let ens=['a';'b';'c'];;
% val ens : char list = ['a'; 'b'; 'c']
% # let tri=['a','b','c'];;
% val tri : (char * char * char) list = [('a', 'b', 'c')]
% # tri=ens;;
% Characters 4-7:
%   tri=ens;;
%       ^^^
% Error: This expression has type char list
%        but an expression was expected of type (char * char * char) list
% \end{lstlisting}

% \end{frame}




% \subsection{Notion de cardinal}\label{cardinal}


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

% \item $\bigl| A-B\bigr| \leq \bigl| A\bigr| .$

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

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

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

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







\section{Calcul booléen}




\subsection{Algèbre de Boole}




\begin{frame}
  $$
\left( \mathcal{P}(E),\cup ,\cap ,\complement_{E},\subseteq
,\emptyset ,E\right) \vspace{0.2cm}
$$


\pause



$$
\left( \mathcal{B},+ ,\cdot ,\overline{a},\leqslant 
,0 ,1\right) \vspace{0.2cm}
$$
\end{frame}








\begin{frame}
  
\begin{table}[h!]
\begin{center}
\begin{tabularx}{0.8\linewidth}{IZ|ZIZ|ZI}
\whline
$\mathcal{P}(E)$ & $\mathcal{B}$ & $\mathcal{P}(E)$ & $\mathcal{B}$\\ 
\whline
$\emptyset \cup \emptyset =\emptyset $ & \pause $0+0=0$ & \pause
$\emptyset \cap \emptyset =\emptyset $ & \pause $0\cdot 0=0$ \\ \hline
\pause $E\cup E=E$ & \pause $1+1=1$ &
\pause $E\cap E=E$ & \pause $1\cdot 1=1$ \\ \hline
\pause $A\cup \emptyset =A$ &\pause $a+0=a$ &
\pause $A\cap \emptyset =\emptyset $ & \pause $a\cdot 0=0$ \\ \hline
\pause $A\cup E=E$ & \pause $a+1=1$ &
\pause $A\cap E=A$ & \pause $a\cdot 1=a$ \\ \hline
\pause $A\cup A=A$ & \pause $a+a=a$ &
\pause $A\cap A=A$ & \pause $a\cdot a=a$ \\ \hline
\pause $A\cup \overline{A}=E$ & \pause $a+\overline{a}=1$ &
\pause $A\cap \overline{A}=\emptyset$ &
\pause $a\cdot \overline{a}=0$
 \\ \whline
\end{tabularx}%
\end{center}
\caption{Correspondance entre $\PR(E)$ et $\BR$}\label{table::bool1}
\end{table}

\end{frame}

\begin{frame} \frametitle{Les surprises}
  \begin{itemize}
  \item $ a+(b\cdot c)$
\item $ (b\cdot c)+a$
\item $a+a$
\item $a\cdot a$
\item $a+1$
\item 
\item $(a+b)\cdot (a+c)$
\item $a+a\cdot b$
\item $a\cdot (a+b)$
\item $a\cdot \overline{a}$
\item  $a+\overline{a}$
  \end{itemize}
\end{frame}



\begin{frame} \frametitle{Realation d'ordre}
$$
a \leqslant b\Longleftrightarrow a+b= $$

\pause

$$
a \leqslant b\Longleftrightarrow a\cdot b= $$

\pause

$$
a \leqslant b\Longleftrightarrow \overline{a}+b= $$

\pause

$$
a \leqslant b\Longleftrightarrow a\cdot \overline{b}=
$$

\pause

$$0\leqslant a\cdot b\leqslant a\leqslant a+b\leqslant 1$$



\end{frame}


\begin{frame} \frametitle{Algèbre de \bsc{Boole} binaire}
 $$\mathcal{B}_{2}$$
\end{frame}




\begin{frame}
  \begin{center}
    Table canonique.

\pause



Loi de \bsc{De Morgan}
  \end{center}
\end{frame}


\begin{frame} \frametitle{Dualité}
  \begin{itemize}
  \item $x(y+z)=xy+xz $: duale?
   \item $ x+yz \pause = (x+y)(x+z)$
  \end{itemize}
\end{frame}





\subsection{Fonctions bool\'{e}ennes}

\begin{frame}\frametitle{Support}
  $$
S_{n}\left( f\right) =\left\{ b\in \mathcal{B}_{2}^{n}\mid f\left( b\right)
=1\right\}
$$

\end{frame}


\begin{frame} \frametitle{Fonctions de $ \BR_2^2$}
  \begin{center}
      \begin{tabularx}{\linewidth}{IZZIZ*{15}ZI}
	     \whline
$x$&$y$&$f_0$&$f_1$&$f_2$&$f_3$&$f_4$&$f_5$&$f_6$&$f_7$&$f_8$&$f_9$&$f_{10}$&$f_{11}$&$f_{12}$&$f_{13}$&$f_{14}$&$f_{15}$\\
\whline
0&0&&&&&&&&&&&1&&&&&\\ \hline
0&1&&&&&&&&&&&0&&&&&\\ \hline
1&0&&&&&&&&&&&1&&&&&\\ \hline
1&1&&&&&&&&&&&0&&&&&\\
             \whline
             \end{tabularx}
  \end{center}
\end{frame}






\begin{frame}
  \begin{itemize}
  \item \textbf{litt\'{e}ral positif}
\item \textbf{litt\'{e}ral n\'{e}gatif}
\item \textbf{mon\^{o}me bool\'{e}en} \pause pourquoi?
\item \textbf{polyn\^{o}me bool\'{e}en}
  \end{itemize}
\end{frame}





\begin{frame}
  \begin{itemize}
  \item Un \textbf{p-terme} \pause \textbf{minterme}
\item Un \textbf{s-terme} (clause) \pause \textbf{maxterme}
\item \textbf{Disjonctive}
\item \textbf{Disjonctive canonique}
\item \textbf{Conjonctive} 
\item \textbf{Conjonctive canonique} 

  \end{itemize}




\end{frame}




\begin{frame}\frametitle{Obtenir la forme canonique disjonctive}
$f=f(x_{1},x_{2},x_{3})=\left(x_1+x_2\right)\overline{x_{3}}$


\begin{center}
             \begin{tabularx}{\linewidth}{IZ|Z|ZIZ|ZIZI}
	     \whline
             $x_1$&$x_2$&$x_3$&$x_1+x_2$&$\overline{x_3}$&$f(x_1,x_2,x_3)$\\
             \whline
             1&1&1&&&\\
             1&1&0&&&\\
             1&0&1&&&\\
             1&0&0&&&\\
             0&1&1&&&\\
             0&1&0&&&\\
             0&0&1&&&\\
             0&0&0&&&\\
             \whline
             \end{tabularx}
             \end{center}


\pause On en déduit aussi la \textbf{forme canonique conjonctive}
\end{frame}


\subsection{Portes logiques}


\begin{frame}\frametitle{Portes US}
  \begin{center}
 
\begin{circuitikz} \draw[color=white]
(0,0) node[and port] (myand) {}
(5,0) node[or port] (myor) {}
(9,0) node[not port] (mynot) {}

(0,-2) node[nand port] (mynand) {}
(5,-2) node[nor port] (mynor) {}
(9,-2) node[xor port] (myxor) {}

(myand.in 1) node[anchor=east] {$x$}

(myand.in 2) node[anchor=east] {$y$}

(myand.out) node[anchor=west] {$x\cdot y$}

(myor.in 1) node[anchor=east] {$x$}

(myor.in 2) node[anchor=east] {$y$}

(myor.out) node[anchor=west] {$x+y$}

(mynot.in) node[anchor=east] {$x$}

(mynot.out) node[anchor=west] {$\overline{x}$}


(mynand.in 1) node[anchor=east] {$x$}

(mynand.in 2) node[anchor=east] {$y$}

(mynand.out) node[anchor=west] {$x\nand y$}

(mynor.in 1) node[anchor=east] {$x$}

(mynor.in 2) node[anchor=east] {$y$}

(mynor.out) node[anchor=west] {$x\nor y$}

(myxor.in 1) node[anchor=east] {$x$}

(myxor.in 2) node[anchor=east] {$y$}

(myxor.out) node[anchor=west] {$x\oplus y$}

 ;
\end{circuitikz}
\end{center}


\end{frame}



\begin{frame}\frametitle{Portes à l'européenne}
  
\begin{center}
 
\begin{circuitikz} \draw[color=white]
(0,0) node[european and port] (myand) {}
(5,0) node[european or port] (myor) {}
(9,0) node[european not port] (mynot) {}

(0,-2) node[european nand port] (mynand) {}
(5,-2) node[european nor port] (mynor) {}
(9,-2) node[european xor port] (myxor) {}

(myand.in 1) node[anchor=east] {$x$}

(myand.in 2) node[anchor=east] {$y$}

(myand.out) node[anchor=west] {$x\cdot y$}

(myor.in 1) node[anchor=east] {$x$}

(myor.in 2) node[anchor=east] {$y$}

(myor.out) node[anchor=west] {$x+y$}

(mynot.in) node[anchor=east] {$x$}

(mynot.out) node[anchor=west] {$\overline{x}$}


(mynand.in 1) node[anchor=east] {$x$}

(mynand.in 2) node[anchor=east] {$y$}

(mynand.out) node[anchor=west] {$x\nand y$}

(mynor.in 1) node[anchor=east] {$x$}

(mynor.in 2) node[anchor=east] {$y$}

(mynor.out) node[anchor=west] {$x\nor y$}

(myxor.in 1) node[anchor=east] {$x$}

(myxor.in 2) node[anchor=east] {$y$}

(myxor.out) node[anchor=west] {$x\oplus y$}

 ;
\end{circuitikz}
\end{center}
\end{frame}







\begin{frame}
  
\begin{center}
\begin{circuitikz} \draw[color=white]
(0,4) node[european and port] (myand1) {}
(3,1) node[european and port] (myand2) {}
(5,2) node[european or port] (myor) {}
(0,0) node[european not port] (mynot1) {}
(0,2) node[european not port] (mynot2) {}

(myand1.in 1) node[anchor=east] {$x$}

(myand1.in 2) node[anchor=east] {$y$}

(mynot1.in) node[anchor=east] {$y$}

(mynot2.in) node[anchor=east] {$x$}


(mynot1.out) -| (myand2.in 2)

(mynot2.out) -| (myand2.in 1)


(myand1.out) -| (myor.in 1)

(myand2.out) -| (myor.in 2)

(myor.out) node[anchor=west] {$x\cdot y+\overline{x}\cdot\overline{y}$}

;
\end{circuitikz}
\end{center}

\end{frame}

\subsection{Minimisation de circuits}


\begin{frame}
  
Construisez  les  circuits  correspondant  à  $xyz+x  \overline{y}z$  et
$xz$. Des remarques?
\end{frame}

% \section{un peu de calcul matriciel}

% \section{Relations binaires}

% \section{Relations binaires sur un ensemble}


% \section{Relations d'équivalence}

% \section{Structures d'ordre}


% \section{Un peu de dénombrement}
\begin{frame}
  \begin{center}
\begin{figure}[!h]
\begin{center}
\unitlength=1mm
\begin{picture}(3,3)
\Karnaughdiagram{2}{{$ \overline{x}\overline{y}$}{$ \overline{x}y$}{$x \overline{y}$}{$xy$}}($ x$,$ y$)[$f$]
\end{picture}
\end{center}
\end{figure}
\end{center}
\end{frame}




\begin{frame}
  
Par exemple, pour $xy+\overline{x}y$ on obtient:




\begin{figure}[!h]
\vspace{3cm}
\begin{center}
\unitlength=1mm
\begin{picture}(3,3)
\Karnaughdiagram{2}{{}{$1$}{}{$1$}}($ x$,$ y$)[$f$]
\PrimImpl(25,10)(8,16)
\end{picture}
\end{center}
\end{figure}
\end{frame}




\begin{frame}
  $f(x,y,z)=x       \overline{y}z+x
\overline{y}\overline{z}+xyz+\overline{x}yz+\overline{x}\overline{y}\overline{z}$.

\vspace{2cm}

\begin{figure}[!h]
\begin{center}
\unitlength=1mm
\begin{picture}(15,5)
\Karnaughdiagram{3}{10011101}($ x$,$ yz$)[$f$]
\PrimImpl(15,10)(8,16)
\PrimImpl(35,10)(8,16)
\PrimImpl(20,5)(16,8)
\end{picture}
\end{center}
\end{figure}

\pause

Alors $f(x,y,z)=\overline{y}\overline{z}+x \overline{y}+yz$.

\end{frame}




\begin{frame}
  $f(x,y,z)=x       \overline{y}z+x
\overline{y}\overline{z}+\overline{x}yz+\overline{x}\overline{y}\overline{z}+\overline{x}\overline{y}z$.

\vspace{2cm}

\begin{figure}[!h]
\begin{center}
\unitlength=1mm
\begin{picture}(15,5)
\Karnaughdiagram{3}{11011100}($ x$,$ yz$)[$f$]
\PrimImpl(20,10)(16,16)
\PrimImpl(30,15)(16,8)
\end{picture}
\end{center}
\end{figure}

\pause


Cette fois, $f(x,y,z)=\overline{y}+\overline{x}z$.

\end{frame}




\begin{frame}
  Écrivez  l'expression   booléenne
correspondant à ce diagramme:
\begin{figure}[!h]
\vspace{4cm}
\begin{center}
\unitlength=1mm
\begin{picture}(5,5)
\Karnaughdiagram{4}{1010001111100011}($x_0x_1$,$x_2x_3$)[$f$]
\PrimImpl(40,20)(16,16)
\PrimImpl(20,5)(16,8)
\PrimImpl(5,-5)(27,27)[rt]
\PrimImpl(5,45)(27,27)[rb]
\PrimImpl(55,45)(27,27)[lb]
\PrimImpl(55,-5)(27,27)[lt]
\end{picture}
\end{center}
\end{figure}


\pause

On obtient $f(x_0,x_1,x_2,x_3)=x_1x_2+\overline{x_1}\overline{x_3}+x_0 \overline{x_1}\overline{x_2}$

\end{frame}





\section{Un peu de Python}

\sage

\subsection{fonctions}




\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> def f(x):
...     return x**2
... 
>>> f(2)
4
\end{lstlisting}
\end{frame}



\subsection{La structure conditionnelle}





\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
def max2(a, b):
    if a <= b:
        return b
    else:
        return a
\end{lstlisting}
\end{frame}






\subsection{Les boucles \og tant que\fg{}}


\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
def pgcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
\end{lstlisting}
\end{frame}


\subsection{Les listes}


\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> liste = [12,11,18,7,15,3]
>>> liste[0]
12
>>> liste[:2]
[12, 11]
>>> liste[2:]
[18, 7, 15, 3]
>>> liste[2:4]
[18, 7]
>>> liste[-1]
3
>>> tete=liste.pop(0)
>>> tete
12
>>> liste
[11, 18, 7, 15, 3]
>>> len(liste)
5
\end{lstlisting}
\end{frame}




\begin{frame}[fragile]
\begin{center}
    \begin{tabular}{ll}
la méthode & son effet \\
\hline
\verb?list.append(x)? & ajoute l'élément \verb?x? en fin de liste    \\
\verb?list.extend(L)? & ajoute en fin de liste les éléments de L     \\
\verb?list.insert(i, x)? & insère un élément \verb?x? en position \verb?i?  \\
\verb?list.remove(x)? & supprime  la première occurence de \verb?x?    \\
\verb?list.pop(i)?  & supprime l'élément d'indice \verb?i? et le renvoie  \\
\verb?list.index(x)?  & renvoie l'indice de la première occurence de \verb?x?  \\
\verb?list.count(x)?  & renvoie le nombre d'occurences de \verb?x?   \\
\verb?list.sort()?    & modifie la liste en la triant \\
\verb?list.reverse()? & modifie la liste en inversant l'ordre des éléments  \\
\hline
\end{tabular}
\end{center}
\end{frame}



\subsection{Les dictionnaires}



\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> tel={'Roger' : '02 40 00 00 00', 'Marcelle' : '02 40 00 00 01'} 
>>> tel['Marcelle']
'02 40 00 00 01'
\end{lstlisting}
\begin{lstlisting}[caption={}]
>>> tel.has_key('Roger')
True
>>> tel.keys()
['Marcelle', 'Roger']
\end{lstlisting}
\end{frame}






\subsection{Les boucles \og pour\fg{}}


\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
>>> r=range(5)
>>> r
[0, 1, 2, 3, 4]
>>> s=range(3,9)
>>> s
[3, 4, 5, 6, 7, 8]
>>> t=range(3,9,2)
>>> t
[3, 5, 7]
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> def f(n):
    for i in range(n):
        print('Je me répète '+str(n)+' fois')
... ... ... 
>>> f(3)
Je me répète 3 fois
Je me répète 3 fois
Je me répète 3 fois
\end{lstlisting}
\end{frame}















\end{document}



%
%
%
%
%
%
%
%
%
\section{EXERCICES}


% \subsection{Raisonnements}




% \begin{frame}\begin{exercice}
% On note $P=$ \og $x$ est un entier naturel\fg{} et $Q=$ \og $2x$ est un entier naturel
% pair\fg{}.

% \begin{enumerate}
% \item $P\Rightarrow Q${\ est-il un th\'{e}or\`{e}me ?}

% \item {Traduire }$\lnot Q\Rightarrow \lnot P.$

% \item $Q\Rightarrow P$ est-il un th\'{e}or\`{e}me ?

% \item $\lnot P\Rightarrow \lnot Q${\ est-il un th\'{e}or\`{e}me ?}

% \item $P\Leftrightarrow Q$ est-il un th\'{e}or\`{e}me ?
% \end{enumerate}


% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% $a$ et $b$ d\'{e}signent des r\'{e}els et il est clair que l'affirmation ou
% l'\'{e}nonc\'{e} $P=$\og$a=b$\fg{}$\Rightarrow Q=$\og$a^{2}=b^{2}$\fg{} est bien un th%
% \'{e}or\`{e}me.


% \begin{enumerate}
% \item $P$ est-elle une condition n\'{e}cessaire de $Q$ ?

% \item $Q$ est-elle une condition n\'{e}cessaire de $P$ ?

% \item $P$ est-elle une condition suffisante de $Q$ ?

% \item $Q$ est-elle une condition suffisante de $P$ ?

% \item Traduire $\lnot Q\Rightarrow \lnot P.$

% \item $a\neq b\Rightarrow a^{2}\neq b^{2}$ est-il un th\'{e}or\`{e}me ?
% \end{enumerate}
% \end{exercice}\end{frame}






% \begin{frame}\begin{exercice}
%   \begin{enumerate}
%   \item Montrer par une preuve  directe que \og \textit{$n$ et $m$ sont
%     des  entiers pairs\fg{}  $\Longrightarrow$ \og  $n+m$ est  un entier
%     pair}\fg{} est un théorème.
% \item  Montrer par contraposition  que \og  \textit{$n^2$ est  un entier
%     pair}\fg{}   $\Longrightarrow$  \og   \textit{$n$   est  un   entier
%     pair}\fg{} est un théorème.
% \item  Montrer  par  l'absurde  que  \og  \textit{$n+m$  est  un  entier
%     impair}\fg{}  $\Longrightarrow$  \og  \textit{exactement un  nombre,
%     parmi $n$ et $m$ est un entier impair}\fg{} est un théorème.
%   \end{enumerate}
% \end{exercice}\end{frame}





% \begin{frame}\begin{exercice}
% On consid\`{e}re la suite $u$ d\'{e}finie par 
% $$
% \left\{ 
% \begin{array}{l}
% u_{0}=1 \\ 
% n\in \mathbb{N},u_{n+1}=\dfrac{1}{2+u_{n}}%
% \end{array}%
% \right.
% $$%
% D\'{e}montrer par r\'{e}currence que pour tout $n\in \mathbb{N}$ on a $
% u_{n}\in \left[ 0,1\right] .$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% D\'{e}montrer par une r\'{e}currence simple que $$\sum\limits_{i=1}^{n}i=%
% \dfrac{n\left( n+1\right) }{2}.$$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% D\'{e}montrer directement (pas par r\'{e}currence) que $$\sum%
% \limits_{i=1}^{n}i=\dfrac{n\left( n+1\right) }{2}.$$
% \end{exercice}\end{frame}








% \begin{frame}\begin{exercice}[Factorielle]
% Écrivez un algorithme récursif qui donne $n!$ pour tout entier naturel $n$.
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}[Somme]
% Écrivez un algorithme récursif qui calcule $\sum_{k=0}^{n}f(k)$ pour une fonction
% $f$ donnée.
% \end{exercice}\end{frame}



%   \begin{frame}\begin{exercice}[Division euclidienne]
% Déterminer  un algorithme  récursif  qui renvoie  le  quotient de  deux
% entiers naturels non nuls $a$ et $b$.

% Déterminer un algorithme récursif qui renvoie le
% reste entier de $a$ et $b$.
%   \end{exercice}\end{frame}


%   \begin{frame}\begin{exercice}[Somme de chiffres]
% Donnez un  algorithme récursif  qui calcule la  somme des  chiffres d'un
% entier naturel $n$ écrit en base 10.
%   \end{exercice}\end{frame}



%   \begin{frame}[fragile]\begin{exercice}[Héron]\label{heron}
% \textsc{Héron} d'Alexandrie a trouvé une méthode permettant de déterminer
% une approximation de la racine  carrée d'un nombre positif vingt siècles
% avant l'apparition des ordinateurs.\\
% Si  $x_n$  est une  approximation  strictement  positive  par défaut  de
% $\sqrt{a}$, alors $a/x_n$ est  une approximation par excès de $\sqrt{a}$
% (pourquoi~?) et vice-versa.\\
% La    moyenne   arithmétique    de   ces    deux    approximations   est
% $\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$  et constitue  une meilleure
% approximation que les deux précédentes.\\
% On  peut  montrer c'est  une  approximation  par  excès (en  développant
% $\left(x_n-\sqrt{a}\right)^2$ par exemple).\\
% On obtient  naturellement un algorithme... Donnez  une version récursive
%  prenant en argument  le nombre dont on cherche la racine
% carrée, une première approximation $x_0$ et une précision \verb+eps+.
% \end{exercice}
% \end{frame}



%   \begin{frame}\begin{exercice}[Décimales de e]
    

% Posons $e_n=1+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{n!}$

% Alors on a aussi
% $$e_n=1+1+\frac{1}{2}\left(1+\frac{1}{3}\left(1+\frac{1}{4}\left(\cdots \left(\frac{1}{n-1}\left(1+\frac{1}{n}\right)\right)\right)\right)\right)$$


% Un           exercice           classique           montre           que
% $e-e_n \ie \frac{n+2}{n+1}\frac{1}{(n+1)!}$.

% Ainsi,   pour  $n=167$,   on   obtiendra  $300$   bonnes  décimales   au
% moins: trouvez-les~!

%   \end{exercice}\end{frame}


% %

%   \begin{frame}\begin{exercice}[Fractions continues dans Q]
    
%  \begin{itemize}
  
% \item Vous connaissez l'algorithme suivant:

% %\begin{minipage}{\textwidth}
% \begin{eqnarray}
% 172&=&3\times\textcolor{0.2white}{51}+\textcolor{0.2white}{19}\\
% \textcolor{0.2white}{51}&=&2\times\textcolor{0.2white}{19}+13\\
% 19&=&1\times13+6\\
% 13&=&2\times 6+1\\
% 6&=&6\times 1+0
% \end{eqnarray}
% %\end{minipage}

% \item On peut donc facilement compléter  la suite d'égalité suivante:


% %\begin{minipage}{\textwidth}
% $$\frac{172}{51}=3+\frac{19}{51}=3+\frac{1}{\frac{51}{19}}=3+\frac{1}{2+
%   \frac{13}{19}}=\dots $$
% %\end{minipage}

% \item  Quand  tous les  numérateurs  sont  égaux à  1,  on  dit qu'on  a
%   développé $\frac{172}{51}$ en
%   fraction continue et pour simplifier l'écriture on note:
% $$\frac{172}{51}=[3; 2; \dots ]$$

% \item Par exemple, on peut développer  $\frac{453}{54}$ en fraction continue.

% \item Dans l'autre sens on peut écrire $[2; 5; 4]$ sous la forme d'une fraction irréductible.

%   \end{itemize}

% On suppose connus les algorithmes  donnant le reste et le quotient d'une
% division euclidienne.

% Écrivez un algorithme donnant le développement en fraction continue d'un
% rationnel.



% Écrivez ensuite un algorithme récursif qui effectue la transformation inverse.

%   \end{exercice}\end{frame}






%   \begin{frame}\begin{exercice}[Fractions continues dans R]

% En  fait,  l'étude précédente  correspond  à  un  cas particulier  d'une
% définition plus générale.

% Soit $x$ un  réel non entier. On construit une  suite entière $(z_n)$ de
% la manière suivante:


% \[x=z_0+\frac{1}{x_1}\qquad          z_0=\lfloor          x\rfloor\qquad
% x_1=\frac{1}{x-z_0}\]

% puis, tant que $x_k$ n'est pas entier:


% \[x_k=z_k+\frac{1}{x_{k+1}}\qquad          z_k=\lfloor          x_k\rfloor\qquad
% x_{k+1}=\frac{1}{x_k-z_k}\]


% Le  développement de  $x$ en  fractions  continues est  alors donné  par
% $[z_0,z_1,z_2,\dots]$, cette liste pouvant être infinie.
    

% Écrivez un  algorithme récursif qui donne $n$  chiffres du développement
% en fraction continue d'un nombre $x$ donné.
%   \end{exercice}\end{frame}

%   \begin{frame}[fragile]
% \begin{exercice}
% On  définit  deux fonctions  \verb+tete+  et  \verb+queue+ qui  renvoient
% respectivement le premier  élément d'une liste et la  liste privée de sa
% tête. La syntaxe dépend des langages.\\
% Écrivez à  présent une fonction  récursive qui renvoie le  maximum d'une
% liste de nombres.
% \end{exercice}
% \end{frame}


%   \begin{frame}\begin{exercice}[Palindrome]
% Écrivez un algorithme récursif qui vérifie si une liste est un palindrome.
%   \end{exercice}\end{frame}








%   \begin{frame}\begin{exercice}[Nombres parfaits]

% Un nombre parfait  est un nombre entier $n$  strictement supérieur à $1$
% qui est égal à la somme de ses diviseurs (sauf $n$ bien sûr~!).

% \begin{enumerate}
% \item Il y en a un caché entre 1 et 10: trouvez-le...
% \item Écrivez un algorithme récursif qui donne la liste des diviseurs
%   d'un entier autres que lui-même.
% \item  Écrivez un  algorithme qui  calcule la  somme des  éléments d'une
%   liste.
% \item  Écrivez un  algorithme  qui  détermine si  un  nombre entier  est
%   parfait.
% \item Écrivez un algorithme récursif qui donne la liste des nombres
% parfaits entre 1 et un nombre $n$ donné.
% \end{enumerate}

%   \end{exercice}\end{frame}



%   \begin{frame}\begin{exercice}[Décomposition en base 2]

% Une  méthode  pour  obtenir  l'écriture   en  base  2  d'un  nombre  est
% d'effectuer des divisions successives. Par exemple pour 11:

% \begin{center}
% \opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{11}{2}\hspace{1cm}
% \opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{5}{2}
% \hspace{1cm}
% \opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{2}{2}
% \hspace{1cm}
% \opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{1}{2}

% \end{center}

% \begin{align*}
% 11 &=\Bigl(2\times5+1\Bigr)
% \\ &=\Bigl(2\times\bigl(2\times2+1\bigr)+1\Bigr)
% \\ &=\Bigl(2\times\bigl(2\times(2\times 1)+1\bigr)+1\Bigr)
% \\ &=\Bigl(2\times (2^2+1)+1\Bigr)
% \\ &=2^3+2+1
% \\ &=1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0 
% \end{align*}



% L'écriture de  11 en base  2 est donc  1011: c'est la liste  des restes
% obtenus mais dans l'ordre inverse.


% La méthode est facilement généralisable.  


% Écrivez un algorithme récursif qui donne la décomposition d'un entier en
% base 2 sous forme d'une liste.
%   \end{exercice}\end{frame}



% \begin{frame}[fragile]
% \begin{exercice}


% On   définit la  partie entière  d'un réel $x$  comme étant  le plus
% grand entier inférieur à $x$.



% On part du fait que la  partie entière d'un nombre appartenant à $[0;1[$
% est nulle.

% Commentez l'algorithme suivant:
% \begin{algo}
% \FUNC{partie\_entiere}{%
% \pfarg{x}{flottant}}{entier}
% \BEGIN
% \IF{x>=0 et x<1}
% \RETURN{0}
% \ELSE
% \IF{x>=0}
% \RETURN{1+partie\_entiere(x-1)}
% \ELSE
% \RETURN{-1+partie\_entiere(x+1)}
% \ENDIF
% \ENDIF
% \END
% \end{algo}
% \end{exercice}
% \end{frame}




% \begin{frame}[fragile]
% \begin{exercice}
% Prouvez par récurrence l'exactitude de l'algorithme suivant:
% \begin{algo}
% \FUNC{Carré}{%
% \pfarg{n}{entier positif}}{entier positif}
% \BEGIN
% \STATE{sq \recoit{} 0}
% \FOR{i}{1}{n}
% \STATE{sq \recoit{} sq+2*i-1}
% \ENDFOR
% \RETURN{sq}
% \END
% \end{algo}
% \end{exercice}
% \end{frame}







% \begin{frame}\begin{exercice}
% On se propose de d\'{e}montrer que tous les \'{e}tudiants en informatique
% ont le m\^{e}me \^{a}ge et, pour cela, on note $P\left( n\right) $
% l'affirmation%



% \og \textit{si \ on choisit $n$ \'{e}tudiants en informatique $\left( n\in \mathbb{N}%
% ^{\ast }\right) $, il est s\^{u}r qu'ils ont tous le m\^{e}me \^{a}ge}\fg{}%



% Il est clair que $P\left( 1\right) $ est vraie. 

% D\'{e}montrons que $P\left(
% n\right) \Rightarrow P\left( n+1\right)$. Pour cela nous supposons que $%
% P\left( n\right) $ est vraie (c'est l'hypoth\`{e}se de r\'{e}currence) et
% nous choisissons un groupe quelconque de $n+1$ \'{e}tudiants que nous
% ordonnons par ordre alphab\'{e}tique (pourquoi pas). D'apr\`{e}s l'hypoth%
% \`{e}se de r\'{e}currence, les $n$ premiers de l'ordre alphab\'{e}tique ont
% tous le m\^{e}me \^{a}ge ainsi que les $n$ derniers. Comme ces deux groupes
% de $n$ \'{e}tudiants ont au moins un \'{e}tudiant en commun, on en d\'{e}%
% duit qu'ils ont tous le m\^{e}me \^{a}ge.%

% Nous venons de d\'{e}montrer que $P\left( n\right) \Rightarrow P\left(
% n+1\right) $ pour tout $n\geq 1$ et, comme $P\left( 1\right) $ est vrai, $%
% P\left(  n\right) $  est toujours  vrai pour  tout $n\geq  1.$ \textbf{Y
%   a-t-il une erreur dans le raisonnement ?}
% \end{exercice}\end{frame}

% \subsection{Ensembles}

% \begin{frame}\begin{exercice}
% On rappelle qu'une paire ordonnée (ou couple) se note $(a,b)$ et qu'on a 
% $$(a,b)=(x,y) \Leftrightarrow a=x \text{ et } b=y$$
% Montrez que le couple $(a,b)$ peut également être défini par:
% $$(a,b)=\bigl\{\bigl\{a\bigr\},\bigl\{a,b\bigr\}\bigr\}$$
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
% $E=\left\{ 0,1,2,3,4,5,6\right\} .$ D\'{e}finir en extension les ensembles
% suivants :
% \begin{enumerate}
% \item $A_{1}=\left\{ x\in \mathbb{N}\mid x^{2}\in E\right\} $

% \item $A_{2}=\left\{ x\in \mathbb{R}\mid x^{2}\in E\right\} $

% \item $A_{3}=\left\{ x\in E\mid x^{2}\in E\right\} $

% \item $A_{4}=\left\{ x\in E\mid \sqrt{x}\in E\right\} $

% \item $A_{5}=\left\{ x\in E\mid 2x\in E\right\} $

% \item $A_{6}=\left\{ x\in E\mid \frac{x}{2}\in E\right\} $
% \end{enumerate}

% \end{exercice}\end{frame}




% \begin{frame}\begin{exercice}
% $E=\left\{ 0,1,2,3,4\right\} .$ Compl\'{e}ter, lorsque c'est possible, par
% un des symboles (il peut y avoir plusieurs solutions, mais on s'obligera 
% \`{a} choisir celle qui donne le plus \og de renseignements\fg{}): 
% $$
% \in ,\ni ,\subset ,\supset ,\subseteq ,\supseteq ,=,\neq ,\varsubsetneq
% ,\cdots$$



% \begin{enumerate}
% \item $2\cdots E,$ $\left\{ 2,3\right\} \cdots E,$ $\left\{ 2\right\} \cdots
% E$

% \item $\left\{ 2,3,4\right\} \cdots \left\{ 4,3,2\right\} ,$ $\left\{
% 2,3,4\right\} \cdots \left\{ 4,3,0\right\} $

% \item $\emptyset \cdots E,$ $E\cdots E,$ $E\cdots \left\{ E\right\} ,$ $%
% \emptyset \cdots \left\{ E\right\} $

% \item $E\cdots \left\{ 0,1,2,3,\ldots ,10\right\} ,$ $\left\{
% 0,1,2,3,4,5\right\} \cdots E$
% \end{enumerate}




% \end{exercice}\end{frame}












% \begin{frame}\begin{exercice}
% On définit un opérateur $\divideontimes$ sur les ensembles de la manière
% suivante:
% $$
% A \divideontimes B = \lnot (A \cap B)
% $$
% Démontrer les égalités suivantes:

% \begin{enumerate}
% \item $A \divideontimes A = \lnot A$;
% \item $(A \divideontimes A)  \divideontimes (B \divideontimes B) =A \cup
%   B$;
% \item  $(A \divideontimes  B) \divideontimes  (A \divideontimes  B)  = A
%   \cdots B$.
% \end{enumerate}

% \end{exercice}\end{frame}













% \begin{frame}\begin{exercice}
%   Expliciter $\mathcal{P}(\mathbb{N}_{n})$ pour pour $n\in \left\{
% 1,2,3\right\}$.         On          rappelle         la         notation
% $\mathbb{N}_{n}=\left\{ 1,2,3,...,n\right\}= \llbracket 1,n\rrbracket.$
% \end{exercice}\end{frame}




% \begin{frame}\begin{exercice}
% Expliciter $\mathcal{P}\left( \left\{ a,\left\{ a\right\} \right\} \right) .$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% Expliciter $\mathcal{P}(\emptyset ),$ $\mathcal{P}\left( \mathcal{P}%
% (\emptyset )\right) .$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% Expliciter $\mathcal{P}\left( \mathcal{P}(\mathbb{N}_{2})\right) .$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% Donner cinq \'{e}l\'{e}ments de $\mathcal{P}\left( \mathcal{P}\left( 
% \mathcal{P}\left( \left\{ a,b,c\right\} \right) \right) \right) .$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% D\'{e}montrer par r\'{e}currence : 
% \begin{center}
% $E$ possède $n$ \'{e}l\'{e}ments $%
% \Rightarrow $ $\mathcal{P}(E)$ poss\`{e}de $2^{n}$ \'{e}l\'{e}ments.
% \end{center}
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% Combien d'\'{e}l\'{e}ments $\mathcal{P}\left( \mathcal{P}\left( \mathcal{P}%
% \left( \left\{ a,b,c\right\} \right) \right) \right) $ contient-il ?
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% \textbf{D\'{e}montrer} que $A\subseteq B\Rightarrow \mathcal{P}(A)\subseteq 
% \mathcal{P}(B)$.
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
% $E=\left\{ a,b,c,d\right\} ,$ $A\subset E,B\subset E$

% \begin{enumerate}
% \item \textit{Vrai ou Faux , }$\left\{ \emptyset ,\left\{ a\right\} ,\left\{
% b,c\right\} \right\} \in \mathcal{P}\left( E\right) .$

% \item \textit{Vrai ou Faux , }$\left\{ \emptyset ,\left\{ a\right\} ,\left\{
% b,c\right\} \right\} \subseteq \mathcal{P}\left( E\right) .$

% \item \textit{Vrai ou Faux , }$\left\{ \emptyset \right\} \in \mathcal{P}%
% \left( E\right) .$

% \item \textit{Vrai ou Faux , }$\emptyset \in \mathcal{P}\left( E\right) .$

% \item \textit{Vrai ou Faux , }$\left\{ \emptyset \right\} \subseteq \mathcal{%
% P}\left( E\right) .$

% \item \textit{Vrai ou Faux , }$\left\{ \emptyset \right\} \subset \mathcal{P}%
% \left( E\right) .$

% \item \textit{Quel est le cardinal de }$\mathcal{P}\left( \mathcal{P}\left(
% E\right) \right) .$

% \item Vrai ou Faux , $\left\{ A,B\right\} \in \mathcal{P}\left( E\right) .$

% \item Vrai ou Faux , $\left\{ A,B\right\} \subset \mathcal{P}\left( E\right)
% .$
% \end{enumerate}

% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
% Trouver deux ensembles $A$ et $B$ qui v\'{e}rifient :%
% $$
% A\in B\text{ et }A\subseteq B
% $$%
% On indiquera 5 solutions.
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
%   $A,$ $B$ et $C$ sont trois parties de l'ensemble $E$ v\'{e}rifiant $A\cap
% B\cap C\neq \emptyset .$ Repr\'{e}senter \`{a} l'aide de \og patates\fg{}
% (diagramme de Venn) les ensembles suivants :


% \begin{enumerate}
% \item $A\cup B,$ $A\cap C,$ $A\bigtriangleup C,$ $\complement_{B}(A\cap
% B), $ $A-\complement_{E}B,$ $\left( \complement%
% _{E}B\right) -A$

% \item $(A\cap B)-C,$ $(A-C)\cap (B-C)$

% \item $(A\bigtriangleup B)\bigtriangleup C,$ $\left( (A\bigtriangleup B)\bigtriangleup C\right) -(A\cup B),$ 
% $\complement_{A\cup B}\left( A\bigtriangleup B\right) $

% \item $\overline{A}\cup \overline{B},$ $\overline{A\cap B},$ $\overline{%
% A\cup B},$ $\overline{A}\cap \overline{B}$
% \end{enumerate}
% \end{exercice}\end{frame}






% \begin{frame}\begin{exercice}
% D\'{e}montrer : $\bigl[ A\cup B=B\bigr] \Leftrightarrow \bigl[ A\subseteq B%
% \bigr] $
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% D\'{e}montrer : $\bigl[ A\cap B=B\bigr] \Leftrightarrow \bigl[ B\subseteq A%
% \bigr] $
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
% Repr\'{e}senter par des \og patates\fg{}, lorsque c'est possible, deux ensembles $A$
% et $B$ v\'{e}rifiant :

% \begin{enumerate}
% \item $A\cap B=\emptyset $

% \item $A\cup B=A$

% \item $A\cap B=B$

% \item $A\bigtriangleup B=B$

% \item $A\bigtriangleup B=\emptyset $
% \end{enumerate}


% \end{exercice}\end{frame}




% \begin{frame}\begin{exercice}
% $A=\left\{ a,b\right\} $ et $E=\left\{ a,b,c,d,e\right\} ,$ expliciter tous
% les ensembles $B$ qui v\'{e}rifient $A\cup B=E.$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% $A$ et $B$ sont deux parties de $E.$ Si $A\subseteq B$ que peut-on dire de $%
% \overline{A}$ et $\overline{B}$ ?
% \end{exercice}\end{frame}



% \begin{frame}\begin{exercice}
% Repr\'{e}senter chacun des 4 ensembles $A_{i\in \left\{ 1,2,3,4\right\} }$
% par une \og patate\fg{} sachant que l'intersection d'un nombre quelconque de ces
% ensembles n'est jamais vide et qu'aucun n'est inclus dans un autre puis repr%
% \'{e}senter 
% $$
% A_{1}\bigtriangleup A_{2}\bigtriangleup A_{3}\bigtriangleup A_{4}
% $$
% On rappelle que l'op\'{e}ration $\bigtriangleup $ est associative et commutative.
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% $A=\left\{ 0,1,2,3\right\} ,$ $B=\left\{ a,b\right\} $ et $C=\left\{
% 1,2\right\} .$ Donner quelques \'{e}l\'{e}ments de:

% \begin{enumerate}
% \item $A\times B,$ $\left( A\times B\right) \times C,A\times B\times C,$ $%
% A\times \left( B\times C\right) ,$ $C\times \left( A\cup B\right) ,$ $A^{5}$

% \item $\mathcal{P}(A)\times \mathcal{P}(B)$

% \item $\mathcal{P}(A\times B)$

% \item $\emptyset \times A,$ $A\times \left( \emptyset \times B\right) ,$ $%
% \left\{ \emptyset \right\} \times B$
% \end{enumerate}
% \end{exercice}\end{frame}







% \begin{frame}\begin{exercice}
%   $A$, $B$ et $C$ sont trois ensembles tous diff\'{e}rents de l'ensemble vide.
% D\'{e}montrer que $$\left( A\cap B\right) \times C=\left( A\times C\right)
% \cap \left( B\times C\right) .$$
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
%   $E=\left\{ a,b,c,d,e\right\} $


% \begin{enumerate}
% \item \textit{Donner 4 partitions de }$E$\textit{.}

% \item \textit{Vrai ou Faux , }$\left\{ \emptyset ,\left\{ a\right\} ,\left\{
% b,c,e\right\} ,\left\{ d\right\} \right\} $\textit{\ est une partition de }$%
% E.$

% \item \textit{Vrai ou Faux , }$\left\{ \left\{ a\right\} ,\left\{
% b,c\right\} ,\left\{ d\right\} \right\} $\textit{\ est une partition de }$E.$
% \end{enumerate}


% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
% \begin{enumerate}
% \item Si $A\cap B=A\cup B$, que peut-on dire de $A$ et $B$?
% \item Si $A\cap B=A\cap C$ et  si $A\cup B=A\cup C$, que peut-on dire de
%   $A$, $B$ et $C$?
% \end{enumerate}
% \end{exercice}\end{frame}




% \begin{frame}\begin{exercice}
%   \begin{enumerate}
%   \item On pose $A=\bigl\{a,b\bigr\}$ et $B=\bigl\{b,c\bigr\}$.
%     \begin{enumerate}
%     \item Comparer $\PR(A)\cap \PR(B)$ et $\PR(A\cap B)$.
%     \item Comparer $\PR(A)\cup \PR(B)$ et $\PR(A\cup B)$.
%     \end{enumerate}
%   \item Répondre aux mêmes questions avec A et B des ensembles quelconques.
%   \end{enumerate}
% \end{exercice}\end{frame}









% \end{document}





\subsection{Calcul booléen}


\begin{frame}\begin{exercice}
  Calculer $1\cdot \overline{0}$, $ 1+\overline{1}$, $0 \cdot
      \overline{0}$ et $ \overline{\left(1+0\right)}$.
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}
\begin{enumerate}
\item Résoudre dans $\BR$ les équations:
\begin{multicols}{2}
  \begin{enumerate}
  \item $x\cdot 1=0$ \item $ x+x=0$
    \item $ x\cdot 1=0$ \item $ x\cdot \overline{x}=1$
  \end{enumerate}
\end{multicols}
\item Résoudre dans $\BR^2$ l'équation $xy=x+y$.
\end{enumerate}
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}\label{bool_exo}
Dresser les tables canoniques des fonctions suivantes:

  \begin{enumerate}
  \item $f(x,y,z)=\overline{z}$ \item $ f(x,y,z)=\overline{x}y+\overline{y}z$
    \item $ f(x,y,z)=x \overline{y}z+\overline{\left(xyz\right)}$ \item $ f(x,y,z)=\overline{y}\left(xz+\overline{xz}\right)$
  \end{enumerate}
\end{exercice}\end{frame}








\begin{frame}
\begin{exercice}
  L'opérateur booléen $\oplus$ est défini par:
$1\oplus 1=0$, $ 1\oplus 0=1$, $ 0\oplus 1=1$ et $ 0\oplus 0=0$.
\begin{enumerate}
\item Simplifier:
  \begin{enumerate}
  \item $x \oplus 0$ \item $x\oplus 1$
  \item $ x\oplus x$ \item $ x \oplus \overline{x}$
\end{enumerate}
\item Montrer que:
  \begin{enumerate}
  \item $x \oplus y=\left(x+y\right)\overline{\left(xy\right)}$
  \item $ x\oplus y=\left(x \overline{y}\right)+\left(\overline{x}y\right)$
  \end{enumerate}
\item L'opération $\oplus$ est-elle commutative?
\item Vrai ou faux?
  \begin{enumerate}
  \item $  x \oplus \left(y\oplus  z\right)=\left(x\oplus y\right)\oplus
    z$
  \item $x+\left(y\oplus z\right)=(x+y)\oplus(x+z)$
\item $x \oplus(y+z)=(x\oplus y)+(x\oplus z)$
  \end{enumerate}
\end{enumerate}
\end{exercice}
\end{frame}









\begin{frame}\begin{exercice}
$\mathcal{B}$ est une alg\`{e}bre de Boole et dans ce qui suit on travaille
dans $\mathcal{B}$ ; d\'{e}velopper et r\'{e}duire les expressions :

\begin{enumerate}
\item $(a+b)(a+b+c)(c+\overline{d})$

\item $(a+b)(b+c)(c+d)(d+a)$

\item $\overline{(a+b)(b+c)(c+d)(d+a)}$

\item $\overline{(a+\overline{b})}.(\overline{c.b.\overline{d})}.(a.b+c).%
\overline{(b.c+d)}.\overline{(a.b.\overline{c}+\overline{a}.d)}$

\item $\overline{\overline{(a+\overline{b})}.(\overline{c.b.\overline{d})}%
.(a.b+c).\overline{(b.c+d)}.\overline{(a.b.\overline{c}+\overline{a}.d)}}$

\item $(a+b)(a+c)(a+d)(a+e)$

\item $\overline{(a+b)(a+c)(a+d)(a+e)}$

\item $(a+b)(a+c)+(a+d)(a+e)+(\overline{a}+b)(\overline{a}+c)+\overline{e}$
\end{enumerate}
\end{exercice}\end{frame}



\begin{frame}\begin{exercice}
On consid\'{e}re la fonction bool\'{e}enne de 4 variables d\'{e}finie par : 

$$f=a\overline{b}c+\overline{a}cd+abc\overline{d}$$



\begin{enumerate}
\item L'\'{e}criture pr\'{e}c\'{e}dente est-elle une \'{e}criture
disjonctive ? conjonctive ?

\item Mettre $f$ { sous forme canonique disjonctive puis
sous forme canonique conjonctive.}
\end{enumerate}
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}
Donner l'\'{e}criture canonique disjonctive puis conjonctive de toutes les
fonctions bool\'{e}\-ennes de 2 variables. On remarquera n\'{e}anmoins que
la fonction nulle n'admet pas d'\'{e}criture canonique disjonctive.
\end{exercice}\end{frame}

\begin{frame}\begin{exercice}
Combien existe-t-il de fonctions bool\'{e}ennes de 3 variables ?
\end{exercice}\end{frame}

\begin{frame}\begin{exercice}
On consid\`{e}re la fonction bool\'{e}enne de 4 variables d\'{e}finie par : 

{\footnotesize
$
f=\overline{\left( (\overline{a}+c+d)(b+c+d)(a+b+\overline{c})(a+\overline{c}%
+\overline{d})(a+\overline{b}+\overline{d})(\overline{b}+c+\overline{d}%
)\right) }
$
}

\begin{enumerate}
\item L'\'{e}criture pr\'{e}c\'{e}dente est-elle une \'{e}criture
disjonctive ? conjonctive ?

\item Mettre 
$f$ sous forme canonique disjonctive puis
sous forme cononique conjonctive.
\end{enumerate}
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}
$f=f(a,b,c)=a+b+c$ est une fonction bool\'{e}enne de 3 variables. Donner la
forme canonique disjonctive de $f$ puis la forme canonique conjonctive de $%
f. $
\end{exercice}\end{frame}





\begin{frame}\begin{exercice}
On définit deux autres opérateurs:
\begin{itemize}
\item  l'opérateur $\nor$  défini  par $1\nor  1=1\nor  0=0\nor 1=0$  et
  $0\nor0=1$ qu'on appellera \og NOR\fg{};
\item l'opérateur  $\nand$ défini par   $1\nand 0=0\nand
  1=0\nand 0=1$ et $1\nand 1=0$ qu'on appellera \og NAND\fg{}.
\end{itemize}
\begin{enumerate}
\item Montrer que:
  \begin{enumerate}
  \item $  \overline{x}=x\nand x=x\nor  x$ \item $  xy=(x\nand y)\nand(x\nand
    y)$
  \item $ x+y=(x\nand x)\nand(y\nand y)$
\item $xy=(x\nor y)\nor(y \nor y)$
\item $x+y=(x\nor y)\nor(x\nor y)$
  \end{enumerate}
\item Exprimer  chacune des  fonctions de l'exercice  \vref{bool_exo} en
  utilisant uniquement l'opérateur $ \nand$ puis uniquement l'opérateur $ \nor$.
\end{enumerate}
\end{exercice}\end{frame}









\begin{frame}\begin{exercice}[Machine à voter]
Le  gouvernement syldave  est constitué  de trois  membres  qui prennent
toutes les décisions en votant  à bulletins secrets. Une proposition est
adoptée lorsqu'elle reçoit au moins deux votes sur trois. Leur conseiller
technique, ancien  étudiant de  l'IUT de Nantes,  leur propose  un petit
circuit qui détermine si une décision est adoptée. 

On note  $x$, $y$  et $z$ les  variables booléennes qui  correspondent à
chacun  des  votes  du  triumvirat. Déterminer  une  fonction  booléenne
$f(x,y,z)$ qui réponde au  problème et dessiner le circuit correspondant
avec les portes NOT, AND et OR.
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}[Interrupteur]
Le  président syldave (il  a fait  exécuter les  deux autres  membres du
gouvernement  grâce  à une  chaise  électrique  mise  au point  par  son
conseiller technique) a fait construire  un palais et désire que dans sa
chambre, la  lumière soit commandée par deux  interrupteurs. En appuyant
sur l'un quelconque  des interrupteurs, il faut que  la lumière s'allume
si elle  est éteinte  et s'éteigne si  elle est allumée.  Déterminer une
fonction  booléenne  $f(x,y)$ répondant  au  problème  avec  $x$ et  $y$
correspondant   à  chacun   des  interrupteurs.   Dessiner   le  circuit
correspondant avec les portes NOT, AND et OR.

Reprendre le problème avec trois interrupteurs.
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}[Comparateur]
  Construire  un  circuit  qui  compare  deux entiers  de  deux  bits  $
  (x_1x_0)_2$ et  $(y_1y_0)_2$ et qui renvoie  1 si le  premier est plus
  grand que le second et 0 sinon.
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}[NOR et NAND]
 Utiliser des portes NOR (puis NAND) pour obtenir les sorties suivantes:

 \begin{multicols}{2}
   \begin{enumerate}
   \item $\overline{x}$ \item $ x+y$
  \item $ xy$ \item $ x \oplus y$
   \end{enumerate}
 \end{multicols}
\end{exercice}\end{frame}



\begin{frame}\begin{exercice}[Demi-additionneur]
  On veut additionner deux nombres binaires de deux bits. La sortie sera
  double: une  variable $u$ contiendra l'\og unité\fg{}  et une variable
  $r$ contiendra la \og retenue\fg{}. Dresser un tableau puis dessiner
  un circuit ayant deux sorties avec les portes NOT, AND et OR.
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}[Recherche: additionneur n-bits]
Un peu de recherche: on  dispose de demi-additionneurs (qu'on notera 1/2
Add) et de portes NOT,
AND et OR.

Imaginez alors un additionneur complet qui prend en entrée un nombre de
deux bits et une retenue et  renvoie une unité et une retenue. On notera
cette porte Add.

Imaginez alors comment, à l'aide de  portes Add et 1/2 Add, fabriquer un
additionneur $n$-bits.
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}
Dessiner   le  circuit  correspondant   aux  fonctions   suivantes  puis
simplifier les formules à  l'aide d'un diagramme de \textsc{Karnaugh} et
dessiner le nouveau circuit à l'aide de portes NOT, AND et OR.

\begin{enumerate}
\item              $              f(x,y,z)=xy             \overline{z}+x
  \overline{y}\overline{z}+\overline{x}y
  \overline{z}+\overline{x}\overline{y}\overline{z}$.
\item $ f(x,y,z)=\overline{x}yz \left((x+\overline{z})+(\overline{y}+\overline{z})\right)$
\end{enumerate}
\end{exercice}\end{frame}


\begin{frame}\begin{exercice}
  Simplifier  les  expressions  suivantes  à l'aide  d'un  diagramme  de
  \textsc{Karnaugh}.

  \begin{enumerate}
  \item    $   f(w,x,y,z)=wxyz+wx    \overline{y}z+wx   \overline{y}z+wx
    \overline{y}\overline{z}+w        \overline{x}y       \overline{z}+w
    \overline{x}\overline{y}z$
\item      $f(w,x,y,z)=wxyz+wxy      \overline{z}+wx     \overline{y}z+w
  \overline{x}yz+w                                          \overline{x}y
  \overline{z}+\overline{w}xyz+\overline{w}\overline{x}yz+\overline{w}\overline{x}y
  \overline{z}+\overline{wxy}z$
  \end{enumerate}
\end{exercice}\end{frame}



\end{document}

% \subsection{Relations binaires}



% \begin{frame}\begin{exercice}
% $E_{1}=\left\{ a,b,c,d\right\} ,E_{2}=\left\{ 0,1,2\right\} ,E_{3}=\left\{
% \alpha ,\beta ,\gamma ,\delta ,\epsilon \right\} .$ On consid\'{e}re les
% relations $\mathcal{R}=\left( E_{1},E_{2},G_{\mathcal{R}}\right) $ et $%
% \mathcal{S}=\left( E_{2},E_{3},G_{\mathcal{S}}\right) $ avec 
% \begin{eqnarray*}
% G_{\mathcal{R}} &=&\left\{ (a,0),(a,1),(c,1),(d,0)\right\} \\
% G_{\mathcal{S}} &=&\left\{ (1,\beta ),(2,\delta ),(2,\varepsilon )\right\}
% \end{eqnarray*}


% \begin{enumerate}
% \item P{r\'{e}ciser }$\limfunc{dom}\mathcal{R}${\ et }$\limfunc{Im}%
% \mathcal{R}.$

% \item $\mathcal{R}${\ est-elle totale ?}

% \item {Reprendre les questions pr\'{e}c\'{e}dentes avec }$\mathcal{S}%
% . $

% \item {D\'{e}terminer }$\mathcal{S}\circ \mathcal{R}.${\ Pr%
% \'{e}ciser }$\limfunc{dom}\left( \mathcal{S}\circ \mathcal{R}\right) ${\
% et }$\limfunc{Im}\left( \mathcal{S}\circ \mathcal{R}\right) .$

% \item {D\'{e}terminer les relations }$\mathcal{R}^{-1}${\ et }$%
% \mathcal{S}^{-1}.$

% \item {Vrai ou faux ?}

% \begin{enumerate}
% \item $a\mathcal{R}1$

% \item $\mathcal{R}\left( b,0\right) $

% \item $\left( 1,c\right) \in \mathcal{R}^{-1}$

% \item $\left( a,\beta \right) \in \mathcal{S}\circ \mathcal{R}$

% \item $\left( a,\beta \right) \in \mathcal{R}.\mathcal{S}$
% \end{enumerate}

% \item $\mathcal{R}^{-1}${\ est-elle une fonction ?}

% \item {D\'{e}terminer la relation }$\mathcal{S}^{-1}.\mathcal{R}%
% ^{-1}. $

% \item {D\'{e}terminer }$\mathcal{R}\circ \mathcal{S}.$

% \item {D\'{e}terminer les relations suivantes :} $\mathcal{R}_{\mid
% \left\{ a\right\} },$ $\mathcal{R}_{\mid \left\{ b\right\} },$ $\mathcal{R}%
% _{\mid \left\{ a,b\right\} },$ $\mathcal{R}_{\mid \left\{ 1\right\} }^{-1},%
% \mathcal{R}_{\mid \left\{ 1\right\} }.$
% \end{enumerate}


% \end{exercice}\end{frame}



















% \begin{frame}\begin{exercice}
% $\mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) ${\ et }$\mathcal{R}%
% ^{\prime }=\left( E^{\prime },F^{\prime },G_{\mathcal{R}^{\prime }}\right) $%
% {\ sont deux relations.}


% \begin{enumerate}
% \item {Dans quel(s) cas }$\mathcal{R}^{-1}${\ n'existe pas ?}

% \item {Dans quel(s) cas }$\mathcal{R}\circ \mathcal{R}^{\prime }$%
% {\ n'existe pas ?}

% \item {Dans quel(s) cas }$\mathcal{R}\circ \mathcal{R}^{\prime }$%
% {\ et }$\mathcal{R}^{\prime }\circ \mathcal{R}${\ existent
% simultan\'{e}ment ?}
% \end{enumerate}

% \end{exercice}\end{frame}








% \begin{frame}\begin{exercice}
% $\mathcal{R}$ est une relation de $E$ vers $F$ dont le graphe est $G_{%
% \mathcal{R}}$. Cette relation est not\'{e}e%
% $$
% \mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) \text{ avec \'{e}videmment }G_{%
% \mathcal{R}}\subseteq E\times F
% $$%
% Si $U$ est une partie de $E$, la relation $\left( U,F,G_{\mathcal{R}}\cap
% \left( U\times F\right) \right) $ est not\'{e}e $\mathcal{R}_{\mid U},$
% c'est la restriction de la relation $\mathcal{R}$ \`{a} la partie $U$ de $E.$
% La relation $\left( E,F,G_{\mathcal{R}}\cap \left( U\times F\right) \right) $
% est une sous relation de $\mathcal{R}$ qui est not\'{e}e $U\vartriangleleft 
% \mathcal{R},$ c'est une restriction de domaine de $\mathcal{R}$ \`{a} $U.$
% Sachant que $U$ est une partie de $E$ et $V$ une partie de $F,$ d\'{e}finir
% les relations suivantes en pr\'{e}cisant leur ensemble de d\'{e}part, leur
% ensemble d'arriv\'{e}e et leur graphe


% \begin{enumerate}
% \item $\mathcal{R}_{1}=\left( \mathcal{R}_{\mid V}^{-1}\right) ^{-1}.$

% \item $\mathcal{R}_{2}=\left( \mathcal{R}_{\mid V}^{-1}\right) _{\mid
% U}^{-1}.$

% \item $\mathcal{R}3=\left( \left( \mathcal{R}_{\mid U}\right) _{\mid
% V}^{-1}\right) ^{-1}.$

% \item $\mathcal{R}_{4}=\left( V\vartriangleleft \mathcal{R}^{-1}\right)
% ^{-1} $ {que l'on note} $\mathcal{R}\vartriangleright V.$

% \item $\mathcal{R}_{5}=U\vartriangleleft \left( V\vartriangleleft \mathcal{R}%
% ^{-1}\right) ^{-1}$ {que l'on note} $U\vartriangleleft \mathcal{R}%
% \vartriangleright V.$

% \item $\mathcal{R}_{6}=\left( \left( \left( U\vartriangleleft \mathcal{R}%
% \vartriangleright V\right) _{\mid U}\right) _{\mid V}^{-1}\right)
% ^{-1}.\medskip $
% \end{enumerate}

% \end{exercice}\end{frame}









% \begin{frame}\begin{exercice}
% $E=\left\{ a,b,c,d\right\} ,$ $F=\left\{ 1,2,3,4,5\right\} ,$ $G_{\mathcal{R}%
% }=\left\{ \left( a,1\right) ,\left( a,2\right) ,\left( c,4\right) ,\left(
% d,2\right) ,\left( d,5\right) \right\} $ et $\mathcal{R}$ est la relation de 
% $E$ vers $F$ qui a pour graphe $G_{\mathcal{R}}.$

% \begin{enumerate}
% \item C{ombien existe-t-il de relations de }$E${\ vers }$F$%
% {\ ?}

% \item {Vrai ou faux ? Vous expliquerez votre r\'{e}ponse.}

% \begin{enumerate}
% \item $\mathcal{R}\in E\longleftrightarrow F$

% \item $\mathcal{R}\in \mathcal{P}\left( E\times F\right) $

% \item $\mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) $

% \item $a\mathcal{R}1${\ ; }$\left( a,1\right) \in \mathcal{R}${%
% \ ; }$\mathcal{R}\left( a,1\right) $

% \item $\mathcal{R}${\ est une relation totale.}

% \item $\mathcal{R}${\ est une fonction.}
% \end{enumerate}

% \item {D\'{e}terminer un ensemble }$B${\ ayant un maximum d'%
% \'{e}l\'{e}ments pour que }$\left( \mathcal{R}_{\mid B}^{-1}\right) ^{-1}$%
% {\ soit une fonction.}

% \item {D\'{e}terminer deux ensembles }$A${\ et }$B${\
% ayant chacun un maximum d'\'{e}l\'{e}ments pour que }$\left( \left( \mathcal{%
% R}_{\mid A}\right) _{\mid B}^{-1}\right) ^{-1}${\ soit une fonction
% totale.}

% \item {D\'{e}terminer deux ensembles }$A${\ et }$B${\
% ayant chacun un maximum d'\'{e}l\'{e}ments pour que }$\left( \left( \mathcal{%
% R}_{\mid A}\right) _{\mid B}^{-1}\right) ^{-1}${\ soit une fonction
% totale surjective et non injective.}

% \item {D\'{e}terminer deux ensembles }$A${\ et }$B${\
% ayant chacun un maximum d'\'{e}l\'{e}ments pour que }$\left( \left( \mathcal{%
% R}_{\mid A}\right) _{\mid B}^{-1}\right) ^{-1}${\ soit une fonction
% totale injective et non surjective.}

% \item {D\'{e}terminer deux ensembles }$A${\ et }$B${\
% ayant chacun un maximum d'\'{e}l\'{e}ments pour que }$\left( \left( \mathcal{%
% R}_{\mid A}\right) _{\mid B}^{-1}\right) ^{-1}${\ soit une fonction
% totale bijective.}

% \item {D\'{e}terminer un ensemble }$B${\ ayant un maximum d'%
% \'{e}l\'{e}ments pour que }$\left( \mathcal{R}\rhd B\right) ^{-1}${\
% soit une fonction.}

% \item {D\'{e}terminer un ensemble }$A${\ ayant un maximum d'%
% \'{e}l\'{e}ments pour que }$\left( A\lhd \mathcal{R}\right) ^{-1}${\
% soit une fonction.}

% \item {D\'{e}terminer un ensemble }$A${\ et un ensemble }$B$%
% {\ ayant chacun un maximum d'\'{e}l\'{e}ments pour que }$\left(
% \left( \left( \mathcal{R}_{\mid A}\right) _{\mid B}^{-1}\right) ^{-1}\right)
% ^{-1}${\ soit une fonction totale.}

% \item {Donner le r\'{e}sultat ou dire que l'\'{e}criture n'a pas de
% sens en expliquant pourquoi :}

% \begin{enumerate}
% \item $\mathcal{R}\left( c\right) ,${\ }$\mathcal{R}\left( \left\{
% b\right\} \right) $

% \item $\mathcal{R}^{-1}\left( 5\right) ,${\ }$\mathcal{R}^{-1}\left(
% \left\{ d\right\} \right) $

% \item $\mathcal{R}^{2}=\mathcal{R}\circ \mathcal{R},${\ }$\mathcal{R}%
% ^{-1}\circ \mathcal{R}$

% \item $\mathcal{R}^{-1}\left( \left\{ 6\right\} \right) $
% \end{enumerate}

% \item {D\'{e}terminer une relation }$\mathcal{R}^{\prime }${\
% de }$E${\ vers }$F${\ de sorte que }$\mathcal{R}\cup \mathcal{R%
% }^{\prime }${\ soit une relation totale.}

% \item {D\'{e}terminer une relation }$\mathcal{R}^{\prime }${\
% de }$E${\ vers }$F${\ de sorte que }$\mathcal{R}\cap \mathcal{R%
% }^{\prime }${\ soit une fonction.}
% \end{enumerate}


% \end{exercice}\end{frame}












% \begin{frame}\begin{exercice}
% $\mathcal{R}_{1}=\left( E,F,G_{\mathcal{R}_{1}}\right) $ et $\mathcal{R}%
% _{2}=\left( E,F,G_{\mathcal{R}_{2}}\right) $ sont deux relations de
% l'ensemble $E$ vers (ou dans) l'ensemble $F,$ $G_{\mathcal{R}_{i}}$ est le
% graphe de la relation $\mathcal{R}_{i}.$ On consid\`{e}re la relation $%
% \mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) $ dont les \'{e}l\'{e}ments $%
% \left( x,y\right) $ du graphe v\'{e}rifient :%
% $$
% \begin{tabular}{c}
% si $\left( x,y\right) \in G_{\mathcal{R}_{2}}\ $alors $\left( x,y\right) \in
% G_{\mathcal{R}}$ \\ 
% si $\left( x,y\right) \in G_{\mathcal{R}_{1}}\ $et pour tout $z\in F,\left(
% x,\,z\right) \notin G_{\mathcal{R}_{2}}$ alors $\left( x,y\right) \in G_{%
% \mathcal{R}}$%
% \end{tabular}%
% $$%
% Il vous est demand\'{e} d'exprimer le graphe de la relation $\mathcal{R}$ en
% utilisant les op\'{e}rations ensemblistes usuelles et des ensembles choisis
% parmi les ensembles suivants : le domaine de $\mathcal{R}_{1}$ not\'{e} $%
% \limfunc{dom}\mathcal{R}_{1},$ le domaine de $\mathcal{R}_{2}$ not\'{e} $\limfunc{%
% dom}\mathcal{R}_{2},$ $G_{\mathcal{R}_{1}},$ $G_{\mathcal{R}_{2}},$ $E$ et $%
% F $.
% \end{exercice}\end{frame}













% \begin{frame}\begin{exercice}
% On consid\`{e}re les ensembles $E=\left\{ a,b,c,d\right\} $ et $F=\left\{
% 1,2,3\right\} $.


% \begin{enumerate}
% \item {Combien existe-t-il de relations de }$E${\ vers }$F$%
% {\ ?}

% \item {On consid\`{e}re les relations }$r${\ et }$s${\
% suivantes :}%
% \begin{eqnarray*}
% r &=&\left( E,E,G_{r}\right) \\
% \text{avec }G_{r} &=&\left\{ \left( a,a\right) ,\left( a,b\right) ,\left(
% c\,,a\right) ,\left( b,c\right) ,\left( d,a\right) \right\} \\
% s &=&\left( E,F,G_{s}\right) \\
% \text{avec }G_{s} &=&\left\{ \left( b,1\right) ,\left( c,1\right) ,\left(
% d,3\right) \right\}
% \end{eqnarray*}%
% {Pour les diagrammes qui suivent, il est exig\'{e} que l'ensemble de d%
% \'{e}part soit \`{a} gauche et l'ensemble d'arriv\'{e}e \`{a} droite, si la
% question n'a pas de sens, d\^{\i}tes-le en expliquant pourquoi.}

% \begin{enumerate}
% \item {Donner un diagramme sagittal de la relation }$r\circ r=r^{2}$

% \item {Donner un diagramme sagittal de la relation }$r.r^{-1}$

% \item {Donner un diagramme sagittal de la relation }$rs=r.s=s\circ r$

% \item {Donner un diagramme sagittal de la relation }$\left( \left\{
% 1\right\} \vartriangleleft s^{-1}\right) .\left( r^{-1}\vartriangleright
% \left\{ a,c,d\right\} \right) $

% \item {Donner un diagramme sagittal de la relation }$\left( r_{\mid
% \left\{ a,c\right\} }^{-1}\right) _{\mid \left\{ a,c\right\} }^{-1}$
% \end{enumerate}

% \item {Donner le r\'{e}sultat ou dire que l'\'{e}criture n'a pas de
% sens en expliquant pourquoi :}

% \begin{enumerate}
% \item $r\left( d\right) =$

% \item $\left( r\vartriangleright \left\{ a\right\} \right) \left( c\right) =$

% \item $\left( r\vartriangleright \left\{ a\right\} \right) \left( b\right) =$

% \item $r_{\mid \left\{ a\right\} }\left( \left\{ d\right\} \right) =$

% \item $\left( r_{\mid \left\{ d\right\} }\right) \left( d\right) =$

% \item $\left( s_{\mid \left\{ a\right\} }\right) \left( \left\{ a\right\}
% \right) =$

% \item $s^{-1}\left( \left\{ 2\right\} \right) =$

% \item $\left( \left\{ d\right\} \vartriangleleft r\right) \left( \left\{
% a\right\} \right) =$

% \item $sr\left( \left\{ 1\right\} \right) =$

% \item $s^{-1}r^{-1}\left( \left\{ 1\right\} \right) =$

% \item $r^{-1}\left( \left\{ 2\right\} \right) =$

% \item $\left( \left\{ a,b\right\} \vartriangleleft s\right) ^{-1}\left(
% 1\right) =$
% \end{enumerate}
% \end{enumerate}

% \end{exercice}\end{frame}



























% \begin{frame}\begin{exercice}
% $E=\left\{ 12,13,33,51,111,128\right\} ,$ $F=\left\{ 2,3,4,5,6,7\right\} .$
% On consid\'{e}re la relation $\mathcal{R}$ de $E$ vers (ou dans) $F$ d\'{e}%
% finie par : $x\in E,y\in F,x\mathcal{R}y$ ssi la somme des chiffres utilis%
% \'{e}s dans l'\'{e}criture de $x$ (on travaille en base 10) est \'{e}gale 
% \`{a} $y.$


% \begin{enumerate}
% \item {D\'{e}terminer le domaine et le codomaine de }$\mathcal{R},$ 
% {son graphe et donner un diagramme sagittal..}

% \item $\mathcal{R}${\ est-elle une fonction ? L'\'{e}criture }$%
% \mathcal{R}(33)${\ est-elle licite ?}

% \item $\mathcal{R}${\ est-elle une application ?}

% \item {Donner le graphe de }$\mathcal{R}^{-1},${\ }$\mathcal{R}%
% ^{-1}${\ est-elle une fonction? L'\'{e}criture }$\mathcal{R}^{-1}(6)$%
% {\ est-elle licite?}

% \item {Calculer, si cela a un sens,}

% \begin{enumerate}
% \item $\mathcal{R}\left( 6\right) ,${\ }$\mathcal{R}\left( 12\right)
% , ${\ }$\mathcal{R}\left( \left\{ 12\right\} \right) ,${\ }$%
% \mathcal{R}(E)$

% \item $\mathcal{R}^{-1}\left( \left\{ 6\right\} \right) ,${\ }$%
% \mathcal{R}^{-1}(F),${\ }$\mathcal{R}^{-1}(2),${\ }$\mathcal{R}%
% ^{-1}\left( \left\{ 2\right\} \right) $
% \end{enumerate}

% \item {D\'{e}terminer le graphe de la restriction de }$\mathcal{R}$%
% {\ \`{a} }$\left\{ 33;51\right\} $

% \item $\mathcal{R}_{\mid E-\left\{ 128\right\} }${\ est-elle une
% application ? Est-elle injective ? surjective ? bijective ?}
% \end{enumerate}

% \end{exercice}\end{frame}









% \begin{frame}\begin{exercice}
% Donner la repr\'{e}sentation sagittale d'une application de l'ensemble fini $%
% E$ dans l'ensemble fini $F$

% \begin{enumerate}
% \item {non injective et non surjective ;}

% \item {non injective mais surjective ;}

% \item {injective mais pas surjective ;}

% \item {bijective.}
% \end{enumerate}
% \end{exercice}\end{frame}







% \begin{frame}\begin{exercice}
% Déterminez  si  les  fonctions  de  $\bbz$ dans  $\bbz$  suivantes  sont
% injectives ou surjectives ou...?
% \begin{multicols}{2}
% \begin{enumerate}
% \item $f(n)=n-1$;
% \item $f(n)=n^2+12$;
% \item $f(n)=n^3+37$;
% \item $f(n)=\lfloor n/2 \rfloor$.
% \end{enumerate}
% \end{multicols}
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
%   Mêmes  questions  avec  les  fonctions de  $\bbz\times  \bbz\to  \bbz$
%   suivantes:
% \begin{multicols}{2}
%   \begin{enumerate}
%   \item $f(m,n)=2m-n$;
% \item $f(m,n)=m^2-n^2$;
% \item $f(m,n)=m^2+n^2$;
% \item $f(m,n)=|m|-|n|$;
% \item $f(m,n)=m-n$;
% \item $f(m,n)=|n|$;
% \item $f(m,n)=m$;
% \item $f(m,n)=m^2-4$.
%   \end{enumerate}
% \end{multicols}
% \end{exercice}\end{frame}












% \begin{frame}\begin{exercice}
% $f$ est une application de $E$ dans $F,$ $A$ et $B$ sont deux parties de $E$
% et $A^{\prime }$ et $B^{\prime }$ sont deux parties de $F.$ D\'{e}montrer :


% \begin{enumerate}
% \item $A\subseteq B\Rightarrow f(A)\subseteq f(B)$

% \item $f(A\cup B)=f(A)\cup f(B)$

% \item $f(A\cap B)\subseteq f(A)\cap f(B),$ donner un exemple o\`{u} il n'y a
% pas \'{e}galit\'{e}.

% \item $A\subseteq f^{-1}\left( f(A)\right) $

% \item $f^{-1}(A^{\prime }\cap B^{\prime })=f^{-1}(A^{\prime })\cap
% f^{-1}(B^{\prime })$

% \item $f\left( f^{-1}(B^{\prime })\right) \subseteq B^{\prime }$

% \item $A^{\prime }\subseteq B^{\prime }\Rightarrow f^{-1}(A^{\prime
% })\subseteq f^{-1}(B^{\prime })$

% \item $f^{-1}(A^{\prime }\cap B^{\prime })=f^{-1}(A^{\prime })\cap
% f^{-1}(B^{\prime })$
% \end{enumerate}
% \end{exercice}\end{frame}






















% \begin{frame}\begin{exercice}
% $E$, $F$ et $G$ sont 3 ensembles (tous les trois $\neq \emptyset ).$ $f\in 
% \mathcal{A(}E,F),$ $g\in \mathcal{A(}F,G).$


% \begin{enumerate}
% \item $g\circ f${\ injective }$\Rightarrow ${\ }$f${\
% injective.} ?

% \item $g\circ f${\ surjective }$\Rightarrow ${\ }$g${\
% surjective.} ?

% \item Si $f$ et $f\circ  g$ son injectives (surjectives), est-ce que $g$
%   est injective (surjective)?
% \end{enumerate}


% \end{exercice}\end{frame}














% \begin{frame}\begin{exercice}
% $A$ est une partie non vide de l'ensemble $E.$ Qu'appelle-t-on l'injection
% canonique de $A$ dans $E$ ?
% \end{exercice}\end{frame}






% \begin{frame}\begin{exercice}
% D\'{e}montrer que la relation r\'{e}ciproque de la fonction totale $f=\left(
% E,F,G_{f}\right) $ est une fonction ssi f est injective.
% \end{exercice}\end{frame}







% \begin{frame}\begin{exercice}
% $E=\left\{ a,b,c,d\right\} $ et $F=\left\{ 1,2,3,4,5,6\right\} .$ D\'{e}%
% montrer qu'il est impossible de construire une surjection et, a fortiori une
% bijection, de $E$ sur $F.$
% \end{exercice}\end{frame}








% \begin{frame}\begin{exercice}
% Donner une bijection de $\mathbb{N}$ sur $\mathbb{Z}.$
% \end{exercice}\end{frame}









% \begin{frame}\begin{exercice}
% Lorsqu'on est en pr\'{e}sence d'ensembles finis, il est facile de savoir
% s'il existe des injections ou surjections entre ces ensembles puisque si
% elles existent on est capable de les construire. Pour des ensembles infinis
% c'est plus difficile mais on est s\^{u}r qu'il n'existe pas de surjection
% entre un ensemble $E$ et l'ensemble de ses parties $\mathcal{P}\left(
% E\right) ,$ c'est le th\'{e}or\`{e}me de Cantor\footnote{%
% Ne pas confondre avec le fameux th\'{e}or\`{e}me de Cantor-Bernstein (qui
% n'est pas \`{a} votre programme) qui dit que s'il existe une injection de $E$
% vers $F$ et une injection de $F$ vers $E$ alors il existe une bijection de $%
% E $ sur $F.$}, on va le d\'{e}montrer :

% \begin{enumerate}
% \item $E=\left\{ a,b,c,d\right\} ${\ et }$f${\ est la fonction
% totale de }$E${\ dans }$\mathcal{P}\left( E\right) ${\ d\'{e}%
% finie par }$f\left( x\right) =\left\{ x\right\} ${, d\'{e}terminer }%
% $$
% A=\left\{ x\in E\mid x\notin f\left( x\right) \right\}
% $$

% \item $E=\left\{ a,b,c,d\right\} ${\ et }$f${\ est la fonction
% totale de }$E${\ dans }$\mathcal{P}\left( E\right) ${\ d\'{e}%
% finie par }$f\left( x\right) =\complement _{E}\left\{ x\right\} ${, d%
% \'{e}terminer }%
% $$
% A=\left\{ x\in E\mid x\notin f\left( x\right) \right\}
% $$

% \item $E=\left\{ a,b,c,d\right\} ${\ et }$f${\ est la fonction
% totale de }$E${\ dans }$\mathcal{P}\left( E\right) ${\ d\'{e}%
% finie par }$f\left( a\right) =\left\{ b,c\right\} ${\ et }$f\left(
% x\right) =E${\ pour }$x\neq a,${\ d\'{e}terminer }%
% $$
% A=\left\{ x\in E\mid x\notin f\left( x\right) \right\}
% $$

% \item $E${\ est un ensemble non vide quelconque, fini ou infini, et }$%
% f${\ est une fonction totale de }$E${\ dans }$\mathcal{P}%
% \left( E\right) ${\ ; }$A${\ est la partie de }$E${\ d%
% \'{e}finie par }$A=\left\{ x\in E\mid x\notin f\left( x\right) \right\} $%
% {\ et pour prouver que }$f${\ n'est pas surjective nous allons
% prouver que }$A${\ ne peut avoir le moindre ant\'{e}c\'{e}dent ! Pour
% cela on suppose que }$A${\ poss\`{e}de au moins un ant\'{e}c\'{e}dent 
% }$u,${\ }$f\left( u\right) =A.${\ De deux choses l'une, ou
% bien }$u\in A${\ ou bien }$u\notin A${\ ; d\'{e}montrer
% l'impossibilit\'{e} de chaque cas et conclure.}
% \end{enumerate}

% \end{exercice}\end{frame}


% \subsection{ Relations binaires sur un ensemble}











% \begin{frame}\begin{exercice}
% Commentez cet énoncé de CM1 (on progresse...)
% %\begin{figure}
% \begin{center}
%   \includegraphics[width=\linewidth]{CM1-rel}
% \end{center}
% %\end{figure}

% \end{exercice}\end{frame}














% \begin{frame}\begin{exercice}
% \begin{enumerate}
% \item   Donner la représentation  matricielle des relations suivantes définies
%   sur $\bigl\{1,2,3,4\bigr\}$:
%   \begin{enumerate}
%   \item $\bigl\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\bigr\}$;
%   \item $ \bigl\{(1,1),(1,4),(2,2),(3,3),(4,1)\bigr\}$;
%   \item                                                                 $
%     \bigl\{(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),$

%         $(3,4),(4,1),(4,2),(4,3)\bigr\}$;
%    \item $ \bigl\{(2,4),(3,1),(3,2),(3,4)\bigr\}$
%   \end{enumerate}
% \item  Quelles sont, parmi  ces relations,  celles qui  sont réflexives?
%   irrefléxives? symétriques? antisymétriques? transitives?
% \end{enumerate}
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
%   \begin{enumerate}
%   \item Énumérer les couples  des relations sur $ \bigl\{1,2,3,4\bigr\}$
%     définies par les matrices suivantes:
%     \begin{multicols}{2}
%  \begin{enumerate}
%     \item
%       $\begin{pmatrix}
%         1&1&0&1\\
%         1&0&1&0\\
%         0&1&1&1\\
%         1&0&1&1
%       \end{pmatrix}$
% \item $
%   \begin{pmatrix}
%     1&1&1&0\\
%     0&1&0&0\\
%     0&0&1&1\\
%     1&0&0&1
%   \end{pmatrix}
% $
% \item $
%   \begin{pmatrix}
%     0&1&0&1\\
%     1&0&1&0\\
%     0&1&0&1\\
%     1&0&1&0
%   \end{pmatrix}
% $
%     \end{enumerate}

%   \end{multicols}
% \item Quelles sont, parmi  ces relations,  celles qui  sont réflexives?
%   irrefléxives? symétriques? antisymétriques? transitives?
%   \end{enumerate}
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
%   Combien  d'éléments  non  nuls  contient la  matrice  représentant  la
%   relation $  \RR$ sur l'ensemble  $ \ER=\bigl\{1,2,3,...,100\bigr\}$ si
%   $\RR$ est:
%   \begin{multicols}{2}
%     \begin{enumerate}
%     \item $ \bigl\{(a,b)\mid a>b\bigr\}$; \item $ \bigl\{(a,b)\mid a\neq
%       b\bigr\}$;
% \item  $   \bigl\{(a,b)\mid  a=b+1\bigr\}$;  \item   $  \bigl\{(a,b)\mid
%   a=0\bigr\}$;
% \item $ \bigl\{(a,b)\mid ab=0\bigr\}$;
% \item $ \bigl\{(a,b)\mid a+b=100\bigr\}$
%     \end{enumerate}
    
%   \end{multicols}
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% Soit  $\RR=\bigl\{(a,b)\in  \bbz^2  \mid  a\neq  b\bigr\}$  Quelle  est  la
% fermeture réflexive de $\RR$?
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% Soit $\RR=\bigl\{(a,b)\in \bbn^2 \mid a \text{ divise }b\bigr\}$ Quelle est la
% fermeture symétrique de $\RR$?
% \end{exercice}\end{frame}



% \begin{frame}\begin{exercice}
%   Soit $\ER=\bigl\{1,2,3,4,5\bigr\}$ et $\RR$ une relation sur $\ER$ qui
%   contient  les  couples $(1,3)$,  $(2,4)$,  $(3,1)$, $(3,5)$,  $(4,3)$,
%   $(5,1)$, $(5,2)$ et $(5,4)$. Déterminer:

%   \begin{multicols}{3}
%     \begin{enumerate}
%     \item $\RR^2$ \item $\RR^3$ \item $\RR^4$
%     \item $\RR^5$ \item $\RR^6$ \item $\RR^+$
%     \end{enumerate}
%   \end{multicols}


% \end{exercice}\end{frame}










% \begin{frame}\begin{exercice}
% On consid\`{e}re les relations binaires $\mathcal{R}$ et $\mathcal{S}$ sur $%
% E=\left\{ a;b;c;d;e\right\} $ qui ont pour graphe : 
% \begin{eqnarray*}
% G_{\mathcal{R}} &=&\left\{ (a,a),(a,b),(b,c),(c,b),(e,b)\right\} \\
% G_{\mathcal{S}} &=&\left\{ (a,a),(b,a),(b,b),(c,b),(e,b),(e,d)\right\}
% \end{eqnarray*}

% \begin{enumerate}
% \item {Donner une repr\'{e}sentation sagittale de }$\mathcal{R}$%
% {\ et de }$\mathcal{S}.$

% \item {D\'{e}terminer le graphe de }$\mathcal{R}\cup \mathcal{S},$%
% {\ de }$\mathcal{R}\cap \mathcal{S},${\ de }$\overline{%
% \mathcal{R}},${\ de }$\mathcal{S}^{-1},${\ de }$\mathcal{RS}$%
% {\ de }$\mathcal{SR}.$

% \item {D\'{e}terminer le graphe de }$\mathcal{R}^{+}${\ et de }%
% $\mathcal{S}^{\ast }.$
% \end{enumerate}
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
% $\mathcal{R}$ est une relation binaire sur l'ensemble $E$ et on supose que $%
% \mathcal{R}$ n'est pas une relation vide.

% \begin{enumerate}
% \item {Rappeler ce qu'est }$\mathcal{R}^{k\in \mathbf{N}^{\ast }}.$

% \item {Rappeler ce qu'est }$\mathcal{R}^{+}.$

% \item {Rappeler ce qu'est }$\mathcal{R}^{\ast }.$

% \item {D\'{e}montrer que si }$x\mathcal{R}^{9}z${\ et }$z%
% \mathcal{R}^{2001}y${\ alors }$x\mathcal{R}^{\ast }y$

% \item {Traduire correctement }$x\mathcal{R}^{\ast }y.$

% \item {D\'{e}montrer que }$\mathcal{R}^{\ast }${\ est une
% relation transitive.}
% \end{enumerate}
% \end{exercice}\end{frame}


% \begin{frame}\begin{exercice}
% $\mathcal{R}$ est une relation binaire sur $E$

% \begin{enumerate}
% \item {D\'{e}montrer que }$\mathcal{R}\cup \mathcal{R}^{-1}${\
% et }$\mathcal{R}\cap \mathcal{R}^{-1}${\ sont sym\'{e}triques.}

% \item {D\'{e}montrer que }$\mathcal{R}^{+}${\ est transitive.}

% \item {D\'{e}montrer que si }$\mathcal{R}${\ est transitive
% alors }$\mathcal{R}=\mathcal{R}^{+}.$

% \item {D\'{e}montrer que si }$\mathcal{R}${\ est r\'{e}flexive
% et transitive alors }$\mathcal{R}=\mathcal{R}^{\ast }$
% \end{enumerate}
% \end{exercice}\end{frame}



% \begin{frame}\begin{exercice}
% $\mathcal{R}$ est une relation binaire sur $E=\left\{ a,b,c,d,e\right\} $
% dont le graphe est 
% \begin{equation*}
% G=\left\{ \left( a,a\right) ,\left( a,b\right) ,\left( a,c\right) ,\left(
% b,a\right) ,\left( d,a\right) ,\left( b,e\right) \right\}
% \end{equation*}

% \begin{enumerate}
% \item {Compl\'{e}tez l'\'{e}criture : }$G\in $

% \item {D\'{e}terminer le graphe de }$\mathcal{R}^{2}.$

% \item {D\'{e}terminer le graphe de }$\mathcal{R}^{3},$ {d\'{e}%
% terminer le graphe de }$\mathcal{R}^{k\geq 2}.$

% \item {Quel est le graphe de }$\mathcal{R}^{0}${\ ?}

% \item {Quel est le graphe de }$\mathcal{R}^{+}?$

% \item {Quel est le graphe de }$\mathcal{R}^{\ast }${\ ?}

% \item $\mathcal{R}^{\ast }${\ est-elle transitive ? justifier votre r%
% \'{e}ponse.}

% \item {D\'{e}terminer le graphe de }$\mathcal{R}^{-1},${\ de }$%
% \mathcal{R}^{-k},${\ }$k\in N^{\ast }.$
% \end{enumerate}

% \end{exercice}\end{frame}






% \subsection{Relations d'équivalence}



% \begin{frame}\begin{exercice}
% Dans $\mathbb{Z}$ on consid\`{e}re la relation $x\mathcal{R}y\Leftrightarrow
% x-y\in 3\mathbb{Z}=\left\{ 3k\mid k\in \mathbb{Z}\right\} .$ D\'{e}montrer
% que c'est une relation d'\'{e}quivalence et d\'{e}terminer l'ensemble
% quotient ; v\'{e}rifier que l'ensemble quotient d\'{e}termine une partition
% de $\mathbb{Z}.$
% \end{exercice}\end{frame}



% \begin{frame}\begin{exercice}
% $E$ est un ensemble non vide et $A$ est une partie non vide fix\'{e}e de $E.$
% On consid\'{e}re la relation binaire $\mathcal{R}$ sur $\mathcal{P}\left(
% E\right) $ d\'{e}finie par : 

% $$X\mathcal{R}Y\Leftrightarrow X\cap A=Y\cap A$$

% \begin{enumerate}
% \item \textit{D\'{e}montrer que }$\mathcal{R}$\textit{\ est une relation d'%
% \'{e}quivalence.}

% \item \textit{On suppose ici que }$E=\left\{ a,b,c,d\right\} $\textit{\ et }$%
% A=\left\{ a,d\right\} .$\textit{\ D\'{e}terminer toutes les classes d'\'{e}%
% quivalence.}
% \end{enumerate}

% \end{exercice}\end{frame}



% \begin{frame}\begin{exercice}
% Soit $ \ER$ l'ensemble des fonctions dérivables de $\bbr$ dans $\bbr$.

% On considère la relation $\RR$ définie sur $\ER$ qui contient toutes les
% couples $(f,g)$ tels que $f'(x)=g'(x)$ pour tout réel $x$.

% \begin{enumerate}
% \item Est-ce que $\RR$ est une relation d'équivalence?
% \item Décrire la classe de $f:x\mapsto x^2$.
% \end{enumerate}
% \end{exercice}\end{frame}

% \subsection{Ordre}



% \begin{frame}\begin{exercice}
% On consid\`{e}re la relation $\preceq $ sur $\mathbb{N}^{2}$ d\'{e}finie par
% : 
% $$
% (a;b)\preceq (a^{\prime };b^{\prime })\Leftrightarrow a\leq a^{\prime }\text{
% et }b\geq b^{\prime }
% $$
% Est-elle une relation d'ordre ?
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% $E$ est un ensemble totalement ordonn\'{e} par $\leq .$ On consid\'{e}re la
% relation binaire sur $E^{2}$ d\'{e}finie par : 
% $$
% (x,y)\preceq (x^{\prime },y^{\prime })\Leftrightarrow \left\{ 
% \begin{array}{l}
% x<x^{\prime }\text{ ou} \\ 
% x=x^{\prime }\text{ et }y\leq y^{\prime }%
% \end{array}%
% \right.
% $$
% D\'{e}montrer que c'est une relation d'ordre total. Cet ordre porte le nom
% d'ordre lexicographique, expliquer pourquoi ?
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% Dans $\mathbb{N}^{\ast }$ on consid\`{e}re la relation not\'{e}e \og $\mid $\fg{}
% qui est  la relation \og  divise\fg{}, $a\mid b$  se lit \og  $a$ divise
% $b$\fg{} ou encore \og $%
% b $ est un multiple de $a$\fg{}; la d\'{e}finition math\'{e}matique de cette
% relation \'{e}tant%
% $$
% a\mid b\text{ ssi il existe }k\in \mathbb{N}^{\ast }\text{ v\'{e}rifiant }%
% b=ka
% $$

% \begin{enumerate}
% \item {D\'{e}montrer que c'est une relation d'ordre sur }$\mathbb{N}%
% ^{\ast }.${\ Cet ordre est-il total ? Donner des \'{e}l\'{e}ments
% comparables et non comparables.}

% \item {D\'{e}montrer que c'est une relation d'ordre sur toute partie }%
% $A${\ de }$N^{\ast }.$

% \item {On consid\`{e}re la relation divise dans }$E=\left\{
% 2,4,6,8,10,12\right\} .$

% \begin{enumerate}
% \item {Construire le diagramme sagittal de cette relation.}

% \item {Construire le diagramme de Hasse de cette relation.}

% \item $E${\ admet-il un \'{e}l\'{e}ment minimum ?}

% \item $E${\ admet-il un \'{e}l\'{e}ment maximum ?}

% \item $E${\ admet-il des \'{e}l\'{e}ments minimaux ?}

% \item $E${\ admet-il des \'{e}l\'{e}ments maximaux ?}

% \item $V=\left\{ 2,4\right\} ,${\ donner trois majorants de }$V$%
% {\ dans }$E.$

% \item $T=\left\{ 8,10\right\} ${\ admet-il des majorants dans }$E$%
% {\ ? Donner des majorants de }$T${\ dans }$\mathbb{N}^{\ast }.$

% \item {Donner des minorants de }$T${\ dans }$E.$

% \item {Donner tous les minorants de }$T${\ dans }$\mathbb{N}%
% ^{\ast }.$

% \item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne sup\'{e}rieure
% dans }$E${\ ?}

% \item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne sup\'{e}rieure
% dans }$\mathbb{N}^{\ast }${\ ?}

% \item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne inf\'{e}rieure
% dans }$E${\ ?}

% \item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne inf\'{e}rieure
% dans }$\mathbb{N}^{\ast }$?
% \end{enumerate}


% \end{enumerate}

% \end{exercice}\end{frame}









% \begin{frame}\begin{exercice}
% $(E,\leq )$ est un ensemble ordonn\'{e}. Repr\'{e}senter les diff\'{e}rents
% diagrammes de Hasse pour un ensemble $E$ de trois \'{e}l\'{e}ments. On pr%
% \'{e}cisera, pour chaque diagramme si $E$ est totalement ordonn\'{e}. M\^{e}%
% me question pour un ensemble de 4 \'{e}l\'{e}ments.
% \end{exercice}\end{frame}





% \begin{frame}\begin{exercice}
% $\mathbb{R}$ est muni de sa relation d'ordre habituelle et $\mathbb{R}^{2}$
% est ordonn\'{e} comme produit direct des ensembles ordonn\'{e}s $\left( 
% \mathbb{R},\mathbb{\leq }\right) $ et $\left( \mathbb{R},\mathbb{\leq }%
% \right) .$ Le plan $P$ est rapport\'{e} \`{a} un rep\`{e}re orthonorm\'{e} $%
% \left( O,\overrightarrow{i},\overrightarrow{j}\right) $ et on pourra
% confondre tout point $M$ du plan, qui a pour coordonn\'{e}es $x$ et $y$ dans
% ce rep\`{e}re, avec le couple $(x,y)$ de $\mathbb{R}^{2}.$ Cela permet
% d'ordonner $P$ par la relation : 
% $$
% M_{1}\preceq M_{2}\Leftrightarrow (x_{1},y_{1})\leq (x_{2},y_{2})
% $$
% $\mathcal{C}$ d\'{e}signe le cercle de centre $O$ et de rayon 1, $\mathcal{D}
% $ d\'{e}signe le disque de centre $O$ et de rayon 1.

% \begin{enumerate}
% \item {Donner 5 majorants et 5 minorants de }$\mathcal{C}${\
% et de }$\mathcal{D}.$

% \item $\mathcal{C}${\ et }$\mathcal{D}${\ admettent-ils une
% borne sup ? une borne inf ? un plus petit \'{e}l\'{e}ment ? un plus grand 
% \'{e}l\'{e}ment?}

% \item {On note }$\mathcal{D}^{+}${\ l'ensemble des points de }$%
% \mathcal{D}${\ qui ont leurs deux coordonn\'{e}es positives ou
% nulles, }$\mathcal{D}^{+}${\ admet-il un plus petit \'{e}l\'{e}ment ?}
% \end{enumerate}

% \end{exercice}\end{frame}








% \begin{frame}\begin{exercice}
% V\'{e}rifier que $\left( \mathcal{P}(E),\subseteq \right) $ est bien un
% ensemble ordonn\'{e}. Soit $\left\{ A,B\right\} $ une partie de $\mathcal{P}%
% (E),$ d\'{e}terminer sa borne sup et sa borne inf dans $\mathcal{P}\left(
% E\right) .$
% \end{exercice}\end{frame}

% \begin{frame}\begin{exercice}
% $\mathbb{N}_{10}$ est ordonn\'{e} par la relation de divisibilit\'{e}
% (rappel : $\mathbb{N}_{10}=\left\{ 1,2,\cdots ,10\right\} $).

% \begin{enumerate}
% \item {Tracer le diagramme sagittal de cette relation puis son
% diagramme de Hasse.}

% \item $\mathbb{N}_{10}${\ admet-il un plus petit \'{e}l\'{e}ment, un
% plus grand \'{e}l\'{e}ment ?}

% \item {\'{E}tudier les \'{e}l\'{e}ments "remarquables"\ (plus petit 
% \'{e}l\'{e}ment, majorant, borne sup, }$\cdots )${\ des parties de }$%
% \mathbb{N}_{10}${\ suivantes :}

% \begin{enumerate}
% \item $A=\left\{ 1,3,6\right\} $

% \item $B=\left\{ 2,3\right\} $

% \item $C=\left\{ 2,3,4\right\} $

% \item $D=\left\{ 2,4\right\} $
% \end{enumerate}
% \end{enumerate}

% \end{exercice}\end{frame}




% \subsection{Dénombrement}


% \begin{frame}\begin{exercice}
% \begin{enumerate} 
% \item Combien existe-t-il de chaînes distinctes de 8 bits?
% \item Combien de chaînes de 10 bits commencent et finissent par 1?
% \item  Combien y  a-t-il  de  chaînes de  quatre  lettres minuscules  de
%   l'alphabet latin contenant la lettre $x$?
% \item Combien de chaînes de  caractères ASCII contiennent le caractère @
%   au moins une fois? (il y a 128 caractères ASCII).
% \item Combien  de chaînes  de 10  bits contiennent au  moins trois  1 et
%   trois 0?
% \item Combien  de chaînes de six caractères formées à partir  de l'alphabet
%   latin contiennent:
%   \begin{enumerate}
%   \item exactement une voyelle?
% \item au moins une voyelle?
% \item exactement deux voyelles?
% \item au moins deux voyelles?
% \item la lettre a?
% \item les lettres a et b?
%   \end{enumerate}
% \end{enumerate}
% \end{exercice}\end{frame}







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