Le mot “algorithme” est devenu de nos jours omniprésent dans la presse, les médias… Il parvient même à s’inviter dans des sujets d’actualité politique. Alors, savez-vous ce qu’est un algorithme ?

C’est un terme qui revient de plus en plus souvent dans nos quotidiens sur divers sujets autour du web : on parle du fameux algorithme de Youtube qui a le pouvoir de vie ou de mort (numérique) sur un créateur de contenu ou du scandale de Cambridge Analytica qui a permis de jouer avec les algorithmes de suggestion de contenu sur Facebook pour influencer l’opinion publique américaine lors des élections de 2016. Deux exemples d’algorithmes qui montrent leur impact sur le monde et les questions morales sous-jacentes.

Prenons un peu de temps pour mettre la chose en lumière et comprendre de quoi il retourne vraiment…

Définition théorique

Commençons par le début : qu’est-ce qu’un algorithme ? Il est vrai que c’est le titre de cet article, mais c’est important de partir d’une définition claire, car après tout on ne va parler que de ça tout du long de cet article, donc autant partir sur les mêmes bases.

D’après le dictionnaire, il s’agit :

(…) d’un ensemble de règles opératoires dont l’application permet de résoudre un problème énoncé au moyen d’un nombre fini d’opérations.

Voilà. Simple, limpide, la clarté incarnée, non ? Fin.

Dictionnaire mis à part, qu’est-ce que c’est concrètement ?

En fait, l’algorithme a plein de visages possibles, puisqu’il ne s’arrête pas vraiment à sa stricte définition : le sens académique du terme ne laisse pas vraiment entrevoir sa place dans l’informatique aujourd’hui, à savoir qu’un algorithme peut servir à déterminer votre trajet pour partir en vacances, vous suggérer un film à regarder ce soir en fonction de vos goûts ou même piloter l’éclairage de votre installation domotique.

En bref, à plein de trucs, partout, tout le temps. Mais comment ce fabuleux terme se retrouve partout dans nos vies ? Par quel super-pouvoir mystérieux ce mot se retrouve dans des sujets d’actualité ?

On peut retrouver ces algorithmes dans tellement d’endroits aujourd’hui, fréquemment juxtaposés à des sujets connotés high-tech qu’on en oublierait presque qu’ils existaient avant l’avènement de l’informatique : on peut trouver des exemples d’algorithmes mathématiques jusque dans l’Antiquité.

L’algorithme, c’est juste un nom un peu technique pour désigner l’énoncé d’un ensemble de règles et d’opérations pour effectuer une tâche. Pensez-y à la prochaine fois où vous jouerez à un jeu de cartes : le simple fait de trier et classer les cartes de votre main selon vos habitudes, c’est appliquer un algorithme de tri !

Il est tout à fait possible de coucher sur papier un algorithme. C’est le principe d’une recette de cuisine, par exemple : on suit une liste d’instructions et on est censé avoir un beau gâteau à la fin (du moins… normalement). Mais cela donne des gâteaux fabriqués artisanalement. La grande révolution que l’informatique a apporté, ce sont les outils et la possibilité de “matérialiser” ces algorithmes : par le biais de langages informatiques pour formuler les idées, de processeurs puissants jouant un nombre de fois impressionnant les instructions de l’algorithme et de disques durs ayant des capacités de stockage monstrueuses pour mémoriser les résultats… Nous ne sommes plus dans l’échelle de la confection de gâteaux dans sa cuisine mais plutôt du niveau d’une usine agroalimentaire.

De plus, toute personne ayant déjà suivi une recette de cuisine sait qu’il y a des approximations : sincèrement, qui mesure précisément “une pincée de sel” ? Moi, pas. Et ces approximations et la place offerte pour l’interprétation personnelle, voire quelque marge de tolérance pour y introduire son “ingrédient secret”… C’est ce qui rend chaque gâteau unique : les approximations et la cuisson ratée. Ça peut être le but recherché. Mais il est des domaines où avoir une consistance dans la répétition a un intérêt et c’est là que l’informatique va marquer des points : cela permet une formulation rigoureuse et une application qui l’est tout autant.

Par contre, tout l’art de l’algorithmie en programmation, c’est plutôt de réussir à reformuler cette logique humaine un peu vague –voir nébuleuse– en une suite d’instructions logiques simples et parfaitement intelligible par une machine qui, dotée d’une précision mécanique inhumaine, va jouer ces instructions sans faillir.

Un peu de pratique

Prenons un exemple dans la vie quotidienne de tout propriétaire de smartphone ou de GPS : une application proposant un itinéraire d’un point A à un point B. Il s’agit d’un des cas d’école les plus connus dans le monde de l’algorithmie, et on appelle cela le problème de plus court chemin. L’objectif est simple : relier deux points de la manière la plus efficiente possible.

