Université USTHB – Bab-Ezzouar Bab-Ezzouar, 2021 / 2022

Faculté de l’Electronique et de l’Informatique, 1ère année Master Informatique

Département de l’Informatique, Système Informatique Intelligent
Module : Conception et Complexité des Algorithmes Semestre 1

Corrigé des exercices 1,2 et 3 de la Série 1:

Exercice N°1:

1- Écrire les six algorithmes décrits ci-dessous pour déterminer si un nombre entier est premier ou
composé.

Algorithme A1 : Sachant qu’un nombre premier n est un nombre entier qui n’est divisible que par
1 et par lui-même. L’algorithme A1 va donc consister en une boucle dans laquelle on va tester si le
nombre n est divisible par 2, 3, ..., n-1.

Algorithme A1 ;
début
premier = vrai ;
i=2;
tant que (i <= n-1) et premier faire
si (n mod i = 0) alors
premier = faux
sinon
i = i+1 ;
fin.

Le pire cas qui nécessite le plus long temps, correspond au cas où n est premier car c’est
dans ce cas que la boucle s’exécute avec un nombre maximum d’itérations. Dans ce cas ce
nombre est égal à n-2.
La complexité est donc en O(n).

Algorithme A2 : Sachant que si n est divisible par 2, il est aussi divisible par n/2 et s’il est
divisible par 3, il est aussi divisible par n/3. De manière générale, si n est divisible par i pour i = 1
... [n/2] où [n/2] dénote la partie entière de n/2, il est aussi divisible par n/i. Selon cet énoncé,
proposer une optimisation de l’algorithme A1.

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
1
 Algorithme A2 ;
début
premier = vrai ;
i=2;
tant que (i <= [n/2]) et premier faire
si (n mod i = 0) alors
premier = faux
sinon
i = i+1 ;
fin.
Le cas le plus défavorable qui nécessite le plus long temps correspond toujours au cas où n
est premier et dans ce cas le nombre d’itérations est égal à n/2 -1.
La complexité est donc en O(n)

Algorithme A3 : Si n est divisible par x, il est aussi divisible par n/x. Il serait intéressant
d’améliorer A2 en ne répétant le test de la divisibilité que jusqu’à x = n/x.

Algorithme A3 ;
début
premier = vrai ;
i=2;
tant que i <= 𝑛 et premier faire
si (n mod i = 0) alors
premier = faux
sinon
i = i+1 ;
fin.

Le nombre maximum d’itérations est égal à [ 𝑛 ] -1, la complexité est en O( 𝑛 ).

Algorithme A4 : Dans le cas où n est impair, il ne faut tester la divisibilité de n que par les
nombres impairs. Proposez l’algorithme correspondant.

Algorithme A4 ;
début
premier = vrai ;
si (n <> 2) et (n mod 2 = 0)
alors premier = faux
sinon si ( n <> 2) alors
début
i=3 ;

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
2
 tant que (i <= n-2) et premier
faire
si (n mod i = 0) alors premier = faux sinon i = i+2 ;
fin
fin.

Le pire cas correspond au cas où n est premier et dans ce cas le nombre maximum
d’itérations de la boucle est égal à [n/2] -2, la complexité est en O(n).

Algorithme A5 : Proposez une hybridation des algorithmes A2 et A4.

Algorithme A5;
début
premier = vrai ;
si (n <> 2) et (n mod 2 = 0) alors
premier = faux
sinon si ( n <> 2) alors
début
i=3 ;
tant que (i <= [n/2]) et premier faire
si (n mod i = 0) alors premier = faux sinon i = i+2 ;
fin
fin.

Le nombre d’itérations de la boucle pour un nombre premier est égal à la moitié du nombre
d’itérations de A3, il est égal à [n/4] – 1. La complexité est donc en O(n).

Algorithme A6 : Concevez l’algorithme A6 en hybridant A3 et A4.

Algorithme A6 ;
début
premier = vrai ;
si (n <> 2) et (n mod 2 = 0) alors premier = faux
sinon si ( n <> 2) alors
début
i=3 ;
tant que (i <= 𝑛) et premier faire
si (n mod i = 0) alors premier = faux sinon i = i+2 ;
fin
fin.

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
3
Le nombre maximum d’itérations de la boucle est égal à ([ 𝑛 ]/2 – 1). La complexité est
donc en O( 𝑛 ).

2- Évaluer la complexité pour chacun des algorithmes proposés.

Récapitulatif:

Algorithme Nombre maximum Complexité théorique Nombre réel

d’itération ( en d’itération avec
fonction de n) n=69524913

A1 n-2 O(n) 69524911

A2 [n/2] – 1 O(n) 34762455

A3 [ 𝑛 ] -1 O( 𝑛) 8337

A4 [n/2] – 1 O(n) 34762455

A5 [n/4] – 1 O(n) 17381227

