La grande épopée des algorithmes

La grande épopée des algorithmes

Claire Mathieu

Longtemps étudiés par les seuls mathématiciens, les algorithmes montent en puissance depuis le début des années 1970, avec la démocratisation de l'informatique. Ils continuent de se développer aujourd'hui, notamment pour proposer de nouvelles technologies d'intelligence artificielle. Entretien avec Claire Mathieu, directrice de recherche CNRS et experte des algorithmes d'approximation et des algorithmes en ligne.

Propos recueillis par Christophe Dutheil.

Cycle hamiltonien © Inria / Photo C. Morel

Pour commencer, pourriez-vous nous exposer ce qu'est un algorithme ?

L'explication la plus claire me semble être celle qui a été donnée dans un article par mon défunt confrère Philippe Flajolet [1], qui a été une figure de l'algorithmique en France pendant près de 40 ans. Un algorithme est simplement une méthode qui explique comment résoudre un problème pas à pas, par le biais d'une suite d'instructions élémentaires. Je pense par exemple aux instructions que l'on vous enseigne à l'école primaire pour les additions à plusieurs chiffres : vous apprenez la méthode d'addition avec retenue, et ensuite vous êtes capable de faire n'importe quelle addition.

La recherche en algorithmique consiste à concevoir de nouveaux algorithmes ou à les analyser, afin de démontrer leurs propriétés.

Dans vos recherches, à quels types d'algorithmes vous intéressez-vous ?

Je suis spécialiste des algorithmes d'approximation qui ont pour objectif de proposer une solution suffisamment bonne pour résoudre des problèmes complexes, pour lesquels la résolution exacte (la « meilleure » solution) serait trop longue ou trop difficile à trouver. Il existe beaucoup de problèmes de ce type, typiquement des problèmes dits « NP-difficiles », qui sont au moins aussi ardus que le fameux problème du voyageur de commerce [2] (un problème d'optimisation qui vise à déterminer, en fonction d'un ensemble de villes, le plus court circuit pour passer par chaque ville au moins une fois). Par exemple, je pense à un déménageur qui chercherait à remplir son camion en laissant le moins d'espace vide possible, ou à un carreleur qui voudrait paver le mieux possible les parois d'une douche aux formes atypiques en découpant le moins de carreaux possibles. Il faudrait beaucoup de temps pour calculer la meilleure solution, alors que ces professionnels ont juste besoin d'une méthode pertinente mais rapide qui les aide dans leur travail. Dans des cas comme ceux-ci, les algorithmes d'approximation permettent d'utiliser une approximation, dont on sait qu'elle est suffisamment bonne et qu'elle peut être trouvée dans un délai raisonnable. Pour cela, on modélise un problème complexe afin qu'il devienne un problème mathématique à résoudre. Puis on définit le degré d'approximation acceptable. L'algorithme va par exemple préciser qu'un résultat pourra être accepté dès lors qu'il se situe à moins de 10 % de l'optimum.

Quelles ont été les grandes évolutions dans le domaine de l'algorithmique, notamment au cours du dernier siècle ?

L'histoire des algorithmes remonte à très loin... Ainsi, le terme algorithme vient du chercheur Al-Khwarizmi [3], actif au 9^e siècle en Irak : il est le premier à avoir décrit et formalisé des méthodes permettant de résoudre des problèmes mathématiques (additions, multiplications, résolutions d'équations simples...). Un changement d'échelle majeur est survenu après la Seconde Guerre mondiale, notamment pour résoudre les problèmes logistiques complexes que posaient la reconstruction des grandes infrastructures d'Europe de l'Est. Ces difficultés logistiques avaient une expression mathématique, qu'il fallait résoudre. Parmi les avancées les plus significatives à cette époque, figure l'algorithme du simplexe [4] inventé en 1947 par l'américain George Dantzig, qui est très utilisé pour résoudre des problèmes d'optimisation linéaire (il permet de minimiser une fonction sur un ensemble défini par des inégalités).

Mais les algorithmes sont vraiment montés en puissance dans les années 1970, à mesure que les ordinateurs devenaient de plus en plus puissants et de plus en plus utilisés. Un algorithme se traduit en un programme, qui est traduit en langage machine, et dont les instructions peuvent ensuite être suivies par l'ordinateur. En 1971, le chercheur américano-canadien Stephen Cook a formalisé le concept de « NP-difficulté » (ces concepts ont également été indépendamment développés par Leonid Levin [5]). Relevant de la théorie de la complexité, l'abréviation NP signifie « non déterministe polynomial » (« nondeterministic polynomial time »). Ce chercheur a prouvé l'existence d'une classe NP, comprenant des problèmes dont on sait vérifier une solution de façon efficace ; un exemple de problème dont on sait vérifier une solution facilement est celui de la factorisation d'un entier N en nombres premiers : on sait — depuis 2002 — tester si un nombre est premier, et il suffit d'effectuer la multiplication pour vérifier si le produit des facteurs est égal à N. Stephen Cook a également démontré, au sein de cette même classe NP, l'existence d'un groupe de problèmes « NP-complets » [6], les plus complexes à résoudre [7]. Son confrère américain Richard Karp [8] a, lui, écrit en 1972 un célèbre article décrivant 21 problèmes « NP-complets ». Cet article a marqué une étape importante dans la théorie de la complexité [9] et il repose sur une conjecture phare, qui reste ouverte à ce jour, décrite comme « P est différent de NP » (P ≠ NP) [10]. Très sommairement, il s'agit de savoir si ce que l'on peut vérifier aisément, peut aussi être découvert facilement. En tant que chercheurs, notre intuition nous dit que non. Mais nous n'avons toujours pas la réponse à cette question !

