Page 1

Ce fichier contient les exercices, astuces et solutions du chapitre 2 de la

livre « Introduction à la conception et à l'analyse des algorithmes », 3e édition, par
A. Lévitine. Les problèmes qui pourraient être difficiles pour au moins certains étudiants
sont marqués par > ; ceux qui pourraient être difficiles pour une majorité d'étudiants sont
marqué par ► .

Exercices 2.1
1. Pour chacun des algorithmes suivants, indiquez (i) une métrique de taille naturelle pour
ses entrées, (ii) son fonctionnement de base, et (iii) si le fonctionnement de base
count peut être différent pour des entrées de même taille :

une. calculer la somme de n nombres

b. informatique m!

c. trouver le plus grand élément dans une liste de n nombres

ré. L'algorithme d'Euclide

e. crible d'Eratosthène

F. algorithme stylo et crayon pour multiplier deux nombres entiers décimaux à n chiffres

2. a. Considérez l'algorithme basé sur la définition pour ajouter deux matrices n×n.
Quel est son fonctionnement de base ? Combien de fois est-il exécuté en fonction
de l'ordre matriciel n? En fonction du nombre total d'éléments dans
les matrices d'entrée ?

b. Répondez aux mêmes questions pour l'algorithme basé sur la définition pour la matrice
multiplication.

3. Considérez une variante de la recherche séquentielle qui parcourt une liste pour renvoyer le
nombre d'occurrences d'une clé de recherche donnée dans la liste. Est-ce que son efficacité
diffèrent de l'efficacité de la recherche séquentielle classique ?

4. a. Sélection de gants Il y a 22 gants dans un tiroir : 5 paires de gants rouges,

4 paires de jaune et 2 paires de vert. Vous sélectionnez les gants dans le noir
et ne peut les vérifier qu'après avoir effectué une sélection. Quel est le
plus petit nombre de gants que vous devez sélectionner pour avoir au moins une correspondance
coupler dans le meilleur des cas ? au pire des cas?

b. Chaussettes manquantes Imaginez qu'après avoir lavé 5 paires de chaussettes distinctes,

vous découvrez qu'il manque deux chaussettes. Bien sûr, vous aimeriez avoir
le plus grand nombre de paires complètes restantes. Ainsi, il vous reste
4 paires complètes dans le meilleur des cas et avec 3 paires complètes dans
le pire des cas. En supposant que la probabilité de disparition pour chaque

1
Page 2

des 10 chaussettes est la même, trouvez la probabilité du meilleur des cas ;

la probabilité du pire des cas ; le nombre de paires que vous devriez
attendre dans le cas moyen.

5. a.> Démontrer la formule (2.1) pour le nombre de bits dans la représentation binaire
d'un entier positif.

b.> Démontrer la formule alternative pour le nombre de bits dans le binaire

représentation d'un entier positif n :

b = dlog 2 (n + 1)e.

c. Quelles seraient les formules analogues pour le nombre de décimales

chiffres ?

ré. Expliquez pourquoi, dans le cadre d'analyse accepté, cela n'a pas d'importance
ter si nous utilisons des chiffres binaires ou décimaux pour mesurer la taille de n.

6. Suggérez comment n'importe quel algorithme de tri peut être augmenté de manière à
le nombre dans le meilleur des cas de ses comparaisons clés égal à juste n−1 (n est la valeur d'une liste
taille, bien sûr). Pensez-vous que ce serait un ajout intéressant à tout
algorithme de tri ?

7. L'élimination gaussienne, l'algorithme classique de résolution de systèmes de n linéaires

équations à n inconnues, nécessite environ 31 n 3 multiplications, qui est le
fonctionnement de base de l'algorithme.

une. Combien de temps devriez-vous vous attendre à ce que l'élimination gaussienne fonctionne
sur un système de 1000 équations versus un système de 500 équations ?

b. Vous envisagez d'acheter un ordinateur 1000 fois plus rapide que

celui que vous possédez actuellement. Par quel facteur l'ordinateur le plus rapide
augmenter la taille des systèmes solubles dans le même laps de temps que sur le
vieux ordinateur?

8. Pour chacune des fonctions suivantes, indiquez de combien la valeur de la fonction

changera si son argument est multiplié par quatre.

une. log 2 n b. dans c. m ré. n 2 e. n 3 F. 2 n

9. Indiquez si la première fonction de chacune des paires suivantes a un

ordre de croissance plus petit, même ou plus grand (à un multiple constant près)
que la deuxième fonction.

Page 3
 une. n(n + 1) et 2000n 2 b. 100n 2 et 0,01n 3

c. log 2 n et lnn ré. journal 2

2 n et log 2 n 2

e. 2 nL1 et 2 n F. (n − 1) ! et n!

10. Invention des échecs a. Selon une légende bien connue, le jeu de
les échecs ont été inventés il y a plusieurs siècles dans le nord-ouest de l'Inde par un certain
sauge. Quand il a apporté son invention à son roi, le roi a tellement aimé le jeu
beaucoup qu'il a offert à l'inventeur toute récompense qu'il voulait. L'inventeur
demandé qu'on obtienne du grain comme suit : juste un seul grain de blé
devait être placé sur la première case de l'échiquier, deux sur la seconde,
quatre le troisième, huit le quatrième, et ainsi de suite, jusqu'à ce que les 64 cases aient
été rempli. S'il ne fallait qu'une seconde pour compter chaque grain, combien de temps faudrait-il
faut-il compter tout le grain qui lui est dû ?

b. Combien de temps faudrait-il si, au lieu de doubler le nombre de grains pour

chaque case de l'échiquier, l'inventeur a demandé d'ajouter deux grains ?

Page 4

Conseils pour les exercices 2.1

1. Les questions sont en effet aussi simples qu'elles le paraissent, bien que certaines
d'entre eux peuvent avoir des réponses alternatives. Aussi, gardez à l'esprit la mise en garde
sur la mesure de la taille d'un entier.

2. a. La somme de deux matrices est définie comme la matrice dont les éléments sont
 les sommes des éléments correspondants des matrices données.

b. La multiplication matricielle nécessite deux opérations : la multiplication et l'ad-

édition. Lequel des deux considéreriez-vous comme basique et pourquoi ?

3. L'efficacité de l'algorithme variera-t-elle sur différentes entrées de même taille ?

4. a. Les gants ne sont pas des chaussettes : ils peuvent être droitiers et gauchers.

b. Vous n'avez que deux résultats qualitativement différents possibles. Compter

le nombre de façons d'obtenir chacun des deux.

5. a. Tout d'abord, prouvez d'abord que si un entier décimal positif n a b chiffres dans son
représentation binaire, alors

2 bL1 n < 2 b .

Ensuite, prenez des logarithmes en base 2 des termes de cette inégalité.

b. La preuve est similaire à la preuve de la formule (2.1).

c. La formule sera la même, avec juste un petit ajustement pour ac-

compter pour les différentes bases.

ré. Comment passer d'une base logarithmique à une autre ?

6. Insérez une vérification indiquant si le problème est déjà résolu.

7. Une question similaire a été étudiée dans la section.

8. Utilisez soit la différence ou le rapport entre f(4n) et f(n), selon

est plus pratique pour obtenir une réponse compacte. Si c'est possible, essayez de
obtenir une réponse qui ne dépend pas de n.

9. Si nécessaire, simplifiez les fonctions en question pour distinguer les termes définissant
leurs ordres de croissance à un multiple constant près. (Nous discuterons
méthodes formelles pour répondre à ces questions dans la section suivante; pourtant,
ces questions peuvent être répondues sans connaissance de ces méthodes.)
m
10. a. Utilisez la formule P
i=0 2 i = 2 n+1 − 1.

b. Utilisez la formule pour la somme des n premiers nombres impairs ou le for-

mula pour la somme de la progression arithmétique.

Page 5

Solutions aux exercices 2.1

1. Les réponses sont les suivantes.

