Pense-bête

Quelques unités mesurant la quantité d’informations en informatique

Notions mathématiques

Rappel concernant les mathématiques élémentaires
– $e \approx 2.7182818284590451$ et $\pi \approx 3.1415926535897931$
– Si $i$ alors $a^i= a \times a \times \cdots \times a$ où la multiplication est répétée $i$ fois.
– Le logarithme en base $b$ satisfait $\log_b b^x = x$.
– On a $\log (ab) = \log a + \log b$.
– On a $\log (a/b) = \log a - \log b$.
– On a aussi $\log_a x = \log_b x / \log_b a$.
– La somme d’une séquence est notée $\sum_{k=1}^n x_k= x_1+x_2+\cdots+x_n$.
– Le produit d’une séquence est noté $\prod_{k=1}^n x_k = x_1 x_2 \cdots x_n$.
– Le logarithme d’un produit est une somme : $\log \prod_{k=1}^n x_k = \sum_{k=1}^n \log x_k$.
– L’exponentielle d’une somme est un produit : $a^{ \sum_{k=1}^n x_k} = \prod_{k=1}^n a^{x_k}$.
– La fonction $f$ est monotone croissante (respectivement décroissante) si $f(x) \geq f(y)$ lorsque $x \geq y$.
– Le symbole $\infty$ est l’infini. Nous savons que $\infty+\infty = \infty$, mais $\infty-\infty$ n’est pas défini.
– Le logarithme est défini pour les nombres supérieurs à zéro, avec la convention que $\log 0 = -\infty$. C’est une fonction monotone croissante.
– La factorielle $k !$ est définie par $k \times (k-1) \times \cdots \times 1$. La factorielle de 1 est 1 ($1 !=1$).
– Un élément $x$ appartient à un ensemble $D$ : $x \in D$.
– Si $x$ est un nombre, alors $\vert x \vert$ est sa valeur absolue : $\vert x \vert = x$ si $x \geq 0 $ et $\vert x \vert = -x$ si $x<0$.
– Si $D$ est un ensemble, alors $\vert D \vert$ est la cardinalité de l’ensemble (le nombre d’éléments).
– L’ensemble vide est noté $\oslash$.
– En logique booléenne, VRAI ET VRAI est VRAI, VRAI ET FAUX est FAUX, FAUX ET VRAI est FAUX, FAUX ET FAUX est FAUX. VRAI OU VRAI est VRAI, VRAI OU FAUX est VRAI, FAUX OU VRAI est VRAI, FAUX OU FAUX est FAUX.

Vecteurs et matrices

Ensemble

L’ensemble des nombres réels (incluant les nombres à virgule flottante) est noté $\mathbb{R}$.
L’ensemble des entiers est noté $\mathbb{Z}$.

Valeur absolue

Étant donné $x \in \mathbb{R}$ ou $x \in \mathbb{Z}$, alors $\vert x \vert = x$ si $x \geq 0$ et $\vert x \vert = -x$ si $x < 0$.

Nombres complexes

Les nombres complexes sont notés $z= x+iy$, avec $x,y\in \mathbb{R}$, et $\vert z \vert = \sqrt{x^2+y^2}$.

Vecteur

Un vecteur est un tableau à une dimension. Le nombre de cellules du tableau est le nombre de composantes du vecteur.

Exemple :

$V = \left [ \begin{array}{l}1 \\ 2 \\ 1\end{array} \right ]. $

On note $V_{i}$ la $i^{\textrm{e}}$ composante du vecteur $V$. Dans notre exemple, $V_1=1$.

Matrice

Une matrice est un tableau à deux dimensions ayant $m$ rangées et $n$ colonnes comme dans cet exemple :

$\left [ \begin{array}{ll}1 & 3 \\ 2 & 5 \\ 1 & 5\end{array} \right ]. $

On note $M_{i,j}$ la valeur se situant à la $i^{\textrm{e}}$ rangée et à la $j^{\textrm{e}}$ colonne de la matrice $M$. Dans l’exemple précédent, $M_{2,1}$ vaut 2 alors que $M_{1,2}$ vaut 3.

