Rappels mathématiques · Algorithmes

Analyser un algorithme, c'est presque toujours ramener son coût à l'une d'une petite dizaine de sommes, puis comparer le résultat à une échelle de croissances. Cette annexe rassemble ces sommes, ces échelles et les trois ou quatre techniques de preuve qui les accompagnent — la récurrence, l'invariant de boucle, la linéarité de l'espérance, le déroulage d'une récurrence. Rien ici n'est propre à l'algorithmique: tout se trouve dans un cours de mathématiques discrètes ou d'analyse. Ce qui est propre à ce cours, c'est la sélection: on n'a gardé que ce que les onze chapitres utilisent effectivement, et chaque énoncé est accompagné de l'endroit où il sert.

Une annexe se consulte, elle ne se lit pas d'un bout à l'autre. Les démonstrations sont données quand elles sont courtes et instructives — celle de la somme arithmétique tient en une figure, celle de la linéarité de l'espérance en trois lignes — et explicitement admises, avec la raison, quand elles relèvent franchement d'un autre cours: la formule de Stirling et la constante $γ$ d'Euler-Mascheroni demandent de l'analyse, pas de l'algorithmique.

Objectifs

Cette annexe vous permet de:

retrouver et démontrer les sommes usuelles — arithmétique, géométrique, $\sum k x^{k}$ — plutôt que de les recopier;
manipuler les nombres harmoniques et savoir que $H_{n} = ln n + γ + O (1/ n)$ , la quantité qui apparaît dans le tri rapide et dans les tables de hachage;
utiliser les logarithmes sans faute: changement de base, , et l'identité qui gouverne le théorème maître;

Sommes usuelles

La somme arithmétique

Démonstration. Écrivons la somme deux fois, une fois dans l'ordre croissant et une fois dans l'ordre décroissant, et additionnons terme à terme:

S (n) = 1 + 2 + \dots + (n - 1) + n S (n) = n + (n - 1) + \dots + 2 + 1

Chacune des $n$ colonnes ainsi formées vaut $n + 1$ , donc $2 S (n) = n (n + 1)$ . $□$

La figure A.1 est la même démonstration, dessinée: l'escalier des $n$ colonnes et son complément remplissent exactement un rectangle de $n$ colonnes sur $n + 1$ lignes.

La conséquence asymptotique est celle que l'on utilise sans arrêt: $\sum_{k = 1}^{n} k \in Θ (n^{2})$ . C'est elle qui donne le pire des cas du tri par insertion et du tri par sélection au chapitre 3, et le coût des $n$ insertions dans un arbre binaire de recherche dégénéré au chapitre 5.

Démonstration. La méthode vaut pour toutes les sommes de puissances, alors autant l'apprendre ici. Partons de l'identité $(k + 1)^{3} - k^{3} = 3 k^{2} + 3 k + 1$ et sommons-la pour $k$ de 1 à . À gauche, la somme : tous les termes intermédiaires s'annulent et il reste . À droite, on reconnaît trois sommes:

(n + 1)^{3} - 1 = 3 k = 1 \sum n k^{2} + 3 \cdot \frac{n ( n + 1 )}{2} + n .

On isole la somme cherchée, on développe et on factorise; il vient (A.2). $□$

Plus généralement, $\sum_{k = 1}^{n} k^{d} \in Θ (n^{d + 1})$ pour tout entier $d \geq 0$ : la majoration $\sum k^{d} \leq n \cdot n^{d}$ est immédiate, et la minoration s'obtient en ne gardant que la seconde moitié des termes, chacun au moins , ce qui donne . C'est exactement l'argument de coupe en deux qui sert au chapitre 1 pour .

La somme géométrique

Démonstration. Posons $G = \sum_{k = 0}^{n} x^{k}$ . Alors $x G = \sum_{k = 1}^{n + 1} x^{k}$ , et la différence télescope:

x G - G = x^{n + 1} - x^{0} = x^{n + 1} - 1.

Comme $x \neq = 1$ , on divise par $x - 1$ et on obtient (A.3). Lorsque $∣ x ∣ < 1$ , le terme $x^{n + 1}$ tend vers 0, et la limite vaut $\frac{- 1}{x - 1} = \frac{1}{1 - x}$ .

Le cas $x = 2$ est celui de tous les arbres binaires de ce cours:

k = 0 \sum n 2^{k} = 2^{n + 1} - 1. (A.4)

