Algorithmique ii - Mémento mathématique

Il s'agit d'un simple mémento, il faudra donc se référer au cours de mathématiques discrètes pour trouver les développements et précisions concernant les notions qui sont rappelées ici brièvement avec cer­tai­nes imprécisions et/ou approximations inévitables par soucis de concision.

Logique

Une proposition est un énoncé auquel on peut attribuer une valeur de vérité vrai ou faux. Quand une proposition est annoncée comme étant vraie (il s'agit donc d'une affirmation), on parle alors d'assertion. Les connecteurs logiques \(\neg\) de négation, \(\vee\) de disjonction et \(\wedge\) de conjonction permettent de connecter des propositions pour en constituer de nouvelles, l'expression cor­res­pon­dan­te s'appelle une formule. Pour un connecteur logique, la table qui regroupe l'ensemble des valeurs de vérité possibles de la formule pour les propositions qu'elle connecte s'appelle une table de vérité.

\(P\)\(\neg P\)
FV
VF
\(P\)\(Q\) \(\ P\wedge Q\ \) \(\ P\vee Q\ \)
FF FF
FV FV
VF FV
VV VV

Tables de vérité des trois connecteurs logiques usuels unaires et binaires.

Deux formules \(E_1\) et \(E_2\) qui ont toujours même valeur de vérité quelles que soient les valeurs logiques des variables propositionnelles qui les constituent sont dites logiquement équivalentes, ce que l'on note \(E_1\equiv E_2\). Le connecteur d'implication \(\Rightarrow\) est défini par \[P\Rightarrow Q\overset{\text{déf.}}{\equiv} \neg P\vee Q.\] On montre aisément que \(P\Rightarrow Q\equiv \neg Q\Rightarrow \neg P\), et la proposition \(\neg Q\Rightarrow \neg P\) est appelée contraposée de la proposition \(P\Rightarrow Q\). Le connecteur d'équivalence \(\Leftrightarrow\) est défini par \[P\Leftrightarrow Q\overset{\text{déf.}}{\equiv} (P\Rightarrow Q)\wedge Q\Rightarrow P).\] On rappelle les lois de De Morgan : \begin{align*} \neg(P\vee Q)&\ \equiv\ \neg P\wedge\neg Q\\ \neg(P\wedge Q)&\ \equiv\ \neg P\vee\neg Q \end{align*}

Ensembles et prédicats

Un ensemble désigne informellement une collection d'objets. Deux symboles mathématiques sont spécifiques aux en­semb­les, le symbole d'égalité \(\def\R{\mathbf R}\def\N{\mathbf N}=\) et le symbole d'appartenance \(\in\). Si deux objets \(A\) et \(B\) sont égaux, i.e. \(A=B\) ils sont totalement interchangeables et l'un peut remplacer l'autre dans n'importe quelle expression. Si deux ensembles \(A\) et \(B\) sont égaux, cela signifie que tous les éléments de l'ensemble \(A\) sont des éléments de l'ensemble \(B\) — on dit que \(A\) est inclus dans \(B\), ce que l'on note \(A\subseteq B\) — et réciproquement, ce que l'on note cette fois \(B\subseteq A\).

Un prédicat est un énoncé bien formé contenant des variables tel qu'en substituant les variables par des valeurs choisies dans un ensemble — ce que l'on qualifie en informatique d'ins­tan­ciation des variables — le nouvel énoncé devient une proposition. Par exemple \(x\geq \pi\) est un prédicat à une variable \(x\) de l'ensemble des nombres réels \(\R\). En le notant \(P(x)\), on a par exemple l'assertion (proposition vraie) \(P(4)\). L'énoncé \(n=2k\) est un prédicat \(P(n,k)\) à deux variables \(n\) et \(k\) de l'ensemble des entiers naturels \(\N\).

Relations binaires