une. (dans; (ii) addition de deux nombres ; (iii) non

b. (i) la grandeur de n, c'est-à-dire le nombre de bits dans sa représentation binaire

phrase; (ii) multiplication de deux nombres entiers ; (iii) non

c. (dans; (ii) comparaison de deux nombres ; (iii) non (pour la norme

algorithme de balayage de liste)

ré. (i) soit l'amplitude du plus grand de deux nombres d'entrée, soit le
l'amplitude du plus petit des deux nombres d'entrée, ou la somme des
études de deux nombres d'entrée ; (ii) division modulo; (iii) oui
 e. (i) la grandeur de n, c'est-à-dire le nombre de bits dans sa représentation binaire
tation; (ii) élimination d'un numéro de la liste des candidats restants
être premier; (iii) non

F. (dans; (ii) multiplication de deux chiffres ; (iii) non

2. a. Addition de deux nombres. Il est exécuté n 2 fois (une fois pour chacun des
n 2 éléments dans la matrice en cours de calcul). .Comme le nombre total de
éléments dans deux matrices données est N = 2n 2 , le nombre total d'additions
peut également être exprimé comme n 2 = N/2.

b. Puisque sur la plupart des ordinateurs la multiplication prend plus de temps que l'addition,
la multiplication est un meilleur choix pour être considérée comme l'opération de base
de l'algorithme standard de multiplication matricielle. Chacun des n 2 éléments
du produit de deux matrices n par n est calculé comme le scalaire (point)
produit de deux vecteurs de taille n, ce qui nécessite n multiplications. le
le nombre total de multiplications est n · n 2 = n 3 = (N/2) 3/2 .

3. Cet algorithme fera toujours n comparaisons clés sur chaque entrée de taille
n, alors que ce nombre peut varier entre n et 1 pour la version classique
de recherche séquentielle.

4. a. Le nombre dans le meilleur des cas est, évidemment, deux. Le nombre le plus défavorable est
douze : un de plus que le nombre de gants d'une seule main.

b. Il n'y a que deux issues possibles ici : les deux chaussettes manquantes
faire une paire (le meilleur des cas) et les deux stocks manquants ne font pas un
paire (le pire des cas). Le nombre total de résultats différents (les moyens

Page 6

pour choisir les chaussettes manquantes) est ¡ 10

2 ¢ = 45. Le nombre de meilleurs cas
est 5 ; donc sa probabilité est de455 = 1 9 . Le nombre de cas les plus défavorables est
45 − 5 = 40 ; donc sa probabilité est de 40 45 = 8 9 . En moyenne, vous devriez
attendre 4 · 1 9 = 28 9 = 3 19 paires correspondantes.
9+ 3 ·8

5. a. Le plus petit entier positif qui a b chiffres binaires dans son binaire
l'expansion est |{z}
de 10...0
, qui est 2 bL1 ; le plus grand entier positif qui a b
bL1

chiffres binaires dans son expansion binaire

|{z}est
, qui
11...1
est 2 bL1 +2 bL2 +...+1 =
bL1

2 b − 1. Ainsi,
2 bL1 n < 2 b .

D'où
log 2 2 bL1 log 2 n < log 2 2 b

ou
b − 1 log 2 n < b.

Ces inégalités impliquent que b − 1 est le plus grand entier ne dépassant pas
log 2 n. En d'autres termes, en utilisant la définition de la fonction de plancher, nous con-
comprendre que
b − 1 = blog 2 nc ou b = blog 2 nc + 1.
 b. Si n > 0 a b bits dans sa représentation binaire, alors, comme indiqué dans
partie a,
2 bL1 n < 2 b .

D'où
2 bL1 < n + 1 ≤ 2 b

et donc
log 2 2 bL1 < log 2 (n + 1) ≤ log 2 2 b

ou
b − 1 < log 2 (n + 1) b.

Ces inégalités impliquent que b est le plus petit entier non inférieur à
log 2 (n + 1). En d'autres termes, en utilisant la définition de la fonction plafond,
nous concluons que
b = dlog 2 (n + 1)e.

c. B = blog 10 nc +1= dlog 10 (n + 1)e.

ré. b = blog 2 nc + 1 log 2 n = log 2 10 log 10 n ≈ (log 2 10)B, où B =

Page 7

blog 10 nc + 1. C'est-à-dire que les deux mesures de taille sont à peu près égales à
multiple constant pour les grandes valeurs de n.

6. Avant d'appliquer un algorithme de tri, comparez les éléments adjacents de

son entrée : si a i ≤ a i+1 pour tout i = 0,..,n − 2, stop. Généralement, il
n'est pas un ajout intéressant car il ralentit l'algorithme sur tous
mais des entrées très spéciales. A noter que certains algorithmes de tri (notamment
le tri à bulles et le tri par insertion, qui sont abordés dans les sections 3.1 et
4.1, respectivement) incorporent intrinsèquement ce test dans le corps du
algorithme.

1
T (2n) c
(2n)
7. a. 3
1
3
= 8, où c m est le temps d'une multiplication.
T (n) ≈ c
3 n3

b. On peut estimer le temps d'exécution pour résoudre des systèmes d'ordre n sur
l'ancien calculateur et celui d'ordre N sur le nouveau calculateur comme T oid (n) ≈
1 1
c m 3 n 3 et T nouveau (N) ≈ 10 L3 c m 3 N 3 , respectivement, où c m est le temps de
une multiplication sur l'ancien ordinateur. Remplacement du T oid (n) et du T nouveau (N)
1
par ces estimations dans l'équation T oid (n) = T nouveau (N) donne c m 3n 3 ≈
1
10 L3 c m 3 N 3 ou N
n 10.

8. a. log 2 4n − log 2 n = (log 2 4 + log 2 n) − log 2 n = 2.

4n

b. n = 2.

c. 4nm = 4.
(4n) 2
ré. n2 =42.

(4n) 3
e. n3 =43.
 F. 2 2
4 = 2 3n = (2 n ) 3 .

9. a. n(n + 1) n 2 a le même ordre de croissance (quadratique) que 2000n 2 à

dans un multiple constant.

b. 100n 2 (quadratique) a un ordre de croissance inférieur à 0,01n 3 (cubique).

c. Puisque changer la base d'un logarithme peut être fait par la formule

log a n = log a blog b n,

toutes les fonctions logarithmiques ont le même ordre de croissance à une con-
multiple permanent.

sept

Page 8

ré. journal 2
2 n = log 2 nlog 2 n et log 2 n 2 = 2 log n. D'où log 2 2 n a une valeur supérieure
ordre de croissance que log 2 n 2 .

e. 2 nL1 = 1 2 2 n a le même ordre de croissance que 2 n à une con-

multiple permanent.

F. (n − 1) ! a un ordre de croissance inférieur à n!=(n − 1)!n.

10. a. Le nombre total de grains dus à l'inventeur est

X64 X63
2 iL1 = 2 j = 2 64 − 1 1,8 · 10 19 .
i=1 j=0

(C'est plusieurs fois plus que ce que l'on peut obtenir en plantant avec du grain tout le
surface de la planète Terre.) S'il ne fallait qu'une seconde pour compter chaque grain,
le temps total nécessaire pour compter tous ces grains est d'environ
585 milliards d'années, plus de 100 fois plus que l'âge estimé de notre planète.

b. Ici, la quantité totale de grains aurait été égale à

1+3+ ... + (2 · 64 − 1) = 64 2 .

Avec la même vitesse de comptage d'un grain par seconde, il aurait

besoin de moins d'une heure et quatorze minutes pour compter sa modeste ré-
salle.
 8

Page 9

Exercices 2.2
1. Utilisez la notation la plus appropriée parmi O, θ et pour indiquer le
classe d'efficacité temporelle de la recherche séquentielle (voir Section 2.1)

une. au pire des cas.

b. Dans le meilleur des cas.

c. dans le cas moyen.

2. Utilisez les définitions informelles de O, θ et pour déterminer si les

les affirmations basses sont vraies ou fausses.

une. n(n + 1)/2 O(n 3 ) b. n(n + 1)/2 O(n 2 )

c. n(n + 1)/2 (n 3 ) ré. n(n + 1)/2 (n)

3. Pour chacune des fonctions suivantes, indiquer la classe θ(g(n)) la fonction

appartient à. (Utilisez le g(n) le plus simple possible dans vos réponses.) Prouvez votre
affirmations.
une. (n 2 + 1) 10 b. 10n 2 + 7n + 3

c. 2nlg(n + 2) 2 + (n + 2) 2 lg n 2 ré. 2 n+1 + 3 nL1

e. blog 2 nc

4. a. Le tableau 2.1 contient les valeurs de plusieurs fonctions qui surviennent souvent dans l'analyse
d'algorithmes. Ces valeurs suggèrent certainement que les fonctions

log n, n, nlog n, n 2 , n 3 , 2 n , n !

sont classés par ordre croissant de leur ordre de croissance. Est-ce que ces valeurs
prouver ce fait avec une certitude mathématique ?

b. Montrer que les fonctions sont bien classées par ordre croissant de leur
ordre de croissance.

5. Ordonnez les fonctions suivantes selon leur ordre de croissance (à partir du

du plus bas au plus élevé):
n ,3n.
(n−2)!, 5 lg(n+ 100) 10 , 2 2n , 0,001n 4 +3n 3 +1, dans 2 n, 3

6. a. Montrer que tout polynôme de degré k, p(n) = a k n k + a kL1 n KL1 +

··· + a 0 avec a k > 0, appartient à θ(n k ).

b. Montrer que les fonctions exponentielles a n ont des ordres de croissance différents
pour différentes valeurs de base a > 0.

9
Page 10

7. Prouver (en utilisant les définitions des notations impliquées) ou réfuter (en
donnant un contre-exemple spécifique) les affirmations suivantes.

une. Si t(n) O(g(n)), alors g(n) Ω(t(n)).

b. θ(ag(n)) = θ(g(n)), où a > 0.

c. (g(n)) = O(g(n)) ∩ Ω(g(n)).

d.> Pour deux fonctions non négatives t(n) et g(n) définies sur l'ensemble des
entiers non négatifs, soit t(n) O(g(n)), soit t(n) ∈ Ω(g(n)), ou les deux.

8. > Démontrer le théorème de la section pour

une. notation.

b. notation.

9. Nous avons mentionné dans cette section que l'on peut vérifier si tous les éléments d'un
array sont distincts par un algorithme en deux parties basé sur le tri préalable du tableau.

une. Si le pré-tri est effectué par un algorithme avec l'efficacité temporelle en

θ(nlog n), quelle sera la classe d'efficacité temporelle de l'ensemble de l'algorithme ?

b. Si l'algorithme de tri utilisé pour le tri préliminaire nécessite un tableau supplémentaire de

taille n, quelle sera la classe d'efficacité spatiale de l'ensemble de l'algorithme ?

10. L'étendue d'un ensemble fini non vide de n nombres réels S est définie comme
différence entre le plus grand et le plus petit élément de S. Pour chaque représentation
sation de S donnée ci-dessous, décrivez en anglais un algorithme pour calculer
la gamme. Indiquer les classes d'efficacité temporelle de ces algorithmes en utilisant
la notation la plus appropriée (O, θ ou Ω).

une. Un tableau non trié

b. Un tableau trié

c. Une liste à chaînage simple triée

ré. Un arbre de recherche binaire

11. Plus léger ou plus lourd ? Vous avez n > 2 pièces d'apparence identique et un
balance panoramique sans poids. L'une des pièces est un faux, mais vous le faites
sait pas si elle est plus légère ou plus lourde que les pièces authentiques, que toutes
peser le même. Concevoir un algorithme θ(1) pour déterminer si le faux
pièce est plus légère ou plus lourde que les autres.

dix

Page 11
 12. > Porte dans un mur Vous êtes face à un mur qui s'étend à l'infini dans les deux
directions. Il y a une porte dans le mur, mais tu ne sais ni jusqu'où
loin ni dans quelle direction. Vous ne pouvez voir la porte que lorsque vous êtes
juste à côté. Concevoir un algorithme qui vous permet d'atteindre la porte
en marchant au plus O(n) pas où n est le nombre (inconnu de vous)
d'étapes entre votre position initiale et la porte. [Par95]

11

Page 12

Conseils pour les exercices 2.2

 1. Utilisez lesdéfinitions
2.1) et les comptes correspondants
de O, θ et Ω. de l'opération de base de l'algorithme (voir Sec-

2. Établir d'abord l'ordre de croissance de n(n+1)/2, puis utiliser le

définitions de O, θ et . (Des exemples similaires ont été donnés dans la section.)

3. Simplifier les fonctions données pour singulariser les termes définissant leurs ordres
de croissance.

4. a. Vérifiez attentivement les définitions pertinentes.

b. Calculer les limites de rapport de chaque paire de fonctions consécutives sur

la liste.

5. Simplifiez d'abord certaines des fonctions. Ensuite, utilisez la liste des fonctions
dans le tableau 2.2 pour « ancrer » chacune des fonctions données. Prouvez leur finale
placement en calculant des limites appropriées.

6. a. Vous pouvez prouver cette affirmation soit en calculant une limite appropriée
ou en appliquant l'induction mathématique.

b. Limite de calcul un n
n→o 1 /un2 n
.

7. Prouvez l'exactitude de (a), (b) et (c) en utilisant la dé-

finitions; construire un contre-exemple pour (d) (par exemple, en construisant deux
fonctions se comportant différemment pour les valeurs paires et impaires de leurs arguments).

8. La preuve de la partie (a) est similaire à celle donnée pour l'assertion du théorème
dans la section 2.2. Bien sûr, différentes inégalités doivent être utilisées pour borner
la somme d'en bas.

9. Suivez le plan d'analyse utilisé dans le texte lorsque l'algorithme a été men-
tionné pour la première fois.

10. Vous pouvez utiliser des algorithmes simples pour les quatre questions posées.
Utilisez la notation O pour la classe d'efficacité temporelle de l'un d'eux, et le θ
notation pour les trois autres.

11. Le problème peut être résolu en deux pesées.

12. Vous devez marcher par intermittence à gauche et à droite à partir de votre position initiale
jusqu'à ce que la porte soit atteinte.

12

Page 13

Solutions aux exercices 2.2

1. a. Puisque C pire (n) = n, C pire (n) θ(n).

b. Puisque C meilleur (n)=1, C meilleur (1) ∈ θ(1).

p(n+1)
c. Puisque C moy (n) = 2 + n(1 − p) = (1 − p 2 )n + p
2 où 0 p 1,
C moy (n) θ(n).

2. n(n + 1)/2 n 2 /2 est quadratique. Donc

 une. n(n + 1)/2 O(n 3 ) est vrai. b. n(n + 1)/2 O(n 2 ) est vrai.

c. n(n + 1)/2 (n 3 ) est faux. ré. n(n + 1)/2 (n) est vrai.

3. a. Informellement, (n 2 + 1) 10 (n 2 ) 10 = n 20 ∈ θ(n 20 ) Formellement,

´ 10
(n 2 +1) 10 (n 2 +1) 10
limite n 20 = limite (n 2 ) 10 = limite n2 == limite = 1.
n→o n→o
n→o ³ n 2 +1 n→o ¡1 + 1
n2 ¢ 10

Donc (n 2 + 1) 10 θ(n 20 ).

Remarque : Une preuve alternative peut être basée sur la formule binomiale et
l'assertion de l'exercice 6a.
10n 2 = √10n ∈ θ(n). Officiellement,
b. Informellement, √10n 2 + 7n + 3 ≈
√10n 2 +7n+3

limite m = limite n2 = limite m +3

n→o
n→o q 10n 2 +7n+3 n→o q10 + 7
n2 = 10.

D'où √10n 2 + 7n + 3 θ(n).

c. 2nlg(n + 2) 2 + (n + 2) 2 lg n 2 = 2n2 lg(n +2)+(n + 2) 2 (lg n − 1) ∈

(nlg n) + θ(n 2 lg n) = θ(n 2 lg n).

ré. 2 n+1 + 3 nL1 = 2 n 2+3 n 1

3 ∈ θ(2 n ) + θ(3 n ) = θ(3 n ).

e. De manière informelle, blog 2 nc log 2 n ∈ θ(log n). Formellement, en utilisant l'in-

égalités x − 1 < bxc ≤ x (voir Annexe A), on obtient une borne supérieure

blog 2 nc ≤ log 2 n

et une borne inférieure

1 1
blog 2 nc > log 2 n − 1 ≥ log 2 n − log 2 n (pour tout n ≥ 4) = log 2 n.
2 2
Donc blog 2 nc θ(log 2 n) = θ(log n).

13

Page 14

4. a. L'ordre de croissance et les notations associées O, Ω et traitent de

le comportement asymptotique des fonctions lorsque n tend vers l'infini. Donc non
valeurs spécifiques de fonctions dans une plage finie de valeurs de n, suggestive
comme ils pourraient être, peuvent établir leurs ordres de croissance avec des mathématiques
certitude.
1
log 2 n (log 2 n) 0 1
b. limite
n→o
m = limite
n→o
(n) 0 = limite
n→o
log 2 e
1 = log 2 e lim
n→o
m = 0.

m 1
limite
n→o
n log 2 n = limite
n→o
log 2 n = 0.

n log 2 n log 2 n
limite
n→o
n2 = limite
n→o
m = (voir la première limite de cet exercice) = 0.

n2 1
limite m = 0.
n→o n3 = limite
n→o

n3 (n 3 ) 0 3n 2 n2 (n 2 ) 0
limite (2 ) 0 = limite 2 ln 2 = 3 en 2 n→o
limite limite
en 2 n→o (2 )0
n→o 2 = limn→o n→o 2 =3
2n m (n) 0
= 3 en 2 limite
2 ln 2 = 6 en 2 n→o limite limite
n→o
2
= 6 en
2
2 2 n→o (2 )0
1 1
= 6 en limite 2 ln 2 = 6 dans limite
2 = 0.
2 2 n→o 3 2n→o

2
limite
n→o
n! = (voir l'exemple 3 dans la section) 0.
 5. (n−2) ! ∈ θ((n−2)!), 5 lg(n+100) 10 = 50 lg(n+100) ∈ θ(log n), 2 2n =
dans
3
(2 2 ) n θ(4 n ), 0,001n 4 + 3n 3 + 1 θ(n 4 ), ln 2 n ∈ θ(log 2 n),
1
??
(n ), 3 n θ(3 n ). La liste de ces fonctions classées par ordre croissant
3

l'ordre de croissance est le suivant :

n, 0,001n 4 + 3n 3 + 1, 3 n , 2 2n , (n − 2) !
5 lg(n + 100) 10 , ln 2 n, 3

p(n) a n +a ^1 n ^1 +...+a 0 un ^1
6. a. limite n =n→o
limite n = limite (un k + m + ... + un 0
n→o n→o n )
= un k > 0.

D'où p(n) (n k ).

b.

0 si un 1 < un 2 un n
un
1 n 1 ∈ o(un2n)
limite = limite = 1 si un 1 = un 2 un n
n→o
un
2 n n→o µa 1 un 2 ¶ n ??
1∈ θ(un n2 )
si a 1 > a 2 un n
2 ∈ o(un 1n)

7. a. L'assertion doit être correcte car elle indique que si l'ordre de

la croissance de t(n) est inférieure ou égale à l'ordre de croissance de g(n), alors

14

Page 15

l'ordre de croissance de g(n) est supérieur ou égal à l'ordre de croissance

de t(n). La preuve formelle est aussi immédiate :

t(n) cg(n) pour tout n ≥ n 0 , où c > 0,

implique
1
(
c)t(n) g(n) pour tout n n 0 .

b. L'assertion selon laquelle θ(ag(n)) = θ(g(n)) devrait être vraie car ag(n)
et g(n) ne diffèrent que par un multiple constant positif et, par conséquent, par le
définition de , doit avoir le même ordre de croissance. La preuve formelle
doit montrer que θ(ag(n)) ⊆ θ(g(n)) et θ(g(n)) ⊆ θ(ag(n)). Laisser
f(n) ∈ θ(ag(n)); nous allons montrer que f(n) θ(g(n)). En effet,

f(n) cag(n) pour tout n ≥ n 0 (où c > 0)

peut être réécrit comme

f(n) c 1 g(n) pour tout n ≥ n 0 (où c 1 = ca > 0),

c'est-à-dire f(n) θ(g(n)).

Soit maintenant f(n) θ(g(n)); nous allons montrer que f(n) ∈ θ(ag(n)) pour a > 0.
En effet, si f(n) θ(g(n)),

f(n) cg(n) pour tout n ≥ n 0 (où c > 0)

et donc
c c
 f(n) une
ag(n) = c 1 ag(n) pour tout n ≥ n 0 (où c 1 = une
> 0),
c'est-à-dire f(n) θ(ag(n)).

c. L'assertion est évidemment correcte (similaire à l'assertion selon laquelle a = b

si et seulement si a b et a ≥ b). La preuve formelle doit montrer que
θ(g(n)) ⊆ O(g(n)) ∩ Ω(g(n)) et que O(g(n)) ∩ Ω(g(n)) ⊆ θ(g(n)),
qui découlent immédiatement des définitions de O, Ω et θ.

ré. L'affirmation est fausse. La paire de fonctions suivante peut servir de

un contre-exemple

n si n est pair n2 si n est pair

t(n) = et g(n) =
?? ??
n2 si n est impair n si n est impair

15

Page 16

8. a. Nous devons prouver que si t 1 (n) Ω(g 1 (n)) et t 2 (n) ∈ Ω(g 2 (n)), alors
t 1 (n) + t 2 (n) Ω(max{g 1 (n), g 2 (n)}).

Preuve Puisque t 1 (n) ∈ Ω(g 1 (n)), il existe une constante positive c 1

et un entier non négatif n 1 tel que

t 1 (n) c 1 g 1 (n) pour tout n ≥ n 1 .

Puisque t 2 (n) Ω(g 2 (n)), il existe une constante positive c 2 et une

entier non négatif n 2 tel que

t 2 (n) c 2 g 2 (n) pour tout n ≥ n 2 .

Notons c = min{c 1 ,c 2 } et considérons n ≥ max{n 1 ,n 2 } de sorte que l'on

peut utiliser les deux inégalités. En additionnant les deux inégalités ci-dessus, on obtient
Suivant:

t 1 (n) + t 2 (n) c 1 g 1 (n) + c 2 g 2 (n)

cg 1 (n) + cg 2 (n) = c[g 1 (n) + g 2 (n)]
cmax{g 1 (n),g 2 (n)}.

D'où t 1 (n) + t 2 (n) ∈ Ω(max{g 1 (n),g 2 (n)}), avec les constantes c et

n 0 requis par la définition O étant min{c 1 ,c 2 } et max{n 1 ,n 2 }, re-
spécifiquement.

b. La preuve découle immédiatement du théorème démontré dans le texte

(la partie O), l'assertion prouvée dans la partie (a) de cet exercice (la partie Ω),
et la définition de (voir exercice 7c).

9. a. Étant donné que le temps d'exécution de la partie de tri de l'algorithme sera toujours
dominer le temps de course du second, c'est le premier qui va dissuader
exploiter l'efficacité du temps de l'ensemble de l'algorithme. Formellement, il résulte de
égalité
(nlog n) + O(n) = θ(nlog n),

dont la validité est facile à prouver de la même manière que celle de la section
théorème.
 b. Étant
la classedonné que la
d'efficacité deuxième
spatiale serapartie de l'algorithme
déterminée par celle n'utilisera pas d'espace
de la première supplémentaire,
partie (de tri). le
Ce sera donc (n).

10. a. Scannez le tableau pour trouver les valeurs maximales et minimales parmi ses
éléments, puis calculez la différence entre eux. L'algorithme
l'efficacité du temps est θ(n). Remarque : bien que l'on puisse trouver à la fois le maximum
et valeurs minimales dans un tableau à n éléments avec environ 1,5n comparaisons

16

Page 17

(voir les solutions au problème 5 dans les exercices en 2.3 et au problème 2 dans Ex-
ercises 5.1), cela ne change pas la classe d'efficacité linéaire, bien sûr.

b. Pour un tableau trié, nous pouvons simplement calculer la différence entre

ses premier et dernier éléments : A[n − 1] − A[0]. La classe d'efficacité temporelle est
évidemment (1).

c. Le plus petit élément est dans le premier nœud de la liste et donc son
les valeurs peuvent être obtenues en temps constant. L'élément le plus important se trouve dans le
dernier nœud accessible uniquement par le parcours de toute la liste, ce qui nécessite
temps linéaire. Calculer la différence entre les deux valeurs nécessite
temps constant. Par conséquent, la classe d'efficacité temporelle est θ(n).

ré. Le plus petit (le plus grand) élément d'un arbre de recherche binaire se trouve à gauche
nœud le plus (le plus à droite). Pour l'atteindre, il faut commencer par la racine et
suivre la chaîne de pointeurs gauche-enfant (droit-enfant) jusqu'à ce qu'un nœud avec le
le pointeur null enfant gauche (enfant droit) est atteint. Selon la structure
de l'arbre, cette chaîne de nœuds peut avoir une longueur comprise entre 1 et n nœuds. D'où,
le temps d'atteindre son dernier nœud sera en O(n). Le temps d'exécution du
tout l'algorithme sera également linéaire : O(n) + O(n) + (1) = O(n).

11. Le puzzle peut être résolu en deux pesées comme suit. Commencez par prendre
de côté une pièce si n est impair et deux pièces si n est pair. Après cela, divisez le
nombre pair de pièces restantes en deux groupes de taille égale et les mettre
sur les plateaux opposés de la balance. S'ils pèsent le même poids, toutes ces pièces
sont authentiques et la fausse pièce fait partie des pièces mises de côté. Afin que nous puissions
peser le groupe mis de côté d'une ou deux pièces contre le même nombre de
pièces authentiques : si la première pèse moins, la fausse pièce est plus légère, sinon,
c'est plus lourd. Si la première pesée n'aboutit pas à une balance, prenez le
groupe plus léger et, si le nombre de pièces qu'il contient est impair, ajoutez-y l'une des
pièces initialement mises de côté (qui doivent être authentiques). Divisez toutes ces pièces
en deux groupes de taille égale et les peser. S'ils pèsent le même poids, tous
ces pièces sont authentiques et donc la fausse pièce est plus lourde ; autrement,
ils contiennent le faux, qui est plus léger.
Remarque : le puzzle fournit un exemple très rare d'un problème qui peut
être résolu en le même nombre d'opérations de base (à savoir, deux pesées)
quelle que soit la taille de l'instance du problème (ici, le nombre de pièces)
est. Bien sûr, si nous avions envisagé de mettre une pièce sur la balance comme
l'opération de base de l'algorithme, l'efficacité de l'algorithme aurait été en
(n) au lieu de θ(1).

12. L'idée clé ici est de marcher par intermittence à droite et à gauche à chaque fois
exponentiellement plus loin de la position initiale. Une mise en œuvre simple
de cette idée est de faire ce qui suit jusqu'à ce que la porte soit atteinte : Pour i = 0,1,...,
faire 2 i pas vers la droite, revenir à la position initiale, faire 2 i pas pour
la gauche et revenez à la position initiale. Soit 2 kL1 < n 2 k . le
 17

Page 18

le nombre d'étapes dont cet algorithme aura besoin pour trouver la porte peut être estimé
ci-dessus comme suit :
kL1
X
4 · 2 i + 3 · 2 k = 4(2 k − 1) + 3 · 2 k < 7 · 2 k = 14 · 2 kL1 < 14n.
i=0

Le nombre de pas effectués par l'algorithme est donc en O(n). (Noter:

Il n'est pas difficile d'améliorer la constante multiplicative avec une meilleure
algorithme.)

18
Page 19

Exercices 2.3
1. Calculez les sommes suivantes.

une. 1+3+5+7+ ··· + 999

b. 2+4+8+16+ ··· + 1024

n+1 n+1 nL1

c. P ré. P e. P
i=3 1 je = 3 je i=0 i(i + 1)
m m nL1
F. P g. P h. P
j=1 3 j+1 i=1 Pn j=1 ij i=0 1/i(i + 1)
2. Trouvez l'ordre de croissance des sommes suivantes.
nL1 nL1
une. P b. P
i=0 (i 2 +1) 2 i=2 lg i 2
m nL1
c. P ré. P
i=1 (i + 1)2 iL1 i=0 P iL1 j=0 (i + j)

Utilisez la notation θ(g(n)) avec la fonction g(n) la plus simple possible.

3. La variance d'échantillon de n mesures x 1 ,x 2 ,...,x n peut être calculée comme

Pn m

i=1 (x i − ¯x) 2 où x = P i=1 xi

n−1 m
ou Pn m

i=1 x 2 je − (P i=1 x i ) 2 /n .
n−1
Trouvez et comparez le nombre de divisions, de multiplications et d'additions.
tions/soustractions (les additions et les soustractions sont généralement regroupées en
ensemble) qui sont nécessaires pour calculer la variance selon chacun des
ces formules.

4. Considérez l'algorithme suivant.

Algorithme Mystère(n)
//Entrée : Un entier non négatif n
S0
pour i 1 à n faire
SS+ii
Retour

une. Que calcule cet algorithme ?

b. Quel est son fonctionnement de base ?

c. Combien de fois l'opération de base est-elle exécutée ?

19

Page 20
 ré. Quelle est la classe d'efficacité de cet algorithme ?

e. Suggérez une amélioration, ou un meilleur algorithme, et en-

indiquer sa classe d'efficacité. Si vous ne pouvez pas le faire, essayez de prouver qu'en fait,
cela ne peut pas être fait.

5. Considérez l'algorithme suivant.

Algorithme Secret(A[0..n − 1])

//Entrée : Un tableau A[0..n − 1] de n nombres réels
minval A[0]; maxval ← A[0]
pour i ← 1 à n − 1 faire
si A[i] < minval
minval A[i]
si A[i] > maxval
maxval A[i]
retourner maxval − minval

Répondez aux questions a—e du problème 4 sur cet algorithme.

6. Considérez l'algorithme suivant.

Algorithme Enigma(A[0..n − 1,0..n − 1])

//Entrée : Une matrice A[0..n − 1,0..n − 1] de nombres réels
pour i ← 0 à n − 2 do
pour j ← i + 1 à n − 1 do
si A[i,j] 6= A[j,i]
retourner faux
retourner vrai

Répondez aux questions a—e du problème 4 sur cet algorithme.

7. Améliorer la mise en œuvre de l'algorithme de multiplication matricielle (voir

Exemple 3) en réduisant le nombre d'ajouts effectués par l'algorithme.
Quel effet ce changement aura-t-il sur l'efficacité de l'algorithme ?

8. Déterminer l'ordre de croissance asymptotique pour le nombre total de fois

les portes sont basculées dans le puzzle des portes de casier (problème 12 dans les exercices
1.1).

9. Démontrer la formule

Xm n(n+1)
i =1+2+ ··· + n =
i=1
2

soit par induction mathématique, soit en suivant l'intuition d'un

ancien écolier nommé Karl Friedrich Gauss (1777-1855) qui a grandi jusqu'à
devenir l'un des plus grands mathématiciens de tous les temps.

20

Page 21

10. Calcul mental Une table 10×10 est remplie de nombres répétés sur sa
diagonales comme indiqué ci-dessous. Calculer la somme totale des nombres du tableau
dans ta tête. (après [Cra07, Question 1.33])

12 3 9 dix
2 3 9 dix 11
 3 9 dix 11
9 dix 11
9 dix 11
9 dix 11
9 dix 11
9 dix 11 17
9 dix 11 17 18
dix 11 17 18 19

11. Considérons la version suivante d'un algorithme important que nous allons
étudier plus tard dans le livre.

Algorithme GE(A[0..n − 1,0..n])

//Entrée : Une matrice n × (n + 1) A[0..n − 1,0..n] de nombres réels
pour i ← 0 à n − 2 do
pour j ← i + 1 à n − 1 do
pour k ← i à n faire
A[j,k] A[j,k] − A[i,k] ∗ A[j,i] / A[i,i]
retour A

a.> Trouver la classe d'efficacité temporelle de cet algorithme.

b.> Quelle inefficacité flagrante ce pseudocode contient-il et comment

être éliminé pour accélérer l'algorithme ?

12. Le voisinage de von Neumann Combien de carrés un par un sont géné-

par l'algorithme qui commence par un seul carré et sur chaque
de ses n itérations ajoute de nouveaux carrés tout autour de l'extérieur. Combien
des carrés un par un sont générés à la nième itération ? [Gar99] (Dans le
langage de la théorie des automates cellulaires, la réponse est le nombre de cellules dans
le voisinage de von Neumann de la plage n.) Les résultats pour n = 0, 1 et

21

Page 22

2 sont illustrés ci-dessous.

n=0 n=1 n=2

13. Numérotation des pages Trouvez le nombre total de chiffres décimaux nécessaires pour
bering pages dans un livre de 1000 pages. Supposons que les pages sont num-
 béré consécutivement en commençant par 1.

22

Page 23

Conseils pour les exercices 2.3

1. Utilisez les formules et les règles de sommation courantes énumérées à l'annexe A. Vous
peut avoir besoin d'effectuer quelques opérations algébriques simples avant d'appliquer
eux.

2. Trouvez une somme parmi celles de l'annexe A qui ressemble à la somme de

question et essayer de transformer la seconde en la première. Notez que vous
n'ont pas besoin d'obtenir une formule fermée pour une somme avant d'établir sa
ordre de croissance.

3. Suivez simplement les formules en question.

4. a. Traçage de l'algorithme pour obtenir sa sortie pour quelques petites valeurs de n (par exemple,
n = 1, 2 et 3) devrait vous aider si vous en avez besoin.

