Etude d'algorithmes

Algorithmes

Un algorithme décrit une suite d'opérations menant à la résolution d'un problème, en une durée finie.

La spécification d'un algorithme est la description précise du résultat que l'on attend de cet algorithme. Un algorithme qui donne un résultat conforme à sa spécification est dit correct

Un même problème peut souvent être résolu par plusieurs algorithmes : on pourra alors mettre en concurrence ces derniers en fonction, par exemple, du nombre d'étapes qu'ils comportent, qui influence directement la durée d'exécution.

L'objectif de ce chapitre est de présenter des caractéristiques et méthodes d'analyse d'algorithmes, en s'appuyant sur le cas d'algorithmes reposant sur le parcours séquentiel (élément par élément) d'un tableau de valeurs à l'aide d'une boucle.

Exemples d'algorithmes

Recherche d'une valeur

L'algorithme de l'exercice 1 repose sur la répétition d'une série d'actions, c'est à dire sur une boucle. Pour que l'algorithme réponde à sa spécification (ne pas risquer de chercher éternellement) vous vous êtes en principe assuré que la boucle se termine.
Pour cela vous avez utilisé sans le savoir un "variant de boucle".

Un variant de boucle est une quantité entière, positive, qui décroît strictement à chaque itération. La présence d'un variant de boucle permet de s'assurer de la terminaison d'une boucle.

Recherche du plus grand ou du plus petit élément

Implémentation sous Python

On dit qu'on implémente un algorithme quand on le traduit dans un langage de programmation pour le faire exécuter par une machine.

Attention : lorsqu'il sera demandé d'implémenter un algorithme par la suite, il faut bien comprendre qu'il s'agira de reproduire la démarche de résolution employée dans l'algorithme, et non simplement obtenir le même résultat. De manière générale, il faudra donc se restreindre à n'utiliser des instructions élémentaires : affectation et lecture de variables, opérations arithmétiques et logiques, tests conditionnels et boucles.

Complexité

Notion de complexité en temps

Une fois l'algorithme implémenté, il pourra être exécuté sur une machine. Selon l'algorithme, le matériel pourra être plus ou moins sollicité : l'exécution de l'algorithme consommera plus ou moins de temps de travail de l'UAL, et plus ou moins d'espace mémoire . Pour désigner ces caractéristiques de l'algorithme, on utilise le terme de complexité.

Le nombre d'opérations élémentaires effectuées lors de l'exécution de l'algorithme influence de manière déterminante la durée d'exécution sur une machine donnée. Cette caractéristique est appelée complexité en temps de l'algorithme.
La complexité en mémoire mesure la quantité d'espace mémoire utilisée par l'algorithme pour stocker ses variables pendant l'exécution.

La complexité en temps, ou plus précisément la façon dont elle évolue en fonction de la taille des données, est souvent déterminante dans le choix d'un algorithme.

Pour les deux algorithmes étudié, le nombre d'opérations est, dans le pire des cas, approximativement proportionnel à la taille n de l'ensemble de données : en effet, dès que cette taille devient un peu grande, l'essentiel du temps d'exécution est occupé par les n itérations de la boucle principale.

La complexité dans le pire des cas peut donc être approximativement considérée comme une fonction linéaire de la taille n des données : n → a × n

La complexité en temps d'un algorithme effectuant le parcours séquentiel d'un tableau de données est une fonction linéaire de la taille du tableau. On parle de "complexité linéaire", ou encore "en O(n)."

Mise en évidence expérimentale

En appliquant à une liste assez grande les implémentations obtenues aux exercices 4 et 5, on constate facilement que la durée d'exécution sous Python devient vite non négligeable. Mais peut-on vérifier si cette durée est bien proportionnelle à la taille de la liste ?

Pour cela il faut appliquer l'algorithme à des listes de tailles différentes et observer la corrélation entre la durée d'exécution et la taille de la liste. On aura intérêt à faire plusieurs mesures pour une même liste, pour lisser les variations aléatoires provenant des autres tâches effectuées en parallèle par l'ordinateur.

Nous allons d'abord faire ces tests sur des opérations natives Python, en utilisant l'instruction in pour vérifier la présence d'une valeur dans la liste, puis la fonction max pour trouver le maximum. Cela nous permettra de vérifier que, même si elles s'écrivent sur une seule ligne, ces opérations n'en suivent pas moins, de manière invisible, des algorithmes dont la complexité dépend de la taille de la liste.

Le programme ci-dessous permet d'observer la façon dont le temps d'exécution varie lorsqu'on vérifie la présence d'une valeur dans une liste de plus en plus grande.

Le programme crée une liste de valeurs entières aléatoires puis mesure la durée d'exécution pour 5000 recherches d'une valeur cible dans cette liste . La mesure est répétée pour des listes de plus en plus grandes, puis le programme trace un graphe montrant les variations de la durée d'exécution (en ordonnée) en fonction de la taille de la liste (en abscisse).

import matplotlib.pyplot as plt, time, random
vx=[]
vy=[]
for taille in range(1000,51000,1000):
alealiste=[random.randrange(taille) for i in range(taille)]
duree=0
repetitions=5000 #nombre de répétitions de l'opération
for essai in range(repetitions):
cible=random.randrange(taille)
debut=time.time()
x=cible in alealiste # vérification de la présence de la valeur cible dans la liste
duree=time.time()-debut+duree
print(taille,duree) # affichage facultatif de la durée totale d'exécution
vx.append(taille)
vy.append(duree)
plt.clf()
plt.plot(vx,vy)
plt.show()