Un arbre binaire de hauteur $h$ a donc au plus $2^{h + 1} - 1$ nœuds, borne atteinte par l'arbre parfait — c'est la majoration du chapitre 5. C'est aussi (A.4) qui donne le coût amorti du tableau dynamique au chapitre 4: $n$ insertions provoquent des recopies de tailles $1, 2, 4, \dots$ jusqu'à $2^{⌊ l o g_{2} n ⌋}$ , dont le total est inférieur à — donc un coût amorti constant par insertion, alors que l'insertion la plus chère coûte . Retenez aussi que est «un de moins que le terme suivant»: la somme de tous les niveaux d'un arbre parfait est presque égale à son seul dernier niveau, ce qui explique pourquoi une opération payée par feuille domine une opération payée par nœud interne.

Les sommes du type somme de k fois x puissance k

C'est la somme qui apparaît dès qu'un coût croît linéairement avec un niveau dont la population décroît géométriquement — la situation exacte de la construction d'un tas au chapitre 5 et de l'analyse en moyenne d'une liste auto-organisée au chapitre 1.

Démonstration. Notons $S_{n} = \sum_{k = 1}^{n} k 2^{- k}$ . En décalant l'indice,

\frac{S _{n}}{2} = k = 1 \sum n \frac{k}{2 ^{k + 1}} = j = 2 \sum n + 1 \frac{j - 1}{2 ^{j}} .

Soustrayons cette égalité de la précédente. Tous les termes d'indice $j$ compris entre 2 et $n$ se combinent en $\frac{j - ( j - 1 )}{2 ^{j}} = \frac{1}{2 ^{j}}$ ; restent le terme de et le terme retranché:

\frac{S _{n}}{2} = \frac{1}{2} + j = 2 \sum n \frac{1}{2 ^{j}} - \frac{n}{2 ^{n + 1}} = 1 - \frac{1}{2 ^{n}} - \frac{n}{2 ^{n + 1}},

la somme géométrique ayant été évaluée par (A.3). En multipliant par 2 on obtient (A.5), et le terme $(n + 2) / 2^{n}$ tend vers 0. La version générale s'obtient par le même calcul avec $x$ au lieu de $1/2$ , ou en dérivant terme à terme $\sum x^{k} = 1/ (1 - x)$ .

Deux valeurs utiles du cas général: $\sum_{k \geq 1} k 3^{- k} = \frac{1/3}{( 2/3 ) ^{2}} = 0, 75$ et . Plus la raison approche 1, plus la somme explose — mais elle reste finie tant que la raison est strictement inférieure à 1, et c'est tout ce dont une analyse a besoin.

Question A.1

Le tri rapide randomisé sur $n$ éléments distincts fait en moyenne $2 (n + 1) H_{n} - 4 n$ comparaisons, où $H_{n}$ est le $n$ -ième nombre harmonique. Combien de comparaisons cela fait-il en moyenne pour $n = 100$ ? Donnez le résultat à un dixième près.

Les nombres harmoniques

