Problème et algorithme
Lorsqu'on écrit un programme, c'est dans le but de résoudre un problème. Cette notion a déjà été présentée à la section 4.2, avec celle de décomposition en sous-problèmes. Définir un problème consiste à identifier deux éléments :
- les données dont on dispose ;
- le résultat à produire.
Voici, par exemple, la description d'un problème en langue naturelle :
« Étant donné un nombre naturel non nul, identifier le nombre de diviseurs stricts qu'il possède. »
On identifie immédiatement les données et le résultat. On reçoit un nombre naturel non nul (une donnée de type int) et on doit calculer le nombre de diviseurs stricts qu'il a (une donnée de type int).
Un algorithme est une description d'un ensemble d'opérations à effectuer, et de l'ordre dans lequel elles doivent l'être. Il s'agit de la description d'un processus qu'il est possible d'exécuter. Voici un algorithme, décrit en langue naturelle, qui résout le problème qui nous intéresse :
« Pour trouver le nombre de diviseurs stricts du nombre $n$, on va examiner tous les entiers compris entre $1$ (inclus) et $n$ (exclu). Pour chacun de ces entiers, on vérifie s'il divise $n$ ou non. En comptant le nombre d'entiers qui passent le test de la division, on obtient la solution au problème. »
Comme le résume la figure 1, un algorithme résout donc un problème. En pratique, on va vouloir résoudre une instance donnée d'un problème, c'est-à-dire que l'on connaitra les données dont on dispose. Dans notre exemple, une instance du problème est :
« Identifier le nombre de diviseurs stricts que possède le nombre naturel $42$. »
Alors que l'algorithme n'est qu'une description, lorsqu'il s'agit de devoir l'exécuter sur une instance donnée d'un problème, il faut l'implémenter. L'implémentation d'un algorithme consiste à en écrire une version exécutable sur une machine à l'aide d'un langage de programmation, c'est-à-dire écrire un programme. Le listing de la figure 2 montre une implémentation possible de l'algorithme.
divisors.py contient une fonction qui compte le nombre de diviseurs stricts d'un nombre naturel non nul.Notez que pour un problème donné, il peut exister plusieurs algorithmes différents. Il n'y a en effet pas toujours qu'une seule approche possible à un problème. De même, un algorithme donné peut être implémenté de plusieurs façons différentes. On aurait, par exemple, pu utiliser une boucle while au lieu d'une for dans l'exemple des diviseurs.