Preuves d'un algorithme, complexité

3. Preuves d'un algorithme, complexité

Prouver un algorithme se fait en trois étapes.

La preuve de terminaison (preuve d'arrêt) vérifie que l'algorithme ne tournera pas indéfiniment quel que soit la donnée d'entrée.
Dans l'exemple ci-dessous, à chaque passage dans le Tanque, n subit une division euclidienne par 2 (DIV). Il atteindra donc forcément 0 ou 1, ce qui mettra fin à l'algorithme. On peut noter que, si n était négatif, l'algorithme terminerait sans entrer dans le Tantque ; cet algorithme est donc de ce point de vue robuste.

Algorithme LOG2
Donnée : un entier naturel e.
Résultat : le logarithme binaire entier k de e (k=lg(e).

k← 0; Tantque n>1 faire

n← e DIV 2;
k← k+1;

L'exemple choisi est suffisamment simple pour que les preuves de l'algorithme soit effectuées en quelques phrases. Pour des algorithmes plus compliqués, il faut effectuer des preuves plus formelles. Un des outils utilisés est la notion d'invariant. Un invariant est une propriété qui reste vraie tout au long de l'algorithme (ou d'un de ses blocs). Dans l'exemple ci-dessus, on aurait par exemple : « A chaque tour du Tantque, k augmente de 1 », « A chaque tour du Tantque, e est divisé par 2 (DIV) et donc diminue », ou « Chaque fois que e est divisé par 2 (DIV) k augmente de 1 ».

La preuve d'effectivité vérifie que l'algorithme fait bien ce qu'il annonce et qu'il le fait pour toutes les instances de la donnée passée en entrée.
Dans l'exemple ci-dessus, k a la valeur initiale 0, il est incrémenté de 1 chaque fois que e est divisé par 2, jusqu'à ce que e atteigne 0 ou 1. Il n'y a pas besoin de formaliser plus le raisonnement pour comprendre que k finit par avoir la valeur du logarithme entier en base 2 de l'entier naturel e.

La preuve d'efficacité vérifie que l'algorithme tourne rapidement. Cette efficacité est évaluée en deux étapes : 1^e mesurer la complexité temporelle de l'algorithme, et 2^e vérifier que cette mesure est acceptable (par rapport aux attentes ou en comparaisons d'autres algorithmes faisant le même travail).
Comme un algorithme peut être plus ou moins rapide selon les instances de la donnée entrée, on mesure la complexité dans le pire cas qui donne une borne supérieure qui ne sera dépassée par aucune instance. Cette mesure a priori peut être complétée par une deuxième mesure en moyenne qui nécessite d'évaluer le comportement moyen des instances et que nous n'étudierons pas.
Ces mesures se font par un outil mathématique appelé mesure asymptotique. On considère la taille n de la donnée qui est le nombre de mots-mémoire servant à la représenter. On cherche alors une fonction f(n) telle que l'algorithme effectue au plus f(n) opérations pour toute instance d'entrée. (On remarque qu'on a une double majoration avec au plus f(n) opérations pour l'instance la plus défavorable qui nécessite donc le plus d'opérations.)
On peut se ramener à ce nombre limité de fonctions grâce à la mesure asymptotique de la complexité : deux fonctions f et g sont équivalentes quand la limite vers l'infini du rapport f(n)/g(n) est une constante. Par exemple, f(n)=5n²+3n+4 sera équivalent à n² car lim_+∞f/n² = 5. On note O(f) (grand O de f) la classe d'équivalence d'une fonction. Dans notre exemple O(f)=O(n²), c'est-à-dire f∈O(n²). Les fonctions de références sont ainsi : lg(n), n lg(n), n², n³, ..., 2ⁿ. (lg dénote le logarithme en base 2. Il existe d'autres références de mesures de complexité avec les symboles Ω et θ que nous ne verrons pas.)
Voici quelques mesures de complexités classiques.
– recherche dichotomique dans un tableau de n valeurs : O(lg(n)),
– boucle Pour i de 1 à n : O(n),
– tri dichotomique de n valeurs : O(n lg(n)),
– boucles imbriqués pour i de 1 à n faire pour j de i à n faire : O(n²).
– tournée minimale d'un voyageur de commerce dans n villes : O(2ⁿ).

Il existe aussi une mesure de complexité d'un problème : un problème est dit en O(f) quand le meilleur algorithme possible est en O(f). Par exemple, déterminer la valeur maximale d'un tableau quelconque de n valeurs est en O(n), car le tableau étant quelconque on doit forcément atteindre chaque valeur, et atteindre une seule fois chacune suffit.

Chercher à optimiser un algorithme n'est pas un travail vain. Supposons qu'on ait une donnée de taille n=10 000 (taille raisonnable), les nombres d'opérations à réaliser seront de l'ordre de :
14 en O(lg(n)),
10⁴ en O(n),
10⁸ en O(n²),
10¹² en O(n³),
..., et 10³⁰¹⁰en O(2ⁿ).
Si on compte 10⁹ opérations élémentaires pour un ordinateur de bureau actuel, on obtient respectivement un temps de calcul de :
ε en O(lg(n)) ou O(n),
1/10 s en O(n²),
17 minutes en O(n³),
..., et 10²⁹⁹⁵ années en O(2ⁿ).
Avec n=10⁶ on aurait 17 minutes de calcul dès O(n²).

Effectuer la trace d'un algorithme sur une instance consiste à faire fonctionner l'algorithme pas-à-pas sur cette instance pour en vérifier la bonne conception. Le choix judicieux de quelques instances permet souvent de mettre en évidence des défauts de conception et facilite la construction de la preuve de l'algorithme.