Multiplication d’un vecteur ou d’une matrice par un scalaire

Si les composantes du vecteur ou de la matrice sont des entiers ou des nombres réels, on peut les multiplier par un entier ou un nombre réel (un scalaire).
La multiplication se fait alors sur chaque composante comme dans cet exemple :

$2 \left [ \begin{array}{l}1 \\ 2 \\ 1\end{array} \right ] = \left [ \begin{array}{l}2 \\ 4 \\ 2\end{array} \right ].$

Multiplication de vecteurs et de matrices

Étant donné une matrice $M$ ayant $m$ rangées et $n$ colonnes et un vecteur $V$ ayant $n$ composantes, la multiplication de $M$ et de $V$, notée $M V$, est un vecteur $R$ ayant $m$ composantes et défini comme :

$R_i = \sum_{k=1,\ldots,n} M_{i,k} V_k$

Voici un exemple :

$\left [ \begin{array}{ll} 1 & 3\\ 1 & 2 \\ 3 & 1 \end{array}\right ] \left [ \begin{array}{l} 1 \\ 1 \end{array}\right] = \left [ \begin{array}{l} 4 \\ 3 \\ 4 \end{array}\right]. $

Multiplication de matrices avec d’autres matrices

Étant donné une matrice $M$ ayant $m$ rangées et $n$ colonnes et une autre matrice $P$ ayant $n$ rangées et $r$ colonnes, la multiplication de $M$ et de $P$, notée $M P$ est un vecteur $R$ ayant $m$ rangées et $r$ colonnes définies comme :

$R_{i,j} = \sum_{k=1,\ldots,n} M_{i,k} P_{k,j}$

Voici un exemple :

$\left [ \begin{array}{ll} 1 & 3\\ 1 & 2 \\ 3 & 1 \end{array}\right ] \left [ \begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right] = \left [ \begin{array}{ll} 4 & 1\\ 3 & 1 \\ 4 & 3 \end{array}\right]. $

Transposée d’une matrice

La transposée d’une matrice $M$ est notée $M^t$ et est tout simplement une réécriture de la matrice où les colonnes deviennent des rangées et vice versa : $M_{i,j}=M^t_{j,i}$. On peut montrer que $(AB)^t=B^tA^t$.

Matrice normale

Une matrice carrée est dite normale si elle commute avec sa transposée : $MM^t= M^tM$.

Matrice diagonale et matrice identité

Une matrice carrée est diagonale si seules les composantes sur la diagonale sont différentes de zéro : $M_{i,j}=0$ lorsque $i\neqj$. (le différent de j ne s’affiche pas...)
Une matrice diagonale est égale à sa transposée : $M = M^t$. Une matrice diagonale est nécessairement normale.

Lorsque la matrice est diagonale et que toutes les valeurs différentes de zéro sont égales à 1, on dit qu’il s’agit d’une matrice identité (notée $I$).
La multiplication d’une matrice par la matrice identité la laisse inchangée : $M I = I M$.

Matrices inverses

Si $M$ et $P$ sont deux matrices carrées telles que $MP= I$, alors $PM=I$ ; on dit que les matrices sont inverses l’une de l’autre et on note $M= P^{-1}$ ainsi que $P=M^{-1}$. Cependant, toutes les matrices n’ont pas un inverse.

Une matrice qui n’est pas carrée peut néanmoins avoir un inverse par la gauche ou par la droite : si $M$ n’est pas carrée, il peut exister $P$
tel que $MP=I$ ou $PM=I$ (mais pas les deux).

On utilise souvent la matrice inverse pour résoudre des équations linéaires. Ainsi, étant donné un matrice $A$ et un vecteur $b$, si on a $Ax=b$, alors $x= A^{-1}b$. Cependant, il est possible que le problème $Ax=b$ ait une solution même si $A$ n’est pas inversible.