Qu'en est-il des découvertes plus récentes ?

En 1978, trois chercheurs (Ronald Rivest, Adi Shamir et Leonard Adleman) [11] ont décrit l'algorithme de chiffrement asymétrique RSA [12] (d'après les initiales de ses trois inventeurs). La particularité de cet algorithme est de permettre d'envoyer des messages chiffrés grâce à une clé publique, messages que le destinataire, étant le seul détenteur de la clé secrète est capable de déchiffrer. Il n'y a pas besoin d'échanger au préalable une clé secrète entre l'émetteur et le destinataire. Cet algorithme de cryptographie asymétrique est toujours très important, notamment pour le chiffrement des données et la signature électronique lors des échanges de données confidentielles sur Internet.

Un peu plus tard, et partant du principe que l'arrivée de données en quantités massives ne permettait plus à nos machines personnelles de stocker en mémoire toutes les données susceptibles d'être traitées par un algorithme, il a fallu inventer de nouveaux modèles de calcul. On appelle cela les problèmes de flux de données. Un exemple de tel problème est celui de la surveillance du trafic de paquets sur Internet pour détecter les anomalies de comportement pouvant être signes d'une attaque du réseau.

Ces problèmes ont nécessité de concevoir une nouvelle classe d'algorithmes très rapides. Sur ce point, l'article écrit en 1985 par Philippe Flajolet et son confrère britannique G. Nigel Martin représente un jalon important. Ainsi, l'algorithme de Flajolet et Martin, précurseur des algorithmes de streaming [13], permet d'estimer le nombre d'éléments distincts dans un flux de données (par exemple une suite de nombres). L'algorithmique a aussi des conséquences majeures pour les autres sciences. Par exemple, elle a révolutionné la biologie moléculaire en permettant d'aligner rapidement des fragments d'ADN pour faire ressortir des régions similaires, élément-clé du séquençage de génomes. Enfin, on ne peut pas ne pas mentionner le développement d'algorithmes d'apprentissage automatique comme par exemple les générateurs de textes.

Avec le recul dont vous disposez aujourd'hui, dans quelle mesure diriez-vous que le regard scientifique mais aussi sociétal porté sur ce domaine a évolué ?

Les algorithmes sont désormais utilisés au quotidien dans la société, par exemple pour effectuer des recommandations ou générer du texte, et cela soulève de nouvelles questions, par exemple sur la possibilité d'identifier les biais qu'ils peuvent introduire. Ainsi, il y a quelques années, notre principal souci était de disposer d'algorithmes rapides et efficaces. Désormais, nous voulons aussi qu'ils soient transparents et équitables. Le public attend ainsi cette transparence sur les algorithmes, mais elle reste difficile à apporter. Car il ne suffit pas d'ouvrir le code d'une application pour que les utilisateurs puissent comprendre l'algorithme et se l'approprier. Je pense qu'il faudra donc définir, en partenariat avec les scientifiques, cette notion de transparence et analyser les garanties attendues par les utilisateurs.

Quelquefois, les algorithmes soulèvent même des débats sur la démocratie. Je pense à leur utilisation pour le redécoupage des circonscriptions électorales aux États-Unis, qui pose un certain nombre de risques. En effet, celle-ci implique de traduire la loi en contraintes mathématiques, puis d'effectuer des optimisations qui restent dans la légalité. Dans ce pays, les lois sur le « redistricting » ont été pensées avant les algorithmes, et donc sans savoir que les marges de liberté laissées au législateur pourraient un jour être exploitées par des outils numériques en vue d'effectuer des redécoupages susceptibles de biaiser les résultats des élections.

À vos yeux, quels sont désormais les grands enjeux propres à votre champ de recherche ?

L'usage généralisé de l'intelligence artificielle et des réseaux de neurones profonds pour l'apprentissage automatique introduit de nouveaux défis. Il peut s'agir de mieux comprendre comment les résultats dépendent des données d'entrée. Les algorithmes qui sortent actuellement utilisent énormément de données pour décrire les objets ou les concepts. Pour améliorer la compréhension de ces algorithmes, il pourrait être intéressant de les appliquer à un certain nombre de problèmes classiques que nous avons déjà étudiés en long, en large et en travers.

Par ailleurs, j'ai l'impression que notre domaine d'activité sera particulièrement concerné par la lutte contre le réchauffement climatique. Les questions théoriques n'ont pas encore été toutes formalisées. Mais je suis certaine que nous allons devoir inventer des algorithmes qui seront moins gourmands en ressources et en énergie et qui pourront aussi être utilisés pour faire évoluer notre mode de vie afin que nous émettions le moins possible de gaz à effet de serre.

Claire Mathieu
Directrice de recherche en informatique au CNRS au sein
de l'Institut de recherche en informatique fondamentale,
spécialiste des algorithmes.

Publié le : 25 juin 2024 sur )I( Interstices.
https://interstices.info/la-grande-epopee-des-algorithmes/

Cet article est sous licence Creative Commons Attribution 4.0 International. https://creativecommons.org/licenses/by/4.0/deed.fr

NOTES

[1] https://interstices.info/quest-ce-quun-algorithme/

[2] https://interstices.info/le-probleme-du-voyageur-de-commerce/

[3] https://interstices.info/famille-algorithmes-programmation/#0

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

[5] https://fr.wikipedia.org/wiki/Leonid_Levin

[6] https://interstices.info/glossaire/np-complet/

[7] https://interstices.info/idee-recue-si-un-probleme-est-np-complet-alors-ce-nest-pas-la-peine-de-sy-attaquer/

[8] https://fr.wikipedia.org/wiki/Richard_Karp

[9] https://interstices.info/la-theorie-de-la-complexite-algorithmique/