Cours du 22 au 26 septembre

5 files changed, 350 insertions, 2 deletions

diff --git a/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.pdf b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.pdf
new file mode 100644
index 0000000..58bc88c
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.pdf
diff --git a/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.tex b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.tex
new file mode 100755
index 0000000..b833d16
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/2- Relations d-ordre, ensembles ordonnés.tex
@@ -0,0 +1,248 @@
+\documentclass[a4paper, titlepage]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{textcomp}
+\usepackage[french]{babel}
+\usepackage{amsmath, amssymb}
+\usepackage{amsthm}
+\usepackage[svgnames]{xcolor}
+\usepackage{thmtools}
+\usepackage{lipsum}
+\usepackage{framed}
+\usepackage{parskip}
+\usepackage{titlesec}
+
+\renewcommand{\familydefault}{\sfdefault}
+
+% figure support
+\usepackage{import}
+\usepackage{xifthen}
+\pdfminorversion=7
+\usepackage{pdfpages}
+\usepackage{transparent}
+\newcommand{\incfig}[1]{%
+	\def\svgwidth{\columnwidth}
+	\import{./figures/}{#1.pdf_tex}
+}
+
+\pdfsuppresswarningpagegroup=1
+
+\colorlet{defn-color}{DarkBlue}
+\colorlet{props-color}{Blue}
+\colorlet{warn-color}{Red}
+\colorlet{exemple-color}{Green}
+\colorlet{corol-color}{Orange}
+\newenvironment{defn-leftbar}{%
+  \def\FrameCommand{{\color{defn-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{warn-leftbar}{%
+  \def\FrameCommand{{\color{warn-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{exemple-leftbar}{%
+  \def\FrameCommand{{\color{exemple-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{props-leftbar}{%
+  \def\FrameCommand{{\color{props-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{corol-leftbar}{%
+  \def\FrameCommand{{\color{corol-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+
+\def \freespace {1em}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+ bodyfont=\sffamily,%
+ headformat=\color{defn-color}Définition~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{defn-leftbar},%
+ postfoothook=\end{defn-leftbar},%
+]{better-defn}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+ bodyfont=\sffamily,%
+ headformat=\color{warn-color}Attention~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{warn-leftbar},%
+ postfoothook=\end{warn-leftbar},%
+]{better-warn}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+notebraces={}{},%
+headpunct=,%
+ bodyfont=\sffamily,%
+ headformat=\color{exemple-color}Exemple~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{exemple-leftbar},%
+ postfoothook=\end{exemple-leftbar},%
+]{better-exemple}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+ bodyfont=\sffamily,%
+ headformat=\color{props-color}Proposition~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{props-leftbar},%
+ postfoothook=\end{props-leftbar},%
+]{better-props}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+ bodyfont=\sffamily,%
+ headformat=\color{props-color}Théorème~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{props-leftbar},%
+ postfoothook=\end{props-leftbar},%
+]{better-thm}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+ bodyfont=\sffamily,%
+ headformat=\color{corol-color}Corollaire~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{corol-leftbar},%
+ postfoothook=\end{corol-leftbar},%
+]{better-corol}
+
+\declaretheorem[style=better-defn]{defn}
+\declaretheorem[style=better-warn]{warn}
+\declaretheorem[style=better-exemple]{exemple}
+\declaretheorem[style=better-corol]{corol}
+\declaretheorem[style=better-props, numberwithin=defn]{props}
+\declaretheorem[style=better-thm, sibling=props]{thm}
+\newtheorem*{lemme}{Lemme}%[subsection]
+%\newtheorem{props}{Propriétés}[defn]
+
+\newenvironment{system}%
+{\left\lbrace\begin{align}}%
+{\end{align}\right.}
+
+\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}}
+
+\usepackage{LobsterTwo}
+\titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{}
+\titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{}
+\titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{}
+
+\newenvironment{lititle}%
+{\vspace{7mm}\LobsterTwo \large}%
+{\\}
+
+\renewenvironment{proof}{\par$\square$ \footnotesize\textit{Démonstration.}}{\begin{flushright}$\blacksquare$\end{flushright}\par}
+
+\title{Relations d'ordre, ensembles ordonnés}
+\author{William Hergès\thanks{Sorbonne Université}}
+
+\begin{document}
+	\maketitle
+	\tableofcontents
+	\newpage
+    \section{ensemble ordoné}
+    \begin{defn}
+        Une relation d'ordre $\preceq$ est une relation binaire sur $E$ si et seulement si~:
+        \begin{itemize}
+            \item réflexive
+            \item anti-symétrique
+            \item transitive
+        \end{itemize}
+
+        L'ordre strict $\prec$ est associé à $\preceq$~: c'est la même, sauf qu'elle n'est pas réflexive~:
+        $$ \prec = \preceq\backslash\mathrm{Id}_E $$
+    \end{defn}
+    \begin{defn}
+        Une relation d'ordre $\preceq$ est~:
+        \begin{itemize}
+            \item totale si et seulement si $\preceq$ permet toujours de comparer deux éléments quelconques de $E$
+            \item partielle s'il existe au moins deux éléments de $E$ incomparables avec $\preceq$
+        \end{itemize}
+    \end{defn}
+    \begin{defn}
+        $(E,\preceq)$ est un ensemble~:
+        \begin{itemize}
+            \item totalement ordonné si $\preceq$ est un ordre total.
+            \item partiellement ordonné si $\preceq$ est un ordre partiel.
+        \end{itemize}
+    \end{defn}
+    \begin{exemple}
+        $(\mathbb{N},\leqslant )$ est un ensemble totalement ordonné.
+
+        $(\mathcal{P}(F),\subseteq)$ est un ensemble partiellement ordoné (pour $F$ un ensemble quelconque).
+
+        $(\mathbb{N}^*, |)$ est aussi partiellement ordoné, où
+        $$ | = \{(a,b)|\exists k\in\mathbb{N}^*, b = na\} $$
+        (c'est la relation divise.)
+    \end{exemple}
+    \begin{proof}
+        Preuve du deuxième exemple.
+
+        Soit $F$ un ensemble.
+
+        Montrons que $\subseteq$ est un ordre pour $\mathcal{P}(F)$.
+        \begin{itemize}
+            \item Soit $A\in\mathcal{P}(F)$.
+                Triviallement, $A\subseteq A$.
+                Alors, $\subseteq$ est réflexive.
+            \item Soit $(A,B)\in\mathcal{P}(F)^2$.
+                Supposons que $A\subseteq B$ et que $B\subseteq A$.
+                Alors, $A=B$ par définition.
+            \item Soit $(A,B,C)\in\mathcal{P}(F)^3$ avec $A\subseteq B$ et $B\subseteq C$.
+                Si $A$ est l'ensemble vide, il est inclu dans tous les ensembles. 
+                Donc $A\subseteq C$.
+                Si $A$ n'est pas l'ensemble vide, tous ses éléments sont dans $B$. 
+                Or, tous les éléments de $B$ sont dans $C$.
+                Donc, tous les éléments de $A$ sont dans $C$.
+                Alors, $A\subseteq C$.
+        \end{itemize}
+        Ainsi, $\subseteq$ est bien un ordre pour $\mathcal{P}(F)$.
+
+        Montrons que $\subseteq$ est un ordre partiel.
+
+        Supposons que $F$ contient au moins deux éléments.
+
+        Soit $(x,y)\in F^2$, deux éléments différents.
+        Soient $A=\{x\}$ et $B=\{y\}$.
+
+        On a que $A\not\subseteq B$ et que $B\subseteq A$.
+        Donc, $\subseteq$ est partiel dans ce cas.
+
+        Si $F$ est vide, alors $\mathcal{P}(F)$ contient un unique élément.
+        Cet ensemble est totalement ordonné.
+
+        Si $F$ est un singleton, alors $\mathcal{P}(F)$ contient $F$ et l'ensemble vide.
+        Cet ensemble est totalement ordonné.
+
+        La slide est ainsi fausse, mais les ensembles à moins de deux éléments sont peux intéressants.
+    \end{proof}
+    Revoir les slides 4 - 6.
+    \begin{defn}
+        Soient $(E_1,\preceq_1)$ et $(E_2,\preceq_2)$ deux ensemble ordonnés.
+
+        L'application $f:E_1\to E_2$ est dite monotone si~:
+        $$ \forall (x,y)\in E_1^2,\quad x\preceq_1 y \implies f(x)\preceq_2 f(y) $$
+    \end{defn}
+    Une application monotone préserve les relations d'ordre.
+    \begin{exemple}
+        On se place dans $(\mathbb{N},\leqslant)$ et dans $(\mathcal{P}(\mathbb{N}))$
+
+        $f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$ tel que $f(n) = \{k\in\mathbb{N}|k\leqslant n\}$ est monotone.
+
+        $g:\mathbb{N}\to \mathcal{P}(\mathbb{N})$ tel que $g(n)=\{n\}$ ne l'est pas par contre~!
+    \end{exemple}
+    \begin{props}
+        Deux ensembles ordonnés $(E_1,\preceq_1)$ et $(E_2,\preceq_2)$ sont isomorphes s'il existe une bijection
+        $f:E_1\to E_2$ telle que $f$ et $f^{-1}$ sont monotones.
+    \end{props}
+    Slide 8 pour des exemples et pour le retour des graphes.
+    \begin{warn}
+        Une bijection $f$ peut être monotone sans que $f^{-1}$ ne le soit~!
+    \end{warn}
+    \begin{proof}
+        Fin de la slide 8 pour la preuve.
+    \end{proof}
+\end{document}
diff --git a/semestre 3/mathématiques discrètes/td/25-09-26.pdf b/semestre 3/mathématiques discrètes/td/25-09-26.pdf
new file mode 100644
index 0000000..cf667e4
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/td/25-09-26.pdf
diff --git a/semestre 3/mathématiques discrètes/td/25-09-26.tex b/semestre 3/mathématiques discrètes/td/25-09-26.tex
new file mode 100755
index 0000000..15b4909
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/td/25-09-26.tex
@@ -0,0 +1,101 @@
+\documentclass[a4paper]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{textcomp}
+\usepackage[french]{babel}
+\usepackage{amsmath, amssymb}
+\usepackage{amsthm}
+\usepackage[svgnames]{xcolor}
+\usepackage{thmtools}
+\usepackage{lipsum}
+\usepackage{framed}
+\usepackage{parskip}
+
+\renewcommand{\familydefault}{\sfdefault}
+
+\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}}
+
+\usepackage{titlesec}
+\usepackage{LobsterTwo}
+\titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{}
+\titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{}
+\titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{}
+
+\title{TD Maths discrètes}
+\author{William Hergès\thanks{Sorbonne Université}}
+
+\begin{document}
+	\maketitle
+    \section*{Exercice 6}
+    \begin{enumerate}
+        \item Supposons que $R$ soit réflexive.
+            On a que pour tout $x$ dans $R$, $(x,x)\in R$, ce qui est la définition de l'identité.
+
+            Supposons que $\mathrm{Id}_E\subseteq R$.
+            On a que pour tout $x$ dans $R$, $(x,x)\in R$ car $(x,x)\in\mathrm{Id}_E$.
+        \item \begin{align*}
+                \text{$R$ symétrique} \iff& \forall (x,y)\in E^2, (x,y)\in R \implies (y,x)\in R \\
+                                      \iff& R = \{(x,y) \in R | (y,x)\in R \} \\
+                                      \iff& R = R^{-1} 
+            \end{align*}
+        \item À faire par équivalence classiquement. 
+    \end{enumerate}
+    \section*{Exercice 8}
+    Si $R$ est relation d'équivalence sur $E$, alors la classe d'équivalence de $a\in R$ est l'ensemble~:
+    $$ \{(a,x)\in R\} $$
+    \begin{enumerate}
+        \item $R$ est réflexive, donc $a\in [a]$ car $(a,a)\in R$
+        \item Si $[a] = [b]$, alors pour tout $x$ dans $A$, on a $(a,x)\in R$ et $(b,x)\in R$, donc $(a,b)\in R$ par
+            symétrie et transitivité.
+
+            Pareil dans l'autre sens.
+        \item Supposons que $[a]\cap[b]\neq\varnothing$. 
+            Alors, $\exists x\in [a]\cap[b]$ tel que $(a,x)\in R$ et $(b,x)\in R$.
+            Par symétrie et transitivité, on a $(b,x)\in R \iff (x,b)\in R \iff (a,b)\in R$.
+            Absurde car si $(a,b)\in R$, on a que $[a] = [b]$, ce qui est faux par hypothèse.
+        \item $\{[a]|a\in A\}$ est une partition de $A$ car 
+            \begin{itemize}
+                \item tous les éléments de $[a]$ pour tout $a\in A$ sont dans $A$ par définition;
+                \item toutes les classes d'équivalence sont disjointes (3);
+                \item tous les éléments de $A$ sont présents dans cet ensemble car $a\in [a]$ (1).
+            \end{itemize}
+    \end{enumerate}
+    \textbf{Ceci est un résultat important~!}
+    \section*{Exercice 9}
+    L'application $\{(a,b), (b,b)\}$ dans $\{a,b\}$ n'est ni injective, ni surjective.
+    \begin{enumerate}
+        \item $f_1$ est injective, mais pas surjective, car il n'existe pas d'inverse sur $\mathbb{N}$.
+            $f_2$ est bijective, car il existe un inverse sur $\mathbb{Q}$.
+        \item $f$ est surjective, car $f(0) = 0$, $f(1) = 1$, $f(2) = 2$ et $f(3) = 0$.
+        \item $f$ est surjective, car $\forall x\in\mathbb{N}, f(x, 0) = x$ et $f(1,0) = f(0,1)$.
+        \item $f$ est bijective, car~:
+            \begin{itemize}
+                \item si $f(n)$ est pair, alors son antécédent est $n+1$
+                \item si $f(n)$ est impair, alors son antécédent est $n-1$
+                \item si $f(n_1) = f(n_2)$, alors $n_1 + 1 = n_2 + 1$ ou $n_1 - 1 = n_2 - 1$, i.e. $n_1=n_2$
+            \end{itemize}
+        \item $f$ n'est pas surjective, car les mots ne finissant par par $b$ ne sont jamais atteint.
+            $f$ est injective, car $f(u_1) = f(u_2) \implies u_1.b = u_2.b\implies u_1 = u_2$. 
+    \end{enumerate}
+    Il existe $2^3 = 9$ applications différentes de $\{a,b,c\}$ vers $\{1,2\}$ (pour chaque élément de $\{a,b,c\}$, on
+    possède deux choix), dont aucune injective, $3\times 2 = 6$ surjectives (on choisit quel élément est le premier et 
+    quel élément est le deuxième, le troisième est libre) et aucune bijective (car aucune n'est injective).
+    \section*{Exercice 19}
+    Soit $n\in\mathbb{N}$.
+
+    Si $n$ est pair, alors $n+1$ est impair.
+    Donc, $$ \exists !p\in\mathbb{N},\quad n+1=2p+1 $$
+    On pose $x=0$ et $y=p$, alors $$ n = 2^0 (2p+1) - 1 = 2^x(2y+1) $$
+    Par conséquent, les nombres pairs s'écrivent comme~:
+    $$ g(0,p) $$
+
+    Si $n$ est impair, il existe un unique $p$ dans $\mathbb{N}$ tel que $n = 2p+1$.
+    Donc, $$ n+1 = 2p+2 = 2(p+1) $$
+    Or, un nombre pair s'écrit d'une manière unique avec $(q,r)\in\mathbb{N}^2$ avec $q$ non nul comme~:
+    $$ 2^q(2r+1) $$
+    On pose $x=q$ et $p=r$, alors $$ n = 2^q(2r+1) - 1 = 2^x(2y+1) - 1 $$
+    Par conséquent, les nombres pairs s'écrivent comme~:
+    $$ g(q,r) $$
+\end{document}
+endsnippet
diff --git a/semestre 3/mathématiques discrètes/td/template.tex b/semestre 3/mathématiques discrètes/td/template.tex
index 23ee891..5bebfd6 100755
--- a/semestre 3/mathématiques discrètes/td/template.tex
+++ b/semestre 3/mathématiques discrètes/td/template.tex
@@ -23,10 +23,9 @@
 \titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{}
 
 \title{Titre}
-\author{William Hergès\thanks{CPES Science Henri-IV / PSL}}
+\author{William Hergès\thanks{Sorbonne Université}}
 
 \begin{document}
 	\maketitle
-	$0	
 \end{document}
 endsnippet