Lors des débats actuels sur ParcourSup, ou à des discussions antérieures au sujet d’« algorithmes » utilisés à différentes fins en rapport avec la société, j’ai vu des questions sur la différence entre « algorithme » et « logiciel ». Je vais ici tenter d’expliquer les différences et similarités entre ses deux concepts.

Prenons un exemple simple : nous avons un tableau de nombres (par exemple 16, 3, 45, 2, 7, 32, 42, 51) et nous voulons les classer par ordre croissant. Ceci est la spécification de notre algorithme : nous spécifions ce que nous désirons obtenir.

Un algorithme possible pour cette tâche de tri est le suivant : on recherche dans le tableau le plus petit nombre, on l’intervertit avec le nombre en première position, puis on recommence pareil sur le reste du tableau privé du premier élément, puis sur le reste du tableau privé du deuxième élément, et ainsi de suite jusqu’à la fin du tableau. (On le connaît dans les cours d’algorithmique sous le nom de tri par sélection.)

Voyons maintenant pourquoi cet algorithme est correct, c’est-à-dire qu’il fait bien ce que nous voulons. Tout d’abord, la sortie est triée : on a bien le plus petit nombre en premier, puis le plus petit parmi les nombres restants, etc. Par ailleurs, cette sortie a bien le même contenu que l’entrée, ce sont bien les mêmes données dans un autre ordre, puisqu’on ne procède que par permutations.

Remarquons que la description de cet algorithme est incomplète : je n’ai pas dit comment je recherche le plus petit nombre dans le tableau. C’est parce que la méthode précise par laquelle je recherche ce plus petit nombre importe peu pour garantir le bon fonctionnement de mon algorithme de tri : ce qui importe c’est qu’on me donne ce nombre, ou plus précisément sa position dans le tableau. J’écris pour que des humains me lisent, je ne vais pas les surcharger de détails !

En revanche, si je programme un logiciel qui procède à un tri, je suis bien obligé de régler tous les détails : comment le tableau est stocké dans l’ordinateur, quelle procédure de recherche du plus petit élément j’utilise. La langue naturelle est imprécise et par ailleurs difficile à faire comprendre par un ordinateur, aussi je décris mon logiciel dans un langage de programmation qui me permet de décrire précisément les étapes de calcul que je désire faire effectuer par l’ordinateur.

Notons qu’un logiciel complet ne se limiterait pas à un unique algorithme : il faut une interface utilisateur (dont l’affichage nécessiterait d’autres algorithmes), des traitements de situations d’erreurs, etc. Tout ceci peut paraître facile et de peu d’intérêt, mais il me semble que, dans la grande majorité des logiciels, la plus grande partie du code du logiciel concerne ces aspects et non des algorithmes délicats.

Revenons à notre algorithme de tri. Étant donné un tableau de nombres passé en entrée, il n’existe qu’une seule sortie permise par la spécification : un tableau avec le même contenu mais trié dans l’ordre. Peu importe la façon dont on a procédé ! Imaginons maintenant qu’il s’agisse d’un tableau de noms d’élèves avec leurs notes, que l’on va trier par notes croissantes. Nous n’avons pas dit comment départager les ex-æquo, aussi, suivant l’algorithme de tri utilisé, nous pourrions avoir plusieurs sorties possibles dans ce cas. Notre spécification est alors incomplète.

Lorsque la spécification est complète (on a complètement défini d’avance le résultat attendu), ni le choix de l’algorithme ni les détails de fonctionnement du logiciel ne nous importent, puisque, quelle que soit la façon dont on s’y prend, il y aura toujours le même résultat au bout. Il nous faut toutefois nuancer cette affirmation.

Le choix de l’algorithme et les détails de fonctionnement du logiciel ont leur importance en ce qui concerne le temps de calcul. Par exemple, l’algorithme de tri que j’ai décrit ci-dessus est très mauvais sous cet aspect : le nombre d’opérations qu’il nécessite croît avec la taille du tableau d’entrée beaucoup plus vite que le nombre d’opérations utilisées par d’autres algorithmes, de sorte que son coût serait prohibitif sur une grosse base de données (et donc une personne compétente ne l’emploiera jamais que sur de petits tableaux).

Par ailleurs, nous pouvons aussi soupçonner qu’il y a des écarts entre l’algorithme « idéal » décrit sur le papier, et ce qui a été effectivement mis en œuvre dans le logiciel, qu’il s’agisse de « bugs » involontaires ou d’altérations censées répondre à certaines contraintes mais pas forcément bien maîtrisées. Il ne suffit donc pas d’avoir la spécification ou l’algorithme idéal pour vérifier qu’un logiciel répond à la demande.

PS On me souffle des analogies : l'algorithme c'est le plan, la théorie; le logiciel, la réalisation, la pratique. La mienne : l'algorithme c'est un thème musical, le logiciel c'est l'interprétation complète d'un morceau comportant plusieurs thèmes orchestrés.