 \documentclass{beamer}

%\input{beamer_settings}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel}

\usepackage{amsfonts,latexsym,amsfonts,amsmath,amssymb,amsthm,amscd,stmaryrd,amstext,amscd}
\usepackage{array}
\usepackage{stmaryrd,mathrsfs}

\usepackage{bbm}
\usepackage{yhmath}

\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{arrows,automata,petri,positioning}

\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{chains,fit,shapes}
\usetikzlibrary{patterns}

\usetheme{Boadilla}
\usecolortheme{seahorse}


\makeatother
\setbeamertemplate{footline}
{
  \leavevmode%
  \hbox{%
  \begin{beamercolorbox}[wd=.45\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertsection
      \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.45\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
    \usebeamerfont{title in head/foot}\insertsubsection
      \end{beamercolorbox}
      \begin{beamercolorbox}[wd=.1\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}
    \insertframenumber{} / \inserttotalframenumber\hspace*{1ex}
  \end{beamercolorbox}}%
  \vskip0pt%
}
\makeatletter


%\input{defs}
\definecolor{darkgreen}{rgb}{0,0.7,0}
\newcommand{\green}[1]{{\color{darkgreen}#1}}
\newcommand{\red}[1]{{\color{red}#1}}

\newcommand{\define}[1]{\textbf{#1}}%\index{#1}}

\newcommand{\Cl}[1]{\mathbf{Cl}(#1)}
\newcommand{\Lang}{\mathcal{L}}
\newcommand{\M}{\mathbbm{M}}
\newcommand{\N}{\mathbbm{N}}
\newcommand{\Z}{\mathbbm{Z}}
\newcommand{\Q}{\mathbbm{Q}}
\newcommand{\R}{\mathbbm{R}}
\newcommand{\C}{\mathbbm{C}}
\newcommand{\G}{\mathbbm{G}}
\newcommand{\K}{\mathbbm{K}}

\renewcommand{\P}{\mathcal{P}}

\newcommand{\Rel}{\mathcal{R}}
\newcommand{\A}{\mathcal{A}}

\newcommand{\U}{\mathbbm{U}}
\newcommand{\V}{\mathbbm{V}}


%%%TIKZ
\newcommand{\Eset}{(-4,-1) rectangle (4,4)}
\newcommand{\Aset}{(0,0) ++(135:2) circle (2)}
\newcommand{\Bset}{(0,0) ++(45:2) circle (2)}



\title{Introduction à la notion d'ensembles}

%\author{Bérénice Delcroix-Oger \and Ralph Matthes \and Martin Strecker}
\institute{Université de Toulouse}
\date{Année 2020/2021} 


\begin{document}

%======================================================================

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


%======================================================================

%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%



\section{Introduction à la notion d'ensembles}

\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Introduction à la notion d'ensembles}}
\end{center}
\end{frame}


\subsection{Premières notions}

%-------------------------------------------------------------
\begin{frame}
\frametitle{Premières notions}

\begin{block}{Notion d'ensembles}
 Un \define{ensemble} est une collection d’objets deux à deux distincts appelés \define{éléments}. On peut définir un ensemble de deux manières:
\begin{itemize}
\item en \define{extension}: on donne la liste des éléments;
\item en \define{compréhension}: on donne une propriété commune vérifiée par les éléments de l’ensemble.
\end{itemize}
\end{block}



\end{frame}
%%%

\begin{frame}
\frametitle{Exemples}
\vspace{-0.7cm}

\begin{overlayarea}{12cm}{8cm}
\begin{itemize}
\item Ensembles d'élèves:
\begin{itemize}
 \item $\{\textrm{Pierre; Paul;Marie;Julie;Karim}\}$
  \item<2-> $\{\textrm{élèves de la classe qui ont les yeux bleus}\}$
 \item<2-> $\{\textrm{élèves qui viennent en cours en pyjama}\}$ (certainement vide!)
 \end{itemize}

\vspace{0.2cm}

\item<3-> Ensembles classiques de nombres:
\begin{itemize}
 \item $\N=\{0,1,2,3,\dots\}$ est l'ensemble des nombres naturels;
 \item $\Z=\{\dots,-3,-2,-1,0,1,2,3,\dots\}$ est l'ensemble des nombres entiers;
 \item $\Q=\{ p/q : p\in\Z \textrm{ et }q\in\N \textrm{ avec }q\ne0\}$;
 \item $\R$ l'ensemble des nombres réels;
\end{itemize}
\vspace{0.2cm}

 \item<4->  Dans les langages de programmation, comme  Python,  certaines variables soient déclarées avec un certain \define{type de données}:
 
\begin{itemize}
 \item \texttt{bool} s’interprète comme l’ensemble	$\{Vrai,Faux\}$,
 \item \texttt{int} s’interprète comme l’ensemble des entiers
 \item \texttt{float} s’interprète comme l’ensemble des nombres à virgule flottante
 \item \texttt{str} s’interprète comme  l’ensemble des chaînes de caractères
 \item \texttt{list} s’interprète comme  l’ensemble des listes.
\end{itemize}
\end{itemize}
\only<1>{
\vspace{-7cm}
\begin{center}
\begin{tikzpicture}
 \draw (0, 0) ellipse (4 and 2);
  \draw (1.9, 0.1) node{$\times$};
  \draw (1.9, 0.1) node[above]{Karim};
  \draw (1.2, 1) node{$\times$};
  \draw (1.2, 1) node[above]{Pierre};
  \draw (0.7, -1) node{$\times$};
  \draw (0.7, -1) node[above]{Paul};
  \draw (-1.4, -0.4) node{$\times$};
  \draw (-1.4, -0.4) node[above]{Marie};  
  \draw (-1.7, 0.8) node{$\times$};
  \draw (-1.7, 0.8) node[above]{Julie};  
\end{tikzpicture}
\end{center}
}
\end{overlayarea}


\end{frame}

%%%

\begin{frame}
\frametitle{Principales règles de fonctionnement}
 
Sans rentrer dans l'axiomatique, la notion d'ensemble satisfait un certain nombre de règles de fonctionnement:
\begin{description}
\item[\bf{Relation d’appartenance}] On note $x\in A$ si l'élément $x$ est dans $A$.
\item[\bf{Objets distincts}] On peut distinguer deux éléments entre eux et un ensemble ne peut pas contenir deux fois le même objet.
\item[\bf{Ensemble vide}] Il existe un ensemble qui ne contient aucun élément, c'est l'ensemble vide noté $\emptyset$.
\item[\bf{Paradoxe de Russell}] Un ensemble peut être élément d'un autre ensemble mais pas de lui même.
\end{description}

\end{frame}

%%%%%%%%
%%%
%%%%%%%%

\subsection{Sous ensembles}

\begin{frame}
 \frametitle{Inclusion}
 
\begin{block}{Inclusion}
 L'ensemble $A$ est un \define{sous-ensemble} de $B$ si tous les éléments de $A$ sont des éléments de $B$, autrement dit 
 \[x\in A\Longrightarrow x\in B\] 
 
On le note $A\subseteq B$ ($A$ \define{inclus} dans $B$).
\end{block}
\textbf{\underline{Exemple:}}

\[\{0,1,2\}\subseteq \{0,1,2,3\}\subseteq \N\subseteq\Z\subseteq\Q\subseteq\R\subseteq\C\]

\textbf{\underline{Remarque:}}

\[A=B\textrm{ si et seulement si }A\subseteq B\textrm{ et }B\subseteq A\]

\end{frame}

%%%

\begin{frame}
 \frametitle{Ensemble des parties}
\begin{block}{Ensemble des parties}
Soit $A$ un ensemble, l'\define{ensemble des parties de $A$} noté $\P(A)$ est l'ensemble des sous-ensembles de $A$.
\end{block}

\textbf{\underline{Remarque:}}

On a toujours 
\begin{itemize}
 \item $\emptyset\in\P(A)$ car $\emptyset\subseteq A$,
 \item $A\in\P(A)$ car $A\subseteq A$.
\end{itemize}

\textbf{\underline{Exemple:}}

Si $A=\{1,2,3\}$ alors \[\P(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\]

\end{frame}

%%%

%%%%%%%%
%%%
%%%%%%%%

\subsection{Opérations sur les ensembles}

\begin{frame}
 \frametitle{Union et intersection}
\vspace{-0.3cm}
 \begin{center}
\begin{tikzpicture}[scale=0.25]
\draw[color=magenta!50] \Eset;
\fill[opacity=0.5,red]  \Aset;
\fill[opacity=0.5,blue] \Bset;
\draw (-1.5,1.5) node{$A$};
\draw (1.5,1.5) node{$B$};
\draw (-4,-1) node[above right]{$\Omega$};
\end{tikzpicture}
  \end{center}
\vspace{-0.8cm}

 \begin{columns}
\begin{column}{5.5cm}
\begin{center}
\begin{block}{Union}
 $A\cup B=\{\textrm{éléments de $A$ ou de $B$}\}$
\end{block}
\begin{tikzpicture}[scale=0.25]
\draw[magenta!50] \Eset;
\draw[dashed,red]  \Aset;
\draw[dashed,blue] \Bset;
\fill[magenta!70] \Bset;
\fill[magenta!70] \Aset;
\draw (0,1.5) node{$A\cup B$};
\end{tikzpicture}
\begin{exampleblock}{Propriétés}
\begin{footnotesize}
  \begin{description}
 \item[Idempotence:] $A\cup A=A$
  \vspace{-0.1cm}
\item[Commutativité:] $A\cup B=B\cup A$
 \vspace{-0.1cm}
 \item[Associativité:] $A\cup(B\cup C)=(A\cup B)\cup C$
 %\vspace{-0.1cm}
 \item[Elément neutre:] $A\cup\emptyset=A$
\end{description}
\end{footnotesize}
\end{exampleblock}
  \end{center}
\end{column}
\begin{column}{5.5cm}
 \begin{center}
\begin{block}{Intersection}
 $A\cap B=\{\textrm{éléments de $A$ et de $B$}\}$
\end{block}
\begin{tikzpicture}[scale=0.25]
\begin{scope}
\draw[magenta!50] \Eset;
\draw[dashed,red]  \Aset;
\draw[dashed,blue] \Bset;
\clip \Bset;
\fill[magenta!70] \Aset;
\end{scope}
\draw (0,1.5) node{$A\cap B$};
\end{tikzpicture}
\begin{exampleblock}{Propriétés}
\begin{footnotesize}
\begin{description}
 \item[Idempotence:] $A\cap A=A$
 \vspace{-0.1cm}
 \item[Commutativité:] $A\cap B=B\cap A$
 \vspace{-0.1cm}
 \item[Associativité:] $A\cap(B\cap C)=(A\cap B)\cap C$
 %\vspace{-0.1cm}
  \item[Elément neutre:]  $A\cap\Omega=A$
\end{description}

\end{footnotesize}
\end{exampleblock}
   \end{center}

\end{column}
\end{columns}
 
\begin{exampleblock}{Distributivité}
\begin{footnotesize}
\[A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\textrm{ et }A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\]
 \end{footnotesize}
\end{exampleblock}
\end{frame}

%%%
\begin{frame}
 \frametitle{Différences et complémentaire}
 \vspace{-0.3cm}
 \begin{center}
\begin{tikzpicture}[scale=0.25]
\draw[color=magenta!50] \Eset;
\fill[opacity=0.5,red]  \Aset;
\fill[opacity=0.5,blue] \Bset;
\draw (-1.5,1.5) node{$A$};
\draw (1.5,1.5) node{$B$};
\draw (-4,-1) node[above right]{$\Omega$};
\end{tikzpicture}
  \end{center}
\vspace{-0.5cm}

\begin{columns}
\begin{column}{9cm}
\begin{block}{Différence}
 $A\smallsetminus B=\{\textrm{éléments dans $A$ mais pas dans $B$}\}$
\end{block} 
\end{column}
\begin{column}{3cm}
\vspace{-0.2cm}
 \begin{tikzpicture}[scale=0.25]
\draw[magenta!50] \Eset;
\draw[dashed,red]  \Aset;
\draw[dashed,blue] \Bset;
\fill[magenta!70] \Aset;
\fill[white] \Bset;
\draw (-2,1.5) node{$A\smallsetminus B$};
\end{tikzpicture}
\end{column}
\end{columns}

\begin{columns}
\begin{column}{9cm}
\begin{block}{Différence symétrique}
 $A\Delta B=\{\textrm{éléments dans $A\cup B$ mais pas dans $A\cap B$}\}$
 $\phantom{A\Delta B}=(A\cup B)\smallsetminus (A\cap B)$ \end{block} 
\end{column}
\begin{column}{3cm}
\vspace{-0.2cm}
 \begin{tikzpicture}[scale=0.25]
\draw[magenta!50] \Eset;
\draw[dashed,red]  \Aset;
\draw[dashed,blue] \Bset;
\fill[magenta!70,even odd rule]\Aset \Bset;
\draw (0,1.5) node{$A\Delta B$};
\end{tikzpicture}
\end{column}
\end{columns}
\begin{columns}
\begin{column}{9cm}
\begin{block}{Complémentaire}
 $\overline{A}=\Omega\smallsetminus A$
\end{block} 
\end{column}
\begin{column}{3cm}
\vspace{-0.2cm}
 \begin{tikzpicture}[scale=0.25]
\draw[magenta!50] \Eset;
\draw[dashed,red]  \Aset;
\draw[dashed,blue] \Bset;
\fill[magenta!70] \Eset;
\fill[white] \Aset;
\draw (2,1.5) node{$\overline{A}$};
\end{tikzpicture}
\end{column}
\end{columns}

\begin{exampleblock}{Propriétés}
\begin{description}
  \item[Involution:] $\overline{\overline{A}}=A$
 \item[Loi de Morgan:] $\overline{A\cap B}=\overline{A}\cup\overline{B}$ et  $\overline{A\cup B}=\overline{A}\cap\overline{B}$
\end{description}
\end{exampleblock}
\end{frame}

%%%

\begin{frame}
 \frametitle{Produit cartésien}
 \begin{block}{Produit cartésien}
$A\times B=\left\{(a,b)\textrm{ où $a\in A$ et $b\in B$}\right\}$.

$A_1\times \dots\times A_k=\left\{(a_1,\dots,a_k)\textrm{ où $a_i\in A_i$ pour tout $i\in\{1,\dots,k\}$}\right\}$. 
\end{block}
\textbf{\underline{Exemple:}}

Pour le système de codage informatique des couleurs RGB, (de l'anglais ''Red, Green, Blue'') une couleur est un élément de $$[0,255]\times[0,255]\times[0,255]=[0,255]^3$$
\begin{itemize}
 \item deux couleurs qui ont le même triplet sont égale;
 \item on peut définir des ensembles de couleur:
 \[\{\textrm{couleur à dominante verte}\}=\left\{(r,g,b):g\geq\frac{4}{5}(r+b)\right\}\]
\end{itemize}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%



\section{Notions de langages}


\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Notions de langages}}
\end{center}
\end{frame}


 \subsection{Exemples de problèmes}

%%%

\begin{frame}
 \frametitle{Exemples de problèmes}
\begin{description}
 \item[Langage naturel] L’ensemble des mots forme un dictionnaire qui s'arrangent suivant des règles grammaticales pour former des phrases.
 \vspace{0.3cm}
  \item[Stockage informatique] de l’information par une succession de bits
 \vspace{0.3cm}
 \item[Algorithme du texte] Recherche de chaîne de caractères dans un texte...
 \vspace{0.3cm}
 \item[Compilation] Un programme est une suite de caractère qui doit être analysé par le compilateur.
 \vspace{0.3cm}
\item[Bio-informatique] L’ADN code l’information génétique.
\end{description}
\end{frame}

%%%
\subsection{Mots sur un alphabet fini}

%%%

\begin{frame}
 \frametitle{Un peu de vocabulaire}

\begin{description}
\item[Alphabet] Ensemble fini (par exemple: $\mathbb{B} =\{0, 1\}$ est l’alphabet binaire, $\A=\{a,b,c,\dots, z\}$ un alphabet à 26 lettres.) 

\item[Mot] Suite finie d’éléments de $\A$ on le note $u=u_1u_2\dots u_n$ et $n$ est la longueur du mot $u$, notée $|u|$. 

\item[Mot vide] Le mot vide est noté $\varepsilon$. 

On note $\A^{\ast}$ l’ensemble des mots sur $\A$ et $\A^+$ l’ensemble des mots sans le mot vide.

\item[Concaténation] $w=u.v$ est le mot de longueur $|u|+|v|$ tel que 
\[w=u_1u_2\dots u_{|u|}v_1v_2\dots v_{|v|}\]

\item[Puissance] on définit par récurrence $u^n$ par
\[u^0=\varepsilon\textrm{ et }u^{n+1}=u.u^n\textrm{ pour tout }n\in\N\]

\item[Préfixe] $v$ préfixe de $u$ s’il existe un mot $w$ tel que $u=v.w$

\item[Suffixe] $v$ suffixe de $u$ s’il existe un mot $w$ tel que $u=w.v$  
\end{description}
 
\end{frame}
%%%
\begin{frame}
 \frametitle{Equidivisibilité}
 
\begin{exampleblock}{Lemme de Levy}
 Soient $u,v,z,t\in\A^{\ast}$ tels que $u.v=z.t$. Alors il existe $w\in\A^{\ast}$ tel que:
\begin{itemize}
 \item ou bien $u=z.w$ et $t=w.v$ si $|u|\geq |z|$,
 \item ou bien $z=u.w$ et $v=w.t$ si $|u|\leq |z|$.
\end{itemize}
\end{exampleblock}
\begin{center}
 \begin{tikzpicture}[scale=0.3]
 \draw (0,0)rectangle (8,1);
 \draw (12,0)rectangle (8,1); 
 \draw (4,0.5) node{$u$};
 \draw (10,0.5) node{$v$};
 \draw (0,-2.5)rectangle (5,-1.5);
 \draw (12,-2.5)rectangle (5,-1.5); 
 \draw (2.5,-2) node{$z$};
 \draw (8.5,-2) node{$t$}; 
 \draw[fill=gray!30] (5,-1.25)rectangle (8,-0.25); 
  \draw (6.5,-0.75) node{$w$};

  \draw (15,-0.75) node{ou bien};
  
\begin{scope}[xshift=19cm]
  \draw (0,-2.5)rectangle (8,-1.5);
 \draw (12,-2.5)rectangle (8,-1.5); 
 \draw (4,-2) node{$z$};
 \draw (10,-2) node{$t$};
 \draw (0,0)rectangle (5,1);
 \draw (12,0)rectangle (5,1); 
 \draw (2.5,0.5) node{$u$};
 \draw (8.5,0.5) node{$v$}; 
 \draw[fill=gray!30] (5,-1.25)rectangle (8,-0.25); 
  \draw (6.5,-0.75) node{$w$};
\end{scope}
\end{tikzpicture}
\end{center}
\begin{exampleblock}{Corollaire: simplification à droite}
Soient $u,v,z$ et $t\in\A^{\ast}$. 

Si $u.v=u.t$ alors $v=t$. 

De même si $u.v=z.v$ alors $u=z$.
\end{exampleblock}
\end{frame}
%%%


\subsection{Langage}

\begin{frame}
 \frametitle{Définition et exemples de langages}
 
\begin{block}{Langage}
 Un \define{langage} $\Lang$ sur un alphabet fini $\A$ est un ensemble de mots  sur $\A$.
 
  Autrement dit $\Lang\subseteq\A^\ast$. 
\end{block}

\textbf{\underline{Exemples:}}
\begin{footnotesize}
  Exemples de langages sur $\mathbb{B}=\{0,1\}$:
\begin{itemize}
 \item $\emptyset\ne\{\varepsilon\}$;
 \item $\mathbb{B}^\ast=\{\varepsilon,0,1,00,01,10,11,000,001,\dots \}$;
 \item $\mathbb{B}^+=\{0,1,00,01,10,11,000,001,\dots \}$;
 \item $\{0^n:n\in\N\}$;
 \item $\{0^n1^m:n,m\in\N\}$;
 \item $\{0^n1^n:n\in\N\}$;
 \item $\{0^p:p\in\N \textrm{ nombre premier}\}$;
 \item $\{u\in\mathbb{B}^{\ast}:u \textrm{ est  le codage en binaire d’un nombre premier}\}$;
 \item $\{u\in\mathbb{B}^{\ast}:u \textrm{ est un palindrome}\}$; 
  \item $\{u\in\mathbb{B}^{\ast} \textrm{ code html certifié}\}\ne\{u\in\mathbb{B}^{\ast} \textrm{ code html interprété par Firefox}\}$; 
  \item $\{u\in\mathbb{B}^{\ast}:u \textrm{ codage en MP3 de votre chanson préférée}\}$;
 \item $\{u\in\mathbb{B}^{\ast}:u \textrm{ codage  d’un programme qui s’arête sur l’entrée vide}\}$ $\dots$
\end{itemize}
 \end{footnotesize}


\end{frame}
%%%

\begin{frame}
 \frametitle{Opérations sur les langages}
 \begin{itemize}
 \item \define{Union}: $\Lang_1\cup \Lang_2$ 
 \item \define{Intersection}: $\Lang_1\cap \Lang_2$ 
 \item \define{Compémentaire}: $\overline{\Lang}=\A^{\ast}\smallsetminus\Lang$
 \item \define{Concaténation}: $\Lang_1.\Lang_2=\{u_1.u_2: u_1\in\Lang_1\textrm{ et }u_2\in\Lang_2\}$
  \item \define{Puissance}: Par récurrence la puissance $n^{\textrm{ème}}$ de $\Lang$, est définie par $$\Lang^0=\{\varepsilon\}\textrm{ et }\Lang^{n+1}=\Lang.\Lang^n$$
  Attention, en général 
\begin{footnotesize}
   $$\Lang^n=\{u\in\A^\ast:\exists u_1,u_2,\dots,u_n\in\Lang\textrm{ tel que }u=u_1.u_2.\cdots.u_n\}\ne\{u^n:n\in\N,u\in\Lang \}$$
 \end{footnotesize}
 \item \define{Fermeture de Kleene}: 
    $$\Lang^\ast=\bigcup_{n\geq0}\Lang^n\qquad\textrm{et}  \qquad\Lang^+=\bigcup_{n>0}\Lang^n$$
\end{itemize}
 
\end{frame}

%%%


\end{document}

