Download informatique et mathématiques

P ROJET DE SUPPORT DE COURS -TD
POUR LE MODULE OPTIONNEL
“I NFORMATIQUE ET MATHÉMATIQUES ”
J. Sauloy 1
13 juin 2011
1. U.F.R. M.I.G., Université Paul Sabatier, 118, route de Narbonne, 31062 Toulouse CEDEX 4
1
Table des matières
1
2
3
Arithmétique élémentaire
1.1 Prélude : la division euclidienne dans Z
1.2 Calcul en base b . . . . . . . . . . . . .
1.2.1 Ecriture en base b . . . . . . . .
1.2.2 Addition en base b . . . . . . .
1.2.3 Multiplication en base b . . . .
1.3 Exponentiation rapide . . . . . . . . . .
1.3.1 Méthode naturelle . . . . . . .
1.3.2 Méthode dichotomique . . . . .
1.3.3 Questions d’optimalité . . . . .
1.4 L’algorithme d’Euclide . . . . . . . . .
1.4.1 L’algorithme de base . . . . . .
1.4.2 L’algorithme classique . . . . .
1.4.3 L’algorithme amélioré . . . . .
1.5 Suppléments facultatifs . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
5
6
9
11
13
13
13
16
17
17
18
19
20
Arithmétique modulaire et applications
2.1 Congruences . . . . . . . . . . . . . . . .
2.1.1 L’ensemble Z/mZ . . . . . . . . .
2.1.2 Le groupe (Z/mZ, +) . . . . . . .
2.1.3 L’anneau (Z/mZ, +, ×) . . . . . .
2.1.4 Le groupe (Z/mZ)∗ , × . . . . . .
2.2 Générateurs pseudo-aléatoires . . . . . . .
2.2.1 Générateurs linéaires congruentiels
2.2.2 Quelques tests . . . . . . . . . . .
2.3 Cryptographie . . . . . . . . . . . . . . . .
2.3.1 Petit préliminaire théorique . . . . .
2.3.2 La méthode RSA . . . . . . . . . .
2.4 Suppléments facultatifs . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
21
21
22
24
25
26
27
28
31
31
32
32
Ensembles finis
3.1 Codage par vecteurs de bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Calcul booléen sur les sous-ensembles . . . . . . . . . . . . . . . . . . . . . . .
3.3 Le produit cartésien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
33
34
35
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
Recherche et tri
4.1 Algorithmes de recherche . . . . . . . . . . . . .
4.1.1 Recherche d’un élément . . . . . . . . .
4.1.2 Recherche du maximum dans un tableau .
4.1.3 Recherche d’un duplicata . . . . . . . . .
4.2 Algorithmes de tri . . . . . . . . . . . . . . . . .
4.2.1 Tri de trois éléments . . . . . . . . . . .
4.2.2 Tri par sélection . . . . . . . . . . . . .
4.2.3 Tri par fusion . . . . . . . . . . . . . . .
4.3 Suppléments facultatifs . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A Rappel de la proposition
A.1 Arithmétique élémentaire (quatre semaines) . . . . . . .
A.1.1 Ecriture et calcul en base b . . . . . . . . . . . .
A.1.2 Exponentiation . . . . . . . . . . . . . . . . . .
A.1.3 Algorithme d’Euclide . . . . . . . . . . . . . . .
A.2 Arithmétique modulaire et applications (quatre semaines)
A.2.1 Congruences . . . . . . . . . . . . . . . . . . .
A.2.2 Générateurs pseudo-aléatoires . . . . . . . . . .
A.2.3 Cryptographie . . . . . . . . . . . . . . . . . .
A.3 Ensembles finis (deux semaines) . . . . . . . . . . . . .
A.4 Recherche et tri (deux semaines) . . . . . . . . . . . . .
A.4.1 Algorithmes de recherche (vuis en cours d’info) .
A.4.2 Algorithmes de tri . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
36
36
36
39
40
41
41
43
44
49
.
.
.
.
.
.
.
.
.
.
.
.
50
50
50
50
51
51
51
51
51
51
51
51
52
Conventions et notations générales
Conventions. La notation A := B signifiera que le terme A est défini par la formule B. Les
expressions nouvelles sont écrites en italiques au moment de la définition. Noter qu’une définition
peut apparaitre au cours d’un théorème, d’un exemple, d’un exercice, etc.
Exemple 0.0.1 L’entier r := a − qb est appelé reste de la division euclidienne de a par b.
Notations. Voici les plus courantes (parmi celles qui ne sont pas totalement standardisées et ne
sont pas introduites dans le cours) :
– Si x ∈ R, l’unique entier n tel que n ≤ x < n + 1 est noté bxc et appelé partie entière de x.
ln a
– si a ∈ R+ et b ∈ N, b ≥ 2, on note logb (a) :=
le logarithme en base b de a.
ln b
–
–
–
3
Chapitre 1
Arithmétique élémentaire
1.1
Prélude : la division euclidienne dans Z
Théorème 1.1.1 Soient a ∈ Z et b ∈ N∗ . Il existe alors un unique couple (q, r) ∈ Z × Z tel que :
(
a = qb + r,
(1.1.1.1)
0 ≤ r ≤ b − 1.
Les entiers q et r sont respectivement appelés quotient et reste de la division euclidienne de a par
b. (Et l’on dit parfois que a est le dividende et b le diviseur.)
Preuve. - On commence par l’unicité. Si a = qb + r = q0 b + r0 avec 0 ≤ r, r0 ≤ b − 1, on a d’une part
−(b − 1) ≤ r0 − r ≤ (b − 1), autrement dit, |r0 − r| ≤ (b − 1) ; d’autre part r0 − r = (q − q0 )b. Cela
entraine r0 − r = 0 (seul multiple de b de valeur absolue strictement inférieure à b) donc q − q0 = 0.
Pour prouver l’existence, on va utiliser un algorithme :
q := 0;
r := a;
Si (a >= 0) alors
tant que (r >= b) faire
r := r - b;
q := q + 1;
fin tant que;
sinon
tant que (r < 0) faire
r := r + b;
q := q - 1;
fin tant que;
fin si;
rendre (q,r);
Tout d’abord, la terminaison de l’algorithme est garantie : dans le cas où a ≥ 0, le “compteur” r
décroit strictement à chaque étape, donc la condition de continuation r ≥ b finit par être fausse ;
et dans le cas contraire, le “compteur” r croit strictement à chaque étape, donc la condition de
continuation r < 0 finit par être fausse.
4
Pour prouver la correction de l’algorithme, supposons d’abord que l’on est dans le premier cas
a ≥ 0. On introduit l’invariant de boucle :
a = qb + r et r ≥ 0.
Il est vérifié à l’initialisation. De plus, chaque exécution de l’instruction (r := r - b; q := q + 1)
sous la condition de continuation r >= b le conserve. En effet, notant r0 , r00 les états avant et après
de r et q0 , q00 les états avant et après de q, on a : r00 = r0 − b et q00 = q0 + 1, donc q00 b + r00 =
(q0 + 1)b + (r0 − b) = q0 b + r0 , d’où la conservation de la condition a = qb + r. D’autre part, r0 ≥ b
(condition d’exécution de la boucle) donc r00 ≥ 0.
A la sortie de la boucle tant que, on a r < b (la condition de sortie est la négation de la condition r >= b) et en plus l’invariant de boucle a = qb + r et r ≥ 0. C’est exactement équivalent aux
conditions énoncées par le théorème : a = qb + r et 0 ≤ r ≤ b − 1.
Supposons maintenant que l’on est dans le deuxième cas a ≥ 0. On introduit l’invariant de boucle :
a = qb + r et r < b.
Le raisonnement est alors similaire, on laisse au lecteur le plaisir de le rédiger. On notera par la suite divEucl(a,b) le résultat de la division euclidienne de a par b, donc les
deux nombres q et r calculés par l’algorithme ci-dessus.
Corollaire 1.1.2 Le quotient de la division euclidienne de a par b est q = ba/bc.
Preuve. - Puisque r et b sont des entiers, la condition r ≤ b − 1 est équivalente à la condition r < b.
L’entier q est alors défini par la condition :
0 ≤ a − qb ≤ b − 1 ⇐⇒ 0 ≤ a − qb < b ⇐⇒ qb ≤ a < (q + 1)b ⇐⇒ q ≤ a/b < (q + 1),
d’où la conclusion. Bien qu’un algorithme ait servi à établir l’existence du quotient et du reste, nous ne prétendons pas que les systèmes de calcul existants (comme par exemple Maple) utilisent réellement
cet algorithme pour effectuer une division euclidienne. Dans la suite de ce chapitre, nous éluderons cette question et admettrons l’existence d’une “fonction primitive” qui prend en argument le
couple (a, b) et donne comme résultat le couple (q, r) ; mode d’emploi : (q, r) := diveucl(a, b).
Nous admettrons de plus que ce calcul s’effectue en temps constant.
Exercice 1.1.3 On appelle mantisse de x ∈ R le réel M(x) := x − bxc.
(i) Montrer que c’est l’unique réel α ∈ [0, 1[ tel que x − α ∈ Z.
(ii) Exprimer le reste de la division euclidienne de a par b en fonction de M(a/b).
TP 1.1.4 Programmer la fonction diveucl en utilisant l’algorithme décrit dans la preuve du théorème.
1.2
Calcul en base b
Dans toute cette section, la base b est un entier naturel fixé tel que b ≥ 2. (Le cas b = 1
correspond à l’écriture en bâtons : 1 mammouth = 1 bâton.) Nous ne traiterons que le cas des
entiers naturels : donc, ni les entiers négatifs, ni les nombres non entiers.
5
1.2.1
Ecriture en base b
Rappelons le principe de l’écriture décimale : le nombre noté 2011 est égal à 2.103 + 0.102 +
1.101 + 1.100 . Le même nombre admet l’écriture binaire 11111011011, ce qui signifie 1.210 +
1.29 + 1.28 + 1.27 + 1.26 + 0.25 + 1.24 + 1.23 + 0.22 + 1.21 + 1.20 . Si l’on ne veut pas confondre
cette écriture binaire 11111011011 avec celle d’un entier de l’ordre de dix milliards, on écrira
plutôt (11111011011)2 . Notons que, dans les deux cas, nous écrivons les puissances (de 10 ou de
2) par ordre décroissant d’exposant : le “chiffre des unités” est à droite.
Avant d’énoncer et de démontrer le théorème fondamental, voici un résultat préliminaire qui
sert beaucoup dans la pratique.
Lemme 1.2.1 Soient k ≥ 0 un entier et c0 , . . . , ck ∈ {0, . . . , b − 1}. On suppose que ck 6= 0. L’entier
a := ck bk + · · · + c0 b0 vérifie alors :
(1.2.1.1)
bk ≤ a ≤ bk+1 − 1.
Preuve. - Puisque ci ≥ 0 et ck ≥ 1, un minorant de a est :
1.bk + 0.bk−1 + · · · + 0.b0 = bk .
Puisque ci ≤ b − 1, un majorant de a est :
(b − 1)bk + · · · + (b − 1)b0 = bk+1 − 1.
Théorème 1.2.2 Soit a ∈ N∗ un entier naturel non nul. Il existe alors un unique entier k ≥ 0 et une
unique suite finie (c0 , . . . , ck ) tels que :

k
0

a = ck b + · · · + c0 b ,
(1.2.2.1)
0 ≤ ci ≤ b − 1 pour i = 0, . . . , k,


ck 6= 0.
On dit alors que (ck · · · c0 )b est l’écriture de a en base b. Les ci sont les chiffres de cet écriture. On
précise parfois que cette écriture se fait poids forts à gauche.
Preuve. - L’unicité se prouve par “récurrence forte” sur a. Si a ≤ b − 1, d’après le lemme, on a
nécessairement k = 0, d’où l’on déduit c0 = a. L’unicité est donc bien démontrée dans ce cas.
Soit donc a ≥ b et supposons l’unicité prouvée pour tout entier a0 tel que a0 < a. (C’est à cause de
cette forme particulière de l’hypothèse de récurrence que l’on parle de “récurrence forte”.) Si l’on
a une écriture a = ck bk + · · · + c0 b0 , on en déduit :
a = a0 b + c0 avec a0 = ck bk−1 + · · · + c1 b0 .
On voit donc que c0 est nécessairement le reste de la division euclidienne de a par b ; que a0 est
nécessairement le quotient de la division euclidienne de a par b ; et que (ck · · · c1 )b est nécessairement une écriture de a0 en base b. Mais, d’après le lemme, a0 ≤ bk − 1 < a. D’après l’hypothèse
6
de récurrence, l’écriture de a0 en base b est unique, il en est donc de même de l’écriture de a.
L’analyse ci-dessus nous suggère l’algorithme dont nous déduirons l’existence de l’écriture en
base b : il consiste en des divisions euclidiennes successives. Le résultat est retourné sous la forme
d’un tableau c tel que a = ∑ki=0 c[i]bi :
x := a;
i := 0;
tant que (x >= b) faire
(q,r) := divEucl(x,b);
c[i] := r;
x := q;
i := i + 1;
fin tant que;
c[i] := x;
k := i;
rendre (k,c);
La terminaison est garantie par le fait que x décroit strictement, donc que la condition de continuation x >= b finit par être fausse.
La correction repose sur l’invariant de boucle :
a = c[0]b0 + · · · + c[i − 1]bi−1 + xbi .
Nous laissons au lecteur le soin de prouver la validité de cet invariant et d’en déduire la correction
de l’algorithme. Plusieurs remarques s’imposent ici :
1. Nous éludons totalement la question de la représentation “interne” de a, de b et des chiffres
ci ; et donc également de la manière dont sont implémentés les calculs de division euclidienne.
2. Nous avons mis à part le cas de 0 qui, quelle que soit la base, s’écrit 0.
3. Nous avons défini et calculé l’écriture propre de a. On aura parfois besoin de ses écritures
impropres, dans lesquelles on s’autorise à ajouter des chiffres 0 au delà du chiffre de poids
fort : par exemple (00011111011011)2 au lieu de (11111011011)2 . Lorsque l’on autorise
les écritures impropres, il n’y a plus unicité de l’écriture.
Exercice 1.2.3 On propose un traitement mathématique de l’invariant de boucle. On pose x0 := a
et, tant que xi > 0, (xi+1 , ci ) := diveucl(xi , b). Démontrer par récurrence que, pour tout i :
a = c0 b0 + · · · + ci−1 bi−1 + xi bi .
TP 1.2.4 Programmer le calcul de l’écriture en base b d’un entier a. A défaut de savoir représenter
les tableaux, on écrira un programme qui affiche les chiffres de a puis l’entier k.
7
Taille du codage d’un entier en base b
L’écriture en base b sert avant tout à coder les entiers. Le codage d’un entier donné représente
un certain espace dans la mémoire d’un ordinateur. Nous estimerons cet espace mémoire en supposant (pour simplifier notre modèle mathématique) qu’il est entièrement occupé par les chiffres.
Cette hypothèse simplificatrice est d’ailleurs une approximation de la réalité puisqu’il faut bien
indiquer quelque part que l’on est au bout de l’écriture de cet entier.
Remarque 1.2.5 Une autre possibilité serait que tous les entiers soient codés dans des espaces
de même taille, donc en écriture impropre avec le même nombre total de chiffres. C’est ce qui
se pratique quand les entiers manipulés ne sont pas trop grands. Dans cette section, nous supposerons que les entiers peuvent être très grands et que la taille de leur codage doit être estimée
correctement.
Nous supposerons également que tous les chiffres de l’écriture en base b d’un entier occupent
des espaces de mêmes tailles : notons K l’espace occupé par un chiffre (disons que c’est un nombre
de bits). Si a = c0 + · · · + ck bk , avec ck 6= 0, l’espace total occupé par a est : (k + 1)K.
Proposition 1.2.6 Le nombre de chiffres de l’écriture de a en base b est égal à 1 + blogb ac.
Preuve. - Ce nombre de chiffres est k + 1 ; or, d’après le lemme 1.2.1 :
bk ≤ a ≤ bk+1 − 1 =⇒ bk ≤ a < bk+1 =⇒ k ≤
ln a
ln a
< k + 1 =⇒ k = b
c.
ln b
ln b
Pour ne pas avoir à tenir compte de l’unité de taille mémoire (ici les K bits occupés par chaque
chiffre), nous ne prendrons en compte dans l’estimation de la taille de a que le nombre de chiffres :
Définition 1.2.7 La taille d’un entier a ∈ N∗ (sous-entendu : écrit en base b) est le nombre de ses
chiffres, 1 + blogb ac. On la notera |a| (donc sans préciser la base b relativement à laquelle cette
taille est calculée).
Exercice 1.2.8 Si l’on écrit en base 2, un chiffre est un bit et K = 1. Si l’on écrit en base 16
(système hexadécimal), on peut supposer qu’un chiffre s’écrit sur quatre bits, et K = 4. Comparer
les espaces mémoire occupés par un même entier dans ces deux représentations.
Le “coût” de l’algorithme de codage en base b
Ici et dans toute la suite de ce cours, nous appellerons coût d’un algorithme le temps d’exécution d’un programme implémentant cet algorithme. Trois points très importants sont à prendre en
compte :
1. Ce temps dépend presque toujours de la taille des données, et nous le considèrerons donc
comme une fonction de cette taille. Par exemple : le temps total de multiplication de deux
entiers par la méthode apprise à l’école primaire dépend du nombre de chiffres de ces entiers.
2. Nous ne mesurons pas ce temps mais tentons de le prédire à partir d’une analyse du comportement dynamique de l’algorithme. Par exemple : pour calculer an , un algorithme simplet
effectuera (n − 1) multiplications.
8
3. Selon la machine utilisée, le langage de programmation, voire l’environnement d’exécution, les opérations élementaires (opérations arithmétiques, mais aussi : comparaisons entre
nombres, lectures et écritures, affectations, etc) ne prennent pas le même temps. Nous n’en
tiendrons pas compte et remplacerons ces temps élémentaires par des constantes.
Comme déjà indiqué, nous supposons que le coût d’une division euclidienne est constant. Il
est raisonnable de supposer que toutes les autres instructions écrites dans l’algorithme s’effectuent
également en temps constant (il y a des additions, des affectations, etc). Le temps total d’exécution
est donc de la forme Ak + B, où k est l’entier qui apparait dans l’écriture de a ; en effet, le nombre
d’exécutions de la boucle interne (c’est-à-dire le nombre de fois que l’on aura x ≥ b) est égal au
nombre de fois où l’on calcule un chiffre ci en ne comptant pas le dernier chiffre ck (qui est calculé
à la fin).
Le coût de l’algorithme de codage en base b est donc une fonction affine 1 de la taille de l’entier
codé : en effet, avec les mêmes notations, |a| = k + 1, d’où :
Ak + B = A |a| + B0 , où B0 = B − A.
Pour des entiers de grande taille k, c’est presque la même chose que si l’on avait un coût de la
forme A |a|, et il est d’usage de dire plus simplement que le coût (du codage) est une fonction
linéaire de la taille.
1.2.2
Addition en base b
0
Soient a = c0 + · · · + ck bk et a0 = c00 + · · · + c0k0 bk les écritures propres des deux nombres à
additionner. Supposons par exemple que k0 < k. On peut alors prolonger l’écriture de a0 en une
écriture impropre en posant a0k0 +1 := 0, . . . , a0k := 0, d’où a0 = c00 + · · · + c0k bk . Cela permet dans
tous les cas d’additionner deux nombres écrits avec (k + 1) chiffres, où k + 1 = max(|a| , |a0 |).
En première approche, on a :
a + a0 = (c0 + c00 ) + · · · + (ck + c0k )bk .
C’est facile à écrire, malheureusement ce n’est en général pas une écriture en base b puisque l’on
peut avoir ci + c0i > b. (Il y a même un peu plus d’une chance sur deux que cela se produise pour un
i donné, donc, si k est grand, il est extrêmement probable que cela se produise pour un i au moins !)
Dans tous les cas, ci + c0i ≤ 2b − 2. Supposons par exemple que b ≤ c0 + c00 ≤ 2b − 2. On écrira
alors :
(c0 +c00 )+(c1 +c01 )b = (c0 +c00 −b)+(c1 +c01 +1)b =⇒ a+a0 = (c0 +c00 −b)+(c1 +c01 +1)b+· · ·+(ck +c0k )bk .
Le problème se repose alors avec c1 +c01 +1 : ce nombre est a priori compris entre 0 et 2b−1, mais
s’il est supérieur ou égal à b on doit recommencer la même manoeuvre. Le lecteur aura reconnu le
problème de la retenue. Pour finir, on obtient l’algorithme appris à l’école primaire d’addition en
base b de deux nombres ∑ki=0 c[i]bi et ∑ki=0 c0 [i]bi pour produire le résultat ∑li=0 d[i]bi :
1. Fonction linéaire : f (x) = αx ; fonction affine : f (x) = αx + β.
9
i := 0;
r := 0;
tant que (i <= k)
d[i] := c[i] + c’[i] + r;
si (d[i] >= b) alors
d[i] := d[i] - b;
r := 1;
sinon
r := 0;
fin si;
i := i + 1;
fin tant que;
si (r = 0) alors
l := k;
sinon
l := k+1;
d[l] := r;
fin si;
rendre (d);
L’entier l apparu à la fin est le nombre de chiffres de la somme : donc k ou k + 1, selon qu’il y
avait ou non une retenue à la toute dernière addition.
Il est évident que cet algorithme se termine après (k + 1) exécutions de l’instruction de boucle.
La correction se prouve à l’aide de l’invariant de boucle :
(c0 + · · · + ci bi ) + (c00 + · · · + c0i bi ) = (d0 + · · · + di bi ) + rbi+1 .
On doit ajouter le fait que, à tout moment, r = 0 ou 1, donc que ci + c0i + r ≤ 2b − 1 ; donc le di
calculé est bien un chiffre (un nombre entre 0 et b − 1).
Exercice 1.2.9 Quelle est la probabilité qu’il n’y ait aucune retenue ?
TP 1.2.10 Programmer l’addition en base b.
Coût de l’algorithme d’addition en base b
Chaque étape de la boucle “tant que” contient une addition de deux chiffres, une addition de
la retenue, un test, peut-être une soustraction, certainement une incrémentation. En prenant en
compte les instructions avant et après la boucle “tant que”, on conclut qu’il existe des constantes
A, A0 > 0 et des constantes B, B0 telles que le coût soit compris entre A(k + 1) + B et A0 (k + 1) + B0 ,
autrement dit, entre A max(|a| , |a0 |) + B et A0 max(|a| , |a0 |) + B0 .
De manière très informelle, on peut encore dire que le coût (de l’addition) est une fonction “à
peu près” linéaire de la taille des données. On peut même préciser cet à-peu-près comme suit :
10
1. L’ordre de grandeur du coût n’est pas pire qu’un coût linéaire. Plus précisément, lorsque la
taille des données a, a0 est de plus en plus grande, le rapport :
coût de l’addition a + a0
max(|a| , |a0 |)
ne croît pas indéfiniment, il reste majoré. L’écriture mathématique de cette propriété est :
coût de l’addition a + a0 = O max(|a| , a0 ) .
2. L’ordre de grandeur du coût n’est pas non plus meilleur qu’un coût linéaire. Plus précisément, lorsque la taille des données a, a0 est de plus en plus grande, le rapport :
max(|a| , |a0 |)
coût de l’addition a + a0
ne croît pas indéfiniment, il reste majoré. Avec la convention précédente, on a donc :
max(|a| , a0 ) = O coût de l’addition a + a0 .
3. Pour dire que l’ordre de grandeur du coût n’est ni pire ni meilleur qu’un coût linéaire, on
résume les deux propriétés précédentes par la formule :
coût de l’addition a + a0 = Θ max(|a| , a0 ) .
Exercice 1.2.11 L’entier k := max(|a| , |a0 |) étant fixé, décrire un cas où l’addition se fait à coût
minimum, resp. à coût maximum, et calculer précisément ce minimum et ce maximum.
1.2.3
Multiplication en base b
Multiplication d’un nombre par un chiffre
Soient a = c0 + · · · + ck bk (écriture propre en base b) et c ∈ {0, . . . , b − 1}. Dans le cas où c = 0
ou 1, le produit ca se calcule sans trop de peine ... En général, on calcule les produits cci et l’on
doit s’occuper des retenues.
Nous admettrons que le produit de deux chiffres (tables de multiplication de l’école primaire ! ! !) se fait en temps constant : il peut être tabulé (les résultats sont en mémoire) ou cablé
(réalisé par du hardware) ou réalisé par un tout petit programme ad hoc.
Le résultat de cette multiplication est inférieur ou égal à (b − 1)2 : nombre à deux chiffres,
qui s’écrit qb + r avec q ≤ b − 2 (puisque (b − 1)2 < (b − 1)b). Attention ! c’est q qui va servir de
retenue et r sera le chiffre à écrire. En effet, par exemple :
cc0 = qb + r =⇒ c(c0 + c1 b) = d0 + d1 b avec d0 = r et d1 = cc1 + q.
Naturellement, on doit encore effectuer une division euclidienne de cc1 + q par b pour calculer le
chiffre d1 et la prochaine retenue ; mais cc1 +q ≤ (b−1)2 +b−2 < b2 −b, et le quotient (prochaine
retenue) sera encore inférieur ou égal à b − 2. Voici l’algorithme (nous notons maintenant s la
retenue). L’algorithme ci-dessous de multiplication du nombre ∑ki=0 c[i]bi par le chiffre c a pour
résultat ∑li=0 d[i]bi :
11
i := 0;
s := 0;
tant que (i <= k)
(q,r) := divEucl(c*c[i] + s,b);
d[i] := r;
s := q;
i := i+1;
fin tant que;
si s = 0
alors l := k
sinon (l := k + 1; d[l] := s);
fin si;;
Le coût de cet algorithme est linéaire en |a|.
Multiplication de deux nombres quelconques
0
Pour multiplier les entiers a = c0 + · · · + ck bk et a0 = c00 + · · · + c0k0 bk , l’algorithme appris en
primaire (multiplications d’un nombre par un chiffre avec décalages vers la gauche et additions)
revient à calculer successivement : ac00 , puis ac01 b, puis ac02 b2 , etc ; et à additionner le tout : dans ce
cas, il s’agit donc d’additionner les (k0 + 1) produits ac0i bi . Bien entendu, à cette heureuse époque
(l’école primaire), l’addition se faisait directement. Pour écrire un programme, il est cependant
plus simple de faire des additions successives de deux nombres. Voici donc le schéma de l’al0
gorithme de multiplication en base b de deux nombres ∑ki=0 c0 [i]bi et a pour produire le résultat
s:
s := 0;
i := 0;
tant que (i <= k’) faire
s := s + c’[i]*a*bi ;;
fin tant que;
rendre (s);
Naturellement, la multiplication c’[i]*a se fait selon l’algorithme vu plus haut ; et la multiplication du résultat par bi n’en est pas réellement une, il s’agit simplement d’un décalage (avec ajout
de chiffres 0 à droite).
On peut démontrer que le coût de la multiplication est linéaire en le produit des tailles :
coût de la multiplication a.a0 = Θ |a| × a0 .
Exercice 1.2.12 Le prouver.
TP 1.2.13 Programmer la multiplication et l’expérimenter pour vérifier l’estimation annoncée du
coût.
12
1.3
Exponentiation rapide
Il s’agit de calculer les puissances an , n ∈ N∗ , d’un nombre a qui peut être compliqué : réel
en écriture flottante, grand entier . . . Un réflexe fréquent pour calculer an avec une calculette en
évitant toute programmation est d’écrire (en supposant bien entendu que a > 0) :
an = exp(n ln a).
Cette méthode est aberrante. En effet, le calcul des fonctions dites “transcendantes” comme
l’exponentielle et le logarithme (ainsi que les fonctions trigonométriques) fait appel à des sousprogrammes qui effectuent un grand nombre de calculs et qui, dans tous les cas, rendent un résultat
approché. Le lecteur est vivement encouragé à calculer 33 par cette méthode et à tenter d’estimer
le temps de calcul et la précision du résultat.
TP 1.3.1 Faire l’expérience : calculer un million de fois 3 × 3 × 3 et exp(3 ln 3).
1.3.1
Méthode naturelle
Il s’agit bien entendu de poser (on suppose ici n ≥ 2) :
an = a × · · · × a,
où il y a n facteurs et donc (n − 1) symboles d’opérations ×. Le calcul représente donc (n − 1)
multiplications. En admettant que le coût de ces multiplications est constant, on en déduit :
coût du calcul de an = Θ(n).
Naturellement, l’unité de coût, c’est-à-dire le coût unitaire de chaque multiplication, dépend ici
d’autres facteurs :
– Type du nombre a : la multiplication de réels en écriture flottante est plus chère que la
multiplication d’entiers courts.
– Algorithmes utilisés par les librairies numériques du langage, du système d’exploitation.
– Vitesse du hardware.
Exercice 1.3.2 On admet que le coût de la multiplication est linéaire en le produit des tailles :
coût de la multiplication a.a0 = Θ |a| × a0 .
Montrer que le coût de calcul de an est alors Θ(n2 ).
1.3.2
Méthode dichotomique
Cette méthode très ancienne est appelée exponentiation dichotomique ou indienne ou chinoise
ou babylonienne . . . On la comprend mieux sur un exemple. Le calcul de a8 , qui devrait coûter 7
multiplications, peut se réaliser en 3 multiplications comme suit :
x1 := a × a,
x2 := x1 × x1 ,
13
x3 := x2 × x2 .
Remarque 1.3.3 Il y a un (petit) prix à payer pour ce gain de performance : l’utilisation de variables pour désigner les calculs intermédiaires cache en réalité l’utilisation d’un peu de mémoire
pour stocker ces résultats.
Naturellement, l’exposant 8 étant pair, la puissance a8 = (a4 )2 est un carré. La situation n’est
pas toujours aussi favorable. Par exemple, le calcul de a7 , qui aurait coûté 6 multiplications par la
méthode naturelle, peut se réaliser en 4 multiplications, donc plus que pour a8 ! La séquence est la
suivante :
x1 := a × a, x2 := x1 × a, x3 := x2 × x2 , x4 := x3 × a.
Il a fallu compléter le carré x1 = a2 en le multipliant par a (à cause de l’exposant impair 3) ; puis
compléter le carré x3 = a6 en le multipliant par a (à cause de l’exposant impair 7). Cela explique
le relatif surcoût. On s’attend en général à réaliser des gains de performance en accord avec le
slogan : “plus il y a d’exposants pairs, plus on y gagne”. Nous allons tout de même vérifier que la
méthode est efficace dans tous les cas, autrement dit que l’on a une “performance asymptotique”
infiniment meilleure que par la méthode naturelle (ces termes seront expliqués).
Tout d’abord, explicitons informellement la méthode. Un algorithme précis sera écrit plus loin.
– Si n = 2p, calculer b := a p puis an := b × b.
– Si n = 2p + 1, calculer b := a p puis an := b × b × a.
Notons c(n) le nombre de multiplications nécessaires pour calculer an . Par exemple c(1) = 0 et,
de toute évidence, c(2) = 1. De la description ci-dessus, on déduit les règles :
c(2p) = c(p) + 1,
c(2p + 1) = c(p) + 2.
Cela permet déjà de calculer les premières valeurs de c(n) :
n
c(n)
n
c(n)
1
0
13
5
2
1
14
5
3
2
15
6
4
2
16
4
5
3
17
5
6
3
18
5
7
4
19
6
8
3
20
5
9
4
21
6
10
4
22
6
11
5
23
7
12
4
24
5
Nous allons maintenant trouver la formule générale donnant le coût c(n). Pour cela, on prend
en compte l’écriture binaire des expressions 2p et 2p + 1. En effet, si l’écriture binaire de p est
(bk · · · b0 )2 , alors :
– L’écriture binaire de 2p est (bk · · · b0 0)2 ;
– L’écriture binaire de 2p + 1 est (bk · · · b0 1)2 .
Comme c(1) = 0, on en tire la règle suivante :
Proposition 1.3.4 Soit (ak · · · a0 )2 l’écriture binaire propre de n (donc ak = 1). Soient α le nombre
de 0 et β le nombre de 1 parmi les bits a0 , . . . , ak−1 (on ne prend donc pas en compte le bit de poids
fort ak ). Alors :
c(n) = α + 2β = k + β.
Preuve. - En effet, on peut reconstituer l’écriture binaire propre de n en partant du bit 1 (écriture
binaire du nombre 1), correspondant au coût c(1) = 0, et en rajoutant successivement à droite des
bits 0 et des bits 1.
14
– Chaque fois que l’on rajoute un bit 0, le coût augmente de 1 ; cela se produit α fois.
– Chaque fois que l’on rajoute un bit 1, le coût augmente de 2 ; cela se produit β fois.
On a donc bien à la fin c(n) = α + 2β. D’autre part, le nombre total de bits que l’on a ajouté est
α + β = k, d’où la deuxième formule. Corollaire 1.3.5 (i) Le cas le meilleur est celui où l’on n’a rajouté que des 0 : alors n = 2k et
c(n) = k.
(ii) Le cas le pire est celui où l’on n’a rajouté que des 1 : alors n = 2k+1 − 1 et c(n) = 2k.
(iii) Dans tous les cas, on a k ≤ c(n) ≤ 2k.
Rappelons d’autre part que k = blog2 nc = |n|2 −1, où l’on désigne par |n|2 la taille de l’écriture
de n en base 2.
Corollaire 1.3.6 (i) Le coût c(n) vérifie :
blog2 nc ≤ c(n) ≤ 2blog2 nc.
(ii) On a c(n) = Θ(log2 n) = Θ (|n|2 ).
log2 n
= 0, on voit que, pour de grandes valeurs de l’exposant n, le rapport du
n
coût par la méthode dichotomique au coût par la méthode naturelle tend vers 0 : c’est le sens de la
phrase “on a une performance asymptotique infiniment meilleure que par la méthode naturelle”.
Comme lim
n→+∞
L’algorithme
On traduit la méthode décrite informellement plus haut par l’algorithme de calcul de r := xn :
r := 1;
x := a;
p := n;
tant que (p > 0)
si p impair alors
r := r*x;
fin si;
x := x * x;
p := p div 2;
fin tant que;
rendre (r);;
(On a noté par p div 2 le quotient de la division de p par 2.)
Si p > 0, le quotient de la division euclidienne par 2 vérifie p ÷ 2 < p. Dans l’algorithme,
l’entier p décroit donc strictement à chaque étape, ce qui garantit la terminaison.
L’invariant de boucle qui permet de prouver la correction est le suivant : après chaque étape,
on a an = rx p et p ≥ 0. Nous laissons au lecteur de vérifier que ces conditions sont conservées. En
fin d’itération, on n’a plus p > 0, donc p = 0 et r = an .
15
Exercice 1.3.7 L’algorithme écrit ci-dessus effectue une multiplication inutile à la fin. Rectifier
ce petit défaut (qui affecte la performance mais pas la correction).
TP 1.3.8 Programmer cet algorithme.
1.3.3
Questions d’optimalité
On peut faire un peu mieux au cas par cas
Pour calculer a15 par la méthode dichotomique, il faut c(15) = 6 multiplications. Voici deux
séquences de calcul qui donnent le résultat en 5 multiplications. La première revient à écrire a15 =
(a3 )5 :
x1 := a × a,
x2 := x1 × a,
x3 := x2 × x2 ,
x4 := x3 × x3 ,
x5 := x4 × x2 .
x3 := x2 × a,
x4 := x3 × x3 ,
x5 := x4 × x3 .
La seconde revient à écrire a15 = (a5 )3 .
x1 := a × a,
x2 := x1 × x1 ,
Ces calculs reposent directement sur une factorisation de n. Il existe une méthode générale pour
trouver de telles séquences optimales de calcul, mais elle est compliquée à mettre en oeuvre et le
gain n’est pas énorme (voir le paragraphe suivant pour en être sûr). Disons que l’effort en ce sens
peut être considéré comme rentable si l’on veut calculer souvent a15 . . .
On ne peut pas faire beaucoup mieux en général
Nous allons démontrer que l’on ne peut pas espérer calculer an en moins de log2 n multiplications. La méthode de démonstration consiste à prendre le problème à l’envers et à chercher la plus
grande puissance de a que l’on peut calculer en k multiplications.
On fixe les règles comme suit. On pose x0 := a (qui n’a coûté aucune multiplication). On va
calculer x1 , . . . , xk en utilisant chaque fois une seule multiplication. De plus, le calcul de chaque
xi ne peut faire intervenir que les valeurs déjà calculées : x0 , . . . , xi−1 . A chaque étape, on calcule
donc une puissance xi = a pi . Bien entendu, p0 = 1 (car x0 = a = a1 ) et p1 = 2 (car x1 = a × a = a2 ).
Ensuite, tout ce que l’on peut dire, c’est que xi = x j × xl , donc pi = p j + pl , avec 0 ≤ j, l ≤ i − 1.
Proposition 1.3.9 (i) On a pi ≤ 2i pour tout i = 0, . . . , k.
(ii) En particulier, si l’on peut calculer an en k multiplications, alors n ≤ 2k .
Preuve. - (i) Se prouve par récurrence forte. C’est clair pour i = 0, 1. Pour un i ≥ 2 fixé, supposons
que c’est vrai pour tout indice j ≤ i − 1. On a vu que pi = p j + pl , avec 0 ≤ j, l ≤ i − 1. Par
hypothèse de récurrence (forte), on a p j ≤ 2 j et pl ≤ 2l , d’où :
pi = p j + pl ≤ 2 j + 2l ≤ 2i−1 + 2i−1 = 2i .
(ii) en découle en prenant i = k et n = pk . Et maintenant, pour le résultat qui nous intéresse, on renverse la conclusion :
16
Corollaire 1.3.10 Le nombre de multiplications nécessaires pour calculer an est supérieur ou égal
à log2 n.
Preuve. - D’après la proposition, ce nombre k vérifie n ≤ 2k , donc k ≥ log2 n. Exercice 1.3.11 Pour quelles valeurs de n ≤ 24 le coût c(n) par la méthode dichotomique peut-il
être amélioré ?
1.4
L’algorithme d’Euclide
Le but est de calculer le pgcd (“plus grand commun diviseur”) de deux entiers naturels a et b.
Rappelons que, si l’on note :
D (a) := {m ∈ N | m divise a}
l’ensemble des diviseurs de a, alors le pgcd de a et b est défini comme le plus grand élément de
D (a) ∩ D (b). Cette définition ne tombe en défaut que si a = b = 0 car alors D (a) = D (b) = N et
il n’y a pas de plus grand élément dans D (a) ∩ D (b) ; nous conviendrons que le pgcd de 0 et 0 est
0. Nous noterons a ∧ b le pgcd de a et b. On a les règles : a ∧ b = b ∧ a et a ∧ 0 = a. Si a et b sont
tous deux non nuls, on peut les décomposer en facteurs premiers :
a = pr11 · · · prkk ,
b = ps11 · · · pskk ,
où l’on a mis tous les facteurs premiers qui apparaissent dans a ou dans b, quitte à poser ri := 0 si
pi ne divise que b, resp. si := 0 si pi ne divise que a. On a alors :
min(r1 ,s1 )
a ∧ b = p1
min(rk ,sk )
· · · pk
.
Malheureusement, cette méthode est impraticable car il n’existe aucun algorithme raisonnablement rapide pour déterminer la décomposition en facteurs premiers d’un entier. Il n’est pas question de justifier ici cette affirmation 2 , il faudra donc l’admettre ! En revanche, il existe des algorithmes raisonnables pour calculer le pgcd.
1.4.1
L’algorithme de base
Il s’agit d’un algorithme rudimentaire mais élégant, qui remonte à Euclide. Il repose sur l’idée
suivante :
Lemme 1.4.1 Si 0 < b ≤ a, alors a ∧ b = (a − b) ∧ b.
Preuve. - Si m divise a et b, alors il divise leur différence, d’où :
D (a) ∩ D (b) ⊂ D (a − b) =⇒ D (a) ∩ D (b) ⊂ D (a − b) ∩ D (b).
2. Elle est liée à la théorie de la complexité, laquelle intervient dans l’une des sept “questions à un million de
dollars” posées par l’institut Clay en l’an 2000. Rappelons que l’une des questions (mais pas celle-ci) a été résolue
récemment par le russe Gregory Perelman.
17
Si m divise a − b et b, alors il divise leur somme, d’où :
D (a − b) ∩ D (b) ⊂ D (a) =⇒ D (a − b) ∩ D (b) ⊂ D (a) ∩ D (b).
On a donc D (a) ∩ D (b) = D (a − b) ∩ D (b), d’où la conclusion. Pour calculer le pgcd de a et b, on peut donc, si 0 < b ≤ a, les remplacer par a − b et b,
donc par des nombres plus petits. Si b = 0, on a a ∧ b = a. Si b > a, on inverse les rôles, puisque
a ∧ b = b ∧ a. Voici l’algorithme qui exprime cette description informelle :
x :=
y :=
tant
si
a;
b;
que (x > 0 et y > 0)
(x < y) alors
y := y - x;
sinon
x := x - y;
fin si;
fin tant que;
si (x = 0) alors
rendre (y);
sinon
rendre (x);
fin si;
La terminaison est garantie parce qu’à chaque étape x + y diminue strictement. L’invariant de
boucle qui permet de prouver la correction découle du lemme : à chaque étape, on a x ∧ y = a ∧ b
et x, y ≥ 0. En sortie de boucle, on a soit x = 0 d’où x ∧ y = y, soit y = 0 d’où x ∧ y = x.
Nous n’analyserons pas le coût de cet algorithme, qui n’est pas très facile à calculer, ni même
à énoncer. On peut montrer que le cas le pire est celui qui est traité dans l’exercice suivant.
Exercice 1.4.2 On rappelle que la suite des nombres de Fibonacci est définie par les conditions
initiales : F0 := 0 et F1 := 1 ; et par la relation de récurrence à deux pas : Fn+1 := Fn + Fn−1 .
Appliquer l’algorithme ci-dessus à a := Fn+1 et b := Fn .
TP 1.4.3 Programmer cet algorithme.
1.4.2
L’algorithme classique
Dans l’algorithme de base, si b est beaucoup plus petit que a, on remplace a par a − b un grand
nombre de fois, ce qui revient en fait à effectuer une division euclidienne de a par b. La version
classique de l’algorithme d’Euclide incorpore directement cette division euclidienne :
x := a;
y := b;
tant que (y > 0)
(q,r) := divEucl(x,y);
18
x := y;
y := r;
fin tant que;
rendre (x);;
A chaque étape, y diminue strictement (il est remplacé par le reste de la division euclidienne par
y), ce qui garantit la terminaison de l’algorithme. Par ailleurs, l’invariant de boucle est : y ≥ 0 et
x ∧ y = a ∧ b (pour la preuve, voir l’exercice ci-dessous) qui donne en sortie x = x ∧ 0 = a ∧ b, d’où
la correction. L’analyse du coût est difficile, mais on peut montrer que le cas le pire est le même
que dans la version de base (avec les nombres de Fibonacci).
Exercice 1.4.4 Si (q, r) := diveucl(x, y), montrer que x ∧ y = y ∧ r. En déduire la validité de l’invariant de boucle ci-dessus.
TP 1.4.5 Programmer cet algorithme.
1.4.3
L’algorithme amélioré
A chaque étape de l’algorithme, x et y sont des “combinaisons linéaires à coefficients entiers
relatifs de a et b”, autrement dit, on peut écrire x = sa + tb et y = ua + vb, avec s,t, u, v ∈ Z. C’est
évident au départ, puisqu’ils sont initialisés avec les valeurs x := a = 1.a+0.b et y := b = 0.a+1.b.
Cela reste vrai au cours de l’exécution de l’algorithme, puisque x est remplacé par y et que y est
remplacé par x − qy avec q ∈ Z. Comme à la fin de l’algorithme on a x = a ∧ b, on en déduit le
théorème de Bézout : il existe des entiers relatifs s,t tels que a ∧ b = sa + tb. Naturellement, on ne
peut espérer trouver s et t naturels puisque le pgcd est plus petit que a et que b.
L’algorithme suivant exploite cette idée pour calculer les “coefficients de Bézout” s,t en même
temps que le pgcd :
x := a;
y := b;
s := 1; t := 0;
u := 0; v := 1;
tant que y > 0
(q,r) := divEucl(x,y);
x := y;
y := r,
w := u; u := s - q*u;
w := v; v := t - q*v;
fin tant que;
rendre (x,s,t);;
s := w;
t := w;
La terminaison se prouve comme ci-dessus. Pour prouver la correction, on ajoute à l’invariant de
boucle les égalités x = sa + tb et y = ua + vb.
Exercice 1.4.6 A quoi sert la variable w dans cet algorithme ?
TP 1.4.7 Programmer cet algorithme.
19
1.5
Suppléments facultatifs
Résolution de l’équation ax + by = c.
Nombres premiers. Le crible d’Eratosthène.
20
Chapitre 2
Arithmétique modulaire et applications
2.1
2.1.1
Congruences
L’ensemble Z/mZ
On fixe un entier naturel m ≥ 2.
Définition 2.1.1 Soient a, b ∈ Z. On dit que a est congru à b modulo m si b − a est multiple de m ;
on écrit a ≡ b (mod m) :
a ≡ b (mod m) ⇐⇒ ∃k ∈ Z : b − a = km.
Proposition 2.1.2 Pour que les entiers a et b soient congrus modulo m, il faut, et il suffit, que
leurs divisions euclidiennes par m donnent le même reste.
Preuve. - Si a = qm + r et si b = q0 m + r, alors b − a = km avec k = q0 − q, donc a ≡ b (mod m).
Réciproquement, supposons que a ≡ b (mod m) et soit k ∈ Z tel que b − a = km. Si la division
euclidienne de a par m s’écrit a = qm + r, 0 ≤ r ≤ m − 1, alors b = (q + k)m + r, de sorte que r est
le reste de la division euclidienne de b par m. La relation de congruence modulo m vérifie les trois propriétés suivantes :
Réflexivité : Quel que soit a ∈ Z, on a a ≡ a (mod m).
Symétrie : Quels que soient a, b ∈ Z, si a ≡ b (mod m), alors b ≡ a (mod m).
Transitivité : Quels que soient a, b, c ∈ Z, si a ≡ b (mod m) et si b ≡ c (mod m), alors a ≡ c (mod m).
On résume ces propriétés en disant que la relation de congruence modulo m est une relation d’équivalence. Cela permet de regrouper les éléments de Z en classes d’équivalence, également appelées
dans ce cas classes de congruence (on ne précise pas toujours le “module” m) : on dit que a et b
sont dans la même classe s’ils sont congrus modulo m.
Exemple 2.1.3 Dans le cas où m = 2, la relation de congruence est la relation “a et b ont même
parité”. Il y a deux classes d’équivalence : celle des entiers pairs et celle des entiers impairs.
On notera a (mod m) ou a la classe de a ; dans le second cas, la notation ne précise pas le
module m, mais on espère que cela ne causera pas de confusion. La principale règle à retenir est
la suivante :
a = b ⇐⇒ a ≡ b (mod m)
21
Remarque 2.1.4 Ce n’est pas n’importe quelle relation entre entiers qui permettrait de les regrouper en classes ! Par exemple, aucune des relations “a est différent de b”, “a est supérieur à b”, “a
divise b”, n’est une relation d’équivalence et ces relations ne permettent pas un tel regroupement.
Bien que l’ensemble Z des entiers relatifs soit infini, il n’y a qu’un nombre fini de classes de
congruence. Si m = 2, on a vu qu’il y en avait deux. Si m = 3, il y a la classe de 0, notée 0 ; puis il
y a la classe de 1, notée 1 ; puis il y a celle de 2, notée 2 ; puis celle de 3, notée 3 . . . mais c’est la
même que celle de 0 puisque 3 ≡ 0 (mod 3). De même, on constate que 4 = 1, que 5 = 2, etc. Si
l’on part “à gauche” de 0, rien de neuf : −1 = 2 puisque −1 ≡ 2 (mod 3). En fin de compte, il n’y
a que trois classes : 0, 1 et 2. Il y en a bien trois car par exemple 0 6= 1 puisque 1 6≡ 0 (mod 3).
Proposition 2.1.5 (i) Pour tout a ∈ Z, il existe un unique b ∈ {0, . . . , m − 1} tel que a = b.
(ii) Il y a exactement m classes de congruence modulo m, qui sont 0, 1, . . . , m − 1.
Preuve. - (i) L’unique b dont on affirme l’existence est tout simplement le reste de la division euclidienne de a par m.
(ii) C’est une conséquence immédiate de (i). On notera Z/mZ l’ensemble des classes de congruence modulo m. On a donc :
Z/mZ = {0, 1, . . . , m − 1}
Par conséquent :
card Z/mZ = m.
Pratiquement, si l’on veut travailler avec un élément x de Z/mZ, c’est-à-dire avec une classe de
congruence modulo m, on choisit un entier a ∈ Z dont x est la classe : x = a, et l’on travaille avec
a (voir un peu plus bas l’exemple de l’addition des classes de congruence). On dit que a est un
représentant de la classe x.
Exemple 2.1.6 On a Z/2Z = {0, 1}. Les entiers −8 et 39 sont des représentants respectifs de ces
deux classes.
On a Z/3Z = {0, 1, 2}. Les entiers 39 et −8 sont des représentants respectifs des deux premières
classes, l’entier 2000 est un représentant de la troisième.
Remarque 2.1.7 La notation est ambigue, puisque l’on ne précise pas le module. Ainsi, dans
Z/2Z, on a 0 = 2 alors que c’est faux dans Z/3Z.
2.1.2
Le groupe (Z/mZ, +)
Proposition 2.1.8 Soient a, a0 , b, b0 ∈ Z. On suppose : a ≡ a0 (mod m) et b ≡ b0 (mod m). Alors
a + b ≡ a0 + b0 (mod m).
Preuve. - Si a0 − a = km et b0 − b = lm, alors (a0 + b0 ) − (a + b) = (k + l)m. Cette propriété est appelée compatibilité de la relation de congruence avec l’addition. On en
déduit immédiatement :
Corollaire 2.1.9 Soient a, a0 , b, b0 ∈ Z. On suppose : a = a0 et b = b0 . Alors a + b = a0 + b0 .
22
Ce corollaire permet de définir une “loi de composition interne”, en l’occurrence une addition,
sur l’ensemble Z/mZ des classes de congruence modulo m. On procède de la façon suivante.
Soient x et y deux éléments de Z/mZ. On choisit un représentant a ∈ Z de x et un représentant
b ∈ Z de y. Alors, si c := a + b, on pose x + y := c. Cette définition pose un problème : obtiendraiton le même résultat si l’on avait choisi d’autres représentants ? (Pour chaque classe, il y a une
infinité de représentants !) Pour le savoir, on choisit un autre représentant a0 ∈ Z de x et un autre
représentant b0 ∈ Z de y, et l’on calcule c0 := a0 + b0 . Logiquement, l’application de la “définition”
ci-dessus donne tout aussi bien x + y := c0 . Pour que ces deux calculs soient cohérents, il faut être
absolument certain que c = c0 . heureusement, le corollaire ci-dessus nous le garantit. En effet,
a = a0 (les deux sont égaux à x) et b = b0 (les deux sont égaux à y), donc, en vertu du corollaire,
a + b = a0 + b0 , c’est-à-dire justement c = c0 . L’addition sur Z/mZ est donc bien définie. Son mode
d’emploi tient principalement dans la règle suivante, qui traduit sa définition :
a+b = a+b
Voici à titre d’exemple les tables d’addition modulo m pour m = 2, 3, 4, 5, 6 :
+
0 1
0
0 1
1
1 0
+
0 1 2
0
0 1 2
1
1 2 0
2
2 0 1
+
0 1 2 3
0
0 1 2 3
1
1 2 3 0
2
2 3 0 1
3
3 0 1 2
+
0 1 2 3 4
0
0 1 2 3 4
1
1 2 3 4 0
2
2 3 4 0 1
3
3 4 0 1 2
4
4 0 1 2 3
+
0 1 2 3 4 5
0
0 1 2 3 4 5
1
1 2 3 4 5 0
2
2 3 4 5 0 1
3
3 4 5 0 1 2
4
4 5 0 1 2 3
5
5 0 1 2 3 4
L’addition dans Z/mZ vérifie les propriétés suivantes :
Commutativité : Pour tous x, y ∈ Z/mZ, on a x + y = y + x.
Associativité : Pour tous x, y, z ∈ Z/mZ, on a (x + y) + z = x + (y + z).
Elément neutre : Pour tout x ∈ Z/mZ, on a x + 0 = 0 + x = x.
Symétrique : Si x = a, l’élément x0 := −a vérifie : x + x0 = x0 + x = 0.
On résume ces propriétés en disant que l’ensemble Z/mZ muni de l’addition est un groupe commutatif. Pratiquement, cela signifie que le calcul avec les classes de congruence ressemble beaucoup
au calcul sur les nombres usuels. Il y a bien quelques différences auxquelles il faut prendre garde ;
on les mentionnera à la volée.
Revenons sur le symétrique. Il est facile de prouver que si a = a0 , alors −a = −a0 . On peut
donc poser −a := −a. Si x = a, l’élément x0 de la dernière propriété ci-dessus est tout simplement
x0 = −a : c’est l’opposé de x. Son existence permet de définir y − x := y + (−x) : c’est l’unique z
tel que x + z = y. On a les règles pratiques :
−a = −a et a − b = a − b
23
2.1.3
L’anneau (Z/mZ, +, ×)
Nous allons définir une multiplication sur Z/mZ selon un processus très similaire à celui de
l’addition : nous irons donc un peu plus vite.
Proposition 2.1.10 Soient a, a0 , b, b0 ∈ Z. On suppose : a ≡ a0 (mod m) et b ≡ b0 (mod m). Alors
ab ≡ a0 b0 (mod m).
Preuve. - Si a0 − a = km et b0 − b = lm, alors a0 b0 − ab = (la + kb + klm)m. La relation de congruence est donc compatible avec la multiplication, d’où :
Corollaire 2.1.11 Soient a, a0 , b, b0 ∈ Z. On suppose : a = a0 et b = b0 . Alors ab = a0 b0 .
Cela permet de définir la multiplication sur Z/mZ de la façon suivante. Soient x et y deux
éléments de Z/mZ. On choisit un représentant a ∈ Z de x et un représentant b ∈ Z de y. Alors, si
c := ab, on pose xy := c. Cette définition est cohérente en vertu du corollaire. On a la règle :
ab = ab
Voici à titre d’exemple les tables de multiplication modulo m pour m = 2, 3, 4, 5, 6 :
×
0 1
0
0 0
1
0 1
×
0 1 2
0
0 0 0
1
0 1 2
2
0 2 1
×
0 1 2 3
0
0 0 0 0
1
0 1 2 3
2
0 2 0 2
3
0 3 2 1
×
0 1 2 3 4
0
0 0 0 0 0
1
0 1 2 3 4
2
0 2 4 1 3
3
0 3 1 4 2
4
0 4 3 2 1
×
0 1 2 3 4 5
0
0 0 0 0 0 0
1
0 1 2 3 4 5
2
0 2 4 0 2 4
3
0 3 0 3 0 3
4
0 4 2 0 4 2
5
0 5 4 3 2 1
La multiplication dans Z/mZ vérifie les propriétés suivantes :
Commutativité : Pour tous x, y ∈ Z/mZ, on a xy = yx.
Associativité : Pour tous x, y, z ∈ Z/mZ, on a (xy)z = x(yz).
Elément neutre : Pour tout x ∈ Z/mZ, on a x1 = 1x = x.
Distributivité : Pour tous x, y ∈ Z/mZ, on a x(y + z) = xy + xz et (y + z)x = yx + zx.
Ajoutons que 0 est un élément absorbant : pour tout x ∈ Z/mZ, on a x0 = 0x = 0. On résume ces
propriétés en disant que Z/mZ muni de l’addition et de la multiplication est un anneau commutatif.
Il y a cependant deux propriétés qui manquent à l’appel : l’intégrité et l’existence d’un inverse. Par exemple, dans Z/4Z, l’élément 2 n’est pas nul, mais 2 × 2 = 0. De plus, aucun élément
x ∈ Z/4Z ne vérifie 2 × x = 1. De même, dans Z/6Z, les éléments 2 et 3 ne sont pas nuls, mais
2 × 3 = 0. De plus, aucun élément x ∈ Z/6Z ne vérifie 2 × x = 1, ni d’ailleurs 3 × x = 1. En
revanche, dans Z/2Z, Z/3Z et Z/5Z, on vérifie par simple examen des tables de multiplication
que le produit de deux éléments non nuls est non nul (on dit que ces anneaux sont intègres) ; et
24
que tout élément non nul x admet un inverse x0 , c’est-à-dire que x × x0 = x0 × x = 1 (on dit que
ces anneaux sont des corps). La différence la plus visible entre 4, 6 d’une part, 2, 3, 5 d’autre part
est que chacun de ces derniers est premier, i.e. il n’admet pas d’autre diviseur que lui-même et 1.
Nous allons voir que c’est bien la raison de cette différence de propriétés de la multiplication.
Nous dirons que x ∈ Z/mZ est diviseur de zéro s’il existe y 6= 0 tel que xy = 0 ; et que x est
inversible s’il existe x0 ∈ Z/mZ tel que xx0 = 1.
Théorème 2.1.12 (i) Si m est premier, l’anneau Z/mZ est intègre (autrement dit, 0 est le seul
diviseur de zéro) ; et c’est un corps (autrement dit, tout x 6= 0 est inversible).
(ii) Si m n’est pas premier, l’anneau Z/mZ n’est ni intègre ni un corps.
Preuve. - C’est en fait un cas particulier de la proposition 2.1.14 que nous prouverons au paragraphe suivant. L’exemple le plus fondamental est celui où m = 2. Le corps Z/2Z est parfois noté F2 .
TP 2.1.13 Programmer le calcul dans l’anneau Z/mZ, y compris le calcul de l’inverse d’un élément quand m est premier.
2.1.4
Le groupe (Z/mZ)∗ , ×
Proposition 2.1.14 Soit a ∈ {0, . . . , m − 1} et soit d := a ∧ m le pgcd de a et m.
(i) Si d > 1, alors a est un diviseur de zéro et n’est pas inversible dans Z/mZ.
(ii) Si d = 1, alors a n’est pas un diviseur de zéro et a est inversible dans Z/mZ.
Preuve. - (i) On écrit a = da0 et m = dm0 . Puisque d > 1, on a 0 < m0 < m donc m0 6≡ 0 (mod m)
donc m0 6= 0. Par ailleurs :
a m0 = am0 = da0 m0 = a0 m = 0.
Comme m0 6= 0, on en déduit que a est un diviseur de zéro. D’autre part, si a était inversible, on
pourrait écrire ab = 1, d’où ab = 1 + km, d’où d(a0 b − km0 ) = 1, ce qui est impossible puisque
d > 1.
(ii) D’après le théorème de Bézout, il existe k, b ∈ Z tels que ab − km = 1. Alors ab = 1 et a est
bien inversible dans Z/mZ. Supposons alors que ax = 0. En multipliant les deux membres de cette
égalité par b, on trouve que x = 0, ce qui montre que a n’est pas un diviseur de zéro. On est conduit à distinguer les éléments inversibles de Z/mZ, c’est-à-dire (d’après la proposition) les éléments de la forme a, où a ∈ {0, . . . , m − 1} et où a ∧ m = 1 (autrement dit, a et m
sont premiers entre eux). On note (Z/mZ)∗ l’ensemble de ces éléments et φ(m) := card(Z/mZ)∗
le nombre de ces éléments. La fonction φ est l’indicatrice d’Euler.
En examinant, les lignes (ou les colonnes) où figure 1 les tables de multiplication, on trouve par
exemple : (Z/2Z)∗ = {1}, d’où φ(2) = 1 ; (Z/3Z)∗ = {1, 2}, d’où φ(3) = 2 ; (Z/4Z)∗ = {1, 3},
d’où φ(4) = 2 ; (Z/5Z)∗ = {1, 2, 3, 4}, d’où φ(5) = 4 ; et (Z/6Z)∗ = {1, 5}, d’où φ(6) = 2.
Si m est premier, il est clair que (Z/mZ)∗ = {1, . . . , m − 1}, d’où φ(m) = m − 1.
25
Le théorème qui suit est d’une importance cruciale dans les deux applications que nous avons
en vue : générateurs pseudo-aléatoires (voir la section 2.2) et méthode RSA de cryptographie à clé
publique (voir la section 2.3).
Théorème 2.1.15 (i) Pour tout x ∈ (Z/mZ)∗ , on a xφ(m) = 1.
(ii) Pour tout a ∈ Z tel que a ∧ m = 1, on a aφ(m) ≡ 1 (mod m).
(iii) Si m est premier et si a ∈ Z n’est pas multiple de m, alors am−1 ≡ 1 (mod m).
Preuve. - (i) C’est un cas particulier du théorème de Lagrange, qui sera démontré dans le cours
d’algèbre de L2.
(ii) Ce théorème, dû à Euler, est simplement la traduction de (i) en termes de congruences.
(iii) Ce cas particulier de (ii) est le petit théorème de Fermat. Exercice 2.1.16 Si m = pr , où p est premier, alors φ(m) = pr − pr−1 . Si m = pq, où p et q sont
premiers distincts, alors φ(m) = (p − 1)(q − 1).
TP 2.1.17 Programmer, pour tout m, la vérification du théorème 2.1.15 : recherche de tous les
éléments de (Z/mZ)∗ , calcul de φ(m) et calcul de xφ(m) pour x ∈ (Z/mZ)∗ .
2.2
Générateurs pseudo-aléatoires
L’un des pères fondateurs de l’informatique, John von Neumann, a dit : “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” 1 . Nous tenterons donc plus modestement de simuler l’aléatoire. Dans un premier paragraphe, nous décrirons
des moyens de produire de longues suites de nombres variés ; et dans un deuxième paragraphe,
des moyens de tester si ces suites ont l’air aléatoire. Il y a, pour ces deux phases, une théorie riche
et compliquée (et amusante). Nous ne l’effleurerons même pas : il n’y a ici que quelques recettes
faciles à mettre en oeuvre.
Vu de l’extérieur, un générateur (pseudo)-aléatoire est un programme qui rend un nombre
chaque fois qu’on l’appelle. Vu de l’intérieur, ce programme calcule en fait les termes d’une suite
numérique (xn ). Chaque fois qu’on l’appelle, il renvoie un terme ; d’un appel sur l’autre, il passe
au terme suivant. Autrement dit, entre deux appels, le programme garde trace du rang du dernier
terme rendu : l’indice n est une variable rémanente, et il faut donc savoir programmer de telles
variables. Le plus souvent, il s’agit de suites définies par récurrence : xn+1 = f (xn ). Dans ce cas,
la variable rémanente contient la dernière valeur de xn qui a été rendue. Dans notre approche élémentaire, nous ne traiterons pas ce problème : nous considèrerons simplement des programmes
qui calculent f (x), donc chaque nouveau terme en fonction du précédent.
Il existe deux types principaux de générateurs aléatoires : ceux qui rendent des nombres réels
entre 0 et 1 ; et ceux qui rendent des entiers entre 0 et m − 1, l’entier m ≥ 2 ayant été passé en
argument. Nous ne nous occuperons que du deuxième type.
Exercice 2.2.1 Comment utiliser un générateur de l’un des deux types pour émuler l’autre ?
1. “Quiconque envisage des méthodes arithmétiques pour produire des nombres aléatoires est, bien entendu, en état
de péché.”
26
2.2.1
Générateurs linéaires congruentiels
Nous supposons fixé le module m ≥ 2 (argument d’appel). Au lieu de considérer une suite
d’entiers compris entre 0 et m − 1, nous considèrerons une suite d’éléments de Z/mZ. Le format
général de cette suite est donné par la relation de récurrence :
∀n ∈ N , xn+1 := axn + b.
Il faut donc choisir a, b, x0 ∈ Z/mZ. On ne prendra évidemment pas a := 0 car la suite serait
constante à partir du rang 1 et n’aurait pas du tout l’air aléatoire. On ne prendra pas non plus
en général a = 1, car on aurait xn = x0 + nb, et l’on repèrerait trop facilement une régularité.
(Attention : la notation nb désigne ici la somme de n termes égaux à b avec l’addition de Z/mZ.)
Cas d’un module premier
Supposons m premier. Puisque l’on a exclu le cas où a = 1, l’élément 1 − a est inversible
dans Z/mZ et l’on va pouvoir appliquer la méthode vue en terminale pour les suites arithméticogéométriques. On cherche un “point fixe” u :
u = au + b ⇐⇒ (1 − a)u = b ⇐⇒ u = b(1 − a)−1 ,
où l’on note x−1 l’inverse d’un élément (inversible) de Z/mZ. La relation de récurrence devient
alors :
xn+1 := axn + b ⇐⇒ (xn+1 − u) := a(xn − u),
et l’on en déduit xn − u = an (x0 − u), donc :
∀n ∈ N , xn = an (x0 − u) + u.
(Attention : la notation an désigne ici le produit de n facteurs égaux à a avec la multiplication de
Z/mZ.) Finalement, à un décalage près de valeur u, tout se passe comme si la suite était géométrique. Pour la suite de ce paragraphe, nous supposons donc que b = u = 0 et donc que xn = an x0 .
On prendra évidemment x0 6= 0, sinon la suite serait constante et n’aurait pas du tout l’air
aléatoire. Finalement, on est donc conduit à examiner la suite des an x0 . Pour savoir si elle a l’air
aléatoire, nous décrirons plus loin des tests empiriques. On peut déjà se demander si elle ne boucle
pas trop vite. En effet, le petit théorème de Fermat nous dit que am−1 = 1 et donc que, si n =
q(m − 1) + r, on a an = (am−1 )q ar = ar , d’où xn = xr : cela signifie que la suite se reproduit avec
une période (m − 1). Mais ce n’est pas nécessairement la période de cette suite.
Exemple 2.2.2 Prenons m := 7. Tout a ∈ (Z/7Z)∗ vérifie a6 = 1, donc la suite des an x0 se reproduit à coup sûr avec une période 6. Mais si l’on prend par exemple a := 2, on a a3 = 1 et la période
tombe à 3. Il vaut mieux prendre a := 3 qui est tel que a0 = 1, a1 = 3, a2 = 2, a3 = 6, a4 = 4,
a5 = 5 sont distincts et qui fournit donc une suite aussi longue que possible.
Dans tous les cas, voici ce dont est sûr quel que soit a ∈ (Z/mZ)∗ :
1. Il existe un plus petit entier n ≥ 1 tel que an = 1.
2. Cet entier est un diviseur de m − 1.
27
3. La suite (xn ) est de période n, elle admet n termes distincts.
L’entier n est appelé ordre de l’élément a ∈ (Z/mZ)∗ . Et maintenant, comme dans l’exemple
ci-dessus, il y a moyen de choisir un élément d’ordre optimal :
Théorème 2.2.3 Il existe un élément a ∈ (Z/mZ)∗ d’ordre m − 1.
Preuve. - Ce sera prouvé dans le cours d’algèbre de L2. Cas d’un module primaire
Supposons m primaire, c’est-à-dire puissance d’un nombre premier : n = pr , où p est premier
et r ≥ 2. Dans ce cas, il n’est pas aussi facile d’étudier une suite arithmético-géométrique générale, aussi prendrons nous d’emblée b := 0. Et, bien entendu, on suppose toujours a 6= 0, 1 et x0 6= 0.
Si a est la classe d’un multiple de p, alors ar est la classe d’un multiple de pr , donc ar = 0.
Dans ce cas, la suite est stationnaire en 0 et donc très peu aléatoire. Nous supposons donc que a
est la classe d’un entier non multiple de p. Mais un tel entier n’a pas de diviseur commun avec
pr = m, donc a est inversible : on a encore a ∈ (Z/mZ)∗ . la situation est analogue à celle décrite
plus haut :
1. Il existe un plus petit entier n ≥ 1 tel que an = 1.
2. Cet entier est un diviseur de φ(m) = pr − pr−1 .
3. La suite (xn ) est de période n, elle admet n termes distincts.
On dit encore que n est l’ordre de a. En ce qui concerne le choix d’un élément d’ordre optimal, la
situation est un tout petit peu plus compliquée :
Théorème 2.2.4 (i) Si p est impair ou si m est égal à 2 ou 4, il existe un élément a ∈ (Z/mZ)∗
d’ordre φ(m).
(ii) Si m = 2r , r ≥ 3, on a φ(m) = 2r−1 . Il n’existe pas d’élément d’ordre 2r−1 ; l’ordre optimal est
2r−2 . C’est l’ordre de l’élément 3 (mais pas uniquement de ce dernier).
Exercice 2.2.5 Démontrer que l’ordre d’un élément de (Z/mZ)∗ divise φ(m).
TP 2.2.6 Trouver dans (Z/mZ)∗ un élément d’ordre optimal.
2.2.2
Quelques tests
Le fait que le générateur pseudo-aléatoire ait une grande période n’est pas un critère suffisant
de bonne qualité. Par exemple, pour m = 2, un tel générateur peut être assimilé à un simulateur
de tirage à pile ou face (mettons que pile = 1 et face = 0). S’il tire avec régularité (109 − 1) fois
pile et une fois face, sa période sera 109 (ce qui n’est pas mal !) mais on le trouvera suspect. Nous
donnons ici, sans justification autre que l’intuition, quelques tests faciles à comprendre et à mettre
en oeuvre.
28
Tests empiriques de fréquence
La première vérification, inspirée de l’exemple ci-dessus, est celle des fréquences : dans une
longue séquence de tirages successifs, chacune des valeurs possibles 0, . . . , m − 1 devrait apparaitre avec une fréquence proche de 1/m. Le test consiste donc à tirer N valeurs, N étant “grand” ;
à compter, pour chaque i = 0, . . . , m − 1 le nombre Ni de fois que l’on a tiré i ; puis à vérifier qu’aucun des nombres Ni /N n’est “trop différent” de 1/m. Par exemple, on peut calculer le maximum
des valeurs absolues |Ni /N − 1/m| et déclarer l’échec du test si ce maximum est supérieur à une
certaine valeur limite α fixée d’avance. Au lieu de calculer le maximum des |Ni /N − 1/m|, on peut
également calculer leur somme. (Le test du chi-deux, décrit plus loin, propose une approche plus
rigoureuse.)
Un autre test plus subtil repose sur l’idée que chaque terme de la suite devrait sembler indépendant du précédent. Pour le vérifier, on tirerait 2N fois, d’où une suite x0 , . . . , x2N−1 ; puis
on examinerait chacun des N couples (x2k , x2k+1 ), pour k = 0, . . . , N − 1 : et l’on compterait pour
tout couple (i, j) ∈ {0, . . . , m − 1}2 le nombre Ni, j de fois qu’il apparait parmi les (x2k , x2k+1 ). Ce
nombre ne devrait pas être “trop différent” de N/m2 .
Enfin, on peut généraliser et tester la fréquence des r-uples : on tire rN fois, on examine les ruples successifs (xrk , xrk+1 , . . . , xr(k+1)−1 ), on compte le nombre Ni1 ,...,ir de fois qu’apparait chacun
des r-uples possibles (i1 , . . . , ir ) ∈ {0, . . . , m − 1}r et l’on vérifie que, dans l’ensemble, les Ni1 ,...,ir
ne sont pas “trop différents” de rN/mr .
Exercice 2.2.7 Serait-il intéressant de calculer la somme des (Ni /N −1/m) (sans valeur absolue) ?
TP 2.2.8 Programmer la mise en oeuvre de ces tests.
Le test du chi-deux
Il s’agit d’une manière scientifiquement fondée de quantifier le jugement “les fréquences ne
s’écartent pas trop de la normale”. Que le lecteur se rassure, nous n’en exposerons pas la justification théorique ! De plus, nous n’en décrirons le fonctionnement que dans le cas du test de
fréquence simple : les Ni /N s’écartent-ils de 1/m ? On calcule la variance :
m−1
V := mN
∑ (Ni /N − 1/m)2 .
i=0
Puis on utilise la table ci-dessous (voir en haut de la page suivante). L’entier ν désigne le nombre
de “degrés de liberté”, dans notre cas, m − 1 ; en effet, les Ni /N ne sont pas indépendants les uns
des autres : leur somme est nécessairement 1. Supposons que m = 16, i.e. que l’on ait tiré des
nombres entre 0 et 15 : donc ν = 15. D’après la table, on a V ≤ 11, 04 avec une probabilité voisine
de 25%. Pour que cette règle soit valable, il faut que le nombre de tirages soit assez grand. Dans
notre cas, une règle pratique est N > 5m.
TP 2.2.9 Programmer la mise en oeuvre de ce test.
29
Méthode de Monte-Carlo à l’endroit et à l’envers
La “méthode de monte-Carlo” permet de calculer des intégrales à l’aide de nombres aléatoires.
Nous allons l’utiliser à l’envers pour vérifier que des nombres sont aléatoires à l’aide d’intégrales.
En fait, ces intégrales n’apparaitront ici qu’en tant qu’aires de parties du plan.
Le principe est le suivant. On choisit m assez grand et l’on tire deux entiers au hasard a, b
dans {0, . . . , m − 1}. Le couple (x, y) := (a/m, b/m) désigne donc un point du carré K := [0, 1]2 ,
dont l’aire est 1. Soit maintenant X une partie de K d’aire A. On peut estimer que la probabilité
que le point (x, y) soit dans X est A. Si donc on tire N fois de tels couples, le nombre de ceux qui
“tombent” dans X ne devrait pas être “trop différent” de NA.
Exercice 2.2.10 On suppose un étang circulaire inscrit dans une parcelle carrée : autrement dit, le
cercle et le carré ont même centre et le diamètre du cercle est égal au côté du carré. Des cloches
de Pâques 2 larguent en grand nombre des oeufs en chocolat sur toute la campagne environnante.
Montrer que, parmi les oeufs tombés dans la parcelle, la proportion de ceux récupérés par les
poissons est d’environ π/4.
TP 2.2.11 Programmer la mise en oeuvre de ce test.
2. Dans la version historique de cet exemple, il s’agissait de tirs de canon.
30
2.3
Cryptographie
2.3.1
Petit préliminaire théorique
Lemme 2.3.1 Soient u et v deux entiers premiers entre eux et soit b un entier multiple de u et de
v. Alors b est multiple de uv.
Preuve. - Par hypothèse, il existe des entiers u0 et v0 tels que b = uu0 = vv0 . D’après le théorème de
Bézout, il existe des entiers k et l tels que ku + lv = 1. Alors :
b = kub + lvb
= kuvv0 + lvuu0
= uv(kv0 + lu0 ).
Proposition 2.3.2 Soient p et q deux entiers distincts. Soient n := pq et n0 := (p − 1)(q − 1). Soit
enfin m ≥ 2 un entier tel que :
m ≡ 1 (mod n0 ).
Alors :
∀a ∈ Z , am ≡ a
(mod n).
Preuve. - Pour montrer que b := am − a est multiple de n = pq, il suffit, d’après le lemme, de
montrer qu’il est multiple de p et multiple de q. Les deux nombres p et q jouant un rôle symétrique,
nous ne prouverons que la première assertion. Soit donc a ∈ Z.
– Si a est multiple de p, alors am aussi, et am − a également. On a donc bien am ≡ a (mod p)
dans ce cas.
– Si a n’est pas multiple de p, notant m = 1 + k(p − 1)(q − 1), on déduit du petit théorème de
Fermat les congruences :
a p−1 ≡ 1 (mod p) =⇒ ak(p−1)(q−1) ≡ 1 (mod p)
=⇒ a1+k(p−1)(q−1) ≡ a (mod p)
=⇒ am ≡ a (mod p),
qui est la congruence voulue.
Remarque 2.3.3 L’entier n0 n’est autre que φ(n) et le théorème d’Euler nous assure que, si a est
0
premier avec n (i.e. s’il n’est divisible ni par p ni par q), alors an ≡ 1 (mod n), d’où l’on déduit
sans peine que am ≡ a (mod n). On pourrait donc prouver la proposition en partant de là : il
resterait à examiner les cas où a est divisible par p ou q.
Exercice 2.3.4 Etendre la proposition au cas de r nombres premiers deux à deux distincts.
31
2.3.2
La méthode RSA
La méthode RSA de cryptographie à clé publique a été inventée en 1978 par Ron Rivest, Adi
Shamir et Leonard Adleman du MIT. Sa mise en oeuvre suppose le choix d’un module n, d’une
clé publique (e, n) et d’une clé secrète (d, n). Les propriétés requises sont les suivantes :
1. L’entier naturel n est assez grand pour que l’on puisse facilement coder (voir la remarque
ci-dessous) tout message sous la forme d’une suite d’entiers de {0, . . . , n − 1}.
2. Les entiers naturels d et e vérifient la propriété :
∀a ∈ Z , ade ≡ a
(mod n).
Remarque 2.3.5 Nous distinguons ici le codage du cryptage. Le codage est simplement la mise
du texte sous une forme adaptée à l’algorithme. Par exemple, chaque caractère du message à
transmettre est représenté par un octet et le message est tronçonné en paquets d’octets de tailles
telles que l’on puisse les représenter par un entier M ∈ {0, . . . , n − 1}. Le problème du cryptage
est alors, pour l’émetteur du message, de remplacer M par un entier M 0 := C(M) ∈ {0, . . . , n − 1}
(la lettre C est ici pour “cryptage”), dont le commun des mortels ne saura que faire, mais que le
destinataire du message saura reconvertir en M := D(M 0 ) (la lettre D est ici pour “décryptage”).
La clé publique (e, n) et la clé secrète (d, n) étant données, le principe est le suivant. Leur
détenteur diffuse publiquement ( !) la clé publique (e, n) et garde par devers lui ( !) la clé secrète
(d, n). Chaque fois que quelqu’un veut lui envoyer un message secret M ∈ {0, . . . , n − 1} :
1. Il crypte M selon la formule M 0 := C(M) := M e (mod n).
2. Le destinataire décrypte M 0 selon la formule M := D(M 0 ) := (M 0 )d (mod n).
Ici, par abus de notation, M e (mod n) désigne le reste de la division de M e par n, et similairement
pour (M 0 )d (mod n). En fait, ces calculs peuvent s’effectuer relativement vite par exponentiation
rapide dans Z/nZ. La méthode RSA est correcte en vertu du calcul :
D(C(M)) = M de
(mod n) = M.
Il reste à voir comment on détermine les clés publique et secrète :
1. On choisit deux grands nombres premiers distincts p et q, et l’on pose n := pq.
2. On choisit un entier e premier avec n0 := (p − 1)(q − 1) ni trop grand ni trop petit.
3. On détermine un entier d tel que de ≡ 1 (mod n0 ) à l’aide de l’algorithme d’Euclide étendu.
Cette méthode est praticable parce qu’il est “plutôt facile” de trouver des grands nombres
premiers. Si l’on savait aussi facilement factoriser n, la méthode de cryptage serait facile à casser.
Mais on ne sait pas factoriser facilement les grands nombres, et, depuis 1978, on n’a pas trouvé
non plus d’autres attaques efficaces contre RSA.
TP 2.3.6 Programmer la mise en oeuvre de l’algorithme RSA. On choisira p et q dans une table.
2.4
Suppléments facultatifs
Recherche de la période (méthode de Brent).
Résolution de l’équation ax ≡ b (mod m). Résolution simultanée (lemme chinois).
Tests de primalité, factorisation (méthodes élémentaires).
32
Chapitre 3
Ensembles finis
3.1
Codage par vecteurs de bits
Théorème 3.1.1 Soit E un ensemble quelconque. A tout sous-ensemble A de E, on associe sa
fonction caractéristique (également appelée indicatrice) χA : A → {0, 1}, qui est définie par :
(
1 si x ∈ A,
∀x ∈ E , χA (x) :=
0 si x 6∈ A.
Alors l’application A 7→ χA réalise une bijection de l’ensemble P (E) des parties de E sur l’ensemble {0, 1}E des applications de E dans {0, 1}.
Preuve. - Il suffit de définir la bijection réciproque, c’est-à-dire, pour un élément arbitraire de l’ensemble d’arrivée, de déterminer son unique antécédent. Soit donc φ : E → {0, 1} une application
quelconque, autrement dit un élément de {0, 1}E . Posons A := {x ∈ E | φ(x) = 1}. C’est un sousensemble de E, et c’est bien l’unique sous-ensemble tel que χA = φ, donc l’unique antécédent de
φ par l’application A 7→ χA . Ce théorème fournit une méthode pour coder les sous-ensemble d’un ensemble fini quelconque
E. Pour cela, notant n := card E le nombre d’éléments de E, on commence par numéroter ces éléments de 0 à n − 1. Cela revient à identifier E avec l’ensemble particulier En := {0, . . . , n − 1}.
Dorénavant, nous travaillerons directement sur l’ensemble En .
Une application φ : En → {0, 1} est alors totalement spécifiée par le n-uplet (x0 , . . . , xn−1 ) ∈
{0, 1}n de ses valeurs xi := φ(i), i = 0, . . . , n − 1. Autrement dit, une partie A de En est représentée
par un vecteur de bits (“bit-vector”) X := (x0 , . . . , xn−1 ) ∈ {0, 1}n , avec les règles :
xi = 1 ⇐⇒ i ∈ A,
xi = 0 ⇐⇒ i 6∈ A.
Par exemple, l’ensemble vide 0/ est codé par le vecteur nul (0, . . . , 0) ∈ {0, 1}n et l’ensemble “plein”
En est codé par le vecteur (1, . . . , 1) ∈ {0, 1}n .
TP 3.1.2 Réaliser ce codage et programmer la fonction associée de test d’appartenance.
33
Exercice 3.1.3 Montrer que l’on peut coder les parties finies de N à l’aide de la bijection A 7→
∑ 2n de l’ensemble P f (N) des parties finies de N sur l’ensemble N.
n∈A
3.2
Calcul booléen sur les sous-ensembles
Le codage décrit ci-dessus permet d’arithmétiser le calcul sur les sous-ensembles de En . Ainsi,
si X := (x0 , . . . , xn−1 ) ∈ {0, 1}n est le vecteur de bits associé au sous-ensemble A de En , le vecteur
de bits associé au complémentaire {A de A dans En est :
X := (x0 , . . . , xn−1 ) ∈ {0, 1}n ,
où l’on a posé 0 := 1 et 1 := 0.
Soient maintenant X := (x0 , . . . , xn−1 ) ∈ {0, 1}n et Y := (y0 , . . . , yn−1 ) ∈ {0, 1}n les vecteurs de
bits respectivement associés à deux sous-ensembles A et B de En . Alors :
i ∈ A ∩ B ⇐⇒ i ∈ A et i ∈ B ⇐⇒ xi = 1 et yi = 1 ⇐⇒ xi yi = 1,
de sorte que le vecteur de bits associé à A ∩ B est le vecteur :
.
0 1
X.Y := (x0 .y0 , . . . , xn−1 .yn−1 ), avec la loi de composition décrite par la table : 0
0 0
1
0 1
+
0 1
X.Y := (x0 .y0 , . . . , xn−1 .yn−1 ), avec la loi de composition décrite par la table : 0
0 1
1
1 1
De même :
i ∈ A ∪ B ⇐⇒ i ∈ A ou i ∈ B ⇐⇒ xi = 1 ou yi = 1 ⇐⇒ xi + yi = 1,
de sorte que le vecteur de bits associé à A ∪ B est le vecteur :
Attention ! Il ne s’agit pas de l’addition de Z/2Z, que nous notons ici ⊕ et qui est rappelée dans
table ci-dessous :
⊕ 0 1
0
0 1
1
1 0
Cette opération code la différence symétrique :
A M B := (A ∩ {B) ∪ (B ∩ {A) = (A \ B) ∪ (B \ A).
On a noté A \ B := A ∩ {B la différence de deux ensembles. Par exemple {A = En M A et X =
(1, . . . , 1) ⊕ X.
34
Enfin, la relation d’inclusion A ⊂ B entre deux sous-ensembles de En peut également s’exprimer en termes des vecteurs de bits X et Y associés. Elle équivaut en effet à A ∩ B = A, donc à la
relation X.Y = X. Elle équivaut d’ailleurs également à A ∪ B = B, donc à la relation X +Y = Y .
TP 3.2.1 Programmer ces fonctions.
3.3
Le produit cartésien
Le produit cartésien E × F des ensembles E et F est, par définition, l’ensemble des couples
(x, y) avec x ∈ E et y ∈ F. On a card(E × F) = (cardE)(cardF). Si l’on a identifié E à En et F à
E p , leur produit cartésien a donc np éléments et l’on est conduit à rechercher une bijection entre
En × E p et Enp . Cela revient donc à ordonner les éléments de En × E p .
Prenons pour fixer les idées n := 3 et p := 4. Les 12 éléments de E3 × E4 sont naturellement
rangés en un tableau rectangulaire (une “matrice”) :
(0, 0) (0, 1) (0, 2) (0, 3)
(1, 0) (1, 1) (1, 2) (1, 3)
(2, 0) (2, 1) (2, 2) (2, 3)
Il y a deux parcours naturels de cette matrice : par lignes ou par colonnes. Le premier fournit
l’ordre suivant :
(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3).
Si l’on veut numéroter ces couples de 0 à 11, on voit que le couple (i, j) reçoit le numéro 4i + j.
Le second parcours fournit l’ordre suivant :
(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3), (2, 3).
Si l’on veut numéroter ces couples de 0 à 11, on voit que le couple (i, j) reçoit le numéro i + 3 j.
Théorème 3.3.1 (i) L’application (i, j) 7→ pi + j réalise une bijection du produit cartésien En × E p
sur Enp .
(ii) L’application (i, j) 7→ i + n j réalise une bijection du produit cartésien En × E p sur Enp .
Preuve. - Dans les deux cas, il suffit d’exhiber l’application réciproque. Dans le premier cas, c’est
k 7→ (i, j) ou i est le quotient et j le reste de la division euclidienne de k par p ; dans le second cas,
c’est k 7→ (i, j) ou j est le quotient et i le reste de la division euclidienne de k par n. TP 3.3.2 Programmer ce codage
Exercice 3.3.3 L’ensemble des parties de En a 2n éléments, il est donc en bijection avec E2n .
Expliciter un algorithme qui permette de convertir un élément de E2n = {0, 1, . . . , 2n − 1} en un
vecteur de n bits.
35
Chapitre 4
Recherche et tri
4.1
Algorithmes de recherche
Nous allons examiner trois problèmes naturels de recherche dans un tableau dont les solutions
illustrent :
– différentes classes de coûts des algorithmes ;
– l’influence des structures de données utilisées ;
– l’intérêt de certaines méthodes dichotomiques, associées au paradigme “diviser pour régner”.
De plus, les problèmes de recherche motivent l’étude des algorithmes de tri, qui seront évoqués à
la section suivante.
4.1.1
Recherche d’un élément
On se donne un tableau T [1], . . . , T [n] d’éléments d’un type arbitraire non spécifié. L’exemple
canonique est celui d’un tableau de chaines de caractères. On cherche un élément particulier e
dans le tableau T : autrement dit, s’il en existe, un indice i ∈ {1, . . . , n} tel que T [i] = e.
Cas d’un tableau arbitraire
L’algorithme de base est alors le suivant (le tableau est noté tab) :
i := 1;
tant que (tab[i] <> e et i <= n) faire
i := i+1;
fin tant que;
si (i <= n) alors
rendre (i)
sinon
ECHEC;
fin si;
Pour estimer le coût de cet algorithme, nous prendrons pour critère le nombre de comparaisons
effectuées (de T [i] avec e). Si l’élément e recherché n’est pas dans le tableau, ce nombre est n. Si
l’élément e recherché est dans le tableau, ce nombre est compris entre 1 et n. Le meilleur des cas
36
est celui où T [1] = e, qui donne un coût de 1. Le pire des cas est celui où T [n] = e et T [i] 6= e pour
i < n, qui donne un coût de n.
Et en moyenne, quel est le coût ? Si nous supposons que l’élément e peut être trouvé dans
chacune des positions T [1], . . . , T [n] avec la même probabilité, le coût moyen est :
1 + · · · + n n(n + 1)/2 n + 1
=
=
·
n
n
2
L’hypothèse d’équiprobabilité des positions signifie concrètement que, lorsque l’on effectue un
très grand nombre N de recherches d’éléments qui figurent effectivement dans le tableau, on trouve
la position T [1] approximativement N/n fois, et de même pour T [2], . . . , T [n]. Cette hypothèse est
raisonnable si tous les éléments du tableau sont distincts. Si ce n’est pas le cas, l’analyse est légèrement plus compliquée, mais le résultat n’est pas substantiellement différent.
En conclusion, le coût d’une recherche avec échec est constant égal à n ; le coût d’une ren+1
cherche avec succès est au pire égal à n, et en moyenne égal à
: le coût est donc linéaire.
2
Remarque 4.1.1 Nous éludons complètement la question des biais d’utilisation du tableau : par
exemple les phénomènes socioculturels qui font qu’un utilisateur cherchera plus fréquemment la
chaine de caractères “Michael Jackson” que la chaine de caractères “Coût des algorithmes”.
Cas d’un tableau trié
On suppose maintenant que le type des éléments du tableau est muni d’une relation d’ordre :
l’ordre évident s’il s’agit de nombres, et, par exemple, l’ordre lexicographique (c’est-à-dire l’ordre
du dictionnaire) s’il s’agit de chaines de caractères. Supposons de plus que le tableau est trié,
autrement dit, que l’on ait :
T [1] ≤ · · · ≤ T [n].
L’algorithme ci-dessus peut alors facilement être modifié pour détecter un échec avant la fin de la
lecture complète du tableau. En effet, dès que T [i] ≥ e, on sait que l’on n’a pas besoin de chercher
plus loin. Voici la version améliorée (le tableau est encore noté tab) :
i := 1;
tant que (tab[i] < e et i <= n) faire
i := i+1;
fin tant que;
si (i <= n et tab[i] = e) alors
rendre (i);
sinon
ECHEC;
fin si;
Il est facile de vérifier que le coût d’une recherche avec succès n’est pas modifié par cette amélioration. Quant au coût d’une recherche avec échec, on peut estimer (en l’absence d’hypothèse
particulière sur les valeurs effectivement recherchées par les utilisateurs) qu’il est en moyenne divisé par deux. C’est une amélioration, mais mineure.
37
On peut faire beaucoup mieux pour exploiter le fait que le tableau est trié. Une recherche
dichotomique consiste à regarder au milieu du tableau ; puis, si l’on n’a pas trouvé, à aller à gauche
ou à droite selon le cas. La taille du domaine de recherche est divisée par deux à chaque étape, ce
qui garantit une terminaison beaucoup plus rapide. Voici une façon d’écrire l’algorithme :
i := 1;
j := n;
trouvé := faux;
tant que (non trouvé et i <= j) faire
k := (i+j) div 2;
si (tab[k] = e) alors
trouvé := vrai;
sinon
si (tab[k] < e) alors
i := k+1;
sinon
j := k-1;
fin si;
fin si;
fin tant que;
si trouvé alors
rendre (i);
sinon
ECHEC;
fin si;
(On a fait appel à la fonction floor qui calcule la partie entière d’un réel.) A chaque étape, la
longueur j − i + 1 de l’intervalle de recherche est au moins divisée par deux, puisque sa borne
gauche passe à droite de son centre ou sa borne droite à gauche de son centre. Le nombre total
d’étapes est donc au pire log2 n. Le coût le pire d’une recherche avec succès ou avec échec est
donc majoré par log2 n. Nous ne calculerons pas le coût moyen, mais on peut démontrer qu’il est
proche du coût le pire.
Quelques conclusions
Nous allons d’abord discuter d l’interêt davoir un coût logarithmique plutôt que linéaire. A une
époque ou la puissance des matériels croît de manière si spectaculaire, cela vaut-il la peine de se
soucier de la qualité des algorithmes ? Pour le voir, nous prendrons comme hypothèse heuristique
la “loi de Moore”, une loi socio-économico-technique qui dit que “la puissance des matériels
informatiques est multipliée par deux tous les dix-huit mois”.
Remarque 4.1.2 La “loi de Moore” n’a rien d’une loi scientifique, c’est, au mieux, une constatation empirique ; voir une discussion là-dessus dans l’article de Wikipedia consultable sur l’URL
http://fr.wikipedia.org/wiki/Loi_de_Moore.
On se place dans la situation suivante : nous avons un ordinateur et un programme qui nous
permettent de retrouver un nom dans une liste de cinq cents éléments en un dixième de secondes.
Il est donc bien adapté à la gestion de l’ensemble des étudiants en informatique de l’UPS, par
38
exemple. Pouvons-nous utiliser le même ordinateur et le même programme dans le cas d’une liste
de cinq cents mille éléments (population de la ville de Toulouse, par exemple) ? Combien de temps
faudra-t-il alors pour trouver un élément dans cette liste ?
Avec notre premier algorithme (coût linéaire), le temps d’exécution est proportionnel à la taille
de la liste (du tableau). Il faut donc mille fois plus de temps, soit cent secondes : ce n’est pas viable.
Cette dégradation peut-elle être compensée par les progrès de la technologie ? Quand ces progrès
nous permettront-ils de travailler sur une telle grosse liste mais avec le temps de réponse actuel ?
Nous interpréterons la loi de Moore comme nous disant que les machines vont deux fois plus vite
tous les dix-huit mois, donc 210 = 1024 fois plus vite au bout de 180 mois. Il nous faudra donc
attendre quinze ans pour pouvoir utiliser notre algorithme à coût linéaire à l’échelle de Toulouse
avec le même temps de réponse qu’auparavant.
Avec notre second algorithme (coût logarithmique), le temps d’exécution est de la forme
C log2 n, avec une constante C telle que C log2 500 = 1/10 (secondes). A l’échelle de Toulouse,
cela donne un temps d’exécution de :
C log2 500000 = 1/10 × (log2 500000/ log2 500) ' 1/10 × 2, 2 secondes.
Le temps d’exécution n’est pas outrageusement plus long, et il nous faudra seulement attendre un
peu plus de dix-huit mois pour pouvoir utiliser notre algorithme à coût logarithmique à l’échelle
de Toulouse avec le même temps de réponse qu’auparavant :
Les bons algorithmes profitent mieux de l’amélioration du matériel.
Reste que notre bon algorithme suppose le tableau trié. Le tri d’un tableau est lui-même une
opération couteuse ! Pratiquement, il n’est pas question de trier un tableau dans lequel on n’effectuera qu’une ou deux recherches ; mais, si les recherches doivent être fréquentes (dictionnaire,
base de donnéees . . .), autant trier le tableau (ou la liste, ou le fichier selon le cas) 1 .
Exercice 4.1.3 On supose que le tableau est non trié et contient des entiers compris entre 1 et m.
Il y a donc mn possibilités de tels tableaux, que l’on considèrera comme équiprobables. Combien
de comparaisons sont en moyenne nécessaires pour trouver un élément e ∈ {1, . . . , m} ?
TP 4.1.4 Programmer l’algorithme de recherche dichotomique.
4.1.2
Recherche du maximum dans un tableau
On suppose encore que le type des éléments du tableau est muni d’une relation d’ordre, et l’on
se propose de rechercher la position du plus grand des éléments T [1], . . . , T [n]. Bien entendu, si le
tableau est trié, ce maximum est T [n] et le problème est trivial. En général, voici un algorithme
simple :
1. On admet implicitement ici que le tableau est constitué et trié une fois pour toutes, ce qui est bien le cas pour un
dictionnaire, mais rarement pour une base de données. Pour un ensemble de données qui évolue, d’autres structures de
données conviennent.
39
i := 1;
j := 1;
m := tab[1];
tant que (i < n) faire
i := i+1;
si (m < tab[i]) alors
m := tab[i];
j := i;
fin si;
fin tant que;
rendre(j,m);
A toute étape de la boucle, m = T [ j] est le maximum de T [1], . . . , T [i]. Le nombre de comparaisons
est toujours n − 1. Comme critère de coût, nous prendrons plutôt le nombre de fois où l’on a dû
mettre à jour j et m (initialisations comprises).
Dans le meilleur des cas, le maximum se trouve en j = 1 et le coût est donc de 1 (initialisations). Dans le pire des cas, le tableau est trié (mais on ne le sait pas !) et j prend successivement
toutes les valeurs de 1 à n : le coût est donc de n. En général, le coût est égal au nombre de “maxima
stricts gauche-droite”, c’est-à-dire au nombre des indices i tels que T [i] > max(T [1], . . . , T [i − 1]).
On peut démontrer que, si le tableau contient n éléments distincts, et que les différents ordres pos1
1
sibles de ces éléments sont équiprobables, alors le coût moyen est égal à Hn := 1 + + · · · +
2
n
(ces nombres forment la série harmonique).
Exemple 4.1.5 Si n = 1, le seul rangement possible ( !) donne un coût de 1 = H1 . Si n = 2, les
deux rangements possibles donnent respectivement des coûts de 1 et 2, d’où un coût moyen de
3/2 = H2 . Pour le cas n = 3, on peut aussi bien supposer que les éléments du tableau sont 1, 2 et
3 pris dans un certain ordre. Il y a six permutations possibles : (123), (132), (213), (231), (312)
et (321). Les coûts correspondants sont respectivement 3, 2, 2, 2, 1 et 1, d’où un coût moyen de
11/6 = H3 .
On démontrera en cours d’analyse de L1 que Hn ∼ ln n, ce qui implique que le coût de l’algorithme ci-dessus est logarithmique.
Exercice 4.1.6 En comparant
Z i+1
dt
i
t
à
Z i+1
dt
i
i
et à
Z i+1
dt
i
i+1
, démontrer l’encadrement :
1
1
≤ ln(i + 1) − ln(i) ≤ ·
i+1
i
En déduire par récurrence l’encadrement ln(n + 1) ≤ Hn ≤ 1 + ln n, puis l’équivalence Hn ∼ ln n.
4.1.3
Recherche d’un duplicata
Pour commencer, on ne fait aucune hypothèse sur le type des éléments du tableau. Le problème
est de déterminer, s’il en existe, des indices distincts i 6= j tels que T [i] = T [ j]. La seule méthode
envisageable est a priori d’effectuer toutes les comparaisons de couples T [i], T [ j] pour 1 ≤ i <
j ≤ n, ce qui représente n(n − 1)/2 comparaisons. Ce nombre correspond au cas le pire (pas de
40
duplicata, il faut tout avoir essayé avant de s’en apercevoir). En moyenne, en cas de succès, on peut
s’attendre à un coût moitié moindre, donc de l’ordre de n2 /2. Il s’agit donc d’un coût quadratique.
Exemple 4.1.7 Reprenant nos considérations heuristiques basées sur la “loi de Moore”. Un algorithme quadratique qui s’exécute en un dixième de seconde sur un tableau de cinq cents éléments
prendra un million de fois plus de temps pour un tableau de cinq cents mille éléments. Il faudra
20 × 18 = 360 mois, soit trente ans, pour que l’amélioration du matériel informatique permette de
compenser cette dégradation de performance.
Si l’on suppose maintenant que le type des éléments du tableau est muni d’une relation d’ordre
et que le tableau est trié. Pour déceler d’éventuelles duplications, il suffit de considérer des paires
d’éléments consécutifs du tableau. (Voyez-vous pourquoi ?) On a donc besoin d’au plus (n − 1)
comparaisons. Le coût est devenu linéaire, ce qui est beaucoup mieux. Nous verrons que l’on
peut trier un tableau de taille n avec un coût de l’ordre de n ln n : donc, même pour chercher les
duplications une seule fois, cela vaut la peine de trier préalablement le tableau. (Bien entendu,
cette affirmation ne concerne que des tableaux assez grands pour que le coût soit un problème !)
TP 4.1.8 Programmer la recherche de duplicata dans un tableau non trié et vérifier l’estimation
du coût moyen par expérimentation sur des tableaux créés à l’aide d’un générateur aléatoire.
4.2
Algorithmes de tri
Il y a d’innombrables bonnes raisons pour trier des tableaux, des listes, des fichiers . . ., l’une
d’entre elles étant que cela donne lieu à des algorithmes intéressants et dont l’analyse est ellemême intéressante !
Dans ce qui suit, on suppose tous les éléments considérés sont de même type et que ce type
est muni d’une relation d’ordre.
4.2.1
Tri de trois éléments
Commençons par un cas d’apparence anodin. Soient a, b, c trois éléments distincts. On veut
produire un triplet (a0 , b0 , c0 ) tel que :
1. le triplet (a0 , b0 , c0 ) soit une permutation du triplet (a, b, c) ;
2. on ait a0 < b0 < c0 .
Pour cela, on s’autorise des tests qui sont des comparaisons : a < b?, a < c? et b < c?. Il peut
arriver que deux tests consécutifs soient suffisants pour trancher : si a < b et b < c sont tous deux
vrais, alors (a0 , b0 , c0 ) = (a, b, c). De même si a < b et b < c sont tous deux faux, alors (a0 , b0 , c0 ) =
(c, b, a). Mais si a < b est vrai et que b < c est faux, il y a deux possibilités : (a0 , b0 , c0 ) = (a, c, b)
ou (a0 , b0 , c0 ) = (c, a, b), et il faudra un troisième test a < c? pour trancher. Dans tous les cas, on
devrait s’en tirer avec un nombre de comparaisons compris entre deux et trois. Pour aller plus loin,
écrivons un algorihme possible 2 :
2. Si l’on veut trier un nombre indéterminé n d’éléments, il ne sera évidemment pas possible d’écrire un algorithme
basé sur des “si . . .alors . . .sinon . . .” comme celui-ci !
41
si (a < b) alors
si (b < c) alors
rendre (a,b,c);
sinon
si (a < c) alors
rendre (a,c,b);
sinon
rendre (c,a,b);
fin si;
fin si;
sinon
si (b < c) alors
si (a < c) alors
rendre (b,a,c);
sinon
rendre (b,c,a);
fin si;
sinon
rendre (c,b,a);
fin si;
fin si;
Si l’on suppose les six ordres a < b < c, a < c < b, b < a < c, b < c < a, c < a < b et c < b < a
équiprobables, on voit que le nombre moyen de comparaisons effectuées (donc le coût moyen) est
2+3+3+3+3+2
= 8/3 ' 2, 67.
6
La procédé des tests successifs avec réponse binaire oui/non peut être modélisé par un arbre
de décision, ici :
fff a < b? XXXXXXXX
XXXXX
fffff
f
f
f
f
XXXXX
fff
f
f
XXXXX
f
f
XXXXX
ffff
f
f
f
f
X,
rff
b < c?H
b < c?H
HH
H
v
HH
vv
HH
vv
v
v
H
v
HH
v
H
v
HH
v
HH
vv
v
v
H
v
zv
$
H$
v
zv
a,b,c
c,b,a
a < c?
a
<
c?
FF
FF
FF
FF
xx
xx
x
x
FF
FF
x
x
FF
FF
xx
xx
FF
FF
xx
xx
x
x
{x
"
|x
#
a,c,b
c,a,b
b,a,c
b,c,a
Les noeuds de l’arbre représentent des tests, la branche gauche (resp. droite) correspondant à une
réponse positive (resp. négative) ; les feuilles représentent les résultats possibles de l’algorithme.
La distance d’une feuille à la racine (qui est le noeud le plus haut en informatique, donc ici
a < b? ! ! !) est appelée profondeur de cette feuille, et elle est dans notre cas égale au coût de
l’exécution qui a amené à cette feuille. On voit bien sur cet arbre pourquoi on n’aurait pas pu s’en
42
tirer avec deux comparaisons dans tous les cas. Cela signifierait en effet que toutes les feuilles
auraient une profondeur inférieure ou égale à 2, et l’arbre ne pourrait alors avoir que 4 feuilles.
Mais cela ne suffirait pas, puisque l’on sait d’avance qu’il y a 6 ordres possibles, donc qu’il faut
au moins 6 feuilles.
Coût optimal d’un tri par comparaisons
Ce raisonnement se généralise ainsi. Supposons que l’on veuille trier n éléments en effectuant 3
un certain nombre de comparaisons entre eux. L’arbre de décision correspondant doit avoir au
moins n! feuilles 4 puisque l’on doit prévoir au moins n! résultats différents possibles. Par ailleurs,
si l’on veut effectuer au plus k comparaisons dans tous les cas, les feuilles de l’arbre ont toutes une
profondeur inférieure ou égale à k, et l’on voit facilement (avec de petits dessins de tels arbres)
qu’il y a alors au plus 2k feuilles. En résumé, si l’on veut trier n éléments en effectuant dans tous
les cas au plus k raisons, on doit avoir :
2k ≥ n! =⇒ k ≥ log2 n!.
Théorème 4.2.1 Le nombre de comparaisons nécessaires pour trier n éléments est, dans le pire
des cas, au moins égal à log2 n!. On a de plus :
log2 n! ∼ n log2 n.
(La deuxième assertion est justifiée par l’exercice ci-dessous.) On peut démontrer une estimation
analogue pour le coût moyen d’un tel algorithme. Comme nous le verrons plus loin, ces ordres de
grandeur en n log2 n peuvent effectivement être réalisés par de bons algorithmes.
Exercice 4.2.2 Démontrer l’encadrement :
1 + n ln n ≤ (n + 1) ln(n + 1) − n ln n ≤ 1 + ln(n + 1).
En déduire par écurrence un encadrement de ln 1 + ln 2 + · · · + ln n = ln n!, puis une preuve de la
deuxième assertion du théorème.
4.2.2
Tri par sélection
On considère un tableau T [1], . . . , T [n]. Le principe de l’algorithme qui va suivre est le suivant :
on détermine le plus grand élément T [ j] du tableau, et l’on permute T [ j] avec T [n], qui est alors en
place définitivement ; puis on détermine le plus grand élément du sous-tableau T [1], . . . , T [n − 1],
que l’on permute avec T [n − 1], etc. L’invariant de boucle qui permet de démontrer la correction de
l’algorithme est donc le suivant : après k étapes, les k derniers éléments du tableau sont en place ;
autrement dit, ce sont les k plus grands et ils sont triés. (Il s’agit évidemment de la boucle externe,
la boucle interne visant chaque fois à déterminer le maximum des (n − k) premiers éléments.)
3. Il existe des méthodes de tri radicalement différentes qui ne reposent pas sur une séquence de comparaisons ; ni
le raisonnement qui suit, ni sa conclusion ne s’appliquent à ces méthodes.
4. On rappelle que n! désigne la factorielle de n, c’est-à-dire le produit 1 × 2 × · · · × n des n premiers entiers non
nuls ; et que le nombre de permutations de n éléments distincts est égal à n!.
43
i := n;
tant que (i > 1) faire
tab[j] := le maximum de tab[1]...tab[i];
permuter tab[i] et tab[j];
i := i - 1
fin tant que;
Noter que l’on n’a rien à faire pour i = 1 : lorsque les (n − 1) derniers éléments sont en place, le
premier l’est également. La recherche du maximum de T [1], . . . , T [i] coûte (i−1) comparaisons, le
nombre total de comparaisons effectué est donc dans tous les cas égal à (n−1)+(n−2)+· · ·+1 =
n(n − 1)/2 ; c’est donc un coût quadratique. On peut cependant choisir d’autres critères. Par
exemple le nombre total de mises à jour de l’indice lors des recherches de maximum, mais ce
nombre est difficile à analyser.
Un autre critère pertinent est le nombre d’échanges de T [i] avec T [ j]. En effet, si les éléments
du tableau sont volumineux, ces échanges peuvent prendre un temps non négligeable. Dans notre
algorithme, il y a dans tous les cas (n − 1) échanges, même si par exemple le tableau est déjà trié et
que l’on a chaque fois i = j ! On peut améliorer l’algorithme sur ce point et n’effectuer l’échange
que s’il est nécessaire :
i := n;
tant que (i > 1) faire
tab[j] := le maximum de tab[1]...tab[i];
si (i <> j) alors
permuter tab[i] et tab[j];
fin si;
i := i - 1;
fin tant que;
Le nombre minimum d’échanges est alors 0 (tableau déjà trié). Le nombre maximum est n −
1 ; il ne correspond d’ailleurs pas à un tableau en ordre inverse n, . . . , 1 mais, par exemple, à
l’ordre 2, 3, . . . , n, 1. On peut prouver que le nombre moyen d’échanges est n − Hn . L’amélioration
n’apporte donc pas vraiment grand-chose, puisque Hn ∼ ln n est négligeable devant n.
Exercice 4.2.3 Combien y a-t-il d’échanges dans le cas de l’ordre inverse n, . . . , 1 ?
TP 4.2.4 Programmer la version améliorée de l’algorithme.
4.2.3
Tri par fusion
Nous allons décrire un algorithme de tri dichotomique. Le nombre de comparaisons effectuées
par cet algorithme dans le cas d’un tableau de n éléments, est de l’ordre de n log2 n : c’est donc
l’ordre de grandeur optimal. Cela ne signifie d’ailleurs pas pour autant que l’algorithme lui-même
est optimal ; mais les autres critères pertinents pour en juger (difficulté de mise en oeuvre, coût des
opérations élémentaires, adéquation de la structure de données . . .) et la comparaison pratique des
différents algorithmes en situation relèvent du cours d’informatique.
44
Description informelle
Le principe est le suivant. Pour trier un tableau de seize éléments (par exemple), on coupe
celui-ci en deux sous-tableaux de huit éléments ; on trie chacun de ces sous-tableaux, puis on
fusionne ces derniers. Le tri des tableaux de huit éléments a été effectué de la même manière : on
les a coupés en tableaux de quatre éléments, que l’on a triés puis fusionné, etc. Cette description
appelle plusieurs remarques :
1. L’algorithme est “récursif” : son exécution sur un gros tableau présuppose son exécution
sur des tableaux plus petits. Pour ne pas se retrouver dans un cercle vicieux, il faut donc
que le tri de très petits tableaux soit direct et ne fasse pas appel au tri de tableaux encore
plus petits. C’est bien entendu le cas de tableaux à un élément, dont le tri est une opération
vide ! Pratiquement, nous ne décrirons pas l’algorithme sous sa forme récursive mais sous
la forme d’une itération directe : d’abord les tableaux à un élément, puis les tableaux à deux
éléments, puis à quatre éléments, etc. (La programmation récursive, c’est pour plus tard !)
2. On doit disposer d’une méthode pour “fusionner” deux tableaux triés de huit éléments en
un tableau trié de seize éléments. Nous verrons qu’il existe en effet une telle méthode efficace, qui, de manière générale, fusionne deux tableaux triés ayant respectivement ` et m
éléments en un tableau trié de n := ` + m éléments. Nous prouverons que le coût d’une telle
fusion est, dans le pire des cas, égal à n : ceci, que l’on prenne comme unités de compte les
comparaisons ou les affectations d’éléments du tableau.
3. Pour que des divisions successives par deux des tailles de tableaux nous ramènent à des
tableaux de taille un, il faut que la taille de départ soit une puissance de deux (seize dans
notre exemple). Si l’on part d’un tableau ayant par exemple douze éléments, il suffira de le
compléter par quatre éléments inutiles de valeur maximale à la fin. Ces éléments resteront à
leur place et, à la fin, seuls les douze premiers éléments du résultat nous intéresseront. Nous
verrons que ce procédé de remplissage (qui est souvent nécessaire dans les algorithmes
dichotomiques) n’a pas d’influence sur l’ordre de grandeur du coût.
4. Nous nous restreindrons donc à des tableaux de n = 2k éléments. Pour simplifier la manipulation des indices des éléments , nous supposerons que ceux-ci varient de 0 à n − 1 (comme
en C, par exemple). En effet, dans ce cas, les indices des deux sous-tableaux varient respectivement de 0 à 2k−1 − 1 et de 2k−1 à 2k − 1 : les formules sont plus simples qu’elles ne le
seraient pour des indices variant de 1 à n.
Dans la figure suivante, on détaille le cas d’un tableau de huit éléments. Par exemple, en
fusionnant le sous-tableau réduit à l’élément T [0] avec le sous-tableau réduit à l’élément T [1], on
obtient le sous-tableau trié formé des éléments T [0], T [1] et le coût de cette fusion est 2 (pour le
moment, on admet qu’il existe une telle méthode de fusion). De même, en fusionnant le soustableau trié formé des éléments T [0], T [1] avec le sous-tableau trié formé des éléments T [2], T [3],
on obtient le sous-tableau trié formé des éléments T [0], T [1], T [2], T [3] et le coût de cette fusion
est 4. Le total des coûts est donc : 4 × 2 + 2 × 4 + 1 × 8 = 24.
45
0 @@
@@
@@
@@
?~0133
~
33
~~
33
~~
~
33
~
33
1
33
33
3
0123
E ,
,,
,,
,,
,,
2 @@
,,
@@
@@
,,
@@ ,,
,,
23
,,
~?
~
,,
~~
~
~
,,
~
~
,,
3
,,
,,
,
01234567
H
4 @@
@@
@@
@@
?4533
33


33

33

33
5
33
33 3 4567
E
6 ??
??
??
?? ?~67
~~
~~
~
~~
coût = 2
coût = 4
coût = 2
coût = 8
coût = 2
coût = 4
coût = 2
7
Coût
Le calcul se généralise ainsi au cas d’un tableau de 2k éléments. Les fusions deux à deux
des 2k sous-tableaux de 1 éléments nous donnent 2k−1 sous-tableaux triés de 2 éléments, pour un
46
coût total de 2k−1 × 2 = 2k . Les fusions deux à deux des 2k−1 sous-tableaux triés de 2 éléments
nous donnent 2k−2 sous-tableaux triés de 4 éléments, pour un coût total de 2k−2 × 4 = 2k ; et
ainsi de suite. Chaque étape fusionnant 2k−i sous-tableaux triés de 2i éléments a pour coût total
2k−i × 2i = 2k , et il y a k telles étapes (pour i variant de 0 à k − 1) : le coût total est donc k2k .
Comme n = 2k , on a bien un coût égal à n log2 n.
Remarque 4.2.5 Si l’on a eu à trier pour commencer un nombre n d’éléments qui n’est pas une
puissance de 2, après remplissage, on a travaillé sur un tableau de 2k éléments avec 2k−1 < n ≤ 2k ,
donc k − 1 < log2 n ≤ k, et le coût total de k2k est compris entre n log2 n et 2n(1 + log2 n) : l’ordre
de grandeur est bien le même.
On dit d’un tel algorithme que son coût est quasi-linéaire ; voici pourquoi. Les différentes
classes de coût que nous avons rencontrées (logarithmique, linéaire, quadratique) peuvent être
caractérisées par la manière dont le coût augmente lorsque l’on double la taille des données :
1. Pour un coût logarithmique C(n) = a log n, on a :
C(2n) = a log(2n) = a log n + a log 2 = C(n) + a log 2,
donc le coût augmente d’une constante lorsque l’on double la taille des données.
2. Pour un coût linéaire C(n) = an, on a :
C(2n) = a(2n) = 2an = 2C(n),
donc le coût double lorsque l’on double la taille des données.
3. Pour un coût logarithmique C(n) = n2 , on a :
C(2n) = (2n)2 = 4n2 = 4C(n),
donc le coût quadruple lorsque l’on double la taille des données.
Pour un algorithme tel que C(n) = an log n, on a :
log 2
C(2n) = 2an log(2n) = 2an log n + 2an log 2 = 2C(n) 1 +
∼ 2C(n).
log n
La manière dont le coût augmente lorsque l’on double la taille des données est donc asymptotiquement la même que pour un algorithme de coût linéaire. Pour de grandes données, cela revient
donc pratiquement au même.
L’algorithme de fusion
Cet algorithme est destiné à servir de procédure à l’intérieur d’un autre algorithme : nous
utiliserons donc des notations un peu plus générales pour les indices et les noms des tableaux.
On suppose donnés un tableau trié de ` éléments T [a + 1], . . . , T [a + `] et un tableau trié de m
éléments U[b + 1], . . . ,U[b + m]. L’algorithme les fusionne et remplit un tableau de n := ` + m
éléments V [c + 1], . . . ,V [c + n], qui sera trié (nous notons tab1 et tab2 les tableaux à fusionner,
tab celui qui reçoit le résultat de la fusion) :
47
i :=
j :=
k :=
tant
si
a + 1;
b + 1;
c + 1;
que (i <= a + l et j <= b + m) faire
tab1[i] < tab2[j] alors
res[k] := tab1[i];
i := i+1;
k := k+1;
sinon
res[k] := tab2[j];
j := j+1;
k := k+1;
fin_si;
fin tant que;
tant que (i <= a + l) faire
res[k] := tab1[i];
i := i+1;
k := k+1;
fin tant que;
tant que (j <= b + m) faire
res[k] := tab2[j];
j := j+1;
k := k+1;
fin tant que;
(Sur les deux dernières boucles, l’une est vide car la condition de sortie de la première boucle est
que l’un des deux tableaux T ,U ait été entièrement parcouru.) Le nombre total d’affectations de
V [k] est exactement n, le nombre de comparaisons est majoré par n dans tous les cas.
L’algorithme de tri
L’algorithme de fusion ci-dessus ne peut être effectué “sur place” : autrement dit, si l’on
fusionne par exemple T [0], T [1] avec T [2], T [3], le résultat ne peut être directement écrit dans
T [0], T [1], T [2], T [3]. La manière la plus évidente de l’exploiter est d’écrire les résultats dans un
tableau U, puis de recopier U dans T , et ceci à chaque étape. Voici le schéma de l’algorithme
complet (où l’on note tab et aux les deux tableaux utilisés) :
pour i dans 0..k-1 faire
pour j dans 0..2k−i−1 faire
fusionner tab[2j.2i ..(2j+1).2i - 1] et tab[(2j+1).2i ..(2j+2).2i - 1]
dans aux[2j.2i ..(2j+2).2i - 1];
fin pour;
recopier aux dans tab;
fin pour;
Quelques remarques finales :
1. Pour la première fois, nous utilisons une boucle “pour” au lieu d’une boucle “tant que” :
c’est bien adapté à un parcours de tableau.
48
2. Nous avons noté T[p..q] le sous-tableau de T formé des éléments d’indices allant de p à
q.
3. On peut améliorer l’algorithme en évitant les recopies ; il suffit pour cela de “basculer” à
chaque étape le tableau source et le tableau but : la première phase de fusion se fait de T
dans U, la deuxième de U dans T , etc, en alternant.
TP 4.2.6 Ecrire et programmer l’algorithme avec alternance des tableaux source et but.
4.3
Suppléments facultatifs
L’arbre des choix et la minoration du coût d’un tri par comparaisons.
Principe (non détaillé) d’un algorithme dichotomique et son coût.
49
Annexe A
Rappel de la proposition
Jacques Sauloy. Université Paul Sabatier. UFR MIG. Hiver 2011
Proposition 1 de contenu pour l’option Math/Info
– C’est conçu avec l’idée (approximative) de douze séances de cours-TD de 1h30 et autant de
TP, mais commençant un peu plus tard.
– La bibliographie indiquée ci-dessous est pour nous enseignants, sauf [4] (modules II.1 et
II.8, ainsi qu’une partie du module I.1), qui concerne les étudiants.
A propos des calculs de coût. Les calculs de coût sont toujours faits dans le cas le pire et le cas
le meilleur ; et en moyenne quand c’est possible. Le but pédagogique n’est pas de montrer que tel
algorithme est plus performant, mais que l’on peut prévoir le comportement d’un algorithme au
prix d’un raisonnement mathématique. Il faudra insérer une discussion des classes (logarithmique,
linéaire, quasi-linéaire, polynomiale, exponentielle) et peut-être quelques expériences en TP pour
observer les comportements correspondants.
A.1
Arithmétique élémentaire (quatre semaines)
A.1.1
Ecriture et calcul en base b
Division euclidienne (rappel).
Ecriture en base b. Algorithme de conversion. Taille d’un entier.
Addition et multiplication en base b. Coût.
A.1.2
Exponentiation
Exponentiation : normale, dichotomique, optimale, aberrante. Correction. Coût simple, coût
affiné.
1. Version révisée après la réunion du 31/01/2011.
50
A.1.3
Algorithme d’Euclide
L’algorithme d’Euclide de calcul du pgcd. Correction. Coût.
L’algorithme d’Euclide étendu (avec calcul des coefficients de Bézout). Coût.
Suppléments facultatifs envisageables. Résolution de l’équation ax + by = c.
Nombres premiers. Le crible d’Eratosthène.
A.2
Arithmétique modulaire et applications (quatre semaines)
A.2.1
Congruences
Calcul modulo m : addition, multiplication.
A.2.2
Générateurs pseudo-aléatoires
Générateur pseudo-aléatoire “linéaire congruentiel”.
A.2.3
Cryptographie
Puissances. Logarithme discret. RSA.
Suppléments facultatifs envisageables. Recherche de la période (méthode de Brent).
Résolution de l’équation ax ≡ b (mod m). Résolution simultanée (lemme chinois).
Tests de primalité, factorisation (méthodes élémentaires).
A.3
Ensembles finis (deux semaines)
Bijection entre P (A) et {0, 1}A .
Calcul dans (Z/2Z)n de : complémentaire, intersection, réunion, différence symétrique, inclusion.
Codage du produit de deux ensembles.
Suppléments facultatifs envisageables.
A.4
Recherche et tri (deux semaines)
A.4.1
Algorithmes de recherche (vuis en cours d’info)
Modèle probabiliste utilisé.
Recherche d’un élément dans un tableau quelconque, dans un tableau trié. Correction. Coût.
Recherche du maximum. Correction. Coût.
Recherche d’un duplicata dans un tableau quelconque, dans un tableau trié. Coût.
51
A.4.2
Algorithmes de tri
Tri de trois éléments. Coût.
Tri par sélection (vu en cours d’info). Correction. Coût.
Tribulle. Correction. Coût. Lien avec les inversions d’une permutation.
Suppléments facultatifs envisageables. L’arbre des choix et la minoration du coût d’un tri par
comparaisons.
Principe (non détaillé) d’un algorithme dichotomique et son coût.
52
Bibliographie
[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction à l’algorithmique. Dunod, 1994.
[2] M. Demazure. Cours d’algèbre. Primalité, divisibilité, codes. Cassini, 1997.
[3] D. E. Knuth. The Art of Computer programming, vol. II, Seminumerical Algorithms. AddisonWesley, 1081.
[4] J.-P. Ramis et A. Warusfel. Mathématiques. Tout-en-un pour la licence, niveau L1. Dunod,
2006.
[5] J.-P. Ramis et A. Warusfel. Mathématiques. Tout-en-un pour la licence, niveau L2. Dunod,
2007.
53