Un algorithme très connu a été formulé par un informaticien en 1959 : l’algorithme de Dijkstra (du nom de son inventeur, Edsger Dijkstra). Son but est de parcourir les chemins possibles entre les deux points et d’en retenir le tracé le plus court.

Le principe de fonctionnement est “simple” puisqu’il s’agit d’une boucle décomposée en deux temps. On part du principe qu’on commence au point de départ :

  1. on évalue toutes les options possibles
  2. on se “déplace” vers l’option la moins couteuse, quitte à revenir X points en arrière, car un embranchement a un cumul plus intéressant

Tentons d’appliquer cet algorithme à une carte composée de lieux reliés par des routes afin de trouver un itinéraire entre les points A et H.

La carte

La solution ?

  1. on va d’abord aller de A vers C (12, le moins coûteux)
  2. déplacement vers D (12 + 25 = 37)
  3. déplacement vers G (12 + 25 + 35 = 72)
  4. déplacement vers H possible (12 + 25 + 35 + 30 = 102) mais il reste des routes plus courtes à explorer
  5. on revient au point C, on tente les autres routes, mais le cumul A->C->F est plus coûteux (12 + 86 = 98) que A->E (90). Même chose pour A->C->B (12 + 90 = 102)
  6. on recule au point A et on tente la route vers E (90). La route vers B valant 121 est automatiquement ignorée, car plus couteuse que la solution déjà trouvée, valant 102
  7. le point H accessible depuis le point E (cumul de 90 + 7 = 97) et aucune route plus courte n’est à explorer => FIN

L’algorithme s’arrête ici et conseille donc de faire le trajet A->E->H. L’avantage de ce parcours en “étoile” (ou latéral) permet d’être sûr d’avoir le trajet le plus court MAIS on a vu qu’on s’est orienté dès le départ vers une route en passant par les points D et G qui ne s’est pas révélée être la plus courte. C’est autant d’opérations “perdues” en puissance de calcul du processeur, de mémoire vive allouée pour rien, etc.

Et les perfs, dans tout ça ?

Aussi, introduisons un challenger : l’algorithme A* ! Ce dernier, publié en 1968, introduit une nouvelle notion : la pondération qui permet de mettre de côté les routes les moins intéressantes en se fondant sur des critères complètement subjectifs et arbitraires. Ici, nous savons dans quelle direction se trouve la destination : à l’est du point A. On décide donc d’autorité qu’un point allant dans la bonne direction de la destination va bénéficier d’une pondération de -80. On lance l’algorithme et… on avise.

Reprenons notre carte !

En partant du point A :

  1. on va d’abord donc regarder le point E qui est le plus à l’est de A (90 - 80 = 10)
  2. le point H est accessible depuis E (90 - 80 + 7 = 17) mais nous avons une route plus courte découverte auparavant, on retourne sur A
  3. Tous les points accessibles depuis C ayant un cumul supérieur à 17 (37 pour le moins coûteux), on abandonne cette route qui était la seule plus courte que la solution trouvée => FIN

On atteint donc notre destination : l’algorithme s’arrête là, mission réussie ! L’approximation ne nous offre pas la certitude du trajet le plus optimum, car une route passant par ce point C aurait pu être plus courte (l’algorithme n’en sait rien, il n’est pas allé jusqu’au bout de l’exploration). Cependant, elle nous apporte malgré tout une solution utilisable rapidement et avec une grande économie de moyens : on a divisé par deux le nombre d’opérations à réaliser pour trouver un chemin !

Cette pondération arbitraire des routes porte un autre nom : l’heuristique. C’est aussi un élément courant et important lorsqu’on parle d’algorithme, puisqu’il s’agit d’un outil très pratique pour “élaguer” les parcours d’arbre de possibilités tout en garantissant un intérêt minimum du résultat…

Je me souviens que mon prof nous l’avait défini en ces termes :

L’heuristique, c’est l’art de la pifométrie appliquée

En pratique, lorsqu’un algorithme cherche à parcourir des options, il peut être intéressant de “noter” ces options, afin de pouvoir les trier et ainsi les prioriser : on appelle cela la pondération. Dans le cas d’un GPS, quel intérêt d’évaluer les chemins qui semblent être plus long ? Peut-être que ces derniers mènent à des solutions plus efficaces, mais que le simple kilométrage peut rendre inintéressantes ! L’exemple que je viens de montrer est volontairement un peu simpliste, car on peut rajouter énormément de facteurs. Dans notre exemple, imaginons que nous rajoutions la vitesse de déplacement et le trafic aux distances dans notre heuristique : vaut-il mieux faire les 12kms de B->C dans un bouchon à 5 km/h, ou les 211kms à 130 km/h en faisant B->A->C ? Allons plus loin : l’heuristique peut être rendue paramétrable en rajoutant des options : on peut souhaiter esquiver les routes à péage, choisir de privilégier les trajets rapides (vitesse) ou courts (kilométrage), etc. Je pense que vous avez saisi le principe.