b. Nous avons été confrontés à la même question pour les exemples abordés dans le texte.
L'un d'eux est particulièrement pertinent ici.

c. Suivez le plan décrit dans la section.

ré. En fonction de n, la réponse doit découler immédiatement de votre

réponse à la partie (c). Vous pouvez également donner une réponse en fonction de
le nombre de bits dans la représentation du n (pourquoi ?).

e. Vous n'avez pas rencontré cette somme quelque part ?

 5. a. Traçage de l'algorithme pour obtenir sa sortie pour quelques petites valeurs de n (par exemple,
n = 1, 2 et 3) devrait vous aider si vous en avez besoin.

b. Nous avons été confrontés à la même question pour les exemples discutés dans la section
tion. L'un d'eux est particulièrement pertinent ici.

c. Vous pouvez soit suivre le plan de la section en configurant et en calculant

une somme ou répondre directement à la question. (Essayez de faire les deux.)

ré. Votre réponse découlera immédiatement de la réponse à la partie (c).

e. L'algorithme doit-il toujours faire deux comparaisons sur chaque

itération? Cette idée peut être développée davantage pour obtenir une
amélioration que l'évidente - essayez de le faire pour un tableau à quatre éléments
puis généraliser l'intuition. Mais peut-on espérer trouver un algorithme
avec une efficacité meilleure que linéaire ?

