3.0 Validité et coût

Lorsqu’on écrit un algorithme, il est impératif de vérifier que cet algorithme va produire un résultat en un temps fini et que ce résultat sera correct dans le sens où il sera conforme à une spécification précise. Nous dirons alors que l’algorithme est valide.

3.1 Validité d’un algorithme itératif

Correction

Un algorithme itératif est construit avec des boucles. Pour prouver qu’il est correct, nous disposons de la notion d’invariant de boucle.

Définition

Un invariant d’une boucle est une propriété qui est vérifiée avant l’entrée dans une boucle, à chaque passage dans cette boucle et à la sortie de cette boucle. On peut faire le lien avec les suites définies par récurrence du programme de mathématiques. Pour démontrer qu’une propriété est un invariant d’une boucle, on utilise un raisonnement semblable au raisonnement par récurrence. On commence par vérifier que la propriété est vraie avant l’entrée dans la boucle. Cette étape s’appelle l’initialisation. On prouve ensuite que si la propriété est vraie avant un passage dans la boucle, alors elle est vraie après ce passage. Cette étape s’appelle l’hérédité. On peut alors conclure que la propriété est vraie à la sortie de la boucle.

Exemple Voici un algorithme de calcul avec une boucle conditionnelle et deux variables \(a\) et \(b\), \(a\) ayant pour valeur un entier naturel :

m = 0
p = 0
tant que m < a
   m = m + 1
   p = p + b
fin du tant que

Notons \(m\) et \(p\) les valeurs des variables \(m\) et \(p\).

Nous allons montrer que la propriété \(p = m * b\) est un invariant de la boucle « tant que ».

Avant le premier passage dans la boucle, \(m = 0\) et \(p = 0\), donc l’égalité \(p = m * b\) est vraie. Supposons que \(p = m * b\) avant un passage dans la boucle. Les nouvelles valeurs de \(m\) et \(p\) après le passage, notées \(m'\) et \(p'\) vérifient : \(m' = m + 1\) et \(p’= p + b\). Alors \(p’ = m * b + b = (m+1) * b = m'* b\). Donc la propriété est vraie après ce passage dans la boucle. Nous pouvons conclure qu’à la sortie de la boucle, \(p = m x b\). Et puisqu’à la sortie de la boucle, la variable \(m\) a pour valeur celle de \(a\), nous avons finalement obtenu le produit \(p = a * b\).

Terminaison

Un algorithme ne doit toujours comporter qu’un nombre fini d’étapes. Afin de prouver la terminaison d’un algorithme itératif, (qui contient une boucle), nous utilisons la notion de variant. Nous parlons ici de boucles conditionnelles. Dans le cas de boucles non conditionnelles, le nombre d’étapes est déterminé.

Méthode

On choisit un variant, c’est-à-dire une expression, la plus simple étant une variable, telle que la suite formée par les valeurs de cette expression au cours des itérations converge en un nombre fini d’étapes vers une valeur satisfaisant la condition d’arrêt. Considérons par exemple le code suivant où la valeur de la variable a est un nombre quelconque :

x = 0
while x ** 2 < a :
  x = x + 1

Si la valeur de \(a\) est négative ou nulle, il n’y a aucun passage dans la boucle. Sinon, la suite des valeurs de la variable \(x\), le variant choisi, est 0, 1, 2, \(n\) et n’est certainement la première valeur supérieure ou égale à la racine carrée de la valeur de \(a\). Le nombre de passages dans la boucle est donc fini.

Revenons sur l’exemple du produit de deux nombres étudié plus haut. Nous avons prouvé qu’en sortie de boucle, la valeur de \(p\) était le produit \(a * x\). Mais nous n’avons pas prouvé la terminaison, c’est-à-dire que la sortie de boucle était effective après un nombre fini de passages. Pour cela, dans cet exemple, nous choisissons comme variant la variable \(m\). Cette variable prend pour valeurs successives 0, 1, …, \(m\) et il y a donc exactement \(a\) passages dans la boucle, ce qui prouve la terminaison.

3.2 Coût

Un programme doit traiter une liste de \(10^7\) éléments puis une liste de \(10^8\) éléments. Est-ce que le temps d’exécution du programme sera multiplié par 10 ? Quel est le rapport entre le temps d’exécution est la taille de la liste?

Ce sont des questions auxquelles il faut réfléchir quand on écrit un algorithme.

Les réponses sont variées et dépendent de l’algorithme et de la liste. Pour une liste donnée, un programme peut être plus rapide qu’un autre, mais avec une autre liste, ce peut être le contraire.

Le même programme peut être plus rapide avec la liste la plus longue.

