Qu'est-ce qu'un algorithme ?

Qu'est-ce qu'un algorithme ?

Jean Cardinal

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 ?

Les algorithmes permettent de résoudre des problèmes mathématiques
et informatiques. Shubham Dhage, Unsplash, CC BY.

Au IXe siè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.

Première page du « Kitāb al-mukhtaşar fī ħisāb al-jabr wa-l-muqābala »,
considéré comme le premier manuel d'algèbre. Wikimedia.

Ses ouvrages sont traduits en latin au cours du XII^e siè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 XXe siècle, la notion d'algorithme construit des branches des mathématiques

Il faut pourtant attendre le début du XX^e siè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.

C'est par les travaux fondateurs d'Alan Turing et d'Alonzo Church, entre autres, que les algorithmes deviennent des objets mathématiques à part entière. Dans son article de 1936 [1], Alan Turing donne sa définition de la « calculabilité » d'une fonction : il doit exister une machine qui donne sa valeur en un nombre fini d'étapes élémentaires, guidées par un système de transitions et le contenu d'un ruban, qui joue le rôle de mémoire. C'est la célèbre « machine de Turing ».

Alan Turing comprend le lien entre la calculabilité d'une fonction et le caractère démontrable d'une assertion mathématique dans un système d'axiomes. L'informatique théorique devient une branche des mathématiques.

Un dispositif matérialisant la machine fictive de Turing,
définition mathématique d'un algorithme. Wikimedia.

On circonscrit la puissance des algorithmes, et certains problèmes sont démontrés indécidables : aucun algorithme n'existe pour les résoudre. En 1970, Julia Robinson et Youri Matiiassevitch résolvent finalement [2] le dixième problème de Hilbert : la résolution des équations diophantiennes est un problème indécidable !

Au cours des années 1970, on établit des hiérarchies de problèmes en fonction du temps et de l'espace qu'un algorithme requiert pour les résoudre : c'est la théorie de la complexité [3].

Comment se présente un algorithme ?

Les algorithmes sont souvent comparés à des recettes de cuisine : une suite d'instructions précises permettant d'obtenir un résultat en un nombre fini d'étapes.

Cette image est juste, mais occulte sans doute un aspect fondamental, le fait qu'un algorithme reçoit des données à traiter (nombres, texte, relations), et certaines instructions sont conditionnelles : les étapes suivies dépendent de ces données, et les exécutions peuvent suivre un cours difficilement prévisible. On peut donner ces instructions sous différentes formes bien définies (organigramme, langage de description), ou même, avec les précautions de rigueur, en langage naturel [4].

Nous avons tous appris l'algorithme de multiplication de deux nombres à l'école primaire, sans l'aide d'un formalisme avancé. Les algorithmes sont en principe destinés à être mis en œuvre sous forme de programme, dans un langage de programmation compréhensible par un ordinateur. Mais l'algorithme existe indépendamment de cette traduction.

Pour cerner la portée des algorithmes dans nos vies modernes, il faut distinguer leurs familles

Pour mieux comprendre les enjeux et les défis actuels autour des algorithmes, il est important de cerner leur portée et les propriétés que nous sommes à même de garantir sur leurs résultats et leurs comportements. Une typologie des algorithmes est indispensable à cette compréhension.

On peut d'abord distinguer une famille d'algorithmes tellement omniprésents dans notre quotidien qu'ils y sont presque devenus invisibles. Il s'agit d'algorithmes exacts pour des tâches parfaitement bien définies, dont le résultat est facilement vérifiable : multiplier deux nombres, trier une liste de noms par ordre alphabétique, stocker et retrouver efficacement une information, effectuer la conversion d'un signal analogique vers un signal numérique, interpréter un programme.

Le boulier, un instrument d'aide au calcul permettant de faire des additions,
soustractions, multiplications et divisions ainsi que l'extraction de racine carrée. HB.

Il s'agit là des algorithmes fondamentaux étudiés depuis les balbutiements des sciences informatiques. Ils ne font pas moins pour autant l'objet de recherches actuelles, tant des mystères subsistent autour de la complexité de certaines opérations fondamentales. La complexité exacte du problème de multiplication de deux nombres entiers, par exemple, est d'un point de vue théorique encore ouverte : nous sommes actuellement incapables de démontrer que la multiplication prend nécessairement plus de temps que l'addition ! Le meilleur algorithme de multiplication connu [5] n'a été publié que très récemment.