On peut aussi retrouver cette notion dans la théorie des jeux : dans n’importe quel jeu à somme nulle, c’est-à-dire des jeux basés sur l’opposition entre deux agents (les échecs ou le jeu de go sont d’excellents exemples), on peut évaluer le ratio risque/récompense de chaque coup possible à partir d’une situation donnée et orienter les choix de coups en fonction de ce score. Dans un jeu vidéo, l’entité régulièrement nommée “ordinateur” ou “IA” (qui est un algo avec une heuristique très élaborée) va évaluer l’ensemble des coups en alternant le “sens” de la pondération : trouver le coup le plus favorable à la machine, puis le coup plus plus favorable à son opposant, etc. Elle peut aussi évaluer “l’intelligence” de son adversaire humain en évaluant l’écart entre le meilleur coup possible et le coup choisit par son opposant. Cette note sera injectée dans le calcul de l’heuristique lors de la détermination du coup de l’opposant, faisant partie des facteurs à prendre en compte pour “prédire” quel coup le joueur humain va retenir. D’ailleurs, c’est en faisant jouer de nombreuses parties et en permettant à l’algorithme de stocker diverses données pour les parties futures, telles que l’évaluation du joueur, que l’on obtient une IA qui va évoluer : la méthode de calcul gagne en complexité mais aussi en précision, elle lui permet de “connaitre” son adversaire et l’heuristique pourra ainsi donner de meilleurs résultats, s’adaptant au comportement de l’opposant humain. Enfin, les jeux permettant de régler la difficulté de l’IA permettent simplement d’altérer la justesse de l’heuristique : une IA “simple” va retirer des critères de calcul, limiter l’horizon des coups possibles, l’historique des parties jouées etc, tandis qu’une IA “difficile” pourra se voir dotée d’une mémoire eidétique et d’une grande précision dans son calcul des coups.

Mais du coup, comment choisir mes critères ?

En théorie, n’importe quel critère peut être utilisé pour orienter un algorithme, que cela soit pour des raisons d’efficacité ou d’optimisation. En pratique, là est la difficulté : quand on parle de route, cela peut nous échapper de prime abord, mais les technologies de l’information brassant toute sorte de données, les routes et les villes peuvent faire place à des humains. Et là, l’éthique s’en mêle ! C’est justement sur ce choix de critères que s’exprime la moralité d’un développement informatique. Un exemple récent pourrait être le scandale Cambridge Analytica où d’énormes quantités de données personnelles, récoltées par le biais de l’usage de la plateforme Facebook, ont permis de concevoir des méthodes de calcul très précises pour optimiser l’exposition de contenus aux publics ciblés. On pourrait aussi citer le robot Tay de Microsoft qui, exposé à du contenu non filtré, a vu ses méthodes de calcul internes totalement biaisées: c’est un cas typique des dérives des algorithmes d’apprentissage. Amazon l’a aussi appris à ses dépens lorsque son logiciel de recrutement interne s’est révélé totalement biaisé par ses données d’apprentissage, reproduisant les mêmes disparitées homme/femme que l’historique des embauches de l’entreprise…

C’est plus clair ?

À partir de là, je pense que les choses commencent à devenir claires : l’algorithme, ce n’est jamais que l’addition des opérations qui, mises bout à bout et “orientée” par l’heuristique, permet d’automatiser certaines choses comme des prises de décision bas niveau. Je n’ai jamais vu le fameux algorithme de Youtube, mais je suis certain qu’il y a dedans une part d’heuristique qui tente d’évaluer la valeur d’une vidéo parmi un panel donné en la pondérant via certains paramètres (nombre de vues, like, dislike, commentaires, historique de visionnage etc) afin de déterminer la “route” de vidéos qui sera la plus rentable tout en conservant l’intérêt du spectateur.

Un petit nœud au cerveau pour la route ?

Depuis une quinzaine d’années, les ordinateurs personnels sont dotés de processeurs multicœurs. Sans entrer dans les détails, il s’agit d’une solution technique pour –entre autres– permettre à un ordinateur d’effectuer efficacement plusieurs tâches “en même temps”. Et si je vous disais que pour faire tourner sur le même processeur plusieurs programmes qui renferment des algorithmes… On utilise un algorithme ?