L'allure du graphe obtenu est la suivante (l'abscisse est la taille de la liste et l'ordonnée la durée d'exécution) :

Le temps d'exécution est bien approximativement proportionnel à la taille de la liste : l'instruction in effectue un algorithme de complexité linéaire.

On peut faire la même constatation en remplaçant la vérification de la présence de la valeur cible par la recherche de la plus grande valeur de la liste à l'aide de la fonction max .

import matplotlib.pyplot as plt, time, random
vx=[]
vy=[]
for taille in range(1000,51000,1000):
alealiste=[random.randrange(taille) for i in range(taille)]
duree=0
repetitions=5000 #nombre de répétitions de l'opération
for essai in range(repetitions):
debut=time.time()
x=max(alealiste) # fonction implémentant l'algorithme étudié
duree=time.time()-debut+duree
print(taille,duree) # affichage facultatif de la durée totale d'exécution
vx.append(taille)
vy.append(duree)
plt.clf()
plt.plot(vx,vy)
plt.show()

La même base peut être utilisée pour tester vos propres implémentations des exercices 4 et 5, mais il faudra vous armer de patience (ou modifier un peu les valeurs dans le programme) car l'exécution de vos implémentations en Python sera beaucoup plus lente que celle des instructions natives équivalentes. Mais les graphes obtenus auront bien, à quelques irrégularités près, la même allure de droites passant par l'origine du graphe, indiquant une complexité linéaire.

Preuve de correction

L'identification d'un variant de boucle permet de vérifier si un algorithme comportant une boucle se termine, mais pas si donne le résultat attendu.

Pour montrer la correction d'un algorithme basé sur une boucle, on peut faire appel à la notion d' invariant de boucle.

Elle doit être vérifiée lors de l'entrée dans la boucle.
Quand elle est vérifiée, à l'tération i, en un point donné de la boucle, alors elle est forcément vérifiée aussi à l'itération i+1 au même point dans la boucle.

Par exemple, si on reprend l'algorithme de recherche de la plus grosse noisette contenue dans une boîte A:

Prendre dans la boîte A une première noisette dans la main gauche.
Tant qu'il reste des noisettes dans la boîte initialement pleine (boîte A) :
- y prendre une noisette avec la main droite
- comparer sa taille avec celle de la noisette tenue dans la main gauche.
- garder la plus grosse noisette dans la main gauche et mettre la plus petite dans la boîte initialement vide (boîte B)
La propriété "Il n'y a dans la boîte B aucune noisette plus grosse que celle que l'on tient dans la main gauche" est un invariant de boucle pour la boucle "tant que" dans cet algorithme.

La propriété est vérifiée à l'entrée dans la boucle : en effet, à ce moment là la boîte B est vide, elle ne contient donc aucune noisette plus grosse que celle qu'on tient dans la main gauche.
Si la propriété est vérifié à la i-ème itération, elle le sera aussi à la i+1-ième :
- admettons qu'à la fin de l'itération i aucune des noisettes contenues dans B ne soit plus grosse que celle qu'on tient dans la main gauche.
- lors de l'itération i+1, on prend une noisette dans la boîte A et on la compare à celle qu'on a dans la main gauche.
  - Si elle est plus petite ou identique, on la place dans la boîte B : celle-ci ne contient donc toujours aucune noisette plus grosse que celle qu'on a gardée dans la main gauche.
  - Si elle est plus grosse, elle remplace la noisette qu'on avait dans la main gauche, et celle-ci va rejoindre dans la boîte B les noisettes plus petites ou identiques à elle-même. La boîte B ne contient donc toujours aucune noisette plus grosse que celle qu'on a dans la main gauche.

Cet invariant suffit-il à prouver que l'algorithme donne le résultat attendu, c'est à dire permet d'identifier la plus grosse noisette de la boîte A ? Pas tout à fait, car il pourrait être véfifié par un autre algorithme incorrect, qui nous autoriserait par exemple à prendre des noisettes soit dans A soit dans une troisième boîte C, contenant éventuellement des noisettes beaucoup plus grosses : on n'aurait alors à la fin la plus grosse noisette, mais elle ne viendrait pas forcément de la boîte A.

Nous devons alors compléter notre invariant ainsi "La noisette qu'on a dans la main gauche provient de la boîte A, et il n'y a dans la boîte B aucune noisette plus grosse qu'elle". Cette version modifiée reste bien un invariant de boucle de l'algorithme du moment que les noisettes ne sont prises que dans la boîte A.

On remarque qu'à la fin de l'exécution de l'algorithme, cet invariant est exactement équivalent à la spécification de l'algorithme, qui était de trouver la plus grosse noisette initialement contenue dans la boîte A. Cela permet à cet invariant d'être une preuve de la correction de notre algorithme, c'est à dire de la conformité de son résultat à sa spécification.

Un invariant de boucle conduisant à la spécification d'un algorithme basé sur une boucle est utilisable comme preuve de correction de cet algorithme.