Qu'est-ce qu'un algorithme ?

Au IXe siècle, en Perse

Au XXe siècle, la notion d’algorithme construit des branches des mathématiques

Il faut pourtant attendre le début du XXe 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.

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 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é.

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.

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.

l 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 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 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 (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 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, 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 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 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.

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, 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 des questions d’équité et d’explicabilité : le développement de méthodes d’apprentissage incluant des critères d’équité (fairness in AI) est en plein essor, tandis que le domaine de l’intelligence artificielle « explicable » (explainable AI) 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 !

Cet article a été écrit par Jean Cardinal, professeur, département d'informatique, Faculté des Sciences, Université Libre de Bruxelles (ULB) pour le site The Conversation.