Toutes les matrices, même les matrices qui ne sont pas carrées ou qui n’ont pas d’inverse, ont une matrice pseudo-inverse qui permet de trouver la meilleure solution (au sens des moindres carrés) pour l’équation $Ax=b$. On peut calculer la matrice pseudo-inverse en utilisant la décomposition en valeurs singulières.

Matrice diagonalisable

Une matrice carrée $M$ est diagonalisable s’il existe une matrice $P$ telle que $P M P^{-1}$ est une matrice diagonale. Toutes les matrices normales sont diagonalisables, mais toutes les matrices ne sont pas diagonalisables. Les valeurs trouvées sur la diagonale sont appelées les valeurs propres de la matrice et sont toujours les mêmes, même si le choix de $P$ n’est pas toujours unique.

Normes

La norme d’un vecteur ou d’une matrice $V$ est « une mesure de longueur » notée $\Vert V \Vert $.

La norme euclidienne est la racine carrée de la somme des composantes au carré : $\Vert V \Vert = \sqrt{ \sum_i \vert V_i \vert^2}$. Étant donné un vecteur $V=(a,b)$, la norme est $\Vert V \Vert = \sqrt{a^2+b^2}$. À moins de mention contraire, nous utilisons toujours la norme euclidienne.

Dans le cas d’une matrice, la norme euclidienne prend le nom de la norme de Frobenius :

$\Vert M \Vert = \sqrt{\sum_{i,j} \vert M_{i,j} \vert^2 }.$

Voici un exemple :

$\left \Vert \begin{array}{ll} 1 & 0\\ 1 & 1 \\ 3 & 2 \end{array}\right \Vert = \sqrt{1+1+1+3^2+2^2}=4. $

Produit scalaire

Le produit scalaire entre deux vecteurs est la somme du produit de leurs composantes une à une :

$V\cdot W = \sum_i V_i W_i$

Pour pouvoir calculer le produit scalaire de deux vecteurs, il faut qu’ils aient le même nombre de composantes.

Voici un exemple :

$\left [ \begin{array}{l} 1 \\ 1 \\ 3 \end{array}\right ] \cdot \left [ \begin{array}{l} 1 \\ 1 \\ 1 \end{array}\right] = 5. $

On peut vérifier que $\Vert V \Vert^2 =V\cdot V$. De plus, le vecteur $\frac{V}{\Vert V \Vert}$ est unitaire, c’est-à-dire qu’il a une norme de 1 : $\Vert\frac{V}{\Vert V \Vert}\Vert=1$.

Le cosinus entre deux vecteurs est donné par

$\cos \theta = \frac{V\cdot W}{\Vert V \Vert \Vert W \Vert}.$

Vecteurs orthogonaux

Les vecteurs $V$, $W$ et $Z$ sont orthogonaux si le produit scalaire entre les vecteurs est nul : $V\cdot W = 0$, $V \cdot Z=0$ et $W \cdot Z = 0$. On dit qu’ils sont orthonormaux si en plus d’être orthogonaux, leurs normes sont unitaires : $\Vert V \Vert^2= V\cdot V = 1$, $\Vert W \Vert^2= W \cdot W=1$ et $\Vert Z \Vert^2=Z \cdot Z = 1$.

Matrice orthonormale

Les colonnes d’une matrice peuvent être vues comme des vecteurs. Si l’ensemble de ces vecteurs sont orthogonaux, alors la matrice est orthonormale [1]. Une matrice orthonormale satisfait $M^tM=I$, c’est-à-dire
que sa transposée est son inverse par la droite. Une matrice orthonormale n’est pas nécessairement carrée.

Attention de ne pas confondre les matrices orthonormales avec les matrices normales ! Par exemple, une matrice qui n’est pas carrée ne peut être normale, mais elle peut être orthonormale. Par contre, une matrice carrée orthonormale est nécessairement normale.

Décomposition en valeurs singulières

Toutes les matrices $M$ peuvent s’écrire sous la forme $M=USV^t$ où $U$ et $V$ sont orthonormales, et $S$ est une matrice diagonale [2].

Notation grand-O