6. a. Les éléments A[i,j] et A[j,i] sont symétriques par rapport au

diagonale de la matrice.

b. Il n'y a qu'un seul candidat ici.

23

Page 24

c. Vous ne pouvez enquêter que sur le pire des cas.

ré. Votre réponse découlera immédiatement de la réponse à la partie (c).

e. Comparez le problème que l'algorithme résout avec la façon dont il le fait.

7. Le calcul d'une somme de n nombres peut être fait avec n − 1 additions. Comment
l'algorithme en fait beaucoup dans le calcul de chaque élément du produit
matrice?

8. Mettre en place une somme pour le nombre de fois toutes les portes et basculées et trouver
son ordre de croissance asymptotique en utilisant certaines propriétés de l'annexe
UNE.

9. Pour l'étape générale de la preuve par induction, utilisez la formule

m nL1
X X
je = je + n.
i=1 i=1

Le jeune Gauss a calculé la somme 1+2+ ··· + 99 + 100 en remarquant

qu'il peut être calculé comme la somme de 50 paires, chacune avec la même somme.

10. Il existe au moins deux manières différentes de résoudre ce problème, qui vient
à partir d'une série de questions d'entretien à Wall Street.

11. a. L'établissement d'une somme ne devrait pas poser de difficultés. En utilisant la somme standard
les formules et les règles de mation demanderont plus d'efforts que dans le précédent
exemples, cependant.

b. Optimisez la boucle la plus interne de l'algorithme.

12. Établir une somme pour le nombre de carrés après n itérations de l'algorithme
puis simplifiez-le pour obtenir une réponse fermée.

13. Pour dériver une formule exprimant le nombre total de chiffres en fonction de
 le nombre de pages n, où 1 n ≤ 1000, il est pratique de partitionner
le domaine de la fonction en plusieurs intervalles naturels.

24

25

Solutions aux exercices 2.3

P
500
P
500
P
500

1. a. 1+3+5+7+...+999 = (2i-1) = 2i- 1=2 500*5012 -500 = 250 000.

i=1 i=1 i=1

P 500

(Ou en utilisant la formule de la somme des nombres entiers (2i-1)

impairs :
= 500 2 =
i=1

250 000.
Soit en utilisant la formule de la somme de la progression arithmétique avec
(a + a ) n (1+999)500 1
un 1 = 1, un n = 999 et n = 500 : 2 = 2 = 250 000.)

Pdix Pdix
b. 2+4+8+16+...+1 024 = 2 je = 2 i −1 = (2 11 −1)−1=2 046.
i=1 i=0

(Ou en utilisant la formule de la somme des séries géométriques avec a = 2,

q = 2, et n = 9 : a q +1 L1 qL1 =22 10 L1
2L1 = 2 046.)

P
n+1

c.
1=(n + 1) − 3+1= n − 1.
i=3
P
n+1
P
n+1
P2 (n+1)(n+2)
ré. je = je = 2 − 3 = n +3nL42 . 2

i=3 i=0
i=0 i −
P
nL1
P
nL1
P
nL1
P
nL1

e. i(i + 1) = (je 2 + je) = je 2 + je = (nL1)n(2nL1)

6 + (nL1)n2
i=0 i=0 i=0 i=0

(n 2 L1)n
= 3 .

Pm Pm Pm
F. 3 j+1 = 3 3j=3[ 3 j − 1] = 3[ 3 +1 L1
3L1 − 1] = 3 +2 L9 2 .
j=1 j=1 j=0

Pm
Pm Pm
Pm Pm n(n+1) n(n+1) Pm n(n+1) n(n+1)
g. ij = je j= je 2 = 2 je = 2 2
i=1 j=1 i=1 j=1 i=1 i=1

n 2 (n+1) 2
= 4 .
m m
h. P i+1 )
i=1 1/i(i + 1) = P i=1 ( 1 je − 1
=(1 2 )+( 1 3 ) + ... + ( 1 m )+( 1 n+1 = n n+1 .
1-1 2−1 nL1 − 1 n − 1 n+1 )=1 − 1
(Il s'agit d'un cas particulier de la série dite télescopique - voir Annexe
vous
A–P ) = un u − un iL1.)
i=i (a i − a iL1

P
nL1
P
nL1
P
nL1
P
nL1
P
nL1

2. a. (je 2 + 1) 2 = (i 4 + 2i 2 + 1) = je 4 + 2 je 2 + 1
i=0 i=0 i=0 i=0 i=0
nL1
P P
nL1

∈ θ(n 5 ) + θ(n 3 ) + θ(n) = θ(n 5 ) (ou juste (i 2 + 1) 2 ≈ i 4 θ(n 5 )).

i=0 i=0

P
nL1
P
nL1 nL1
P Pm
 b. i=2 log 2 je 2 = i=2 2 log 2 i = 2 i=2 log 2 i = 2 i=1
log 2 i − 2 log 2 n
∈ 2θ(nlog n) − θ(log n) = θ(nlog n).

25

Page 26

Pm Pm Pm Pm P
nL1

c. (i + 1)2 iL1 = i2 iL1 + 2 iL1 = 1 2 i2 je + 2j

i=1 i=1 i=1 i=1 j=0

Pm
Pm

∈ θ(n2 n ) + θ(2 n ) = θ(n2 n ) (ou (i + 1)2 iL1 ≈ 1 2 i2 i θ(n2 n )).

i=1 i=1

P
nL1
P
iL1
P
nL1 iL1
P P
iL1
P
nL1
P
nL1

ré. (i + j) = [ je + j] = [i 2 + (iL1)i)2 ]= [ 23 je 2 − 21 je]

i=0 j=0 i=0 j=0 j=0 i=0 i=0
nL1
P P
nL1

=32 je 2 − 21
i=0
i=0 i ∈ θ(n 3 ) − θ(n 2 ) = θ(n 3 ).

3. Pour la première formule : D(n)=2, M(n) = n, A(n) + S(n) = [(n − 1) +

(n − 1)] + (n + 1) = 3n − 1.

Pour la deuxième formule : D(n) = 2, M(n) = n + 1, A(n) + S(n) =

[(n − 1) + (n − 1)] + 2 = 2n.

Pm
4. a. Calcule S(n) = je 2 .
i=1

b. La multiplication (ou, si la multiplication et l'addition sont supposées prendre

le même laps de temps, l'un ou l'autre).

Pm
c. C(n) = 1 = n.
i=1

ré. C(n) = n θ(n). Puisque le nombre de bits b = blog 2 nc + 1 log 2 n

et donc n 2 b , C(n) ≈ 2 b ∈ θ(2 b ).

Pm n(n+1)(2n+1)
e. Utilisez la formule je 2 = 6 pour calculer la somme dans θ(1)
i=1

temps (qui suppose que le temps des opérations arithmétiques reste constant
quelle que soit la taille des opérandes des opérations).

5. a. Calcule la plage, c'est-à-dire la différence entre le plus grand et le

plus petits éléments.

b. Une comparaison d'éléments.

P
nL1

c. C(n) =
i=1 2 = 2(n − 1).
ré. (n).

e. Une amélioration évidente pour certaines entrées (mais pas pour le pire des cas)
consiste à remplacer les deux instructions if par la suivante :

si A[i] < minval minval ← A[i]

26
27

sinon si A[i] > maxval maxval A[i].

Une autre amélioration, à la fois plus subtile et substantielle, repose sur la
observation qu'il est plus efficace de mettre à jour le minimum et le maximum
valeurs vues jusqu'à présent non pas pour chaque élément mais pour une paire de deux
éléments. Si deux de ces éléments sont d'abord comparés l'un à l'autre, le
les mises à jour ne nécessiteront que deux comparaisons supplémentaires pour un total de trois com-
paraisons par paire. Notez que la même amélioration peut être obtenue en
un algorithme diviser pour régner (voir le problème 2 dans les exercices 5.1).

6. a. L'algorithme renvoie « vrai » si sa matrice d'entrée est symétrique et

"faux" si ce n'est pas le cas.

b. Comparaison de deux éléments matriciels.

P
nL2
P
nL1
P
nL2

c. C pire (n) = 1=
i=0 j=i+1
i=0 [(n − 1) − (i + 1) + 1)
P
nL2
(nL1)n
= 2 .
i=0 (n − 1 − i)=(n − 1) + (n − 2) + ... +1=
ré. Quadratique : C pire (n) ∈ θ(n 2 ) (ou C(n) ∈ O(n 2 )).

e. L'algorithme est optimal car tout algorithme qui résout ce problème

lem doit, dans le pire des cas, comparer (n − 1)n/2 éléments dans le
partie triangulaire de la matrice avec leurs homologues symétriques dans le
partie triangulaire inférieure, qui est tout ce que fait cet algorithme.

7. Remplacez le corps de la boucle j par le fragment suivant :

C[i,j] A[i,0] ∗ B[0,j]

pour k ← 1 à n − 1 do
C[i,j] C[i,j] + A[i,k] ∗ B[k,j]

Cela diminuera le nombre d'ajouts de n 3 à n 3 − n 2 , mais le

nombre de multiplications sera toujours n 3 . La classe d'efficacité de l'algorithme
restera cubique.

8. Soit T(n) le nombre total de fois où toutes les portes sont basculées. le
l'énoncé du problème implique que

Xm
T(n) = bn/ic.
i=1

m
Puisque x − 1 < bxc x et P
i=1 1/i lnn + 7, où 7 = 0,5772...( voir

27

Page 28
 Annexe A),

Xm Xm
T(n) n/je = n 1/i n(lnn + 7) ∈ θ(nlog n).
i=1 i=1

De la même manière,

Xm Xm Xm
T(n) > (n/i − 1) = n 1/i − 1 ≈ n(lnn + 7) − n ∈ θ(nlog n).
i=1 i=1 i=1

Ceci implique que T(n) θ(nlog n).

Remarque : Alternativement, nous pourrions utiliser la formule pour approximer les sommes
par des intégrales définies (voir Annexe A) :
m m
X X m
1
T(n) n/i = n(1+
i=1 1 xdx) = n(1+lnn) ∈ θ(nlog n)
i=2 1/i) n(1+Z
et
m m m
X X X n+1
1
T(n) > (n/i−1) = n 1/je−
i=1 i=1
1 xdx−n= nln(n+1)−n θ(nlog n).
i=1 1 nZ

Pm n(n+1)
9. Voici une preuve par induction mathématique que je = 2 pour chaque
i=1

entier positif n.
Pm P1 ??
n(n+1) ?? 1(1+1)
(i) Pas de base : Pour n = 1, je = je = 1 et 2 ¯ n=1 = 2 = 1.
i=1 i=1
Pm n(n+1)
(ii) Étape inductive : supposons que je = 2 pour un entier positif n.
i=1

P
n+1
(n+1)(n+2)
Il faut montrer qu'alors je = 2 . Ceci est obtenu comme suit :
i=1

P
n+1
Pm
n(n+1) n(n+1)+2(n+1) (n+1)(n+2)
je = i + (n + 1) = 2 + (n + 1) = 2 = 2 .
i=1 i=1

Le jeune Gauss a calculé la somme

1+2+ ··· + 99 + 100

en remarquant qu'il peut être calculé comme la somme de 50 paires, chacune avec le
somme 101 :
1 + 100 = 2 + 99 = ... = 50 + 51 = 101.

Par conséquent, la somme totale est égale à 50·101 = 5 050. (Le célèbre historique
l'anecdote prétend que son professeur a donné cette tâche à une classe pour garder

28

Page 29

la classe occupée.) L'idée de Gauss peut être facilement généralisée à un

n en ajoutant
S(n)=1+2+ ··· + (n − 1) + n
 et
S(n) = n + (n − 1) + ··· +2+1

obtenir

n(n+1)
2S(n)=(n + 1)n et donc S(n) = .
2

10. Le but ici est de calculer (dans sa tête) la somme des nombres dans
Le tableau ci-dessous:

12 3 9 dix
2 3 9 dix 11
3 9 dix 11
9 dix 11
9 dix 11
9 dix 11
9 dix 11
9 dix 11 17
9 dix 11 17 18
dix 11 17 18 19

La première méthode est basée sur l'observation que la somme de deux nombres
bres dans les carrés symétriques par rapport à la diagonale reliant les
les coins inférieur gauche et supérieur droit sont égaux à 20 : 1+19, 2+18, 2+18 et
bientôt. Donc, puisqu'il y a (10·10-10)/2 = 45 de telles paires (nous avons soustrait
le nombre de carrés sur cette diagonale du nombre total de
carrés), la somme des nombres en dehors de cette diagonale est égale à 20,45
= 900. Avec 10·10 = 100 sur la diagonale, la somme totale est égale à 900
+ 100 = 1000.

