Thème : Algorithmique Activité : Un bon algorithme NSI 1ère

Lorsque l’on écrit un algorithme, en particulier un algorithme avec une boucle (POUR ou TANT QUE), il est
bon de se demander trois choses avant de le coder : L’algorithme est-il efficace ? La boucle se termine-t-
elle ? Fait-elle ce que je veux qu’elle fasse ?
Pour répondre à ces questions, on étudie la complexité, la terminaison et la correction de l’algorithme.

Partie I : Complexité (à comprendre)

« Deux algorithmes qui pour les mêmes données d’entrée donnent le même résultat sont-ils équivalents ? »
C’est le type de question que l’étude de la complexité d’un algorithme cherche à répondre. En effet, un bon
algorithme est un algorithme rapide et qui utilise peu de mémoire.
Pour déterminer la complexité d’un algorithme, on s’intéresse au nombre d’étapes nécessaires pour
compléter l’algorithme dans le pire des cas (c’est-à-dire quand la boucle tourne jusqu’au bout).
Les étapes correspondent aux affectations de variable et aux comparaisons.
Exemple : vérifier si la somme des entiers naturels entre 0 et n est pair
Entrée : n, un entier
somme = 0 Dans cet exemple, on compte :
i=0
 2 affectations pour initialiser somme et i
TANT QUE i < n
Ajouter i à somme  n+1 comparaison dans le TANT QUE
Ajouter 1 à i  n itérations donc :
FIN TANT QUE o n×2 affectations (somme et i)
SI somme est paire  1 comparaison dans le SI
AFFICHER "somme pair"
Le nombre d’étape est donc :
SINON
2 + n + 1 + 2n + 1= 3n + 4 étapes
AFFICHER "somme impair"
FIN SI

Note : dans les études de complexité, il est souvent préférable de remplacer une boucle POUR par une
boucle TANT QUE, pour avoir une meilleure compréhension
i=0  1 affectation Boucle POUR entre
POUR i allant à n exclus  TANT QUE i<n  n+1 comparaisons 0 et n
Ajouter 1 à i  n itérations de 1 affectation = 2n+2 étapes

I.1. Déterminer la complexité des algorithmes suivants.

 Algorithme A  Algorithme B
Entrée : n, un entier Entrée : n, un entier
factorielle = 1 resultat = 0
i=1 POUR i allant à n exclus
TANT QUE i <n+1 POUR j allant à 3
Multiplier factorielle par i Ajouter i*j à resultat
Ajouter 1 à i FIN POUR
FIN TANT QUE FIN POUR

 Algorithme C  Algorithme D
Entrée : n, un entier ; m, un entier Entrée : n, un entier
resultat = 0 resultat = 0
POUR i allant à m exclus POUR i allant à n exclus
Ajouter 1 à resultat POUR j allant à n
FIN POUR Ajouter i*j à resultat
POUR j allant de m à n exclus FIN POUR
Multiplier resultat par 2 FIN POUR
FIN POUR

Mélanie Gendre – Spécialité NSI 1ère – Lycée International de Saint Germain en Laye
Dans la pratique, il n’est souvent pas nécessaire de comptabiliser chaque étape d’un algorithme pour avoir
une idée de sa complexité. On peut définir un ordre de complexité qui classifie la performance de l’algorithme
en fonction de la taille des données d’entrée.

On peut citer différents ordres de complexité :

 O(1) quand la complexité est constante
 O(n) quand la complexité est linéaire (complexité ∝ taille)
 O(n2) quand la complexité est quadratique (complexité ∝ taille2)
 O(ln(n)) quand la complexité est logarithmique (complexité ∝ ln(taille))
 Etc…

Exemple :
Dans l’exemple précédent de « vérifier si la somme des entiers naturels entre 0 et n est pair », nous avons
trouvé qu’il y avait 3n étapes ; on peut donc dire que la complexité est linéaire.

I.2. Quel est l’ordre de complexité des algorithmes de la question précédente ?

Partie II : Terminaison (connaitre la définition et savoir que ça existe)

Lorsque l’algorithme contient une boucle, il est toujours intéressant de vérifier que la boucle se termine
avant de le coder (on ne veut pas se retrouver avec une boucle infinie). On appelle cela la terminaison.

Pour étudier la terminaison, on utilise un variant de boucle : S’il existe une fonction mathématique,
n’importe laquelle, d’un contrôleur de boucle (donc fonction entière), positive et strictement décroissante à
travers les tours de boucle, alors on peut conclure que la boucle se termine (puisqu’on peut montrer que,
quoi qu’il arrive, cette fonction dépendant du contrôleur de boucle va tendre vers zéro).
Exemple :
Dans la boucle de l’exemple précédent de « vérifier si la somme des entiers naturels entre 0 et n est pair », la fonction
VB(i) = n-i est bien entière (car fonction du contrôleur de boucle i), positive pour tous les i et strictement décroissante.
Puisqu’il existe un variant de boucle, on peut conclure que la boucle se termine.