A6 ([ 𝑛 ]/2 – 1) O( 𝑛) 4168

Exercice N°2:

1- Calculer les ordres de grandeur suivants en secondes : 1 heure, 1 jour, 1 semaine, 1 mois, 1
année, 1 siècle, 1 millénaire.

● 1min = 60 s
● 1 heure = 3600s = 3.6 * 103s
● 1 jour = 86400s = 8.64* 104s
● 1 semaine = 604800s ≈ 6.05* 105s
● 1 mois= 2 592 000s ≈ 2.59 *106s
● 1 année =31 536 000 ≈ 3.15 *107s
● 1 siècle =3 153 600 000≈3.15* 109s
● 1 millénaire = 31 536 000 000 ≈ 3.15* 1010s

2- Considérer 7 algorithmes A0, A1, ..., A6 conçus pour résoudre un même problème de taille n.
La complexité en temps de chacun de ces algorithmes est exprimée dans la table ci-dessous.

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
4
 Complexit Temps (secondes) Temps (milliseconde)
Algo é
temporelle n=10 n=100 n=1000 n=10 n=100 n=1000

A0 O(1) 1s 1s 1s 10-3s 10-3s 10-3s

A1 O(𝑙𝑛(𝑛)) 2.3s 4.6s 6.9 0.0023 0.0046s 0.0069s

s

A2 O( 𝑛) 3.16s 10s 31.62s 0.003s 0.01s 0.031s

A3 O(n) 10s 1min 40s 103s=16min 0.01s 0.1s 1s

40s

A4 2
O(𝑛 ) 102s = 104=2 h 46 106=11 jrs 13 0.1s 10s 16mn40s
1min 40s min 40 s h 46 m 40 s

A5 3
O(𝑛 ) 103s = 106 =11 jrs 109=31ans 1s 16mn40s 11j13h 46min
16min 13 h 46 m 8mois 40s
40s 40 s 19jrs 1 h 46
min 40 s

A6 4
O(𝑛 ) 10 000s = 100 000 1012s ≃ 31 10s 1j 3h 46min 31ans 8mois
2h 46min 000s = millénaires 40s 19jrs 1h 46min
40s 38mois 17 40s
jours 9h
46min 40s

A7 𝑛
O(2 ) 1 024s = 1.267*1030s 1.07*10301 ≃ 1.02s 3.2*1016mill 3.2*10286millé
17min 4s ≃ 4*1019 3*10290 énaires naires
millénaires millénaires

En supposant qu’une unité de taille s’exécute en 1 seconde, calculer le temps nécessaire pour
traiter des tailles respectivement égales à 10, 100 et 1000.

3- Répéter la question 2 avec une unité de temps égale à une milliseconde puis à une
microseconde.

4- Que peut-on en conclure ?

Nous concluons que l’augmentation de la performance de la machine de calcul apporte les effets
suivants :

● Améliore le temps de calcul pour des complexités polynomiales

● La puissance de la machine n’améliore pas vraiment le temps de calcul pour les grandes
complexités lorsque la taille du problème est grande et ne peut donc pas constituer une
solution pour contourner le problème de l’explosion combinatoire.

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
5
 ● Pour les petites tailles de problème, la fonction exponentielle est plus intéressante que
certaines fonctions polynomiales (n = 10, A7 est plus rapide que A6)

Exercice N°3:

Considérer le théorème suivant sur le PGCD (le Plus Grand Commun Diviseur) :
PGCD(a,b) = PGCD(b, a mod b)

1- Utiliser ce théorème pour écrire un algorithme de calcul itératif du PGCD de deux entiers a et
b.

fonction PGCD(a,b : entier) : entier ;

var
quotient, reste : entier;
début
quotient := a / b;
reste := a – q*b;
tant que (reste <> 0) faire
début
a :=b;
b := reste;
quotient := a / b;
reste := a – quotient*b ;
fin;
pgcd := b;
fin;

2- Calculer la complexité temporelle de l’algorithme.

Le pire cas correspond à la situation où à chaque itération, le quotient de la division de a par b est
égal à 1 et donc au nombre maximum d’itérations. Dans ce cas le reste de la division est égal à la
différence entre a et b puisque :
reste := a – q*b = a – 1*b = a-b
⇒ a= reste+b

Les différentes itérations de l’algorithme donnent:

1. an=reste(a,b)+b ⇒ an-1=b
2. an-1= reste(b,reste(a,b))+reste(a,b)
3. .
4. .
...
n-2. a2=a1+a0

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
6
 Passage de PGCD à Fibonacci Exemple