La deuxième méthode calcule la somme ligne par ligne (ou colonne par colonne).
La somme de la première ligne est égale à 10·11/2 = 55 selon la formule
(S2). La somme des nombres de la deuxième rangée est 55 + 10 puisque chacun des
nombres est plus grand de 1 que leurs homologues de la rangée ci-dessus. le
il en est de même pour toutes les autres lignes. Donc la somme totale est égale
à 55 + (55+10) + (55+20) + ...+ (55+90) = 55·10 + (10+20+...+90) =

29

30

55·10 + 10·(1+2+...+9) = 55·10 + 10·45 =1000.

Notez que la première méthode utilise la même astuce Carl Gauss vraisemblablement
utilisé pour trouver la somme des cent premiers entiers (problème 9 dans les exercices
2.3). Nous avons également utilisé cette formule (deux fois, en fait) dans la deuxième solution pour
le problème.

11. a. Le nombre de multiplications M(n) et le nombre de divisions D(n)

réalisés par l'algorithme sont donnés par la même somme :
nL2 nL1
X X Xm nL2
X nL1
X
M(n) = D(n) = 1= (n − i + 1) =
 i=0 j=i+1 k=je i=0 j=i+1
nL2 nL2
X X
= (n − i + 1)(n − 1 − (i + 1) + 1) = (n − i + 1)(n − i − 1)
i=0 i=0

= (n + 1)(n − 1) + n(n − 2) + ... + 3 1

nL1 nL1 nL1
X X X
= (j + 2)j = j2+ 2j =(n − 1)n(2n − 1) + 2(n − 1)n
j=1 j=1 j=1
6 2

1
=n(n − 1)(2n + 5) ?? n 3 θ(n 3 ).
6 3

b. L'inefficacité est l'évaluation répétée du rapport A[j,i] / A[i,i]

dans la boucle la plus interne de l'algorithme, qui, en fait, ne change pas avec
la variable de boucle k. Par conséquent, cet invariant de boucle peut être calculé une seule fois
avant d'entrer dans cette boucle : temp A[j,i] / A[i,i] ; la boucle la plus intérieure est
puis changé en

A[j,k] A[j,k] − A[i,k] temp.

Ce changement élimine l'opération la plus coûteuse de l'algorithme, la

division, à partir de sa boucle la plus interne. Le gain de temps de fonctionnement obtenu par ce
le changement peut être estimé comme suit :
1 1
T oid (n) c m 3n 3 + c D 3 n3 cm+cD cD
1 = = + 1,
T nouveau (n) ≈ c m 3 n3 cm cm

où c D et c m sont le temps d'une division et d'une multiplication,

respectivement.

12. La réponse peut être obtenue par une évaluation directe de la somme
m
X
2 (2i − 1) + (2n +1)=2n 2 + 2n + 1.
i=1

30

31

(On peut également obtenir la réponse fermée en notant que les cellules sur l'al-
diagonales ternantes du voisinage de von Neumann de rang n composent
deux carrés de tailles n + 1 et n, respectivement.)

13. Soit D(n) le nombre total de chiffres décimaux dans le premier n positif
entiers (pages de livre). Les neuf premiers nombres sont à un chiffre, donc
D(n) = n pour 1 n ≤ 9. Les 90 prochains nombres de 10 à 99 inclus sont
à deux chiffres. D'où

D(n)=9+2(n − 9) pour 10 n 99.

La valeur maximale de D(n) pour cette plage est D(99) = 189. De plus, il
sont 900 décimales à trois chiffres, ce qui conduit à la formule

D(n) = 189 + 3(n − 99) pour 100 n 999.

La valeur maximale de D(n) pour cette plage est D(999) = 2889. En additionnant quatre
chiffres pour la page 1000, on obtient D(1000) = 2893.
 31

Page 32

Exercices 2.4
1. Résolvez les relations de récurrence suivantes.

une. x(n) = x(n − 1) + 5 pour n > 1, x(1) = 0

b. x(n)=3x(n − 1) pour n > 1, x(1) = 4

c. x(n) = x(n − 1) + n pour n > 0, x(0) = 0

ré. x(n) = x(n/2) + n pour n > 1, x(1) = 1 (résoudre pour n = 2 k )

e. x(n) = x(n/3) + 1 pour n > 1, x(1) = 1 (résoudre pour n = 3 k )

2. Établir et résoudre une relation de récurrence pour le nombre d'appels passés par
F(n), l'algorithme récursif pour le calcul de n!.

3. Considérons l'algorithme récursif suivant pour calculer la somme des

n premiers cubes : S(n)=1 3 + 2 3 + ··· + n 3 .

Algorithme S(n)
//Entrée : Un entier positif n
//Sortie : La somme des n premiers cubes
si n = 1 renvoie 1
sinon renvoie S(n − 1) + n ∗ n ∗ n

une. Établir et résoudre une relation de récurrence pour le nombre de fois que le
l'opération de base de l'algorithme est exécutée.

b. Comment cet algorithme se compare-t-il avec le simple non récursif

algorithme pour calculer cette fonction?
 4. Considérez l'algorithme récursif suivant.

Algorithme Q(n)
//Entrée : Un entier positif n
si n = 1 renvoie 1
sinon renvoie Q(n − 1) + 2 ∗ n − 1

une. Mettre en place une relation de récurrence pour les valeurs de cette fonction et la résoudre
pour déterminer ce que cet algorithme calcule.

b. Établir une relation de récurrence pour le nombre de multiplications faites par

cet algorithme et le résoudre.

c. Mettre en place une relation de récurrence pour le nombre d'additions/soustractions

faite par cet algorithme et le résoudre.

32

Page 33

5. Tour de Hanoï a. Dans la version originale du puzzle de la Tour de Hanoï,

tel qu'il a été publié par Edouard Lucas, un mathématicien français, dans le
années 1890, le monde prendra fin après que 64 disques auront été déplacés d'un
Tour de Brahma. Estimez le nombre d'années qu'il faudrait si les moines pouvaient
déplacer un disque par minute. (Supposez que les moines ne mangent pas, ne dorment pas ou ne meurent pas.)

b. Combien de coups sont effectués par le ième plus grand disque (1 ≤ i ≤ n) dans
cet algorithme ?

c. Trouvez un algorithme non récursif pour le puzzle de la Tour de Hanoï et im-

le mettre dans la langue de votre choix.

6. > Tour restreinte de Hanoï Considérez la version de la Tour de Hanoï

