L’histoire de l’algorithmique

Atteindre des objectifs

Nous vivons dans un univers à la fois déterministe et probabiliste. Déterministe parce que de nombreux phénomènes s’expliquent grâce au principe de cause à effet. Probabiliste parce que, même si nous ignorons un certain nombre des causes à l’origine d’un événement ou phénomène précis, nous pouvons essayer de prévoir l’issue de cet événement grâce à des outils mathématiques. Comme le disait Galilée, "la nature est un livre écrit en langage mathématique". Si l’univers n’était ni déterministe ni probabiliste, notre quotidien se résumerait en la constatation du chaos et de l’aléatoire le plus complet. Ce lien entre mathématiques et monde physique a conduit le prix Nobel de physique Eugène Wigner (1902-1995) à parler de "la déraisonnable efficacité des mathématiques dans les sciences de la nature" dans le cadre d’un article qui a fait couler beaucoup d’encre. Réfléchissez à ce qu’impliquerait un monde dans lequel le chaos et l’aléatoire seraient la règle. Dans un tel monde, nous serions dans l’impossibilité de faire une chose à la fois naturelle et vitale : nous fixer des objectifs....

Où trouve-t-on les algorithmes ?

Vous voyez des algorithmes partout et tous les jours : la recette permettant de préparer un kouign-amann, l’itinéraire pour vous rendre à un rendez-vous, la notice de montage d’un nouveau lit (en utilisant toutes les vis sans exception), la stratégie pour rentrer dans votre jean préféré devenu trop petit suite au confinement, trouver la définition d’un mot dans un dictionnaire… Tous ces exemples sont des algorithmes, autrement dit des objectifs découpés en étapes précises. En toute logique, si l’objectif change, la méthode ou l’algorithme pour l’atteindre change aussi. Par contre, si deux objectifs sont très proches, les algorithmes utilisés pour les atteindre sont très proches. C’est ce que la définition de Wikipédia sous-entend quand elle parle de "classe de problèmes". Une classe de problèmes est une catégorie précise d’objectifs à atteindre qui utilise le même type de méthode ou d’algorithme. Par exemple, "trouver la définition d’un mot dans un dictionnaire".

Évidemment, il peut exister plusieurs manières, donc algorithmes, permettant d’atteindre un même résultat, de la même façon que plusieurs routes mènent...

Depuis quand les algorithmes existent-ils ?

Quels sont les algorithmes les plus anciens ? On cite couramment l’algorithme d’Euclide (III^e av. J.-C.), qui calcule le plus grand commun diviseur (ou PGCD, c’est-à-dire le plus grand entier qui en divise deux autres en laissant un reste nul), ou encore le crible d’Eratosthène (III^e siècle av. J.-C.), qui permet de trouver tous les nombres premiers (c’est-à-dire les nombres entiers naturels qui ne peuvent être divisés que par eux-mêmes ou par 1 pour donner un reste nul) inférieurs à un certain entier naturel donné. Même si ces algorithmes sont très anciens, il est faux de dire que les premiers algorithmes datent de l’Antiquité. Ils sont beaucoup, beaucoup plus anciens.

Pour s’en convaincre, il suffit de reprendre la définition d’un algorithme. Comme dit précédemment, c’est une chaîne d’actions claires et ordonnées, réalisées dans le but d’atteindre un objectif précis. Or, ces chaînes d’actions existaient bien avant l’Antiquité. S’il n’en avait pas été ainsi, comment les hommes ayant vécu avant l’Antiquité s’y seraient-ils pris pour réaliser les peintures de la grotte de Lascaux ? Comment auraient-ils fait pour cultiver...

Les algorithmes et les ordinateurs

Selon Gérard Berry (professeur au Collège de France et titulaire de la chaire "Algorithmes, machines et langages"), "un algorithme, c’est tout simplement une façon de décrire […] comment procéder pour faire quelque chose. Il se trouve que beaucoup d’actions mécaniques, toutes probablement, se prêtent bien à une telle décortication. Le but est d’évacuer la pensée du calcul, afin de le rendre exécutable par une machine numérique (ordinateur…)."

Dans sa définition, Gérald Berry énonce l’une des raisons qui font systématiquement associer les algorithmes à l’informatique. En effet, l’ordinateur est l’élément central de la révolution numérique. L’usage des ordinateurs dans le cadre de l’informatique (science du traitement automatique de l’information) est devenu indispensable dans un nombre toujours plus grand de domaines. Et puisqu’un ordinateur n’est au fond qu’un système électromécanique, il est non seulement possible, mais aussi extrêmement efficace de lui faire exécuter différents algorithmes au travers de calculs. L’ordinateur exécutera ces algorithmes par l’intermédiaire de programmes informatiques, qui sont des suites d’instructions écrites ou codées dans un langage informatique.

Quand Gérald Berry parle d’"évacuer la pensée", il fait référence au fait que les instructions d’un algorithme doivent être explicites, non ambiguës (nous reviendrons sur cette notion dans le chapitre Les algorithmes d’intelligence artificielle). L’ordinateur doit être en mesure de réaliser les actions sans "réfléchir", car un ordinateur ne sait pas réfléchir, il ne fait qu’exécuter des instructions l’une après de l’autre. Rappelons cependant que l’association "algorithme" et "informatique" est restrictive. Les algorithmes sont partout. On ne les trouve pas que dans le domaine de l’informatique.