Qu’est-ce qu’un algorithme ?

Le mot « algorithme » est utilisé pour désigner le fonctionnement opaque des moteurs de recherche et des réseaux sociaux. Mais qu’est ce que c’est?

Partager sur:
Sauvegarder cet article
Aimer cet article 0
facebook By: Book Catalog - CC BY 2.0

La liberté d’expression n’est pas gratuite!

Mais déductible à 66% des impôts

N’oubliez pas de faire un don !

Faire un don

Qu’est-ce qu’un algorithme ?

Publié le 13 décembre 2021
- A +

Par Jean Cardinal.
Un article de The Conversation

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 avons-nous sur leur comportement ? Quels sont leurs impacts sociétaux ?

Au IXe siècle, en Perse

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 

 

 

 

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

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

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 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 devons-nous attendre pour avoir une réponse ? De quelle quantité de mémoire devons-nous 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.

L’algorithme de Gale-Shapley, utilisé par la plate-forme Parcoursup 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.

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 !The Conversation

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

Cet article est republié à partir de The Conversation sous licence Creative Commons. Lire l’article original.

The Conversation

Voir les commentaires (12)

Laisser un commentaire

Créer un compte Tous les commentaires (12)
  • Je me demande toujours d’où vient le ‘h’ de algorithme. Une petite préférence d’origine grecque plutôt qu’arabe?

  • bonjour,
    excellent article, toutefois un peu abstrait et théorique (pour les non connaisseurs), mais pour les curieux, il existe un truc qui s’appelle « scratch » qui permet aux enfants en particulier, de s’initier à la programmation (il existe une version en ligne) et pour les adultes de « percer » les secrets de certains programmeurs. On y trouve des méthodes de résolution (algorithme), parfois originales et astucieuses et même géniales dans les réalisations. A voir, mais ça prend du temps.

  • Comme dit dans l’article, un algoritme est une recette de cuisine.

    Les recettes des grands cuisiniers étoilés sont sans aucun doute tout aussi complexes. Sinon n’importe quel bistrot pourrait servir les mêmes plats.

    Mais on ne se pose pas des question métaphysique d’efficacité, de qualité objective, d’équité ou de transparence quand on va manger dans un « 3 étoiles » – à part par snobisme.

    La différence avec « Parcoursup » est qu’on est encore libre de manger où l’on veut. Pourvu que cela dure.

  • C’est un article confus, il ne définit pas un concept d’algorithme clair. Il met dans « l’idée » (pas concept) d’algorithme toutes sortes des fonctions même des dispositifs physiques de conversion analogue-numérique. L’algorithme étant tout, il ne correspond plus à rien.

    • Un algorithme prend une entrée retourne une sortie. Pour toute entrée, il doit terminer en temps fini. Il est correct s’il répond à la spécification demandée pour toutes les entrées.
      Attention, il n’existe pas d’algorithme pour vérifier qu’un programme termine toujours, encore moins qu’il soit correct…

    • « L’algorithme étant tout, il ne correspond plus à rien. »

      C’est la « prose » de Mr Jourdain. (Et les exponentielles de Véran).

  • Pour ce qui est de l’interaction entre algorithmique et prétendue « intelligence artificielle », j’ai l’impression que le problème est pris à l’envers par manque de recul.
    On cherche simplement à imiter en bottom-up les deux systèmes naturels qui exhibent une intelligence réelle: réseaux de neurones et sélection naturelle. En bidouillant bien on arrive à des résultats objectivement convenables mais on n’a pas compris pourquoi ça marche et encore moins comment l’améliorer. Ce qui est amusant est que si on prend le problème en top-down sans chercher à singer quoi que ce soit on s’aperçoit que les approches mathématiquement efficaces sont du même ordre:
    Pour la reconnaissance des formes, l’apprentissage par interpolation est le plus rapide et précis quand l’information se propage à travers un réseau suffisamment plastique (adaptation par renforcement nodal).
    Pour l’optimisation, l’approche dite par recuit simulé ressemble beaucoup au processus mutation-sélection à la Darwin (algorithmes génétiques).

  • Algorithme vient de Al kwarismi, c’est a dire que le matheux inventeur du concept vient du Koresme, province de l’actuel Ouzbékistan. Sauf erreur, le Koresme ne fait pas partie de la Perse

  • Je vais vous citer un algorithme simple , c’est le suivant :
    Tout nombre est divisible par neuf (9) si la somme des chiffres qui le composent est divisible par neuf. C’est ça un algorithme, c’est une règle en simplifié

  • Les commentaires sont fermés.

La liberté d’expression n’est pas gratuite!

Mais déductible à 66% des impôts

N’oubliez pas de faire un don !

Faire un don

Jeudi 5 décembre 2023. L’ange Gabriel (Attal) descend sur la France, porteur d’une bonne et d’une mauvaise nouvelle.

Commençons par la mauvaise : les conclusions de la dernière étude PISA pointent les résultats catastrophiques des petits Français, en particulier en mathématiques. Une « baisse historique » des performances, peut-on lire çà et là. Rien de surprenant pourtant : l’enseignement public est en piteux état depuis des décennies. Il ne se relèvera pas spontanément de cette longue maladie.

Heureusement – et voilà la bonne ... Poursuivre la lecture

La découverte d’une nouvelle maladie, le syndrome VEXAS, au moyen des technologies de la génomique, montre la puissance de celle-ci et les progrès considérables qu’elle permettra en biologie et en médecine, dans un contexte de mondialisation croissante. Moins que jamais, il ne faut céder aux sirènes de l’irrationalisme, car la méthode scientifique issue des Lumières, appliquée à la médecine, soulage et guérit dans des proportions inconnues jusqu’alors.

Le syndrome VEXAS est une maladie récemment identifiée grâce aux progrès de la génom... Poursuivre la lecture

Au début, il n’y a pas si longtemps au regard de l’histoire, l’astronome ne disposait que de l’intensité de la lumière et de ses propres yeux pour tenter de comprendre les astres qu’il contemplait la nuit.

Après une série de progrès dans la réflexion scientifique et de progrès technologiques, les spectroscopes, ces instruments dont nous disposons aujourd’hui pour décomposer la lumière, sont devenus extraordinairement raffinés. Grâce à eux on peut, non seulement analyser la lumière des étoiles proches mais aussi les atmosphères d’exopla... Poursuivre la lecture

Voir plus d'articles