puzzle dans lequel n disques doivent être déplacés de la cheville A à la cheville C en utilisant la cheville
B de sorte que tout mouvement devrait soit placer un disque sur la cheville B, soit déplacer un disque
de cette cheville. (Bien sûr, l'interdiction de placer un disque plus grand sur le dessus
d'un plus petit reste également en place.) Concevoir un algorithme récursif pour
ce problème et trouver le nombre de mouvements effectués par celui-ci.

7. > une. Montrer que le nombre exact d'additions faites par la récursive
algorithme BinRec(n) pour un entier positif arbitraire n est blog 2 nc.

b. Etablir une relation de récurrence pour le nombre d'ajouts effectués par

la version non récursive de cet algorithme (voir Section 2.3, Exemple 4)
et le résoudre.

8. a. Concevoir un algorithme récursif pour calculer 2 n pour tout non négatif

entier n basé sur la formule : 2 n = 2 nL1 + 2 nL1 .

b. Etablir une relation de récurrence pour le nombre d'ajouts effectués par

l'algorithme et le résoudre.

c. Dessinez un arbre d'appels récursifs pour cet algorithme et comptez le nombre

des appels effectués par l'algorithme.

ré. Est-ce un bon algorithme pour résoudre ce problème ?

9. Considérez l'algorithme récursif suivant.

Algorithme Devinette(A[0..n − 1])

 //Entrée : Un tableau A[0..n − 1] de nombres réels
si n = 1 renvoie A[0]
else temp ← Devinette(A[0..n − 2])
si temp ≤ A[n − 1] retour temp
sinon renvoie A[n − 1]

une. Que calcule cet algorithme ?

33

Page 34

b. Configurez une relation de récurrence pour le nombre d'opérations de base de l'algorithme et

résoudre.

10. Considérez l'algorithme suivant pour vérifier si un graphe défini par son
la matrice de contiguïté est terminée.

Algorithme GraphComplete(A[0..n − 1,0..n − 1])

//Entrée : Matrice d'adjacence A[0..n − 1,0..n − 1]) d'un graphe non orienté G
avec n 1 sommets
//Sortie : 1 (vrai) si G est complet et 0 (faux) sinon
si n = 1 renvoie 1 //le graphe à un sommet est complet par définition
autre
sinon GraphComplete(A[0..n − 2,0..n − 2]) renvoie 0
sinon pour j 0 à n − 2 do
si A[n − 1,j]=0 renvoie 0
retour 1

Quelle est la classe d'efficacité de l'algorithme dans le pire des cas ?

11. Le déterminant d'une matrice n × n

??
un 0 0 un 0 nL1
un 1 0 un 1 nL1 ??
??
A= ... ??,
?? ??
un nL1 0 un nL1 nL1

noté detA, peut être défini comme un 00 pour n = 1 et, pour n > 1, par le
formule récursive
nL1
X
detA = s j a 0 j detA j ,
j=0

où s j est +1 si j est pair et −1 si j est impair, a 0 j est l'élément de la ligne 0

et la colonne j, et A j est la matrice (n−1)×(n−1) obtenue à partir de la matrice
A en supprimant sa ligne 0 et sa colonne j.

a.> Mettre en place une relation de récurrence pour le nombre de multiplications effectuées
par l'algorithme implémentant cette définition récursive.

b.> Sans résoudre la récurrence, que pouvez-vous dire de la solu-

l'ordre de croissance de tion par rapport à n! ?

12. Le voisinage de von Neumann revisité Trouvez le nombre de cellules dans le

voisinage de von Neumann de l'intervalle n (problème 12 des exercices 2.3) par
mise en place et résolution d'une relation de récurrence.

34
Page 35

13. Faire frire des hamburgers Il y a n hamburgers à faire frire sur un petit grill
qui ne peut contenir que deux hamburgers à la fois. Chaque hamburger doit être
frit des deux côtés; faire frire un côté d'un hamburger prend une minute, re-
indépendamment du fait qu'un ou deux hamburgers soient frits en même temps.
Considérez l'algorithme récursif suivant pour exécuter cette tâche. Si
n ≤ 2, faire revenir le hamburger (ou les deux hamburgers ensemble si n = 2)
de chaque côté. Si n > 2, faites frire deux hamburgers ensemble de chaque côté puis
faire frire les n − 2 hamburgers restants par le même algorithme.

une. Configurer et résoudre la récurrence pour la durée de cet algorithme

rithm doit faire frire n hamburgers.

b. Expliquez pourquoi cet algorithme ne fait pas frire les hamburgers dans le mini-
durée minimale pour tout n > 0.

c. Donner un algorithme récursif correct qui exécute la tâche dans le mini-

durée minimale pour tout n > 0 et trouver une formule fermée pour le
durée minimale.

14. > Problème de célébrité Une célébrité parmi un groupe de n personnes est une personne
qui ne connaît personne mais est connu de tout le monde. La tâche est de
identifier une célébrité en ne posant des questions qu'aux personnes de la forme :
tu le connais ?" Concevoir un algorithme efficace pour identifier une célébrité
ou déterminer que le groupe n'a pas une telle personne. Combien de questions
votre algorithme a-t-il besoin dans le pire des cas ? [Homme89]

35
Page 36

Conseils pour les exercices 2.4

1. Chacune de ces récurrences peut être résolue par la méthode des sous-récurrences
établissements.

2. La relation de récurrence en question est presque identique à la récurrence

relation pour le nombre de multiplications, qui a été établie et résolue dans
la section.

3. a. La question est similaire à celle de l'efficacité de la récursive

algorithme de calcul de n!.

b. Écrivez un pseudocode pour l'algorithme non récursif et déterminez son

Efficacité.

4. a. Notez que vous êtes interrogé ici sur une récurrence pour la fonction
valeurs, pas sur une récurrence pour le nombre de fois que son opération est
réalisé. Suivez simplement le pseudocode pour le configurer. Il est plus facile de résoudre ce
récurrence par substitutions en avant (voir Annexe B).

b. Cette question est très similaire à celle que nous avons déjà discutée.

c. Vous pouvez inclure la soustraction nécessaire pour diminuer n.

5. a. Utilisez la formule pour le nombre de déplacements de disque dérivée dans la section.

b. Résoudre le problème pour 3 disques pour enquêter sur le nombre de déplacements effectués
par chacun des disques. Puis généraliser les observations et prouver leur
validité pour le cas général de n disques.

6. L'algorithme requis et la méthode de son analyse sont similaires à ceux

de la version classique du puzzle. En raison de la contrainte supplémentaire,
plus de deux instances plus petites du puzzle doivent être résolues ici.

7. a. Considérez séparément les cas des valeurs paires et impaires de n et montrez que
pour les deux blog 2 nc satisfait la relation de récurrence et sa valeur initiale
état.

b. Suivez simplement le pseudo-code de l'algorithme.

8. a. Utiliser la formule 2 n = 2 nL1 +2 nL1 sans la simplifier ; ne pas oublier

pour fournir une condition d'arrêt de vos appels récursifs.

b. Un algorithme similaire a été étudié dans la section 2.4.

c. Une question similaire a été étudiée à la section 2.4.

ré. Une mauvaise classe d'efficacité d'un algorithme en soi ne signifie pas que

36

Page 37
 l'algorithme est mauvais. Par exemple, l'algorithme classique de la Tour de
Le puzzle de Hanoi est optimal malgré son efficacité en temps exponentiel. Donc,
une affirmation selon laquelle un algorithme particulier n'est pas bon nécessite une référence à un
le meilleur.

9. a. Le traçage de l'algorithme pour n = 1 et n = 2 devrait aider.

b. Il est très similaire à l'un des exemples abordés dans la section.

10. Obtenez le nombre d'opérations de base en résolvant une relation de récurrence ou

en calculant directement le nombre d'éléments de la matrice d'adjacence le
l'algorithme vérifie dans le pire des cas.

11. a. Utilisez la formule de la définition pour obtenir la relation de récurrence pour le nombre
bre de multiplications faites par l'algorithme.

b. Étudiez le membre de droite de la relation de récurrence. L'informatique

les premières valeurs de M(n) peuvent également être utiles.

12. Vous pouvez utiliser la symétrie du voisinage pour obtenir un

formule du nombre de carrés ajoutés au voisinage le nième
itération de l'algorithme.

13. Le temps minimum nécessaire pour faire frire trois hamburgers est plus petit
plus de quatre minutes.

14. Résolvez d'abord une version plus simple dans laquelle une célébrité doit être présente.

37

Page 38

Solutions aux exercices 2.4

1. a. x(n) = x(n − 1) + 5 pour n > 1, x(1) = 0

x(n) = x(n − 1) + 5
= [x(n − 2) + 5] + 5 = x(n − 2) + 5 · 2
= [x(n − 3) + 5] + 5 · 2 = x(n − 3) + 5 · 3
= ...
 = x(n − i)+5 · i
= ...
= x(1) + 5 · (n − 1) = 5(n − 1).

Remarque : La solution peut également être obtenue en utilisant la formule du n

terme de la progression arithmétique :

x(n) = x(1) + d(n − 1) = 0 + 5(n − 1) = 5(n − 1).

b. x(n)=3x(n − 1) pour n > 1, x(1) = 4

x(n) = 3x(n − 1)
= 3[3x(n − 2)] = 3 2 x(n − 2)
= 3 2 [3x(n − 3)] = 3 3 x(n − 3)
= ...
= 3 i x(n − i)
= ...
= 3 nL1 x(1) = 4 · 3 nL1 .

Remarque : La solution peut également être obtenue en utilisant la formule du n

terme de la progression géométrique :

x(n) = x(1)q nL1 = 4 · 3 nL1 .

c. x(n) = x(n − 1) + n pour n > 0, x(0) = 0

x(n) = x(n − 1) + n
= [x(n − 2) + (n − 1)] + n = x(n − 2) + (n − 1) + n
= [x(n − 3) + (n − 2)] + (n − 1) + n = x(n − 3) + (n − 2) + (n − 1) + n
= ...
= x(n − i)+(n − i +1)+(n − i + 2) + ··· + n
= ...
n(n+1)
= x(0) + 1 + 2 + ··· + n = .
2

38

Page 39

ré. x(n) = x(n/2) + n pour n > 1, x(1) = 1 (résoudre pour n = 2 k )

x (2 k ) = x (2 KL1 ) 2 k
= [x(2 kL2 )+2 kL1 ]+2 k = x(2 kL2 )+2 kL1 + 2 k
= [x(2 kL3 )+2 kL2 ]+2 kL1 + 2 k = x(2 kL3 )+2 kL2 + 2 kL1 + 2 k
= ...
= x(2 kLi )+2 kLi+1 + 2 kLi+2 + ··· + 2 k
= ...
= x(2 kLk )+2 1 + 2 2 + ··· + 2 k =1+2 1 + 2 2 + ··· + 2 k
= 2 k+1 − 1=2 · 2 k − 1=2n − 1.

e. x(n) = x(n/3) + 1 pour n > 1, x(1) = 1 (résoudre pour n = 3 k )

 x (3 k ) = x (3 KL1 ) 1
= [x(3 kL2 )+1]+1= x(3 kL2 )+2
= [x(3 kL3 )+1]+2= x(3 kL3 )+3
= ...
= x(3 kLi ) + je
= ...
= x(3 kLk ) + k = x(1) + k = 1 + log 3 n.

2. C(n) = C(n − 1) + 1, C(0) = 1 (il y a un appel mais pas de multiplication

quand n = 0).

C(n) = C(n − 1)+1=[C(n − 2) + 1] + 1 = C(n − 2)+2= ...

= C(n − i) + i = ... = C(0) + n =1+ n.

3. a. Soit M(n) le nombre de multiplications effectuées par l'algorithme.

On a pour cela la relation de récurrence suivante :

M(n) = M(n − 1) + 2, M(1) = 0.

39

Page 40

Nous pouvons le résoudre par des substitutions en amont :

M(n) = M(n − 1) + 2
= [M(n − 2) + 2] + 2 = M(n − 2)+2+2
= [M(n − 3) + 2] + 2 + 2 = M(n − 3)+2+2+2
= ...
= M(n−i)+2i
= ...
= M(1) + 2(n − 1) = 2(n − 1).

b. Voici un pseudocode pour l'option non récursive :

Algorithme NonrecS(n)
// Calcule la somme des n premiers cubes de manière non récursive
//Entrée : Un entier positif n
//Sortie : La somme des n premiers cubes.
S1
pour i 2 à n faire
S←S+ii∗i
Retour

Le nombre de multiplications effectuées par cet algorithme sera

Xm Xm
 2=2 1 = 2(n − 1).
i=2 i=2

C'est exactement le même nombre que dans la version récursive, mais le non-re-
la version cursive ne supporte pas les frais généraux de temps et d'espace associés à
la pile de la récursivité.

4. a. Q(n) = Q(n − 1) + 2n − 1 pour n > 1, Q(1) = 1.

Le calcul des premiers termes de la suite donne :

Q(2) = Q(1) + 2 · 2 − 1=1+2 · 2 − 1 = 4 ;
Q(3) = Q(2) + 2 · 3 − 1=4+2 · 3 − 1 = 9 ;
Q(4) = Q(3) + 2 · 4 − 1=9+2 · 4 − 1 = 16.

Ainsi, il apparaît que Q(n) = n 2 . Nous vérifierons cette hypothèse en substi-

intégrer cette formule dans l'équation de récurrence et la condition initiale.
Le membre de gauche donne Q(n) = n 2 . Le côté droit cède

Q(n − 1) + 2n − 1=(n − 1) 2 + 2n − 1 = n 2 .

40

Page 41

La condition initiale est vérifiée immédiatement : Q(1) = 1 2 = 1.

b. M(n) = M(n − 1) + 1 pour n > 1, M(1) = 0. Résoudre à l'envers

substitutions (c'est presque identique à l'exemple factoriel-voir Exemple
1 dans la section) ou en appliquant la formule du nième terme d'une arith-
la progression métrique donne M(n) = n − 1.

c. Soit C(n) le nombre d'additions et de soustractions effectuées par le

algorithme. La récurrence pour C(n) est C(n) = C(n − 1) + 3 pour n > 1,
C(1) = 0. Le résoudre par substitutions en arrière ou en appliquant la formule
pour le nième terme d'une progression arithmétique, on obtient C(n) = 3(n − 1).

Remarque : Si nous n'incluons pas dans le décompte les soustractions nécessaires pour dé-
pli n, la récurrence sera C(n) = C(n − 1) + 2 pour n > 1, C(1) = 0.
Sa solution est C(n) = 2(n − 1).

5. a. Le nombre de coups est donné par la formule : M(n)=2 n − 1. D'où

2 64 − 1
≈ 3,5 · 10 13 ans
60 · 24 · 365

par rapport à l'âge de l'Univers estimé à environ 13 · 10 9 ans.

b. Observez que pour chaque mouvement du ième disque, l'algorithme se déplace d'abord
la tour de tous les disques plus petits qu'elle à une autre cheville (cela nécessite un
déplacement du (i + 1)er disque) puis, après le déplacement du ième disque, ce
la plus petite tour est déplacée au sommet (cela nécessite à nouveau un déplacement de
le (i + 1)er disque). Ainsi, pour chaque mouvement du ième disque, l'algorithme
déplace le (i + 1)er disque exactement deux fois. Puisque pour i = 1, le nombre de
coups est égal à 1, on a la récurrence suivante pour le nombre de
mouvements effectués par le ième disque :

m(i +1)=2m(i) pour 1 i < n, m(1) = 1.

Sa solution est m(i)=2 iL1 pour i = 1,2,...,n. (Le moyen le plus simple d'obtenir
 cette formule Notez
progression.) consiste
queà utiliser la formule
la réponse dubien
s'accorde terme générique
avec d'un
la formule pour le
nombre total de coups :
m m
X X
M(n) = m(i) = 2 iL1 =1+2+ ··· + 2 nL1 = 2 n − 1.
i=1 i=1

6. Si n = 1, déplacez le disque unique de la cheville A d'abord à la cheville B, puis de

du piquet B au piquet C. Si n > 1, procédez comme suit :
transférer récursivement les n − 1 disques supérieurs de la cheville A à la cheville C via la cheville
B

41

Page 42

déplacer le disque de la cheville A à la cheville B

transférer récursivement n − 1 disques de la cheville C à la cheville A via la cheville B
déplacer le disque de la cheville B à la cheville C
transférer récursivement n − 1 disques de la cheville A à la cheville C en passant par la cheville B.

La relation de récurrence pour le nombre de coups M(n) est

M(n)=3M(n − 1) + 2 pour n > 1, M(1) = 2.

Il peut être résolu par des substitutions vers l'arrière comme suit

M(n) = 3M(n − 1) + 2
= 3[3M(n − 2) + 2] + 2 = 3 2 M(n − 2) + 3 · 2+2
= 3 2 [3M(n − 3) + 2] + 3 · 2+2=3 3 M(n − 3) + 3 2 · 2+3 · 2+2
= ...
= 3 i M(n − i) + 2(3 iL1 + 3 iL2 + ··· +1)=3 i M(n − i)+3 i − 1
= ...
= 3 nL1 M(1) + 3 nL1 − 1=3 nL1 · 2+3 nL1 − 1=3 n − 1.

7. a. On vérifiera par substitution que A(n) = blog 2 nc satisfait la récurrence

pour le nombre d'ajouts

A(n) = A(bn/2c)+1 pour tout n > 1.

Soit n pair, c'est-à-dire n = 2k.

Le côté gauche est :
A(n) = blog 2 nc = blog 2 2kc = blog 2 2 + log 2 kc = (1 + blog 2 kc) =
blog 2 kc + 1.
Le côté droit est :
A(bn/2c)+1= A(b2k/2c)+1= A(k)+1= blog 2 kc + 1.

Soit n impair, c'est-à-dire n = 2k + 1.

Le côté gauche est :
A(n) = blog 2 nc = blog 2 (2k + 1)c = en utilisant le blog 2 xc = dlog 2 (x + 1)e − 1
dlog 2 (2k + 2)e − 1 = dlog 2 2(k + 1)e − 1
= dlog 2 2 + log 2 (k + 1)e − 1=1+ dlog 2 (k + 1)e − 1 = blog 2 kc + 1.
Le côté droit est :
A(bn/2c)+1 = A(b(2k + 1)/2c)+1 = A(bk + 1/2c)+1= A(k)+1 =
blog 2 kc + 1.
 La condition initiale est vérifiée immédiatement : A(1) = blog 2 1c = 0.

42

Page 43

b. La relation de récurrence pour le nombre d'ajouts est identique à

celui de la version récursive :

A(n) = A(bn/2c)+1 pour n > 1, A(1) = 0,

avec la solution A(n) = blog 2 nc + 1.

8. a. Puissance de l'algorithme (n)

// Calcule 2 n récursivement par la formule 2 n = 2 nL1 + 2 nL1
//Entrée : Un entier non négatif n
//Sortie : renvoie 2 n
si n = 0 renvoie 1
sinon renvoie Puissance(n − 1) + Puissance(n − 1)

b. A(n)=2A(n − 1) + 1, A(0) = 0.

A(n) = 2A(n − 1) + 1
= 2[2A(n − 2) + 1] + 1 = 2 2 A(n − 2)+2+1
= 2 2 [2A(n − 3) + 1] + 2 + 1 = 2 3 A(n − 3) + 2 2 +2+1
= ...
= 2 i A(n − i)+2 iL1 + 2 iL2 + ··· + 1
= ...
= 2 n A(0) + 2 nL1 + 2 nL2 + ··· +1=2 nL1 + 2 nL2 + ··· +1=2 n − 1.

c. L'arbre des appels récursifs de cet algorithme se présente comme suit :

n- 1 n- 1

n -2 n -2 n -2 n -2

1
... 1
... 1
... 1

0 0 0 0 0 0 0 0

Notez qu'il a un niveau supplémentaire par rapport à l'arbre similaire pour la Tour
du puzzle de Hanoï.

ré. C'est un très mauvais algorithme car il est largement inférieur à l'algo-
rithm qui multiplie simplement un accumulateur par 2 n fois, sans parler
algorithmes beaucoup plus efficaces discutés plus loin dans le livre. Même si seulement
les ajouts sont autorisés, ajouter deux fois 2 nL1 est meilleur que cet algorithme.