Les algorithmes d'optimisation constituent une deuxième famille importante. Ils résolvent des problèmes dans lesquels on cherche à identifier des paramètres ou une configuration qui maximise ou minimise une valeur, appelée « fonction objectif ». Les applications concrètes consistent par exemple en la recherche d'un chemin le plus court entre deux points, l'ordonnancement des phases d'un projet pour en minimiser la durée, le choix des emplacements d'antennes pour couvrir à moindre coût une zone donnée, ou celui des paramètres des routeurs d'un réseau pour en minimiser la latence.

Les objectifs des algorithmes de ces deux familles sont quantifiables et leurs résultats sont mathématiquement garantis. Les méthodes formelles [6] permettent de vérifier rigoureusement les propriétés d'un algorithme. Les algorithmes d'optimisation linéaire sont bien compris.

Une troisième famille d'algorithmes, plus spécialisés, est celle des algorithmes cryptographiques, destinés à garantir la sécurité des communications et transactions. Cette sécurité repose souvent sur des hypothèses liées à la complexité de problèmes algorithmiques. Le célèbre algorithme RSA [7] (du nom de ses inventeurs : Ronald Rivest, Adi Shamir et Leonard Adleman), par exemple, fait reposer la sécurité des transactions commerciales électroniques sur l'hypothèse qu'il n'existe pas d'algorithme efficace pour décomposer un nombre en ses facteurs premiers.

Certaines procédures issues des recherches en intelligence artificielle, en revanche, ne se soumettent pas facilement à une analyse rigoureuse.

Les algorithmes changent de nature avec l'intelligence artificielle

Parmi ceux-ci, les algorithmes de classification cherchent à placer les données reçues en entrée dans une catégorie correspondant à une réalité extérieure. Un algorithme de reconnaissance d'animaux, par exemple, recevra en entrée une image sous forme d'un tableau de pixels, et devra déterminer si cette image représente plutôt un chat ou un dauphin. Cette tâche n'est pas formellement bien définie : on peut probablement trouver une image ambiguë pour laquelle les réponses fournies par des humains pourraient être différentes. Le caractère correct de ces algorithmes dépend d'une réalité extérieure, qui n'est pas formalisée, et leur exactitude, ou précision, ne peut être établie qu'expérimentalement.

De la même manière, les algorithmes de prédiction cherchent à anticiper l'évolution de certaines quantités mesurées dans le monde physique, ou des comportements dans une population. Ils sont utilisés par exemple en finance [8] pour prédire l'évolution des marchés, ou en marketing, pour présenter aux visiteurs d'un site web les produits ou publicités les plus susceptibles d'attirer leur attention. La pertinence des résultats est ici encore validée empiriquement, et non mathématiquement. À tel point qu'en 2006, la société Netflix a lancé un concours pour améliorer les performances de son algorithme de prédiction d'évaluations de films, avec un prix d'un million de dollars à la clé.

Le développement des ces algorithmes fait massivement appel à des modèles probabilistes, mais aussi à des structures difficilement analysables rigoureusement. C'est le cas en particulier pour les algorithmes de réseaux de neurones artificiels utilisés dans ce qu'on appelle désormais l'« apprentissage profond », en référence au nombre de couches utilisées dans ces réseaux. Ces réseaux encodent implicitement la mémoire des données fournies lors d'une phase d'apprentissage, et permettent de classifier de nouvelles données en entrée.

Que pouvons-nous exiger des algorithmes ?

L'omniprésence des algorithmes fait légitimement l'objet de craintes. Quelles sont les garanties que nous pouvons exiger ?

Un premier type de garantie porte sur l'efficacité. Combien de temps doit-on attendre pour avoir une réponse ? De quelle quantité de mémoire doit-on disposer ? Ces questions sont bien étudiées et ont des formulations et des réponses rigoureuses [9], mais partielles. Les lacunes dans notre compréhension de la complexité algorithmique laissent en particulier ouverte la possibilité d'attaques inédites mettant en péril la cryptographie basée sur l'algorithme RSA.

La question traditionnelle des performances est intimement liée aux questions de consommation de ressources, qui ont des impacts écologiques. On peut donner à cette question un cadre plus large, et s'interroger sur les ressources consommées [10] par les logiciels, les serveurs. Dans le domaine des algorithmes cryptographiques, certains mécanismes au cœur du fonctionnement des cryptomonnaies, en particulier le principe de la « preuve de travail », ont un impact énergétique dramatique.

