Trois questions essentielles sur un algorithme

Étant donné un algorithme. On se pose usuellement trois questions:

• Est-ce que l'algorithme stoppe bien à un moment donné?
• Est-ce que l'algorithme produit bien ce que l'on attend de lui?
• Est-ce que l'algorithme calcule en un temps raisonnable? en utilisant une quantité de mémoire raisonnable?

Nous précisons ci-dessous un peu la défiinition de ces trois points. La terminaison est ce qui nous intéressera dans les pages suivantes.

La terminaison

La question de terminaison est la suivante: est-on certain que pour toute entrée, l'algorithme proposé se terminera.

La question se ramènera souvent à prouver qu'une boucle n'est pas infinie.

On définira la notion de variant comme outil théorique pour justifier qu'un algorithme se termine.

La correction

La définition d'un algorithme comprend toujours une spécification de cet algorithme.

On peut voir de façon simple la notion de spécification comme suit:

• quelles sont les entrées?
• quelle est la sortie?
• quel lien existe entre les entrées et la sortie?

On peut résumer cela par "spécification = que calcule l'algorithme".

Établir la correction (partielle) d'un algorithme, c'est prouver que si les instructions définissant l'algorithme terminent alors elles calculent bien ce qu'annonce la spécification de cet algorithme.

Pour établir la correction d'un algorithme, l'outil théorique que nous utiliserons est la notion d'invariant de boucle.

Note

Correction dite totale = correction partielle + terminaison

La complexité

La complexité d'un algorithme se décompose en deux types de complexité:

• La complexité en temps: combien de temps prend un algorithme pour s'exécuter. On ramène cette question à la question du nombre d'opérations élémentaires nécessaires pour le déroulement de l'algorithme.

• La complexité en mémoire: quel espace en mémoire est nécessaire au déroulement de l'algorithme.