43
Page 44

9. a. L'algorithme calcule la valeur du plus petit élément dans un

déployer.

b. La récurrence du nombre de comparaisons clés est

C(n) = C(n − 1) + 1 pour n > 1, C(1) = 0.

Le résoudre par des substitutions en amont donne C(n) = n − 1.

10. Soit C w (n) le nombre de fois où l'élément de la matrice d'adjacence est vérifié
dans le pire des cas (le graphique est complet). On a la récurrence suivante
pour C w (n)

C w (n) = C w (n − 1) + n − 1 pour n > 1, C (1) = 0.

La résolution de la récurrence par des substitutions en arrière donne ce qui suit :

C w (n) = C w (n − 1) + n − 1
= [C w (n − 2) + n − 2] + n − 1
= [C w (n − 3) + n − 3] + n − 2 + n − 1
= ...
= C w (n − i)+(n − i)+(n − i + 1) + ··· + (n − 1)
= ...
= C w (1) + 1 + 2 + ··· + (n − 1)=0+(n − 1)n/2=(n − 1)n/2.

Ce résultat pourrait aussi être obtenu directement en observant que dans le pire des cas
cas, l'algorithme vérifie chaque élément en dessous de la diagonale principale du
matrice d'adjacence d'un graphe donné.

11. a. Soit M(n) le nombre de multiplications effectuées par l'algorithme

nL1
basé sur la formule detA = P
j=0 s j a 0j detA j . Si nous n'incluons pas
multiplications par s j , qui sont juste ±1, alors
nL1
X
M(n) = (M(n − 1) + 1),
j=0

c'est à dire,
M(n) = n(M(n − 1) + 1) pour n > 1 et M(1) = 0.

b. Puisque M(n) = nM(n − 1) + n, la suite M(n) croît jusqu'à l'infini à

moins aussi rapide que la fonction factorielle définie par F(n) = nF(n − 1).

44

Page 45
 12. Le nombre de carrés ajoutés à la nième itération à chacun des quatre
côtés symétriques du voisinage de von Neumann est égal à n. D'où
on obtient la récurrence suivante pour S(n), le nombre total de carrés
dans le voisinage après la nième itération :

S(n) = S(n − 1) + 4n pour n > 0 et S(0) = 1.

La résolution de la récurrence par des substitutions en arrière donne ce qui suit :

S(n) = S(n − 1) + 4n
= [S(n − 2) + 4(n − 1)] + 4n = S(n − 2) + 4(n − 1) + 4n
= [S(n − 3) + 4(n − 2)] + 4(n − 1) + 4n = S(n − 3) + 4(n − 2) + 4(n − 1) + 4n
= ...
= S(n − i) + 4(n − i + 1) + 4(n − i + 2) + ··· + 4n
= ...
= S(0) + 4 · 1+4 · 2 + ··· + 4n = 1 + 4(1 + 2 + ··· + n)
= 1+4n(n + 1)/2=2n 2 + 2n + 1.

13. a. Soit T(n) le nombre de minutes nécessaires pour faire frire n hamburgers par le
algorithme donné. On a alors la récurrence suivante pour T(n) :

T(n) = T(n − 2) + 2 pour n > 2, T(1) = 2, T(2) = 2.

Sa solution est T(n) = n pour tout n pair > 0 et T(n) = n + 1 pour tout
n impair > 0 peut être obtenu soit par substitutions en arrière, soit par application-
la formule du terme générique d'une progression arithmétique.

b. L'algorithme ne parvient pas à exécuter la tâche de faire frire n hamburgers dans le

minimum de temps pour tout n impair > 1. En particulier, il faut
T(3) = 4 minutes pour faire frire trois hamburgers, alors qu'on peut le faire en 3
minutes : d'abord, faites frire les crêpes 1 et 2 d'un côté. Puis faire frire la crêpe 1 sur
le deuxième côté avec la crêpe 3 sur le premier côté. Enfin, faites frire les deux
crêpes 2 et 3 sur la deuxième face.

c. Si n 2, faire frire le hamburger (ou les deux hamburgers ensemble si n = 2)

de chaque côté. Si n = 3, faire revenir les crêpes en 3 minutes comme indiqué dans le
réponse à la question de la partie b. Si n > 3, faire frire deux hamburgers ensemble
de chaque côté puis faire frire les n − 2 hamburgers restants de la même
algorithme. La récurrence du nombre de minutes nécessaires pour faire frire n
hamburgers ressemble maintenant à ceci :

T(n) = T(n − 2) + 2 pour n > 3, T(1) = 2, T(2) = 2, T(3) = 3.

Pour chaque n > 1, cet algorithme nécessite n minutes pour faire le travail. C'est
le minimum de temps possible car n crêpes ont 2n faces à faire frire

45

Page 46

et n'importe quel algorithme ne peut pas faire frire plus de deux côtés en une minute. le
algorithme est aussi évidemment optimal pour le cas trivial de n = 1, nécessitant
deux minutes pour faire frire un seul hamburger des deux côtés.

Remarque : le cas de n = 3 est une énigme bien connue, qui remonte à

 au moins jusqu'en 1943. Sa version algorithmique pour un n arbitraire est incluse dans Al-
gorithmic Puzzles par A. Levitin et M. Levitin, Oxford University Press,
2011, problème 16.

14. Le problème peut être résolu par un algorithme récursif. En effet, en demandant
juste une question, nous pouvons éliminer le nombre de personnes qui peuvent être un
célébrité par 1, résoudre le problème pour le groupe restant de n − 1 personnes
récursivement, puis vérifiez la solution renvoyée en ne demandant pas plus de
deux questions. Voici une description plus détaillée de cet algorithme :

Si n = 1, renvoyez cette personne en tant que célébrité. Si n > 1, procédez comme

suit :

Étape 1 Sélectionnez deux personnes dans le groupe donné, disons A et B, et demandez à A si

A connaît B. Si A connaît B, supprimez A des personnes restantes qui peuvent
être une célébrité ; si A ne connaît pas B, supprimez B de ce groupe.

Étape 2 Résolvez le problème de manière récursive pour le groupe restant de n − 1 personnes

qui peut être une célébrité.

Étape 3 Si la solution renvoyée à l'étape 2 indique qu'il n'y a pas de célébrité

parmi le groupe de n − 1 personnes, le plus grand groupe de n personnes ne peut
contenir une célébrité non plus. Si l'étape 2 a identifié une célébrité, une personne
autre que A ou B, disons, C, demandez si C connaît la personne renvoyée
à l'étape 1 et, si la réponse est non, si la personne renvoyée à l'étape
1 connaît C. Si la réponse à la deuxième question est oui, " renvoyez C comme un
célébrité et "pas de célébrité" autrement. Si l'étape 2 a identifié B comme une célébrité,
demandez simplement si B connaît A : retournez B comme une célébrité si la réponse est non
et "pas de célébrité" sinon. Si l'étape 2 a identifié A comme une célébrité, demandez
si B connaît A : renvoie A en tant que célébrité si la réponse est oui et « non
célébrité" autrement.

La récurrence pour Q(n), le nombre de questions nécessaires dans le pire des cas,
est comme suit:

Q(n) = Q(n − 1) + 3 pour n > 2, Q(2) = 2, Q(1) = 0.

Sa solution est Q(n)=2+3(n − 2) pour n > 1 et Q(1) = 0.

Remarque : Une discussion sur ce problème, y compris une mise en œuvre de cet al-
gorithm dans un pseudo-code de type Pascal, peut être trouvé dans l'introduction d'Udi Manber
aux algorithmes : une approche créative. Addison-Wesley, 1989.

46

47

Exercices 2.5
1. Trouver un site Web dédié aux applications des nombres de Fibonacci et
l'étudier.

2. Le problème des lapins de Fibonacci Un homme a mis une paire de lapins dans un endroit sur-
arrondi par un mur. Combien y aura-t-il de couples de lapins par an si le
la paire initiale de lapins (mâle et femelle) est nouveau-née, et toutes les paires de lapins
ne sont pas fertiles au cours de leur premier mois de vie mais donnent ensuite naissance à
un nouveau couple mâle/femelle à la fin de chaque mois ?

3. Monter des escaliers Trouver le nombre de façons différentes de monter un n-escalier

escalier si chaque marche est une ou deux marches. Par exemple, un escalier à 3 marches
peut être grimpé de trois manières : 1-1-1, 1-2 et 2-1.
 4. Combien y a-t-il de nombres pairs parmi les n premiers nombres de Fibonacci ?
Donnez une formule fermée valable pour tout n > 0.
m
5. Vérifier par substitutions directes que la fonction 1√5 (ф n −ф ) satisfait en effet
récidive (2.6) et conditions initiales (2.7).

6. Les valeurs maximales des types primitifs Java int et long sont 2 31 -1
et 2 63 -1, respectivement. Trouver le plus petit n pour lequel le nième de Fibonacci
nombre ne va pas tenir dans une mémoire allouée pour
une. le type int. b. le type long.

7. Considérez l'algorithme récursif basé sur la définition pour calculer le nième

nombre de Fibonacci F(n). Soit C(n) et Z(n) le nombre de fois F(1)
et F(0), respectivement, sont calculés. Prouve-le
une. C(n) = F(n). b. Z(n) = F(n − 1).

8. Améliorer l'algorithme Fib du texte afin qu'il ne nécessite que θ(1) espace.

9. Prouver l'égalité
F(n − 1) m
F(n) 01
pour n 1.
F(n) F(n + 1) = ∙ 11

10. > Combien de divisions modulo sont faites par l'algorithme d'Euclide sur deux
nombres de Fibonacci consécutifs F(n) et F(n − 1) comme
mettre?

11. Disséquer un rectangle de Fibonacci Étant donné un rectangle dont les côtés sont deux
nombres de Fibonacci consécutifs, concevez un algorithme pour le disséquer en
les carrés dont au plus deux des carrés sont de la même taille. Quoi
est la classe d'efficacité temporelle de votre algorithme ?

47

Page 48

12. Dans le langage de votre choix, implémentez deux algorithmes de calcul

les cinq derniers chiffres du nième nombre de Fibonacci qui sont basés sur (a)
l'algorithme récursif à base de définition F(n) ; (b) la définition itérative-
algorithme basé sur Fib(n). Effectuer une expérience pour trouver la plus grande valeur
de n pour laquelle vos programmes s'exécutent en moins d'1 minute sur votre ordinateur.
 48

49

Conseils pour les exercices 2.5

1. Utilisez un moteur de recherche.

2. Établissez une équation exprimant le nombre de lapins après n mois dans

en termes de nombre de lapins au cours des mois précédents.

3. Il existe plusieurs façons de résoudre ce problème. Le plus élégant d'entre eux

permet de poser le problème dans cette section.

4. Écrire le premier, disons, dix nombres de Fibonacci fait le modèle

évident.
m
5. Il est plus facile de substituer ф n et фséparément dans l'équation de récurrence.
Pourquoi cela suffira-t-il ?

6. Utilisez une formule approximative pour F(n) pour trouver les plus petites valeurs de n à
dépasser les nombres donnés.

7. Établir les relations de récurrence pour C(n) et Z(n), avec les initiales appropriées
conditions, bien sûr.

8. Toutes les informations nécessaires à chaque itération de l'algorithme sont les valeurs
des deux derniers nombres de Fibonacci consécutifs. Modifier l'algorithme pour
profiter de ce fait.

9. Démontrez-le par induction mathématique.

10. Considérons d'abord un petit exemple tel que le calcul de pgcd(13,8).

11. Profitez de la nature particulière des dimensions du rectangle.

12. Les k derniers chiffres d'un entier N peuvent être obtenus en calculant N mod 10 k .
Réaliser toutes les opérations de vos algorithmes modulo 10 k (voir Annexe
A) vous permettra de contourner la croissance exponentielle du Fibonacci
 [Link]
l'analyse Notez également que la section 2.6 est consacrée à une discussion générale de
des algorithmes.

49

50

Solutions aux exercices 2.5

1. n/a

2. Soit R(n) le nombre de couples de lapins à la fin du mois n. Clairement,

R(0) = 1 et R(1) = 1. Pour chaque n > 1, le nombre de paires de lapins,
R(n), est égal au nombre de paires à la fin du mois n−1, R(n−1),
plus le nombre de couples de lapins nés à la fin du mois n, qui est
selon les hypothèses du problème est égal à R(n − 2), le nombre
de couples de lapins à la fin du mois n − 2. On a donc la récurrence
relation

R(n) = R(n − 1) + R(n − 2) pour n > 1, R(0) = 1, R(1) = 1.

Le tableau suivant donne les valeurs des treize premiers termes de la sé-
séquence, appelée les nombres de Fibonacci, définie par cette relation de récurrence :

m 012345 6 sept 8 9 dix 11 12

R(n) 1 1 2 3 5 8 13 21 34 55 89 144 233

Notez que R(n) diffère légèrement de la séquence canonique de Fibonacci,

qui est défini par la même équation de récurrence F(n) = F(n − 1) +
F(n−2) mais les différentes conditions initiales, à savoir, F(0) = 0 et F(1) =
1. Évidemment, R(n) = F(n + 1) pour n 0.

Remarque : le problème a été inclus par Léonard de Pise (alias Fibonacci)

dans son livre de 1202 Liber Abaci, dans lequel il a préconisé l'utilisation de l'hindou-
Chiffres arabes.

3. Soit W(n) le nombre de façons différentes de monter un escalier à n marches.

W(n−1) d'entre eux commencent par une montée d'un escalier et W(n−2) d'entre eux commencent
avec une montée de deux marches. Ainsi,