Lorsque les objectifs sont facilement vérifiables, comme dans le cas d'un algorithme de tri, ou quantifiés explicitement, comme dans le cas d'un algorithme d'optimisation, il existe une mesure objective de la qualité de la solution. Dans le cas des algorithmes d'optimisation, cependant, le choix de la fonction objectif, la quantité que l'on optimise, peut avoir un impact humain considérable.

Des questions d'éthique

Les questions d'équité et de transparence [11] des algorithmes de classification et de prédiction deviennent pressantes. Dans un ouvrage devenu classique, Cathy O'Neil alerte sur les dérives des systèmes de prise de décision dans les domaines de la justice, de l'action policière, des assurances, de l'évaluation des enseignants, entre autres.

L'algorithme de Gale-Shapley, utilisé par la plate-forme Parcoursup [12] satisfait des propriétés d'optimalité, mais garantit également qu'un comportement stratégique de la part des postulants est impossible.

Interview de Claire Mathieu : Parcoursup : les dessous de l'algorithme.
Source : Le Blob, l'extra-media [13].

Les méthodes d'apprentissage supervisé pour la classification consistent classiquement en une collection d'exemples, de paires « entrée-sortie », dont on espère qu'ils peuvent être généralisés, de façon qu'une nouvelle donnée en entrée puisse être associée à une réponse en sortie qui fasse sens. En ne fournissant que des exemples connus lors de ces phases d'apprentissage, on inculque au système tous les biais présents de facto dans les exemples dont on dispose, et l'on apprend ainsi à la machine à les reproduire. C'est le thème du documentaire Coded Bias [14], relatant l'expérience d'une étudiante du MIT avec les algorithmes de reconnaissance faciale.

Le caractère parfois inexplicable des résultats termine d'expliquer le glissement sémantique récent du mot algorithme : de simple méthode de calcul, l'algorithme est perçu comme une boîte noire omnipotente, dont le fonctionnement interne est inaccessible, et dont les réponses finissent par se substituer à la réalité. Cette perception s'explique notamment par la résurgence des méthodes de réseaux de neurones, dont la complexité défie toute analyse formelle. Les succès expérimentaux dans les tâches confiées aux réseaux profonds sont indéniables et fascinants. Mais certaines expériences mettent en évidence leur fragilité : des chercheurs ont montré qu'en modifiant de manière imperceptible quelques pixels bien choisis d'une image, on peut changer du tout au tout la réponse fournie. En l'absence d'explicitation de la réponse (« c'est un chat, car il a des oreilles pointues et des moustaches »), les questions de confiance et de responsabilités se posent.

La communauté de recherche en intelligence artificielle et en apprentissage automatique s'est emparée [15] des questions d'équité et d'explicabilité : le développement de méthodes d'apprentissage incluant des critères d'équité (fairness in AI) [16] est en plein essor, tandis que le domaine de l'intelligence artificielle « explicable » (explainable AI) [17] traite de la justification des résultats et de la confiance.

Al-Khuwārizmī aurait sūrement été surpris de la postérité de son patronyme !

Jean Cardinal
Professeur, Département d'informatique,
Faculté des Sciences,
Université Libre de Bruxelles (ULB)

Paru le 9 décembre 2021, sur The Conversation, l'expertise universitaire, l'exigence journalistique. https://theconversation.com/quest-ce-quun-algorithme-162896

Cet article est sous licence Creative Commons (selon la juridiction française = Paternité - Pas de Modification). http://creativecommons.org/licenses/by-nd/2.0/fr/

NOTES

[1] https://historyofinformation.com/detail.php?entryid=735

[2] https://mitpress.mit.edu/books/hilberts-10th-problem

[3] https://fr.wikipedia.org/wiki/Théorie_de_la_complexité_(informatique_théorique)

[4] https://fr.wikipedia.org/wiki/Langage_naturel

[5] https://annals.math.princeton.edu/2021/193-2/p04

[6] https://fr.wikipedia.org/wiki/Méthode_formelle_(informatique)

[7] https://dl.acm.org/doi/10.1145/359340.359342

[8] https://www.franceculture.fr/emissions/cultures-monde/un-futur-sans-humains-44-finance-quand-les-algorithmes-prennent-le-pouvoir

[9] https://press.princeton.edu/books/hardcover/9780691189130/mathematics-and-computation

[10] https://lejournal.cnrs.fr/articles/numerique-le-grand-gachis-energetique

[11] https://theconversation.com/emploi-securite-justice-dou-viennent-les-biais-des-ia-et-peut-on-les-eviter-154579