Qu’est-ce qu’un algorithme ?
Publié le 19 09 2022 | Mis à jour le 18 04 2024
Le mot « algorithme » est utilisé couramment dans la presse pour désigner le fonctionnement opaque des moteurs de recherche et des réseaux sociaux. Mais de quoi parlons-nous exactement ? Qu’est-ce qu’un algorithme ? Cette notion a traversé l’histoire, depuis Euclide jusqu’aux algorithmes des GAFAM. Les algorithmes peuvent-ils résoudre n’importe quel problème ? Quelles garanties a-t-on sur leur comportement ? Quels sont leurs impacts sociétaux ?
Au IXesiècle, en Perse
L’étymologie fait remonter l’histoire des algorithmes au savant persan Muhammad Ibn Mūsā al-Khuwārizmī, qui aux alentours de l’an 800 a publié les premiers manuels de résolution d’équations. Ses méthodes, à l’origine de l’algèbre, concernent typiquement des problèmes de calcul pratiques : des questions d’héritage ou de mesure.
Ses ouvrages sont traduits en latin au cours du XIIesiècle et popularisés par des personnalités telles que le mathématicien italien Leonardo Fibonacci. C’est son nom, latinisé en « algoritmi » ou « algorismi », qui est à l’origine du terme « algorithme ». Près d’un millénaire avant lui, Euclide avait décrit dans les Éléments une méthode pour calculer le plus grand diviseur commun de deux nombres.
Au XXesiècle, la notion d’algorithme construit des branches des mathématiques
Il faut pourtant attendre le début du XXesiècle pour que la notion d’algorithme soit formalisée. Dans son célèbre discours au deuxième congrès international des mathématiciens à Paris en 1900, le mathématicien allemand David Hilbert propose 23 problèmes ouverts, 23 défis à relever pour la communauté mathématique, dont les énoncés auront une influence considérable sur le développement des mathématiques dans les décennies suivantes. Le dixième problème porte sur l’existence d’une « méthode par laquelle, au moyen d’un nombre fini d’opérations, on pourra déterminer l’existence d’une solution en nombres entiers à une équation polynomiale à coefficients entiers » (les équations « Diophantiennes »). C’est bien de l’existence d’un algorithme qu’il s’agit.
Lire la suite (The conversation)