De plus, pour traiter un même problème, non seulement nous pouvons disposer de plusieurs algorithmes mais un même algorithme peut avoir un temps d’exécution différent selon le langage de programmation utilisé et suivant la machine sur laquelle le programme est exécuté. L’étude n’est pas simple à réaliser et pour comparer deux algorithmes nous allons ici nous concentrer sur le nombre d’opérations à effectuer en essayant d’évaluer un ordre de grandeur de ce nombre en fonction de la taille des données.

Nous parlerons du coût d’un algorithme ou de sa complexité. Ce coût pouvant être très différent pour une même taille de données, nous nous placerons dans le pire des cas, celui où le coût est le plus important.

Etudions quelques exemples simples qui sont à la base de ce type d’étude. Nous commençons par un algorithme rencontré précédemment.

m = 0
p = 0
tant que m < a
   m = m + 1
   p = p + b
fin du tant que

Les passages dans la boucle ont lieu pour les valeurs de \(m\) égales à 0, 1, 2, …, \(a - 1\) si la valeur de la variable \(a\) est un entier naturel \(a\). Nous avons donc exactement \(a\) passages dans la boucle.

A chaque passage, nous comptons deux additions ainsi que deux affectations. Nous pouvons donc dire que le nombre d’additions est \(2a\) ou que le nombre d’opérations, au sens large en comptant les affectations, est \(4a\). Nous dirons alors que le coût est proportionnel à \(a\) ou qu’il est linéaire. Avec une boucle « tant que », le calcul peut être plus compliqué puisque le nombre de passages dans la boucle varie avec les cas pour une même taille de données. Nous devons alors identifier le pire des cas, c’est-à-dire celui où le nombre de passages est maximal.

Considérons une boucle « pour » où le nombre de passages dans la boucle est bien déterminé.

somme = 0
for i in range(1, n+1) :
   somme = somme + i

Cet algorithme, ou ce programme, permet de calculer la somme des entiers de 1 à \(n\). Il y a clairement \(n\) passages dans la boucle. A chaque passage nous avons une addition et une affectation, donc un total de \(n\) additions et \(n\) affectations. Nous pouvons affirmer que le coût est linéaire.

3.3 Complexité linéaire

Soit \(n\) la taille d’une donnée. Si le nombre d’opérations à effectuer peut s’écrire \(αn + β\) , avec \(α\) et \(β\) réels et \(α > 0\),nous disons que l’algorithme a un coût linéaire ou une complexité linéaire. Dans le cas de deux boucles for imbriquées, nous avons trois cas typiques. Dans un cas, le coût est linéaire. Dans les deux autres cas, nous disons que le coût est quadratique.

3.4 Complexité quadratique

Soit n la taille d’une donnée. Si le nombre d’opérations à effectuer peut s’écrire \(αn2 + βn + γ\), avec \(α\), \(β\) et \(γ\) réels, \(α > 0\), nous disons que l’algorithme a un coût quadratique ou une complexité quadratique. Dans les codes qui suivent, les pointillés sous-entendent un nombre fixe d’opérations.

Premier cas : \(n\) est la taille de la donnée, \(k\) est un nombre fixé.

for i in range(n) :
    ....
    for j in range(k) :
      ....

Deuxième cas : est la taille de la donnée.

for i in range(n) :
    ....
    for j in range(n) :
      ....

Nous avons \(n\) passages dans la boucle externe. À chaque passage, nous avons un nombre fixe d’opérations \(q\) puis \(n\) passages dans la boucle interne. Dans la boucle interne, nous avons un nombre fixe d’opérations \(r\). Donc pour chaque valeur de \(i\), nous avons \(q + n * r\) opérations. Le nombre total d’opérations est donc \(n(q + n x r) = rn_2 + qn\) et le coût est quadratique.

Troisième cas: \(n\) est la taille de la donnée.

for i in range(n) :
    ....
    for j in range(i) :
      ....

Nous avons \(n\) passages dans la boucle externe. À chaque passage, pour chaque valeur de \(i\), nous avons un nombre fixe d’opérations \(q\) puis \(i\) passages dans la boucle interne. Dans la boucle interne, nous avons un nombre fixe d’opérations \(r\). Donc pour chaque valeur de \(i\), nous avons \(q + i * r\) opérations. Les valeurs de \(i\) sont successivement \(0, 1, 2,..., n-1\).

Le nombre total d’opérations est donc \(q + (q + 1 * r) + (q + 2 * r) + ... + (q + (n - 1) * r)\), soit \(nq + r(1 + 2 + ... + (n - 1))\).

Le calcul de la somme des entiers est connu. Le résultat est \(nq + r (n (n-1)) / 2\).

Finalement le nombre d’opérations est \(r/2 * n2 + (q – r/2)n\) de la forme \(αn2 + βn\) et le coût quadratique.