Définition. Soit $f(n)$ le nombre d’opérations effectuées par un algorithme ; on dit que le temps mis par l’algorithme est $O(g(n))$ (ou bien $f(n) \in O(g(n))$) s’il existe deux nombres $M$ et $n_0$ tels que $f(n) \leq M g(n)$ pour $n>n_0$.

Les grandes classes importantes pour ce cours sont (de la plus rapide à la plus lente) : $O(1) \subset O(n) \subset O(n \log n) \subset O(n^2)$.

Probabilités

La moyenne

La moyenne d’un vecteur $V$ est la somme de ses composantes divisée par le nombre de composantes ; elle est notée $\overline{V}$.

La corrélation

Étant donné deux vecteurs de même taille, on peut calculer la corrélation de Pearson entre les deux vecteurs comme étant :

$\mathrm{Pearson}(V,W)= \frac{ (V-\overline{V})\cdot(W-\overline{W}) }{ \Vert V-\overline{V} \Vert \Vert W-\overline{W} \Vert }$

La corrélation de Pearson est une valeur entre -1 et 1. Le carré de la corrélation de Pearson donne le pourcentage de corrélation.

La fréquence

La fréquence est le nombre de fois qu’une instance ou objet se manifeste. Par exemple, la fréquence du mot rue dans le journal est le nombre de fois que le mot rue est utilisé dans les textes du journal.

La distribution

Dans le cadre de ce cours, la distribution est une fonction qui, pour chaque instance possible, nous donne la probabilité correspondante. La somme de toutes les probabilités doit être 1.

Le rang

Étant donné une distribution, l’instance la plus probable occupe le premier rang, la deuxième instance la plus probable occupe le second rang et ainsi de suite.

Les lois de Zipf et Mandelbrot : origine et définition

Selon la loi de Zipf, si $n$ est le $n^{\mathrm{e}}$ mot le plus fréquent dans un texte, alors il doit avoir la fréquence $f(n)=\frac{K}{n}$ où $K$ est une constante (indépendante de $n$).

La théorie de l’information

Si un mot $x$ apparaît $f(x)$ fois dans un texte de longueur $n$, la probabilité de choisir le mot $x$ par hasard dans le texte est $p(x)=f(x)/n$. On dit que la quantité d’informations associée au mot $x$ est de $-\log p(x)$. Ainsi, si $p(x)$ est très petit, la quantité est très grande alors que si $p(x)$ est très grand, la quantité est presque nulle. La moyenne de la quantité d’informations dans les mots d’un texte est donnée par $-\sum_x p(x) \log p(x)$ et la quantité d’informations dans un texte est mesurée comme étant $-\sum_x p(x) \log p(x) n$.

La probabilité

La probabilité est toujours une valeur entre 0 (un événement impossible) et 1 (un événement certain).

On note la probabilité que l’événement $A$ se produise par $P(A)$ et la probabilité qu’il ne se produise pas, par $P(\bar A)$. Nous avons $P(A)+P(\bar A)=1$.

$P(A\textrm{ ET }B)=P(A \cap B)$ est la probabilité que $A$ et $B$ se produisent.

Les événements $A$ et $B$ sont indépendants si et seulement si $P(A\textrm{ ET }B)=P(A \cap B)=P(A)P(B)$.

La probabilité conditionnelle et la vraisemblance

La probabilité conditionnelle est la probabilité étant donné un fait connu. On note la probabilité conditionnelle avec la barre verticale, comme ceci ($P(A|B)$), probabilité de $A$ sachant $B$.

Formellement, on définit la probabilité conditionnelle ($P(A|B)$) comme
$P(A|B)=P(A\textrm{ ET }B) / P(B)$.

Nous avons $P(A|B)+P(\bar A|B)=1$. En général, $P(A|B)\neq P(B|A)$ ; cependant, on peut calculer l’une des valeurs à partir de l’autre en utilisant le théorème de Bayes.

Le théorème de Bayes stipule que $P(A|B) = \frac{P(B | A) P(A)}{P(B)}$.

La vraisemblance est définie comme $L(B|A)=P(A|B)$.