On appelle relation binaire sur \(E\) tout prédicat \(R(x,y)\) à deux variables dans \(E\). On note généralement une relation binaire de manière infixe \(x\ R\ y\), plus en adéquation avec la langue naturelle : \(x\) est en relation avec \(y\) pour la relation \(R\). Les relations binaires peuvent posséder des propriétés re­mar­qua­bles :

  1. Réflexivité : \(\forall x\in E,\ x\ R\ x\) ;
  2. Symétrie : \(\forall x,y\in E,\ x\ R\ y\Leftrightarrow y\ R\ x\) ;
  3. Antisymétrie : \(\forall x,y\in E,\ (x\ R\ y\ \text{et}\ y\ R\ x)\Rightarrow y= x\) ;
  4. Transitivité : \(\forall x,y,z\in E,\ (x\ R\ y\ \text{et}\ y\ R\ z)\Rightarrow x\ R\ z\).

Une relation binaire qui est à la fois réflexive, symétrique et transitive est appelée relation d'équi­valen­ce. Si \(R\) est une relation d'équivalence sur un ensemble \(E\) et \(x\in E\), le sous-ensemble de \(E\) constitué par tous les éléments en relation avec \(x\) est appelé classe d'équivalence de \(x\).

Une relation binaire qui est à la fois réflexive, antisymétrique et transitive est appelée relation d'ordre. Si \(R\) est une relation d'ordre sur un ensemble \(E\), on dit que deux éléments \(x\) et \(y\) sont comparables si \(x\ R\ y\) ou \(y\ R\ x\). Si tous les éléments sont comparables deux-à-deux, il s'agit d'un ordre total sinon d'un ordre partiel. Si \(R\) est une relation d'ordre sur un ensemble \(E\), la relation \(R'\) définie sur \(E\) par \(x\ R\ y\) et \(x\not=y\) est appelée ordre strict associé à \(R\), ce n'est pas une relation d'ordre.

L'ordre naturel \(\leq\) sur l'ensemble \({\mathbf N}\) des entiers naturels est une relation d'ordre total alors que l'inclusion \(\subseteq\) sur l'ensemble \({\mathcal P}(E)\) des parties d'un ensemble \(E\) est une relation d'ordre partiel, tout comme la relation de divisibilité \(|\) sur l'ensemble des entiers naturels \({\mathbf N}\). Le couple \((E,\preceq)\) constitué d'un ensemble \(E\) et d'une relation d'ordre \(\preceq\) sur \(E\) est appelé ensemble ordonné. Par analogie avec l'ordre naturel, si \(a\preceq b\), on dit que \(a\) est plus petit que \(b\). De la même manière, si \(A\subset E\) et s'il existe un élément \(m\in A\) tel que \(\forall x\in A\), \(m\preceq x\) (respectivement \(\forall x\in A\), \(x\preceq m\)) il est nécessairement unique et on dira que \(m\) est le plus petit élément de \(A\) ou minimum de \(A\) que l'on note \(\min A\) (respectivement plus grand élément de \(A\) ou maximum de \(A\) que l'on note \(\max A\)). Dans un ensemble partiellement ordonné, on appelle élément minimal (resp. élément maximal) un élément \(m\in E\) (resp. \(M\)) plus petit (resp. plus grand) que tous les éléments auxquels il est com­pa­ra­ble.

Correspondances, fonctions, applications

Soient \(E\) et \(F\) deux ensembles. Une cor­res­pon­dan­ce de \(E\) dans \(F\) est un triplet \(c:=(E,F,\Gamma)\) où \(E\) est l'ensemble de départ, \(F\) l'ensemble d'arrivée et \(\Gamma\subseteq E\times F\) le graphe de \(c\). Si de plus le graphe \(\Gamma\) ne contient jamais deux couples distincts \((x,a)\) et \((x,b)\) il s'agit d'une correspondance fonctionnelle ou encore d'une fonction. On note alors de manière condensée \(f:E\rightarrow F\) pour spécifier les ensembles de départ et d'arrivée, le graphe étant défini explicitement pas l'ensemble des couples \((x,y)\) ou par un prédicat à deux variables \(P(x,y)\) (supposé être satisfait pour au plus un \(y\) par \(x\) donné). Ainsi, si \((x,y)\in \Gamma\), on note \(y=f(x)\) et \(y\) est l'image de \(x\) par \(f\) et \(x\) est un antécédent de \(y\) par \(f\). Le domaine de définition d'une fonction \(f:E\rightarrow F\) est le sous-ensemble de \(E\) des éléments qui ad­met­tent une image, on le note \({\mathcal D}_f\). Si \({\mathcal D}_f=E\), on dit que \(f\) est une application.

On appelle injection toute application \(f:E\rightarrow F\) telle que deux éléments distincts de \(E\) ont des ima­ges distinctes, ce que l'on exprime souvent par la contraposée: \[\forall (x,y)\in E\times E,\ \ f(x)=f(y)\Rightarrow x=y.\] On appelle surjection toute application \(f:E\rightarrow F\) telle que tout élément de l'ensemble d'arrivée \(F\) admet au moins un antécédent: \[\forall y\in F,\ \exists x\in E,\quad f(x)=y.\] On appelle bijection toute application \(f:E\rightarrow F\) qui est à la fois une injection et une surjection, au­tre­ment dit telle que tout \(y\in F\) admet un unique antécédent \(x\).

Permutations

Soit \(n\) un entier naturel. On appelle permutation toute bijection \(\sigma:[1,n]\rightarrow[1,n]\). On note gé­né­ra­le­ment une per­mu­ta­tion \(\sigma\) sous la forme d'une matrice \(2\times n\) : \[\sigma=\begin{pmatrix} 1&2&3&\cdots&n\\ \sigma(1)&\sigma(2)&\sigma(3)&\cdots&\sigma(n) \end{pmatrix} \] L'ensemble de toutes les permutations des entiers de l'intervalle \([1,n]\) est noté \({\mathfrak S}_n\) et constitue un groupe (non commutatif dès que \(n\geq 3\)) quand il est muni de la loi de composition des applications, c'est le groupe symétrique. On appelle inversion d'une permutation \(\sigma\), tout couple \((\sigma(i),\sigma(j))\) tel que \(i < j\ \text{et}\ \sigma(i) > \sigma(j)\). Une permutation \(\sigma\) qui laisse tous les termes fixes, sauf deux d'entre eux s'appelle une trans­po­si­tion. S'il existe \(k\) entiers \(x_0,x_1,\ldots,x_{k-1}\in[1,n]^k\) tels que \[\forall i\in[0,k-1],\quad \sigma(x_i)=x_{i+1\pmod k}\] et \(\sigma(x)=x\) pour toutes les autres valeurs \(x\) de l'intervalle \([1,n]\), la permutation \(\sigma\) est appelée k-cycle, ou cycle de longueur \(k\geq 2\) que l'on note plus simplement \(\sigma=(x_0,x_1,\ldots,x_{k-1})\). Un \(2\)-cycle est donc une transposition que l'on note également \(\tau_{i,j}\) si elle échange les entiers \(i\) et \(j\), i.e. \(\tau(i) = j\) et \(\tau(j)=i\). On montre que toute permutation se décompose en produits de cycles (le produit désignant la com­po­si­tion des applications). La permutation suivante se décompose en deux cycles, un \(4\)-cycle et un \(3\)-cycle : \[\sigma=\begin{pmatrix} \color{yellow}1&2&\color{yellow}3&\color{yellow}4&\color{#AAF}5&\color{#AAF}6&7&\color{yellow}8&\color{#AAF}9\\ \color{yellow}3&2&\color{yellow}8&\color{yellow}1&\color{#AAF}6&\color{#AAF}9&7&\color{yellow}4&\color{#AAF}5 \end{pmatrix}={\color{yellow}(1,3,8,4)}{\color{#AAF}(5,6,9)} \]

Cardinalité, suites

Deux ensembles \(E\) et \(F\) sont dits équipotents, Équipotent signifie mê­me puis­san­ce ce que l'on note \(E\approx F\), s'il existe une bijection \(f:E\rightarrow F\). Si \(a\) et \(b\) sont deux entiers naturels, on définit l'intervalle \([a,b]:=\{n\in{\mathbf N}\mid a\leq n\leq b\}\). Un ensemble \(E\) est dit fini s'il existe un entier \(n\), appelé cardinal de \(E\) tel que \(E\approx[1,n]\), on le note \(\#E\) ou \(|E|\). Dans le cas contraire, \(E\) est dit infini. Un ensemble infini équipotent à \(\mathbf N\) est dit dénombrable. Un ensemble fini ou dénombrable est dit au plus dénombrable.

Soit \(E\) un ensemble. Une application \(u:{\mathbf N}\rightarrow E\) est appelée suite d'éléments de \(E\), on la note \((u_n)_{n\in {\mathbf N}}\) ou par commodité \((u_n)\) et la notation indicée \(u_n\) est utilisée au lieu de \(u(n)\), c'est le terme général de rang \(n\) de la suite. Si \(u:I\rightarrow E\) où \(I\) est un ensemble fini totalement ordonné de cardinal \(n\) (souvent \([1,n]\) ou \([0,n-1]\)), on parle de séquence ou de suite finie de longueur \(n\in{\mathbf N}\) indexée par \(I\) ou d'ensemble d'in­de­xa­tion \(I\).

Soient \(I\) et \(E\) deux ensembles quelconques. Une famille d'ensembles indexée par \(I\) est une application \(A\) de \(I\) dans \({\mathcal P}(E)\). On la note \((A_i)_{i\in I}\) avec \(A_i:=A(i)\).

Une partition d'un ensemble \(E\) est une famille \((E_i)_{i\in I}\) de parties de \(E\) telle que

  1. \(\forall i\in I,\quad E_i\not=\varnothing\),
  2. \(\forall (i,j)\in I\times I,\ i\not=j\Rightarrow E_i\cap E_j=\varnothing\),
  3. \(\displaystyle\bigcup_{i\in I}E_i=E\).
Si l'assertion 2 n'est pas satisfaite on parle de recouvrement de \(E\). Une partition d'un ensemble \(E\) définit une relation d'équivalence sur \(E\) : deux éléments sont en relation si et seulement s'ils ap­par­tien­nent à une même classe \(E_i\). Réciproquement les classes d'équivalence d'une relation d'équi­va­len­ce sur \(E\) cons­ti­tuent une partition de \(E\).

Formulaire de combinatoire

Des extraits de ce paragraphe sont disponibles en mémo pdf. Dans toute la suite, \(E\) et \(F\) désignent deux ensembles finis et totalement ordonnés quand cette propriété est nécessaire avec \(n=\#E\) et \(p=\#F\). On rappelle que l'application factorielle est l'appli­cation de \(\mathbf N\) dans \(\mathbf N\) définie par \begin{equation} n!:=n(n-1)(n-2)\ldots 2\times 1\quad\text{et par convention}\quad 0!:=1. \end{equation}

On dénombre le

Compléments

Soient \(E\) et \(F\) deux ensembles finis de même cardinal. Alors une application \(f:E\rightarrow F\) est injective si et seulement si elle est surjective.
[de récurrence] Soit \(P(n)\) un prédicat sur \({\mathbf N}\) et \(a\in{\mathbf N}\). Si \(P(n)\) satisfait les deux assertions suivantes :
  1. \(P(a)\) est vrai (initialisation),
  2. \(\forall n\in{\mathbf N},\ n\geq a,\quad P(n)\Rightarrow P(n+1)\) (hérédité).
Alors \(P(n)\) est vrai pour tout entier \(n\geq a\).

Exercices

Démontrez les formules (\ref{eq:pascal}). Indication : en notant \(E=\{a_1,a_2,\ldots,a_n\}\), montrez que l'application \(\pi:\{0,1\}^n\rightarrow{\mathcal P}(E)\) définie par \(\pi(x):=\{a_i\ |\ x_i=1\}\) est une bijection. Montrez que la famille \({\mathcal P}_k(E):=\{A\in {\mathcal P}(E)\ |\ \#A=k\}\) pour \(k\in[0,n]\) est une partition de \({\mathcal P}\) et que \(\#{\mathcal P}_k(E)=\binom{n}{k}\) puis concluez à l'aide de la formule de sommation (\ref{eq:sommation}).
Soit \(n\in{\mathbf N}\). Démontrez que le nombre maximal d'inversions d'une permutation de \({\frak S}_n\) est égal à \(\frac{n(n-1)}{2}\) (Comptez le nombre de couples \((i,j)\) tels que \(i < j\)). Soit \(\sigma\in{\frak S}_n\), on note \(\bar\sigma\in{\frak S}_n\) la permutation miroir de \(\sigma\) définie par \[\bar\sigma(i):=\sigma(n-i+1).\] Montrez que \((i,j)\) est/n'est pas une inversion de \(\sigma\) si et seulement si \((i,j)\) n'est pas/est une inversion de \(\bar\sigma\). En déduire que la somme du nombre d'inversions de \(\sigma\) et de \(\bar\sigma\) est égal à \(\frac{n(n-1)}{2}\). Montrez que l'on peut partitionner \({\frak S}_n\) en deux ensembles \(\Sigma\) et \(\bar\Sigma\) tels que \[\sigma\in\Sigma\Leftrightarrow\bar\sigma\in\bar\Sigma.\] En déduire que la somme du nombre d'inversions de toutes les permutations de \({\frak S}_n\) est égal à \[ n!\ \frac{n(n-1)}{4}. \]
Soit \(r\in{\mathbf R}\). On rappelle qu'une suite \((a_n)_{n\in{\mathbf N}}\) est une suite arithmétique (respectivement suite géométrique) de raison \(r\) si pour tout \(n\in{\mathbf N}\), \(a_{n+1}=a_n+r\) (respectivement \(a_{n+1}=ra_n\)).

Montrez que la somme partielle \(S_n\) d'une série arithmétique de raison \(r\) est égale à \[(n+1)(a_0+\frac{nr}{2}).\]

Montrez que la somme partielle \(S_n\) d'une série géométrique de raison \(r\) est égale à \[a_0\left(\frac{r^{n+1}-1}{r-1}\right).\]

Soit \(a\) un nombre réel tel que \(|a|<1\). Démontrez que la série de terme général \(a^n\) est convergente et que sa limite est égale à \begin{equation} \sum_{i=0}^\infty a^i=\frac{1}{1-a}. \end{equation}
Vous souhaitez emprunter un capital de \(C\) euros à votre banque qui vous propose un taux annuel de \(T\%\) et un remboursement en \(n\) mensualités fixes de \(m\) euros.

(1) En notant \(t:=\frac{T}{12}\) le taux mensuel, montrez que la mensualité \(m\) à payer est donnée par l'équa­tion \begin{equation} \label{eq:teg} m=Ct\left[1-\left(1+t\right)^{-n}\right]. \end{equation}

Indication : Votre \(i\)ème mensualité \(m_i:=m\) (constante) est constituée d'un intérêt \(I_i\), qui sert à payer la banque, et d'un capital \(C_i\) qui permet de rembourser votre emprunt : \[m_i = m = I_i+C_i.\] Un mois après que le capital \(C_0:=C\) vous a été fourni, l'intérêt à régler à la banque est donc \(I_1:=\frac{t}{12}C_0\), ainsi \(C_1:=C_0-I_1\) est le capital qui vous reste à rembourser. Le processus se répète chaque mois sur un nouveau capital restant dû jusqu'à ce qu'il soit entièrement remboursé à l'issue des \(n\) mois, soit \(C_n=0\).

Pour obtenir ce prêt, la banque vous facture des frais de dossier et de caution d'un montant de \(F\) euros et vous propose une assurance décès-invalidité au taux annuel de \(a\%\) sur le capital initial, c'est-à-dire que vous devrez payer mensuellement \(\frac{a C}{12}\) euros pour cette assurance.

(2) Estimez le Taux Effectif Global (teg) \(T_e\) de ce prêt qui intègre l'ensemble des frais liés au crédit sous forme de taux annuel unique. Indication : considérez que le montant mensuel à rembourser est \(m_r:=m+\frac{a C}{12}\) et que le capital réellement prêté est \(C_r:=C-F\). Reprenez la formule \((\ref{eq:teg})\) de la question (1) et exprimez \(t\) en fonction des autres paramètres grâce à un développement limité à l'ordre 3 de \((1+t)^{-n}\) au voisinage de \(0\).

(3) Vous souhaitez emprunter 180.000€ pour l'achat de votre appartement avec un remboursement sur 10 ans. La banque \(A\) vous propose un taux de crédit annuel de 1,40%, des frais de dossier de 700€ et une assurance au taux de 0,33%, la banque \(B\) un taux de crédit annuel de 1,15%, des frais de dossier de 1000€ et une assurance au taux de 0,50%. Dans quelle banque avez-vous intérêt à prendre votre crédit ?