W(n) = W(n − 1) + W(n − 2) pour n 3, W(1) = 1, W(2) = 2.

Résoudre cette récurrence soit « à partir de zéro » ou, mieux encore, en remarquant que
la solution a une longueur d'avance sur la séquence canonique de Fibonacci F(n),
on obtient W(n) = F(n + 1) pour n 1.

4. Partant de F(0) = 0 et F(1) = 1 et la règle F(n) = F(n − 1) +

F(n − 2) pour chaque élément suivant de la séquence, il est facile de voir
 que les nombres de Fibonacci forment le modèle suivant
pair, impair, impair, pair, impair, impair, ...

D'où le nombre de nombres pairs parmi les n premiers nombres de Fibonacci

peut être obtenu par la formule dn/3e.

50

51

5. En substituant ф n dans le membre de gauche de l'équation, nous obtenons

F(n) − F(n − 1) − F(n − 2) = n − ф nL1 − ф nL2 = ф nL2 (ф 2 − ф − 1) = 0
car ф est une des racines de l'équation caractéristique r 2 −r −1=0.
m
La vérification de ф fonctionne pour la même raison. Puisque l'équation
F(n) − F(n − 1) − F(n − 2) = 0 est homogène et linéaire, tout linéaire
m
combinaison
m
de ses solutions ф n et ф , c'est-à-dire toute séquence de la forme
aф n + ßф sera aussi une solution de F(n) − F(n − 1) − F(n − 2) = 0. Dans
en particulier, ce sera le cas pour la suite de Fibonacci 1 Æn-1 √5
5 ф n.
Les deux conditions initiales sont vérifiées de manière
m
assez simple
(mais, bien sûr, pas individuellement pour ф n et ф
).

6. a. La question est de trouver la plus petite valeur de n telle que F(n) > 2 31 -1.
En utilisant la formule F(n) = √5
1 ф n arrondi à l'entier le plus proche, on obtient

(approximativement) l'inégalité suivante :

1
√5ф n > 2 31 − 1 ou ф n > √5(2 31 − 1).

Après avoir pris les logarithmes naturels des deux côtés, on obtient

ln(√5(2 31 − 1))
n> § 46.3.
lnф

Ainsi, la réponse est n = 47.

b. De même, nous devons trouver la plus petite valeur de n telle que F(n) >
2 63 − 1. Ainsi,

1
√5ф n > 2 63 − 1, ou ф n > √5(2 63 − 1)

ou, après avoir pris les logarithmes naturels des deux côtés,

ln(√5(2 63 − 1))
n> § 92.4.
lnф

Ainsi, la réponse est n = 93.

7. Puisque F(n) est calculé récursivement par la formule F(n) = F(n − 1) +

F(n − 2), les équations de récurrence pour C(n) et Z(n) seront les mêmes que
la récurrence pour F(n). Les conditions initiales seront :

C(0) = 0, C(1) = 1 et Z(0) = 1, Z(1) = 0

pour C(n) et Z(n), respectivement. Par conséquent, étant donné que la récurrence
l'équation et les conditions initiales pour C(n) et F(n) sont les mêmes, C(n) =

51
52

F(n). Quant à l'affirmation selon laquelle Z(n) = F(n − 1), il est facile de voir qu'elle
devrait être le cas puisque la séquence Z(n) ressemble à ceci :

1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...,

c'est-à-dire que c'est la même chose que les nombres de Fibonacci déplacés d'une position vers le
à droite. Ceci peut être formellement prouvé en vérifiant que la suite F(n−1)
(où F(−1) est défini comme 1) satisfait la relation de récurrence

Z(n) = Z(n − 1) + Z(n − 2) pour n > 1 et Z(0) = 1, Z(1) = 0.

Il peut également être prouvé soit par induction mathématique, soit en dérivant un
formule explicite pour Z(n) et montrant que cette formule est la même que la
valeur de la formule explicite pour F(n) avec n remplacé par n − 1.

8. Algorithme Fib2(n)
// Calcule le n-ième nombre de Fibonacci en utilisant seulement deux variables
//Entrée : Un entier non négatif n
//Sortie : le n-ième nombre de Fibonacci
u 0 ; v 1
pour i 2 à n faire
v←v+u
u←v−u
si n = 0 retourne 0
sinon retourner v

9. (i) La validité de l'égalité pour n = 1 découle immédiatement de la

définition de la suite de Fibonacci.
(ii) Supposons que
F(n − 1) m
F(n) 01
pour un entier positif n.
F(n) F(n + 1) = ∙ 11

Il faut montrer qu'alors

?? n+1
F(n) F(n+1) 01
.
F(n + 1) F(n + 2) = ∙ 11

En effet,
01 n+1 m
01 01
=
11 11 11
01 F(n − 1) F(n) F(n) F(n+1)
= .
11 F(n) F(n+1) = ∙ F(n+1) F(n+2)

52

53
 10. L'observation principale ici est le fait que l'algorithme d'Euclide remplace
deux nombres de Fibonacci consécutifs comme entrée par une autre paire de
nombres de Fibonacci utifs, à savoir :

pgcd(F(n),F(n − 1)) = pgcd(F(n − 1),F(n − 2)) pour tout n ≥ 4.

En effet, puisque F(n − 2) < F(n − 1) pour tout n 4,

F(n) = F(n − 1) + F(n − 2) < 2F(n − 1).

Donc pour tout n 4, le quotient et le reste de la division de F(n)

par F(n − 1) sont 1 et F(n) − F(n − 1) = F(n − 2), respectivement. Cette
est exactement ce que nous avons affirmé au début de la solution. À son tour, ce
conduit à la récurrence suivante pour le nombre de divisions D(n) :

D(n) = D(n − 1) + 1 pour n 4, D(3) = 1,

dont la condition initiale D(3) = 1 est obtenue en traçant l'algorithme sur

la paire d'entrée F(3),F(2), soit 2,1. La solution à cette récurrence est :

D(n) = n − 2 pour tout n ≥ 3.

(On peut aussi facilement trouver directement que D(2) = 1 et D(1) = 0.)

11. Étant donné un rectangle de côtés F(n) et F(n + 1), le problème peut être
résolu par l'algorithme récursif suivant. Si n = 1, le problème est
déjà résolu car le rectangle est un carré 1 × 1. Si n > 1, disséquer
le rectangle dans le carré F(n) × F(n) et le rectangle avec des côtés
F(n−1) et F(n) puis disséquer cette dernière par le même algorithme. le
L'algorithme est illustré ci-dessous pour le carré 8 × 13.

× × 11
11

2×
2
3×3

8×8

5×5

53

54

Puisque l'algorithme dissèque le rectangle de côtés F(n) et F(n + 1)

 en n carrés – qui peuvent être formellement obtenus en résolvant la récurrence
pour le nombre de carrés S(n) = S(n−1)+1, S(1) = 1–son efficacité temporelle
appartient à la classe θ(n).

12. s.o.

54

Page 55

Exercices 2.6
1. Considérons l'algorithme de tri bien connu suivant (nous l'étudierons
plus près plus loin dans le livre) avec un compteur inséré pour compter le nombre
bre de comparaisons clés.

Algorithme TrierAnalyse(A[0..n − 1])

//Entrée : Un tableau A[0..n − 1] de n éléments commandables
//Résultat : le nombre total de comparaisons clés effectuées
compter ← 0
 pour i ← 1 à n − 1 faire
v A[i]
j je − 1
tandis que j 0 et A[j] > v do
compter ← compter + 1
A[j + 1] A[j]
jj−1
A[j + 1] v

Le compteur de comparaison est-il inséré au bon endroit ? Si vous croyez que c'est le cas,
prouve le; si vous pensez que ce n'est pas le cas, apportez une correction appropriée.

2. a. Exécutez le programme du problème 1, avec un compteur correctement inséré (ou

compteurs) pour le nombre de comparaisons clés, sur 20 tableaux aléatoires de tailles
1000, 1500, 2000, 2500,...,9000, 9500.

b. Analyser les données obtenues pour former une hypothèse sur l'algorithme
efficacité moyenne.

c. Estimez le nombre de comparaisons clés auxquelles il faut s'attendre pour une

tableau généré par domly de taille 10 000 trié par le même algorithme.

3. Répétez le problème 2 en mesurant le temps d'exécution du programme en millisecondes.

onds.

4. Faire l'hypothèse d'une classe d'efficacité probable d'un algorithme sur la base des éléments suivants
observations empiriques du décompte de son fonctionnement de base :

Taille 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
compter 11 966 24 303 39 992 53 010 67 272 78 692 91 274 113 063 129 799 140 538

5. Quelle transformation d'échelle fera ressembler un nuage de points logarithmique à un

linéaire ?

6. Comment distinguer un nuage de points pour un algorithme dans (lg lg n) de

un nuage de points pour un algorithme dans θ(lg n) ?

55

Page 56

7. a. Trouvez empiriquement le plus grand nombre de divisions faites par l'al-

gorithme pour le calcul du pgcd(m,n) pour 1 ≤ n ≤ m ≤ 100.

b. Pour chaque entier positif k, trouvez empiriquement la plus petite paire d'in-
entiers 1 ≤ n ≤ m ≤ 100 pour lesquels l'algorithme d'Euclide doit faire k
divisions afin de trouver pgcd(m,n).

8. L'efficacité au cas moyen de l'algorithme d'Euclide sur des entrées de taille n peut
être mesuré par le nombre moyen de divisions D moy (n) effectué par le
algorithme de calcul pgcd(n,1), pgcd(n,2), ..., pgcd(n,n). Par example,

1
D moy (5) = (1 + 2 + 3 + 2 + 1) = 1,8.
5

Produisez un nuage de points de D moy (n) et indiquez une efficacité probable de cas moyen
classe d'efficacité de l'algorithme.

9. Exécutez une expérience pour déterminer la classe d'efficacité du tamis d'Eratos-

thenes (voir Section 1.1).
 10. Exécutez
présentéune expérience
dans la section de
[Link] pour les trois algorithmes de calcul du pgcd(m,n)

56

57

Conseils pour les exercices 2.6

1. Renvoie-t-il un nombre de comparaisons correct pour chaque tableau de taille 2 ?

2. Déboguez votre comptage de comparaison et la génération d'entrées aléatoires pour les petits
tailles de tableau en premier.

3. Sur un ordinateur de bureau raisonnablement rapide, vous pouvez très bien obtenir zéro temps, au moins pour
des tailles plus petites dans votre échantillon. La section 2.6 mentionne une astuce pour surmonter
cette difficulté.

4. Vérifiez à quelle vitesse les valeurs de comptage augmentent en doublant la taille.

5. Une question similaire a été abordée dans la section.

6. Comparez les valeurs des fonctions lg lg n et lg n pour n = 2 k .

7. Insérez le compteur de division dans un programme mettant en œuvre l'algorithme

et exécutez-le pour les paires d'entrées dans la plage indiquée.

8. Obtenez les données empiriques pour les valeurs aléatoires de n dans une plage comprise entre, disons,
10 2 et 10 4 ou 10 5 et tracer les données obtenues. (Vous pouvez utiliser
différentes échelles pour les axes de votre système de coordonnées.)

9. n/a

10. n/a
 57

Page 58

Solutions aux exercices 2.6

1. Il ne compte pas la comparaison A[j] > v lorsque la comparaison échoue (et,
par conséquent, le corps de la boucle while n'est pas exécuté). Si la langue
implique que la seconde comparaison sera toujours exécutée même si le
la première clause de la conjonction échoue, le compte doit être simplement incrémenté
par un soit juste avant l'instruction while, soit juste après l'instruction while
la fin de la déclaration. Si la deuxième clause de la conjonction n'est pas exécutée
après l'échec de la première clause, nous devrions ajouter la ligne

si j ≥ 0 compte ← compte + 1

juste après la fin de l'instruction while.

2. a. On devrait s'attendre à des nombres très proches de n 2 /4 (le

nombre orique de comparaisons clés effectuées par tri par insertion aléatoire
tableaux).

b. La proximité des rapports C(n)/n 2 à une constante suggère le θ(n 2 )

efficacité moyenne. La même conclusion peut également être tirée par l'observation
multipliant par quatre le nombre de comparaisons clés en réponse à
doubler la taille du tableau.

c. C (10 000) peut être estimé soit à 10 000 2 /4, soit à 4C (5 000).

3. Voir les réponses à l'exercice 2. Notez, cependant, que les données de temps sont
intrinsèquement beaucoup moins précis et volatiles que les données de comptage.

4. Les données présentent un comportement indicatif d'un algorithme nlg n.

5. Si M(n) obstruer n, alors la transformation n = a k (a > 1) donnera

M(a k ) ≈ (obstruer a)k.

6. La fonction lg lg n croît beaucoup plus lentement que la fonction à croissance lente.

lg n. De plus, si nous transformons les tracés par substitution n = 2 k , le tracé
du premier semblerait logarithmique tandis que l'intrigue du second serait
apparaissent linéaires.
 7. a. 9 (pour m = 89 et n = 55)

b. Deux nombres de Fibonacci consécutifs – m = F k+2 , n = F k+1 – sont les

plus petite paire d'entiers m ≥ n > 0 qui nécessite k comparaisons pour chaque
k 2. (C'est un fait théorique bien connu établi par G. Lamé (par exemple,
[KnuII].) Pour k = 1, la réponse est F k+1 et F k , qui sont tous deux égaux à
1.

58

Page 59

8. L'expérience doit confirmer le résultat théorique connu : la moyenne

l'efficacité au cas de l'algorithme d'Euclide est dans (lg n). Pour un peu différent
métrique T(n) étudiée par D. Knuth, T(n) ≈ 12 ln 2 2
lnn 0,843 lnn (voir
[KnuII], Section 4.5.3).

9. n/a

10. n/a
59