II.1. Pour les algorithmes suivants (2 niveaux en fonction de votre aise) :

 Niveau « je suis assez à l’aise » : Sans regarder la réponse, trouver un variant de boucle
montrant que la boucle est finie.
 Niveau « oula, c’est quoi ça ? » : Montrer que les fonctions proposées en petit, à l’envers, en bas
de chaque algorithme sont variant de boucle pour cette boucle.

 Algorithme E :  Algorithme F
Puissances de n par multiplications successives Division euclidienne par soustractions successives
Entrée : n, un entier ; k, un entier Entrée : a, un entier ; b, un entier
puissance = 1 quotient = 0
i=1 reste = a
TANT QUE i <k TANT QUE reste ≥b
Multiplier puissance par n Soustraire b de reste
Ajouter 1 à i Ajouter 1 à quotient
FIN TANT QUE FIN TANT QUE
AFFICHER puissance AFFICHER quotient, reste
VB(i) = k-i VB(reste) = reste

Partie III : Correction (connaitre la définition et savoir que ça existe)

Tout comme tester la terminaison, vérifier si la boucle fait bien ce qu’on lui demande de faire est important :
c’est la correction.
Pour tester la correction, on utilise un invariant de boucle, qui est une affirmation (fonction du paramètre
de boucle qui doit être vrai à chaque itération). Cette affirmation est associée à la fonction utilisée dans la
boucle. A notre niveau, l’invariant de boucle sera toujours donné.
Mélanie Gendre – Spécialité NSI 1ère – Lycée International de Saint Germain en Laye
On prouve sa véracité par récurrence en suivant les deux étapes suivantes :
 On montre que l’assertion est vraie pour une certaine valeur du paramètre de boucle
 On montre ensuite que, en supposant que cette assertion est vraie pour i, elle l’est aussi pour i+1

Exemple :
Dans la boucle de l’exemple précédent de « vérifier si la somme des entiers naturels entre 0 et n est pair » correspond
i(i+1)
à une suite arithmétique (la somme de termes consécutifs), donc l’invariant de boucle peut être somme(i)= .
2
(cette relation provient d’une propriété des suites arithmétiques – on l’admettra ici)
Preuve
1×(1+1) 2
Pour i = 1, on a somme(1)= = = 1, ce qui est vrai
2 2
En remplaçant i  i+1, on a :
(i+1)(i+2) i2 + 3i + 2 i2 + i +2i + 2 i2 + i i(i+1)
somme(i+1)= = = = +(i+1)= +(i+1)= somme(i) + (i+1), ce qui est aussi vrai
2 2 2 2 2
Donc somme(i) est vrai à chaque itération de la boucle (comme somme(1) est vrai, ce sera aussi vrai pour somme(2),
puis somme(3), etc…), c’est bien un invariant de boucle.

III.1. Montrer que p(i) = ni-1 est un invariant de boucle pour l’algorithme E précédent (puissances de n par
multiplications successives).
Aide : Montrer d’abord que, pour la valeur initiale i=1, p(1) = 1 (ce qui est vrai car n0 = 1)
Ensuite, remplacer i  i+1 et montrer que p(i+1) = p(i)×n (ce qui est vrai car ni+1 = ni×n)

III.2. Montrer que a = (quotient×b + reste) est un invariant de boucle pour l’algorithme F précédent
(division euclidienne par soustractions successives). Attention, il y a 2 paramètres de boucle.
Aide : Tester l’assertion pour quotient = 0 et reste = a (les valeurs initiales de quotient et reste)
Ensuite, remplacer quotient  quotient+1 et reste  reste-b (l’itération suivante de la boucle) et montrer que l’assertion a =
(quotient×b + reste) est toujours vraie

Ce qu’il faut retenir

 Complexité
La complexité d’un algorithme permet de déterminer l’efficacité de l’algorithme et de le comparer avec
d’autres algorithmes réalisant les mêmes fonctionnalités.
Pour déterminer la complexité d’un algorithme, on s’intéresse au nombre d’étapes nécessaires pour
compléter l’algorithme dans le pire des cas (c’est-à-dire quand la boucle tourne jusqu’au bout).
Les étapes correspondent aux affectations de variable et aux comparaisons.
On peut définir un ordre de complexité qui classifie la performance de l’algorithme en fonction de la taille
des données d’entrée : ordre constant, linéaire, quadratique, logarithmique…

 Terminaison
Pour tester qu’une boucle se termine, on utilise un variant de boucle : s’il existe une fonction d’un
paramètre de boucle (donc fonction entière), positive et strictement décroissante à travers les tours de
boucle, alors la boucle est finie.

 Correction
Pour tester la correction, c’est-à-dire que la boucle fait bien ce qu’on lui demande de faire, on utilise un
invariant de boucle, qui est une assertion (fonction du paramètre de boucle qui doit être vrai à chaque
itération). Cette assertion est associée à la fonction utilisée dans la boucle.

Mélanie Gendre – Spécialité NSI 1ère – Lycée International de Saint Germain en Laye