Démonstration. La fonction $x \mapsto 1/ x$ est décroissante sur $[1, + \infty [$ . Sur l'intervalle $[k, k + 1]$ elle reste donc sous la valeur constante $1/ k$ , d'où

\int_{k}^{k + 1} \frac{d x}{x} \leq \frac{1}{k} .

En sommant pour $k$ de 1 à $n$ , l'intégrale se recolle en $\int_{1}^{n + 1} d x / x = ln (n + 1)$ , ce qui donne la minoration. Pour la majoration, la même comparaison dans l'autre sens: sur $[k - 1, k]$ la fonction reste de , donc pour . En sommant de 2 à et en ajoutant le premier terme resté à part, il vient .

L'encadrement (A.6) suffit pour toutes les analyses de ce cours, puisqu'il donne la classe $Θ (lo g n)$ . Quand la constante compte — et elle compte pour comparer deux tris —, on dispose d'un résultat bien plus précis, que nous admettons parce qu'il relève de l'analyse et non de l'algorithmique:

H_{n} = ln n + γ + \frac{1}{2 n} + O (\frac{1}{n ^{2}}), γ = 0, 5772156649 \dots (A.7)

La constante $γ$ est dite d'Euler-Mascheroni; on ignore encore si elle est rationnelle. Le contrôle numérique de (A.7) est frappant: la quantité $n (H_{n} - ln n - γ)$ vaut $0, 4881$ pour $n = 7$ , $0, 4992$ pour et pour — elle converge bien vers , exactement comme le terme l'annonce.

$n$	1	7	10	100	1 000	1 000 000
$H_{n}$	1	2,5929	2,9290	5,1874	7,4855	14,3927
$ln n + γ$	0,5772	2,5231	2,8798	5,1824	7,4850	14,3927

Où ils apparaissent. Trois fois dans ce cours, et jamais par hasard — un $H_{n}$ signale une somme $\sum 1/ k$ , donc un événement dont la probabilité décroît comme l'inverse du rang.

Tri par insertion en moyenne (chapitre 1): le nombre moyen de comparaisons vaut $\frac{n ( n - 1 )}{4} + n - H_{n}$ , le terme $- H_{n}$ venant des passes où l'élément remonte jusqu'à l'indice 0, événement de probabilité .

Logarithmes

Convention du cours: $lo g n$ signifie $lo g_{2} n$ ; $ln n$ est le logarithme naturel; $lo g_{b} n$ s'écrit avec sa base quand la base compte.

Les règles de calcul se ramènent à trois: $lo g (ab) = lo g a + lo g b$ , $lo g (a / b) = lo g a - lo g b$ , et $lo g (a^{c}) = c lo g a$ . La troisième est celle qui sert le plus, parce qu'elle transforme une exponentielle en droite — c'est elle qui rend lisibles les figures à échelle logarithmique du chapitre 1.

Démonstration. Pour (A.8), posons $y = lo g_{b} n$ , c'est-à-dire $b^{y} = n$ . En prenant le logarithme en base $c$ des deux membres: $y lo g_{c} b = lo g_{c} n$ , d'où le quotient annoncé. Pour (A.9), prenons le logarithme en base de chaque membre. À gauche: . À droite: . Les deux expressions sont le même produit de deux réels; comme est injective sur les réels strictement positifs, les deux membres sont égaux.

La relation (A.8) dit que deux logarithmes de bases différentes ne diffèrent que d'un facteur constant: $lo g_{10} n = lo g_{2} n / lo g_{2} 10 = lo g_{2} n /3, 3219$ et . Dans une classe , un facteur constant disparaît, donc : , et c'est pourquoi ce cours écrit sans jamais préciser la base.

Le logarithme de la factorielle. Le chapitre 1 démontre que $lo g_{2} (n!) \in Θ (n lo g_{2} n)$ , avec les constantes explicites $\frac{1}{4}$ et . La formule de Stirling (section suivante) raffine cet encadrement en une égalité:

lo g_{2} (n!) = n lo g_{2} n - n lo g_{2} e + \frac{1}{2} lo g_{2} (2 π n) + O (\frac{1}{n}), (A.10)

avec $lo g_{2} e = 1, 4427$ . Pour $n = 1000$ , le membre de droite vaut $8529, 3979$ et la valeur exacte $8529, 3980$ : quatre décimales correctes. Le terme $- n lo g_{2} e$ n'est pas négligeable — il vaut —, ce qui explique que le rapport ne vaille que pour et converge très lentement vers 1.

Question A.2

Parmi ces quatre affirmations, laquelle est FAUSSE?

La récurrence et les invariants de boucle

Le principe de récurrence

Un algorithme «diviser pour régner» qui traite deux moitiés s'analyse par récurrence forte, jamais par récurrence simple: $T (n)$ dépend de $T (⌊ n /2 ⌋)$ et de $T (⌈ n /2 ⌉)$ , pas de $T (n - 1)$ . Le chapitre 3 en fait un usage typique pour majorer le nombre de comparaisons du tri fusion, et le chapitre 5 pour minorer le nombre de nœuds d'un arbre AVL de hauteur $h$ par $φ^{h}$ — cette dernière récurrence a besoin de cas de base, parce que son hérédité s'appuie sur et .

L'invariant de boucle

Ce que la récurrence est à une fonction récursive, l'invariant l'est à une boucle. C'est l'outil de correction standard de ce cours: le chapitre 2 l'emploie pour la recherche dichotomique, le chapitre 3 pour le tri par insertion et pour la fusion, le chapitre 7 pour Dijkstra et le chapitre 8 pour Kruskal.

La terminaison se démontre presque toujours par un variant: une quantité entière, positive ou nulle, qui décroît strictement à chaque tour. Une telle quantité ne peut décroître indéfiniment, donc la boucle s'arrête. Pour la recherche dichotomique, le variant est la largeur de l'intervalle de recherche; pour le tri par insertion, c'est l'indice j de la boucle interne.

Exemple A.3 · Un invariant complet: l'exponentiation rapide

L'algorithme calcule $x^{n}$ en $Θ (lo g n)$ multiplications au lieu de $n$ .

def puissance(x, n):
    """Renvoie x ** n pour n entier positif ou nul."""
    resultat, base, exposant = 1, x, n
    while exposant > 0:

Dénombrement

Deux valeurs à connaître par cœur: $(2 n) = \frac{n ( n - 1 )}{2}$ , le nombre de paires d'un ensemble à $n$ éléments — celui des paires en inversion d'une permutation au chapitre 1, celui des paires en collision d'une table de hachage au chapitre 4 —, et $(1 n) = n$ .

La formule de Pascal $(k n) = (k - 1 n - 1) + (k n - 1)$ se démontre sans calcul: on fixe un élément, on sépare les parties qui le contiennent de celles qui ne le contiennent pas. C'est le même raisonnement «avec ou sans cet objet» qui structure la table du sac à dos au chapitre 10.

Démonstration. Développons le produit $(a + b) (a + b) \dots (a + b)$ de $n$ facteurs sans rien regrouper: chaque terme du développement s'obtient en choisissant $a$ ou $b$ dans chacun des $n$ facteurs. Un terme contenant exactement $k$ fois $a$ vaut , et le nombre de façons de choisir les facteurs qui fournissent le est par définition. En regroupant les termes semblables on obtient (A.11). Le cas particulier est : le membre de gauche vaut , et le membre de droite compte toutes les parties d'un ensemble à éléments.

Nous admettons ce résultat: sa démonstration relève de l'analyse (formule d'Euler-Maclaurin ou intégrale de Wallis) et n'apporte rien à l'algorithmique. Ce qui compte ici est sa précision, que l'on peut vérifier:

$n$	5	10	20	50	100
rapport Stirling / $n!$	0,98349	0,99170	0,99584	0,99833	0,99917
borne $1/ (12 n)$	0,01667	0,00833	0,00417	0,00167	0,00083

L'erreur relative est bien inférieure à $1/ (12 n)$ pour chaque valeur, et déjà de un pour mille à $n = 100$ . En algorithmique on utilise Stirling pour trois choses: obtenir (A.10), estimer le coefficient binomial central $(n 2 n) \sim 4^{n} / π n$ — qui compte les chemins monotones d'une grille et donc, au chapitre 10, les chemins de reconstruction d'une table de programmation dynamique —, et se convaincre que croît strictement plus vite que toute exponentielle.

Probabilité et espérance sur un espace fini

Tout ce dont ce cours a besoin tient sur un espace fini: on tire une permutation au hasard, on choisit un pivot au hasard, on suppose qu'une clé tombe uniformément dans l'une de $m$ cases. Aucune théorie de la mesure n'est requise.

Les variables indicatrices

Cette égalité d'apparence triviale est l'outil le plus rentable de tout le cours. La recette est toujours la même: la quantité à estimer est un compte (des inversions, des clés dans un paquet, des comparaisons); on l'écrit comme une somme d'indicatrices, une par objet compté; et on remplace chaque espérance par une probabilité, que la symétrie donne souvent immédiatement.

Démonstration. Il suffit de le vérifier pour deux variables et un scalaire, le cas général s'en déduisant par récurrence sur $n$ . Par la définition (A.13),

E [X + Y] = ω \sum Pr [ω] (X (ω) + Y (ω))

et la somme finie se sépare en deux:

ω \sum Pr [ω] X (ω) + ω \sum Pr [ω] Y (ω) = E [X] + E [Y] .

De même $E [c X] = \sum_{ω} Pr [ω] c X (ω) = c E [X]$ . Le passage de deux à $n$ est une récurrence simple sur $n$ , le cas de base $n = 1$ étant l'homogénéité qu'on vient d'établir.

La démonstration tient en trois lignes parce qu'elle ne fait que réorganiser une somme finie — et c'est exactement pour cela qu'elle ne demande aucune indépendance. Le contraste avec l'espérance d'un produit est instructif: $E [X Y] = E [X] E [Y]$ est faux en général et n'est vrai que sous indépendance. La linéarité, elle, est gratuite.

L'espérance conditionnelle, en un paragraphe

Si $B_{1}, \dots, B_{r}$ forment une partition de $Ω$ en événements de probabilité non nulle, l'espérance de $X$ sachant $B_{i}$ est , et la loi de l'espérance totale s'écrit : elle se lit directement sur la définition (A.13) en découpant la somme selon la partition. C'est le raisonnement «on conditionne sur le rang du pivot» du tri rapide — les sont les choix possibles de pivot, chacun de probabilité — et celui de toutes les récurrences en moyenne du cours: .

Question A.3

Vous voulez calculer le nombre moyen de paires en collision dans une table de hachage. Vous écrivez ce nombre comme une somme d'indicatrices, une par paire de clés. Ces indicatrices ne sont pas indépendantes: si les clés 1 et 2 entrent en collision et que les clés 2 et 3 aussi, alors 1 et 3 entrent forcément en collision. Que pouvez-vous en conclure?

Résoudre une récurrence

Le chapitre 2 donne le théorème maître, qui traite d'un coup toutes les récurrences de la forme $T (n) = a T (n / b) + f (n)$ . Cette section rassemble les trois méthodes générales dont le théorème maître n'est qu'un raccourci — et qui restent seules disponibles dès qu'il ne s'applique pas.

Le déroulage

On remplace $T$ par sa définition, encore et encore, jusqu'à voir apparaître le motif, puis on somme.

L'arbre de récursion

C'est le déroulage, dessiné. On place à la racine le coût $f (n)$ payé hors appels récursifs, on lui donne $a$ enfants portant chacun $f (n / b)$ , et ainsi de suite jusqu'aux feuilles. Le coût total est la somme de tous les nœuds, qu'on organise par niveau: le niveau $i$ porte $a^{i}$ nœuds de coût $f (n / b^{i})$ chacun. Le nombre de niveaux est et le nombre de feuilles — l'identité (A.9), qui est ainsi la raison d'être de l'exposant critique du théorème maître.

Trois régimes sont alors possibles, et ce sont exactement les trois cas du théorème: la suite des coûts par niveau est géométrique décroissante et la racine domine; elle est géométrique croissante et les feuilles dominent; elle est constante et les $lo g_{b} n$ niveaux se valent, d'où le facteur logarithmique supplémentaire. La règle de l'encadré sur les sommes géométriques suffit à trancher.

La substitution, vérifiée par récurrence

On devine la réponse — souvent par déroulage ou par analogie — puis on la démontre par récurrence. La méthode est la seule qui donne une preuve complète avec des constantes explicites.

Exemple. Montrons que $T (n) = 2 T (n /2) + n$ avec $T (1) = 0$ vérifie $T (n) \leq n lo g_{2} n$ pour toute puissance de deux. Cas de base: . Hérédité: en supposant l'inégalité acquise pour ,

T (n) \leq 2 \cdot \frac{n}{2} lo g_{2} \frac{n}{2} + n = n (lo g_{2} n - 1) + n = n lo g_{2} n .

L'inégalité est même une égalité ici, ce que la vérification numérique confirme jusqu'à $n = 2^{20}$ .

Le changement de variable

Quand la récurrence porte sur $n$ , ou quand $n$ n'apparaît que par son logarithme, on pose $n = 2^{k}$ et on travaille sur $k$ .

Comparaison asymptotique

La question pratique est toujours la même: entre deux coûts, lequel finit par dominer? La hiérarchie ci-dessous répond pour toutes les fonctions rencontrées dans ce cours. On y lit, de gauche à droite, de la plus lente à la plus rapide, avec $a > 0$ , $b > 0$ et $c > 1$ quelconques:

1 ≺ lo g lo g n ≺ lo g^{b} n ≺ n^{a} ≺ c^{n} ≺ n! ≺ n^{n},

où $f ≺ g$ signifie $f \in o (g)$ , c'est-à-dire $f (n) / g (n) \to 0$ .

Démonstration. Polynôme contre logarithme. Posons $n = e^{t}$ , donc $t = ln n \to + \infty$ , et travaillons en logarithme naturel, ce qui ne change qu'une constante multiplicative élevée à la puissance $b$ . Le quotient s'écrit $t^{b} / e^{a t}$ . Or l'exponentielle domine toute puissance: pour tout entier , la série de contient le terme , donc pour . En prenant et , on obtient puisque .

Exponentielle contre polynôme. Prenons le logarithme du quotient: $a ln n - n ln c$ . Comme $ln c > 0$ et que $ln n \in o (n)$ par ce qui précède, cette expression tend vers $- \infty$ , donc le quotient tend vers 0.

Factorielle contre exponentielle. Le quotient $u_{n} = c^{n} / n!$ vérifie $u_{n + 1} / u_{n} = c / (n + 1)$ . Dès que , ce rapport est au plus : à partir de ce rang , la suite est majorée par une suite géométrique de raison , donc tend vers 0.

La quatrième séparation, $n! ≺ n^{n}$ , se lit sur Stirling: le quotient vaut $2 π n e^{- n}$ à un facteur près, qui tend vers 0.

Le tableau suivant donne les valeurs des classes usuelles pour quatre tailles, toutes calculées:

$n$	$lo g_{2} n$	$lo g_{2}^{2} n$	$n$

Deux lectures. D'abord, $lo g_{2} n$ reste minuscule: pour un million d'éléments il vaut 20, et c'est pourquoi une recherche dichotomique ou une opération sur un arbre équilibré est «pratiquement gratuite». Ensuite, l'écart entre $n lo g_{2} n$ et $n^{2}$ passe de 4 à 52 429 sur ces quatre lignes: c'est l'écart entre un tri utilisable et un tri qui ne l'est pas, et il ne cesse de croître.

Synthèse

Les quatre sommes à savoir retrouver sont $\sum_{k \leq n} k = \frac{n ( n + 1 )}{2}$ , $\sum_{k \leq n} k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ , et , d'où ; une somme géométrique de raison différente de 1 vaut, à une constante près, son plus grand terme.

Exercices

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

Exercice A.1 · La somme des entiers impairs, de deux façons

Montrez que $\sum_{k = 1}^{n} (2 k - 1) = n^{2}$ , d'abord en vous ramenant à la somme arithmétique (A.1), puis par récurrence sur $n$ . Donnez ensuite une interprétation géométrique de l'identité.

Exercice A.2 · Deux séries que l'on croise en algorithmique

Montrez que $\sum_{k = 1}^{n} \frac{1}{k ^{2}} \leq 2 - \frac{1}{n}$ pour tout , et concluez que la série converge. Pourquoi cette somme est-elle bornée alors que diverge?

Exercice A.3 · Un invariant pour l'évaluation d'un polynôme

Le schéma de Horner évalue $P (x) = a_{0} + a_{1} x + \dots + a_{d} x^{d}$ en multiplications au lieu de .

Exercice A.4 · Combien de records dans une permutation aléatoire

On tire uniformément une permutation $p$ de ${1, \dots, n}$ et on la parcourt de gauche à droite. Un élément est un record s'il est strictement plus grand que tous ceux qui le précèdent (le premier élément en est toujours un). Calculez le nombre moyen de records. Quelle quantité algorithmique ce nombre mesure-t-il?

Solution

Le calcul. Posons $X_{i} = 1$ si le -ième élément lu est un record, 0 sinon, pour . Le nombre de records est .

Exercice A.5 · Trois récurrences et un changement de variable

Résolvez, en donnant à chaque fois la classe $Θ$ et la méthode employée. On suppose $n = 2^{k}$ et $T (1) = 0$ sauf mention contraire.

$T (n) = 2 T (n /2) + n lo g_{2} n$ .

Références

Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — annexe A pour les sommes usuelles et leurs bornes, annexe C pour le dénombrement et la probabilité discrète, chapitre 4 pour les méthodes de résolution de récurrences.
Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes annexes, utile pour la terminologie.
Graham, Knuth & Patashnik, Concrete Mathematics, 2ᵉ éd., Addison-Wesley — la référence pour les sommes, les nombres harmoniques et les techniques de manipulation; les chapitres 2 et 6 couvrent tout ce qui précède, et bien au-delà.
Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 13 pour les variables indicatrices et la linéarité de l'espérance appliquées aux algorithmes randomisés.
Mitzenmacher & Upfal, Probability and Computing, 2ᵉ éd., Cambridge University Press — pour la probabilité discrète orientée algorithmes, au-delà de ce que cette annexe rappelle.

16	4	16	4	16	64	256
256	8	64	16	256	2 048	65 536
1 024	10	100	32	1 024	10 240	1 048 576
1 048 576	20	400	1 024	1 048 576	20 971 520	$1, 1 \times 1 0^{12}$