Mémento mathématique

Ce cours ne demande presque aucun prérequis mathématique, mais il s'appuie sans cesse sur une petite boîte à outils: les puissances de deux, le logarithme en base 2, deux ou trois sommes, le dénombrement élémentaire, l'arithmétique modulaire et un minimum de probabilités. Les chapitres renvoient ici plutôt que de les redémontrer à chaque fois. Cette annexe est une fiche de référence travaillée: chaque notion y est définie, la plupart sont démontrées, et chaque section se termine par des exemples entièrement calculés. Tous les nombres imprimés ci-dessous ont été recalculés en Python avec des entiers exacts.

Lisez-la une fois en entier avant le chapitre 2, puis revenez-y ponctuellement: le chapitre 3 a besoin de ${\log }_2(n!)$, le chapitre 6 de l'espérance, le chapitre 9 de l'inverse modulaire.

Puissances de deux et changement de base

Les puissances de deux à connaître

Un bit vaut 0 ou 1; $k$ bits forment donc $2^k$ configurations distinctes. Toute question du type «combien de valeurs puis-je coder?» revient à lire la ligne correspondante de ce tableau.

Trois repères suffisent à reconstruire tout le reste: $2^{10}\approx 10^3$, $2^{32}\approx 4,3\cdot 10^9$ («quatre milliards», la taille de l'espace IPv4), $2^{64}\approx 1,8\cdot 10^{19}$ («dix-huit milliards de milliards»). Une quatrième vaut d'être citée pour la cryptographie: , soit à peu près le nombre d'atomes de l'univers observable, de l'ordre de .

Le réflexe «mille pour $2^{10}$», et son erreur

Comme $2^{10}=1024$, on approche volontiers $2^{10}$ par $10^3$. L'approximation est excellente une fois, mais elle se compose: chaque tranche de dix bits multiplie l'écart par $1,024$.

Formellement, $2^{10m}/10^{3m}=1,024^m$. C'est exactement l'écart entre les préfixes binaires et décimaux du chapitre 1 (Kio contre ko, Gio contre Go): la confusion des deux familles produit une erreur de 2,4 % au kilo et de 7,4 % au giga, pas une erreur constante.

Numération positionnelle

Deux conséquences immédiates et constamment utilisées.

Le nombre de chiffres. Pour $N\ge 1$, le nombre de chiffres en base $b$ vaut $\lfloor {\log }_{b}N\rfloor +1$; le nombre de bits d'un entier $N\ge 1$ est donc $\lfloor {\log }_{2}N\rfloor +1$, ce qui s'écrit aussi . Réciproquement, coder valeurs distinctes demande bits.

Le passage d'une base à l'autre. De la base 10 vers la base $b$, on divise répétitivement par $b$ et l'on lit les restes de bas en haut. Vers la base 10, on évalue le polynôme, de préférence par la méthode de Horner. Entre 2 et 16, aucun calcul n'est nécessaire: $16=2^4$, donc un chiffre hexadécimal vaut exactement quatre bits, et l'on convertit en regroupant les bits par paquets de quatre depuis la droite.

Logarithmes

Définition et identités

Le cours emploie ${\log }_2$ presque partout — parce que l'unité d'information est le bit et que les algorithmes divisent par deux — et $\ln ={\log }_{\mathrm{e}}$ pour les calculs continus. Conformément à la notation du cours, la base est toujours écrite — ${\log }_2$, jamais $\lg$ — avec : à l'intérieur d'une classe de complexité on l'omet, et l'on écrit ou . Le théorème A.1 ci-dessous dit pourquoi: changer de base ne fait que multiplier par une constante, et une classe de complexité ne voit pas les constantes. Partout où vous comptez des bits ou des comparaisons réelles, la base se réécrit.

De $b^{u+v}=b^u{b}^v$ découlent les trois identités dont on se sert sans arrêt:

La première est la propriété caractéristique: c'est elle qui fait apparaître le logarithme au chapitre 6, où l'on exige que l'information de deux événements indépendants soit la somme de leurs informations. La troisième est celle qui sert le plus en complexité: elle transforme un produit de $n$ facteurs en une somme de $n$ termes, et c'est ainsi que ${\log }_2(n!)$ devient calculable.

Démonstration. Posons $y={\log }_{b}x$, de sorte que $b^y=x$. En prenant le logarithme en base $a$ des deux membres et en utilisant ${\log }_a(b^y)=y{\log }_{a}b$, il vient , d'où le résultat puisque .

Changer de base ne fait donc que multiplier par une constante. C'est pour cette raison que la notation asymptotique ne précise pas la base: ${\log }_{2}n$, $\ln n$ et ${\log }_{10}n$ sont tous $\Theta (\log n)$. En revanche, dès qu'on compte des bits ou des comparaisons, la constante compte et la base doit être écrite.

«Diviser par deux jusqu'à un»

L'intuition à retenir est la suivante: ${\log }_{2}n$ est le nombre de fois où l'on peut diviser $n$ par deux avant d'atteindre 1. C'est la lecture algorithmique du logarithme, et elle explique d'un coup la recherche dichotomique, le tri fusion et la hauteur d'un arbre binaire équilibré.

Le nombre de divisions entières menant de $n$ à 1 vaut exactement $\lfloor {\log }_{2}n\rfloor$. Attention à ne pas le confondre avec le nombre de comparaisons d'une recherche dichotomique, qui vaut $\lceil {\log }_2(n+1)\rceil$ dans le pire cas — 20 pour un million, et non 19. La différence d'une unité entre plancher et plafond n'est pas une coquetterie: elle décide si un tableau de $2^{20}$ éléments demande 20 ou 21 comparaisons.

La figure porte une leçon qu'aucun tableau ne fait voir. Sur des axes logarithmiques, $n$ et $n^2$ deviennent des droites de pentes 1 et 2, parce que ce sont des lois de puissance. Le logarithme, lui, s'aplatit jusqu'à devenir presque horizontal: trois décades d'entrée ne le font passer que de 1 à 10. Quant à $n{\log }_{2}n$, c'est la seule des quatre courbes qui plie — précisément parce que ce n'est pas une loi de puissance. Elle suit $n$ à un facteur ${\log }_{2}n$ près, soit un facteur 10 seulement à , alors que l'écart qui l'y sépare de atteint déjà un facteur 100.

Sommes usuelles

La somme des premiers entiers

Démonstration. Écrivons la somme $S$ deux fois, la seconde à l'envers, et additionnons colonne par colonne:

D'où $S=n(n+1)/2$. $\square$

Le chapitre 2 utilise la variante ${\sum }_{k=1}^{n-1}k=n(n-1)/2$: c'est le nombre de comparaisons du tri par sélection, et aussi le nombre de paires d'un ensemble de $n$ éléments — d'où les $499500$ clefs symétriques de mille personnes au chapitre 9. Retenez que cette somme est quadratique: doubler $n$ quadruple le travail.

La somme géométrique

Démonstration. Posons $S={\sum }_{k=0}^n{q}^k$. Alors $qS={\sum }_{k=1}^{n+1}{q}^k$, et la différence télescope: tous les termes de à s'annulent et il reste , soit . Comme , on divise. Pour la somme infinie, lorsque , et le quotient tend vers .

Le cas $q=2$ est celui qui revient partout:

Autrement dit, la somme de toutes les puissances de deux inférieures à $2^n$ vaut $2^n-1$: elle est dominée par son dernier terme, qu'elle dépasse à peine. C'est ce qui rend un arbre binaire complet de hauteur $h$ porteur de $2^{h+1}-1$ nœuds, dont plus de la moitié sont des feuilles, et c'est aussi la raison pour laquelle le tri fusion du chapitre 3 fait un travail dominé par son niveau le plus bas.

La somme harmonique

Elle n'a pas de forme close, mais sa croissance est connue: $H_n=\ln n+\gamma +\frac{1}{2n}+O\left(\frac{1}{n^2}\right)$, où est la constante d'Euler–Mascheroni. En particulier : , donc très lentement, mais elle diverge. Elle apparaît dans le coût moyen de plusieurs algorithmes — notamment le tri rapide et la recherche du maximum — et dans le problème du collectionneur de vignettes.

Dénombrement

Le principe multiplicatif

C'est le seul principe dont le cours ait vraiment besoin; tout le reste en découle. Un mot de $k$ symboles sur un alphabet de $q$ lettres: $q^k$ possibilités. Un mot de $k$ bits: $2^k$. Un code PIN à quatre chiffres: $10^4=10000$.

Arrangements, permutations, combinaisons

On tire $k$ éléments parmi $n$ distincts. Quatre cas, dont trois servent ici.

Le coefficient binomial $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, lu «$k$ parmi $n$», compte les parties à $k$ éléments d'un ensemble à $n$ éléments. Il vérifie $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$, la relation de Pascal , et surtout

puisque les parties à $k$ éléments, réunies pour tous les $k$, forment toutes les parties d'un ensemble à $n$ éléments — et qu'il y en a $2^n$, une par mot de $n$ bits. Le chapitre 8 s'en sert pour compter les mots à distance donnée d'un mot de code.

Démonstration. Développer $(a+b{)}^n=(a+b)(a+b)\cdots (a+b)$ revient à choisir, dans chacun des $n$ facteurs, soit $a$ soit $b$, puis à sommer tous les produits obtenus. Un produit vaut exactement lorsqu'on a choisi dans facteurs, ce qui peut se faire de façons.

Le choix $a=b=1$ redonne ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$; le choix , donne pour .

La factorielle et la formule de Stirling

La factorielle croît plus vite que toute exponentielle: $10!=3628800$ et $20!\approx 2,43\cdot 10^{18}$. La formule de Stirling en donne la taille.

Ce résultat est admis: sa démonstration demande l'analyse asymptotique d'une intégrale, hors du programme de première année. Il est cité ici parce que la borne inférieure du tri par comparaisons du chapitre 3 en dépend: tout tri par comparaisons effectue au moins $\lceil {\log }_2(n!)\rceil$ comparaisons dans le pire cas, et Stirling montre que cette borne vaut $n{\log }_{2}n$ à un terme linéaire près. Le tri fusion, en $\Theta (n{\log }_{2}n)$, est donc optimal pour l'ordre de grandeur.

Notation asymptotique: fiche de référence

Ces trois notations sont définies et discutées au chapitre 2, avec leurs pièges; cette section n'en est que le rappel compact. Soient $f,g:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$.

Les deux quantificateurs existentiels sont toute la subtilité: $c$ autorise à ignorer les facteurs constants, $n_0$ à ignorer les petites tailles. Une affirmation en $O$ ne dit donc rien du temps d'exécution sur une entrée donnée. Le théorème 2.3 ajoute deux caractérisations commodes: $f=\Theta (g)$ équivaut à «$f=O(g)$ et $f=\Omega (g)$», et il suffit que tende vers une limite avec pour conclure .

Hiérarchie de croissance. Chaque terme est négligeable devant le suivant:

Règles de calcul. Si $f_1=O(g_1)$ et $f_2=O(g_2)$, alors

et les mêmes règles valent pour $\Omega$ et $\Theta$. S'y ajoutent la transitivité ($f=O(g)$ et $g=O(h)$ donnent $f=O(h)$), l'absorption des constantes ($O(cf)=O(f)$ pour fixé), l'indifférence à la base du logarithme (), et la règle des polynômes: un polynôme de degré à coefficient dominant positif est .

Arithmétique modulaire

Congruences

La congruence modulo $n$ est une relation d'équivalence, et elle est compatible avec l'addition et la multiplication: si $a\equiv a^{\prime }$ et $b\equiv b^{\prime }$ modulo $n$, alors

C'est la propriété décisive pour le calcul: on peut réduire modulo $n$ après chaque opération sans changer le résultat final. Calculer $65^{17}\mathrm{mod}3233$ ne demande donc jamais de manipuler un nombre supérieur à $3232^2$, alors que $65^{17}$ compte 31 chiffres décimaux.

Diviseur commun et algorithme d'Euclide

Le plus grand commun diviseur $\gcd (a,b)$ se calcule sans factoriser, par l'algorithme d'Euclide: on remplace $(a,b)$ par $(b,a\mathrm{mod}b)$ jusqu'à ce que le second terme soit nul; le premier est alors le pgcd. Il termine parce que le second terme décroît strictement, et le nombre de divisions est $O(\log \min (a,b))$.

L'algorithme d'Euclide étendu produit en plus les coefficients de Bézout, c'est-à-dire deux entiers $u,v$ tels que

Démonstration. Si $\gcd (a,n)=1$, Bézout fournit $u,v$ avec $au+nv=1$; en réduisant modulo $n$ le terme $nv$ disparaît et il reste $au\equiv 1$. Réciproquement, si , il existe tel que , donc ; tout diviseur commun de et divise alors 1, donc . Unicité: si , alors .

Exponentiation rapide

Pour calculer $a^k\mathrm{mod}n$, on écrit $k$ en binaire et l'on parcourt ses bits du plus fort au plus faible: à chaque bit on élève au carré, et l'on multiplie en plus par $a$ lorsque le bit vaut 1, en réduisant modulo $n$ après chaque produit. Le nombre de multiplications modulaires est au plus $2{\log }_{2}k$, contre pour la méthode naïve: c'est la différence entre impossible et instantané dès que a quelques centaines de bits.

Fermat et Euler

Les démonstrations sont au chapitre 9, qui en a besoin pour établir la correction de RSA. Deux valeurs de $\phi$ suffisent ici: $\phi (p)=p-1$ si $p$ est premier, et $\phi (pq)=(p-1)(q-1)$ si $p\ne q$ sont premiers. Ainsi .

L'usage pratique de ces théorèmes est la réduction de l'exposant: puisque $a^{\phi (n)}\equiv 1$, on peut remplacer l'exposant $k$ par $k\mathrm{mod}\phi (n)$. Par exemple $7^{222}\mathrm{mod}11$: comme 11 est premier, et , donc — deux lignes au lieu de 221 multiplications. Vérifié en Python.

Probabilités élémentaires

Les chapitres 6 et 8 n'ont besoin que du strict minimum, rappelé ici. Pour la théorie — variables continues, lois usuelles, convergence, estimation — reportez-vous au cours de Probabilités et statistique, qui en fait un développement complet; les notations $\mathbb{P}$ et $\mathbb{E}$ sont les siennes.

Deux propriétés servent constamment. La linéarité, $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$ et $\mathbb{E}[cX]=c\mathbb{E}[X]$, vaut toujours, même si $X$ et $Y$ ne sont pas indépendantes — c'est ce qui rend tant de calculs de coût moyen faciles. Et l'entropie du chapitre 6 n'est rien d'autre qu'une espérance: , l'espérance de la quantité d'information.

L'indépendance est une hypothèse de modèle, pas une propriété que l'on constate: le canal binaire symétrique du chapitre 8 suppose que les erreurs frappent chaque bit indépendamment, et le chapitre dit explicitement que ce modèle ne décrit pas une rayure de disque, qui produit une rafale d'erreurs voisines.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• R. L. Graham, D. E. Knuth et O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2e éd., Addison-Wesley. La référence sur les sommes, les coefficients binomiaux et les approximations asymptotiques; les chapitres 2, 5 et 9 recouvrent exactement cette annexe.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest et C. Stein, Introduction to Algorithms, 4e éd., MIT Press. Les annexes A (sommes) et C (dénombrement et probabilités) ainsi que le chapitre 3 (notation asymptotique) sont écrits pour ce même usage.
• K. H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. Chapitres sur les entiers et l'arithmétique modulaire, avec l'algorithme d'Euclide étendu et les théorèmes de Fermat et d'Euler entièrement traités.
• D. J. C. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge University Press (disponible librement). Le chapitre 2 rappelle probabilités, espérance et logarithmes exactement au niveau dont les chapitres 6 à 8 ont besoin.
• Cours de Probabilités et statistique de cette collection, pour tout ce que la dernière section ne fait qu'esquisser: variables continues, lois usuelles, variance, convergence et estimation.