Notons que: a=an = 60 et b=bn = 37
resten = resten(an ,bn) = bn - an an= resten(an,bn) + bn
60 = reste(60, 37) + 37 = 23 + 37
On sait que: an = resten + bn an-1 ← bn=37 et bn-1 ← resten=23
et que : an-1 ← bn -------------------------------------------
et que : bn-1 ← resten an-1= resten-1(an-1,bn-1) + bn-1
(division euclidienne) 37 = reste(37, 23) + 23 = 14 + 23
an-2 ← bn-1=23 et bn-2 ← resten-1=14
en remplaçant : bn-1 ← resten -------------------------------------------
dans : an = resten + bn an-2= resten-2(an-2,bn-2) + bn-2
⇒ an = bn-1+ bn 23 = reste(23, 14) + 14 = 9 + 14
an-3 ← bn-2=14 et bn-3 ← resten-2=9
en remplaçant par : an-2 ← bn-1 -------------------------------------------
dans : an = bn-1+ bn an-3= resten-3(an-3,bn-3) + bn-3
⇒ an = an-2+ bn 14 = reste(14, 9) + 9 = 5 + 9
an-4 ← bn-3=9 et bn-4 ← resten-3=5
en remplaçant par : an-1 ← bn -------------------------------------------
dans : an = an-2+ bn an-4= resten-4(an-4,bn-4) + bn-4
⇒ an = an-2+ an-1 avec a0 =0 et a1 = 1 9 = reste(9, 5) + 5 = 4 + 5
⇒ Suite de Fibonacci an-5 ← bn-4=5 et bn-5 ← resten-4=4
-------------------------------------------
an-5= resten-5(an-5,bn-5) + bn-5
5 = reste(5, 4) + 4 = 1 + 4
an-5 ← bn-4=4 et bn-5 ← resten-4=1
-------------------------------------------
an-6= resten-6(an-6,bn-6) + bn-6
4 = reste(4, 4*1) + 4*1 = 0 + 4
bn-5=1 et resten-5=0
-------------------------------------------
PGCD(60, 37) = bn-5 = 1

Si a est supérieur à b, la séquence reste, b et a fait partie de la suite de Fibonacci, car les deux
dernières itérations correspondent respectivement à reste=1 et à reste=0, qui coïncident avec
l’initialisation de la suite de Fibonacci. En résumé le cas le plus défavorable correspond au calcul
du pgcd de deux nombres consécutifs de la suite de Fibonacci:
Fn-1 et Fn-2 où Fn = Fn-1 + Fn-2 ; F1 = 1 et F0 = 0.
Sachant que :
Fn = Fn-1 + Fn-2 et Fn-1 = Fn-2 + Fn-3 ⇒ Fn = 2*Fn-2 + Fn-3 ⇒ Fn ≥ 2* Fn-2
De la même manière:
F n > 2*F n-2 > 2*2*F n-4 > ...> 2 k

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
7
Où k est égal approximativement à la moitié de la longueur de la suite de Fibonnacci qui
correspond au nombre d’itérations de la boucle. Le nombre d'itérations est égal à 2k. Si a est
supérieur à b, a=Fn et par conséquent :
a > 2k
ln a > ln2k = k ln 2
𝑙𝑛 𝑎
k<
𝑙𝑛 2
d’où :
𝑙𝑛 𝑎 2 * 𝑙𝑛 𝑎
2*k < 2 *
𝑙𝑛 2
⇒m< 𝑙𝑛 2
La complexité est donc en O(ln a).

3- Écrire la version récursive de l’algorithme trouvé en (1) et calculer sa complexité temporelle.

fonction pgcdRécursive(a,b : entier) : entier ;

var
q,r,pgcd : entier ;
début
si (b = 0) alors
retourner a;
sinon
début
q := a div b; //division entière
r := a – q*b;
pgcd := pgcdRécursive(b,r);
fin;
retourner pgcd
fin;

La complexité de la fonction pgcd est la même que celle calculée pour la 2ème question.
c’est-à-dire en O(ln a) avec a > b.

4- Écrire un algorithme pour calculer le PPCM (Plus Petit Commun Multiple) de deux nombres a
et b et calculer sa complexité.

|𝑎*𝑏|
𝑃𝑃𝐶𝑀(𝑎, 𝑏)=
𝑃𝐺𝐶𝐷(𝑎,𝑏)

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
8
Remarque :
Au lieu d’utiliser le quotient et le reste, il est possible d’utiliser seulement le modulo pour
résoudre les questions 1 et 3.

fonction PGCD(a,b : entier) : entier ;

var
temp : entier;
début
tant que (b <> 0) faire
début
temp=b;
b := a mod b;
a=temp;
fin;
pgcd := b;
fin;

fonction pgcdRécursive(a,b : entier) : entier ;

var
q,r,pgcd : entier ;
début
si (b = 0) alors
retourner a;
sinon
début
pgcd := pgcdRécursive(b, a mod b);
fin;
retourner pgcd
fin;

● HOUACINE Naila Aziza n.a.houacine@gmail.com

● BENDIMERAD Lydia Sonia l.s.bendimerad@gmail.com
9