Version classiqueVersion mobile
OpenEdition Books

L’algorithmique

 | 
Claire Mathieu

L’algorithmique

Leçon inaugurale prononcée le jeudi 16 novembre 2017

Claire Mathieu

Texte intégral

1Un ami à qui j’avais envoyé une invitation à assister à cette leçon inaugurale, après m’avoir remerciée et avoir exprimé ses regrets de ne pouvoir y être présent, ajouta timidement, en hésitant un peu : « Mais… n’y aurait-il pas une faute d’orthographe sur ce carton ? » Après un instant d’inquiétude, je compris la raison de sa question : il s’était demandé si le « i » du mot algorithme n’aurait pas dû être un « y » ! Eh bien non. Algorithme n’a rien à voir avec rythme. Algorithme ne vient pas du grec. Un algorithme, avant d’être un procédé de calcul, a d’abord été un homme originaire d’une région qui correspond à peu près à l’Ouzbékistan actuel, Al-Khwarizmi, mathématicien d’origine iranienne qui vivait à Bagdad au ixe siècle et qui écrivait en arabe, la langue utilisée pour la science dans l’ensemble du monde islamique à cette époque-là.

2Cette question de mon ami est révélatrice de notre manque de familiarité avec les algorithmes. Pourtant, on en entend de plus en plus parler. En quelques années, ce mot a envahi les médias. Autrefois, lorsqu’on allait dans une administration et qu’on n’arrivait pas à obtenir ce que l’on souhaitait, la réponse était : « Ah, Madame, vous comprenez, c’est l’informatique ! » Maintenant on entend : « Ah, c’est l’algorithme. » L’algorithme de Facebook, de Google, l’algorithme APB, l’algorithme de notre GPS, d’Amazon ou de la SNCF, ou l’algorithme d’approvisionnement des entrepôts de supermarché : ils sont partout, ils envahissent tout, ils font disparaître nos emplois, et certains craignent le remplacement des travailleurs par les algorithmes. Algorithme, mot mystérieux, vaguement sulfureux, qui contient tout sans rien expliquer.

3En réalité, les algorithmes ne sont pas si mystérieux, et il y a des algorithmes que, sans le savoir, nous connaissons depuis longtemps. On apprenait autrefois à lire avec la méthode syllabique, en apprenant d’abord à reconnaître les lettres puis à les combiner pour former des syllabes, à combiner les syllabes pour former des mots, à aligner des mots pour former des phrases, et à assembler des phrases pour former des textes. Quand, enfin, un enfant était capable d’ânonner un texte à haute voix, on espérait que cela signifiait qu’il pouvait également le comprendre.

4Cette façon de procéder pour l’apprentissage de la lecture part de l’idée que tout enfant est capable d’apprendre ses lettres, et qu’ensuite chaque nouvelle étape de l’apprentissage suit l’étape précédente en exigeant un petit effort supplémentaire. C’est une façon constructive de prendre un problème complexe, l’apprentissage de la lecture, et de le résoudre en le décomposant en briques de base faciles à manipuler. Or, un algorithme, c’est une méthode pour résoudre un problème de façon constructive en le décomposant en briques de base faciles à manipuler. Ainsi, la méthode syllabique peut être interprétée comme une sorte d’algorithme.

L’algorithmique par l’exemple : greffes de reins

5Dans quels contextes les algorithmes interviennent-ils ? Ils n’existent pas dans le vide mais sont développés dans un cadre, précédés par la modélisation d’un problème concret et suivis par l’application au problème de départ. Illustrons cette démarche par un exemple, celui des greffes de reins (fig. 1).

Figure 1

Figure 1

Greffe de reins : donneur et malade.

Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.

6Un malade a besoin d’une greffe de rein. Il lui faudrait un donneur. Chacun de nous a deux reins. Cela en fait un de trop : nous avons du surplus. Si un membre de notre famille avait les reins malades et avait besoin d’une greffe, nous serions volontiers prêts à lui en donner un des nôtres, afin de prolonger sa vie. Malheureusement, cela ne peut se faire que si le donneur et le malade sont compatibles.

7Bien que la population ait grosso modo deux fois plus de reins que nécessaire, il y a actuellement un manque aigu de reins. En 2014 aux États-Unis, il y avait une centaine de milliers de malades en attente de greffe ! Dans le courant de l’année, environ 5 000 sont décédés en attendant, un peu plus de 15 000 ont reçu une greffe, et les autres ont continué à attendre. Comme des dizaines de milliers de malades se sont ajoutés à la liste en cours d’année, la liste s’allonge, et l’attente est loin de se résorber. Il faut mieux organiser les choses, et c’est là que les algorithmes arrivent à la rescousse. Le problème consiste donc à décider quel malade recevra une greffe de rein de quel donneur afin de sauver le maximum de vies.

8La première étape consiste à modéliser le problème. Considérons deux paires. La première comprend un malade nommé Bernard et sa mère, nommée Anne, qui est en bonne santé et possède deux reins, donc un en trop, qu’elle aimerait bien donner à Bernard, mais malheureusement Anne et Bernard ne sont pas compatibles. De même, la seconde paire comprend une malade nommée Dorothée et son mari, nommé Charles, donneur potentiel mais non compatible. Imaginons qu’Anne soit compatible avec Dorothée, et Charles compatible avec Bernard : alors il suffit d’organiser des opérations croisées pour enlever un rein à Anne et le donner à Dorothée, et en même temps enlever un rein à Charles et le donner à Bernard. Les deux malades ont reçu la greffe qu’ils attendaient !

  • 1 C. Bradley Wallis, Kannan P. Samy, Alvin E. Roth et Michael A. Rees, « Kidney paired donation », N (...)

9Comment profiter de cette possibilité pour satisfaire le maximum de malades ? On définit un graphe dont chaque sommet représente une paire (malade, donneur), et deux paires sont reliées par une arête si les compatibilités autorisent à faire des opérations croisées entre les deux paires1. Planifier des greffes de reins pour le maximum de malades, c’est trouver dans ce graphe un maximum d’arêtes disjointes. En théorie des graphes, un ensemble d’arêtes disjointes s’appelle un « couplage », et il s’agit donc de trouver un couplage de cardinal maximum. Ceci termine la modélisation.

  • 2 Jack Edmonds, « Paths, trees, and flowers », Canadian Journal of Mathematics, vol. 17, 1965, p. 44 (...)

10La deuxième étape consiste à concevoir un algorithme pour construire un couplage maximum dans un graphe. Or il se trouve que ce problème a indépendamment été étudié en théorie des graphes, bien avant que l’on pense à l’appliquer aux greffes de reins croisées. C’est Jack Edmonds qui, le premier, a conçu un algorithme efficace, il y a une cinquantaine d’années : l’algorithme des fleurs et des pétales2.

11La première idée de l’algorithme, c’est qu’au lieu d’essayer directement d’obtenir un couplage de cardinal maximum, il est plus simple de procéder pas-à-pas, en essayant à chaque pas de modifier le couplage pour qu’il comporte une arête de plus : de même que, pour lire une phrase, il suffit de savoir lire mot par mot, pour trouver une solution avec beaucoup d’arêtes, il suffit de savoir faire grossir la taille du couplage un par un.

12La deuxième idée, c’est d’explorer le graphe de proche en proche pour trouver un chemin qui relie deux sommets qui ne sont pas encore « couplés », et dont une arête sur deux est utilisée dans le couplage. On appelle une telle structure un « chemin alternant », puisqu’il emprunte alternativement une arête du couplage et une arête qui n’est pas dans le couplage. Observons que, puisque ce chemin se commence et se termine avec des sommets isolés, ni sa première ni sa dernière arête ne sont dans le couplage, et donc sa longueur est impaire. Trouver un tel chemin est l’étape la plus délicate de l’algorithme, et c’est là qu’on utilise des structures de « fleurs » et de « pétales ».

13La troisième idée, qui lui fait suite, c’est de prendre les arêtes du chemin et de changer l’alternance, en enlevant du couplage les arêtes du chemin qui y étaient et en ajoutant au couplage les arêtes du chemin qui n’y étaient pas. C’est tout simple, mais comme le chemin a une longueur impaire, le résultat est un couplage qui a été modifié le long du chemin, qui contient désormais une arête de plus, et qui permet donc à deux personnes de plus de recevoir une greffe ! Comme chaque étape est rapide, on a donc rapidement construit une solution, et on voit bien ici que l’algorithme se décompose en une suite d’opérations plus simples.

14Lorsque l’on déroule toutes les idées, les opérations de base consistent simplement à regarder le voisinage des sommets du graphe. Ceci illustre le fait que l’algorithmique est une science constructive. Il s’agit de montrer non seulement qu’il existe une solution, mais aussi de quelle façon on peut la construire, par une suite d’opérations simples.

15L’algorithme des fleurs et des pétales est-il satisfaisant ? C’est une bonne façon de résoudre le problème du couplage maximum : on peut démontrer qu’il est assez rapide et trouve effectivement le plus grand couplage possible. De telles démonstrations relèvent du domaine de l’analyse d’algorithme. Là, il ne s’agit plus d’inventer une nouvelle méthode, mais de démontrer que la méthode proposée fonctionne bien.

16Il ne reste plus alors qu’à traduire l’algorithme en un programme adapté au problème de départ, et d’en déduire une liste des greffes de reins à planifier.

17Ainsi, le cœur du domaine, c’est la conception d’un algorithme en vue d’un modèle mathématique abstrait, détaché du contexte concret de malades en attente de greffes d’organes. Il ne s’agit pas là d’une exception mais d’un cas représentatif. Pourquoi en est-il ainsi ? Parce que, en éliminant les détails, les accrétions secondaires, en faisant le vide, on peut se concentrer sur l’essentiel. Pour que ce soit fructueux, il faut de la simplicité. On contemple les choses, on cherche des exemples intéressants, c’est-à-dire qui permettent de comprendre un peu mieux les obstacles sur notre chemin. À chaque fois que l’on comprend quelque chose de nouveau, c’est comme si un coin de brouillard se levait et découvrait un peu du paysage. On voit avec plus de clarté la structure sous-jacente, dont on peut ainsi dégager les propriétés qui permettent des constructions efficaces. Cette simplicité est belle (fig. 2).

Figure 2

Figure 2

Conception et analyse d’algorithme : problèmes, modèles, techniques.

Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.

Une modélisation flexible

18Peut-on mieux faire ? Non, dira le chercheur un peu myope, puisque l’analyse de l’algorithme d’Edmonds démontre qu’il donne des greffes au maximum de malades. Mais en prenant un peu de recul sur la question, il est possible de donner une réponse différente en modifiant sa perspective : et si on changeait la modélisation ?

19Nous avons défini les paires compatibles en croisant malade et donneur associé. Et si on considérait des croisements plus complexes ? Ainsi, même si Charles n’est pas compatible avec Bernard, qu’adviendrait-il si en revanche il était compatible avec une autre malade, Florence, et si le donneur de la famille de Florence, Étienne, était compatible avec Bernard ? Alors, ne pourrait-on pas faire un échange plus complexe, à l’issue duquel les trois malades recevraient des organes des trois individus « sains de reins » ? (Remarquons que du point de vue logistique, on atteint là la limite des possibilités, car ces opérations doivent se dérouler de façon parfaitement synchronisée pour éviter que l’un des donneurs ne risque de changer d’avis entre-temps...)

20La modélisation du problème est à peine plus compliquée : les sommets du graphe sont comme auparavant des paires (donneur, malade), on dessine maintenant un arc orienté lorsque le donneur de la première paire est compatible avec le malade de la deuxième paire, et il s’agit de trouver dans ce graphe des triangles orientés, c’est-à-dire dont les trois flèches se suivent pour former un cycle, et qui soient disjoints les uns des autres. Il ne reste plus qu’à résoudre le problème de décomposition d’un graphe orienté en un nombre maximum de triangles orientés disjoints.

  • 3 Voir par exemple David J. Abraham, Avrim Blum et Tuomas Sandholm, « Clearing algorithms for barter (...)

21Malheureusement, ce problème est connu pour être NP-difficile. Cela signifie que si la célèbre conjecture PNP est vraie, il n’existe pas d’algorithme rapide pour le résoudre. On doit alors se contenter d’approximations ou autres heuristiques3.

22Pourtant, cette modélisation n’est pas inutile. Nous pouvons l’exprimer de façon mathématique. On définit une variable xt pour chaque triangle orienté dans le graphe. xt = 1 signifie que le triangle fait partie de la solution, xt = 0 signifie que le triangle ne fait pas partie de la solution. Maximiser le nombre de triangles, c’est maximiser la somme de ces variables max Σt xt. Exiger que les triangles soient disjoints, cela veut dire que si on considère tous les triangles passant par un même sommet u, la solution en sélectionne au plus un parmi eux, et donc la somme de leurs variables vaut au plus 1 : Σt :ut xt ≤ 1.

23On obtient ainsi une expression mathématique pour ce problème : maximiser une fonction linéaire des variables, avec un ensemble de conditions, une pour chaque sommet u, qui sont des inégalités linéaires.

24Reste à trouver les valeurs des variables. Ce problème est tout à fait classique : c’est de la programmation linéaire en nombres entiers. On ne connaît pas d’algorithme efficace en général, mais il existe des heuristiques et des techniques d’optimisation qui permettent de trouver des solutions lorsque le graphe n’est pas trop grand. Lorsque l’on utilise cette idée en combinaison avec l’algorithme de couplage que j’avais présenté auparavant, on arrive à augmenter le nombre de greffes de reins de façon significative.

25De plus, on peut tirer parti de donneurs altruistes, à savoir de ceux qui ne forment pas une paire avec un malade. Le cas se présente par exemple si un malade décède : le donneur associé est susceptible de souhaiter malgré tout aider un autre malade. Un tel donneur permet de ne plus synchroniser les opérations puisqu’il est prêt à donner son rein à un malade sans garantie que le donneur apparié ne change pas d’avis plus tard. Si cette confiance est trahie, le mal est moindre que dans les scénarios précédents. En poursuivant cette observation, on se rend compte qu’un donneur altruiste peut être le point de départ d’une longue cascade d’opérations, et qu’en faisant gratuitement, sans contrepartie, don de l’un de ses reins, il peut sauver non pas un, mais plusieurs, peut-être beaucoup de malades.

26Cette brève étude relativise le côté abstrait de l’algorithmique que j’avais auparavant mis en évidence. L’algorithmique ne se focalise pas uniquement sur la résolution optimisée du problème modélisé. De plus en plus, nous nous sentons libres de modifier le problème. Lorsque l’on a atteint nos limites, lorsqu’une solution semble hors de portée ou qu’elle ne satisfait pas complètement, c’est le moment de revenir au problème concret d’où vient à l’origine la question théorique étudiée, et de revoir la modélisation.

27Ainsi, il y a plus de flexibilité, et cela ouvre la voie à des algorithmes toujours plus efficaces. Un atout pour le chercheur en algorithmique, c’est de toujours garder à l’esprit la réalité concrète, le contexte sous-jacent. Cela permet de poser les bonnes questions et de les modifier de façon pertinente. La modélisation n’est pas figée une fois pour toutes, mais, comme la conception d’algorithmes, elle est toujours susceptible d’évoluer. Cette instabilité des problèmes est un aspect frappant de l’algorithmique contemporaine.

Gérer les problèmes NP-difficiles

28La notion de problème NP-difficile mentionnée ci-dessus est centrale en informatique et permet d’aborder l’un des principaux critères de qualité des algorithmes (fig. 3).

Figure 3

Figure 3

Gérer les problèmes NP-difficiles.Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.

29À l’école primaire, nous avons appris à additionner des chiffres. La méthode d’addition telle que nous l’avons apprise, qui procède de droite à gauche avec propagation des retenues, c’est un algorithme. Si on déroule cette addition sur un exemple, on voit que l’on calcule la somme de deux grands nombres par une suite de briques de bases très simples : pour pouvoir additionner deux grands nombres, il suffit de savoir additionner deux chiffres.

30Cet algorithme a une première qualité, c’est qu’il est correct : sauf erreur de calcul, le résultat est bien égal à la somme des deux nombres. Cependant, lorsque nous étions enfants, la plupart d’entre nous étions probablement inconscients des raisons pour lesquelles l’algorithme d’addition donnait bien la bonne réponse. Nous savions suivre les instructions pas à pas comme de bons petits singes qui imitent leur professeur, mais nous ne comprenions probablement pas pourquoi l’algorithme était correct. Nous savions faire le calcul de façon mécanique, mais nous ne comprenions pas le sens de ce que nous faisions. Cela avait peut-être une dimension magique : quand on applique la recette, on trouve le bon résultat. C’est ainsi, il n’y a pas à chercher à comprendre ! De même, les logiciels qui calculent un itinéraire pour un trajet en voiture ou qui font de la traduction automatique n’ont aucune compréhension de ce qu’ils font. Ils appliquent des algorithmes parfois complexes, y compris des algorithmes conçus pour vérifier des calculs, mais la notion de sens est absente. On peut dire que c’est le royaume de l’absurde.

31L’algorithme d’addition a une deuxième qualité, c’est qu’il est rapide. Une dizaine d’opérations de base pour additionner deux nombres à dix chiffres, une centaine pour additionner deux nombres à cent chiffres, ce n’est pas hors de portée, même pour des humains. Lorsque la taille des nombres double, l’algorithme fait le double de travail. C’est raisonnable (et il existe des algorithmes encore bien plus rapides tirant parti des possibilités de parallélisme.)

32Au contraire, prenons un problème NP-difficile célèbre : le problème du voyageur de commerce. Il s’agit de trouver le plus court chemin pour visiter un ensemble donné de villes. Le voyageur a une liste d’adresses où il doit faire des visites, avec un plan qui lui donne toutes les distances et les durées des trajets. Il doit planifier son itinéraire de façon à se rendre à toutes les adresses de la liste, mais en effectuant un parcours ou « tour » aussi court que possible. Ce problème est NP-difficile : on ne lui connaît pas de solution raisonnable, et si on en trouvait une, cela en donnerait aussi pour une large classe de problèmes. La solution la plus simple serait de considérer toutes les solutions possibles, de calculer la longueur du trajet obtenu dans chaque solution, et de choisir la meilleure.

33Cet algorithme n’est pas rapide. Combien de solutions faut-il examiner ? C’est le nombre de façons d’ordonner les lieux. Supposons que la taille du problème double et qu’il y ait deux fois plus de lieux à visiter : cela augmente énormément le temps d’exécution. Ce n’est pas un algorithme raisonnable. Même pour un problème comportant quelques centaines de lieux à visiter, si l’on devait exécuter cet algorithme et attendre qu’il trouve la meilleure solution, cela prendrait jusqu’à la fin de vie du Soleil ! Le voyageur pourrait faire la sieste indéfiniment s’il attendait que son itinéraire soit ainsi calculé (fig. 4).

Figure 4

Figure 4

Problème du voyageur de commerce : regarder tous les chemins possibles prend trop de temps.

Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.

34En pratique, il n’y a donc pas de différence entre un algorithme qui terminera son calcul à la fin des temps, et un algorithme qui exécute une boucle infinie et ne s’arrête jamais de calculer. Le message est clair : un bon algorithme se doit d’être rapide. Les critères de qualité des algorithmes varient selon le contexte, mais celui-ci est toujours présent : il faut obtenir le résultat après un temps raisonnable.

35Comment, dans ces conditions, le métier de voyageur de commerce peut-il exister ? C’est une bonne question : sommes-nous certains que ce métier existe ? De fait, si on utilise un moteur de recherche pour regarder ce qui concerne les voyageurs de commerce, on s’aperçoit que tous les résultats portent sur des algorithmes en informatique ! Il s’agit en réalité d’une image. Mais le problème existe bel et bien en informatique, et des solutions doivent donc être trouvées. Comment contourner l’obstacle formidable de la NP-difficulté ? Il existe plusieurs approches complémentaires.

36L’une d’entre elles concerne l’approximation. Au lieu de chercher le tour le plus court possible, on se contente de chercher un tour qui soit suffisamment court, par exemple au plus 5 % plus long que nécessaire. Si l’on accepte ainsi une marge d’erreur relative sur la qualité du résultat, en compensation de ce petit sacrifice, on obtient un algorithme qui peut être beaucoup plus rapide. C’est le domaine des algorithmes d’approximation.

37Une autre possibilité est de résoudre des cas particuliers, par exemple lorsque les données sont suffisamment « lisses ».

L’aléatoire en algorithmique

38Ces approches reviennent à exploiter diverses techniques pour concevoir les algorithmes. L’une d’entre elles est particulièrement puissante et versatile : l’aléatoire joue un grand rôle.

39Commençons par un exemple ludique : le problème des huit reines. Comment placer huit reines sur un échiquier de façon qu’elles ne se menacent pas mutuellement ? Les reines peuvent se déplacer le long des lignes, des colonnes et des deux diagonales. Bien entendu, l’échiquier n’ayant que huit lignes, il est impossible d’y placer neuf reines, mais est-il même possible d’y placer huit reines ? Il existe une solution (ci-dessous).

R
R
R
R
R
R
R
R

40La façon la plus rapide de résoudre ce problème est sans doute d’écrire un court programme. On peut par exemple envisager d’écrire un algorithme d’exploration systématique de l’espace des possibilités. On numérote les cases de 1 à 64 et on positionne les reines une à une, chaque nouvelle reine étant placée sur la première case où elle ne menace pas les reines déjà placées. Lorsqu’on est bloqué, on revient en arrière en modifiant le placement des reines précédentes, en les faisant avancer pas à pas. C’est un bon exercice de programmation !

41Avec cette méthode, on trouve effectivement une solution, au bout d’un temps assez raisonnable puisqu’il y a seulement 114 configurations de reines sur l’échiquier à considérer avant de trouver une configuration gagnante.

42Mais il existe un algorithme beaucoup plus simple : avancer au hasard. Pour ajouter une reine, on regarde les cases où l’on aurait le droit de la placer, et au lieu de la mettre sur la première case possible, on place la reine sur n’importe laquelle des cases possibles, au hasard ! Et que fait-on lorsque l’on est bloqué et que l’on se trouve dans une configuration où aucun ajout n’est possible ? On enlève toutes les reines déjà placées et on recommence tout depuis le début.

  • 4 Gilles Brassard et Paul Bratley, Algorithmics: Theory and Practice, Englewood Cliffs (N.J.), 1988.

43Cette méthode est quelque peu brutale, et néanmoins beaucoup plus simple à programmer. On pourrait penser qu’elle est inefficace. Mais de façon surprenante, elle est également plus rapide : en effet, on trouve une solution après avoir examiné, en moyenne, seulement 56 configurations de reines sur l’échiquier au lieu de 1144.

44Il y a là quelque chose de déconcertant. L’algorithme lui-même fait des lancers de pièces à pile ou face. Si vous essayez cet algorithme deux fois, vous pouvez très bien trouver deux solutions différentes, car le résultat dépend des choix aléatoires faits en cours d’exécution de l’algorithme. De plus, l’algorithme peut très bien être tantôt rapide, tantôt lent, selon les choix aléatoires. On ne peut pas prévoir exactement ce qui va se passer, ce qui a quelque chose de déconcertant pour le planificateur. Et pourtant, c’est une petite merveille de simplicité.

45Cet exemple illustre bien le défi des algorithmes qui utilisent l’aléa. Ils sont souvent très simples – donc produisant des programmes qui contiennent moins d’erreurs de programmation –, rapides, mais déconcertants, presque fantasques, imprévisibles.

46Après cet exemple introductif, revenons au problème du voyageur de commerce. Plaçons-nous dans un cadre familier : celui du plan euclidien. Les tours allant de ville en ville sont des permutations, et leurs longueurs peuvent être extrêmement variables. Où se trouvent les tours courts ?

  • 5 Voir Vijay V. Vazirani, Algorithmes d’approximation, Paris, Springer, 2006.

47Voici un algorithme conçu pour trouver un tour de longueur proche de celle du tour optimal5. On commence par enfermer les villes dans un cadre carré calculé au plus juste, puis on découpe la région ainsi définie en quatre secteurs : Nord-Est, Nord-Ouest, Sud-Ouest, Sud-Est ; ensuite on redécoupe chaque secteur en quatre sous-secteurs, et ainsi de suite. Cela définit un quadrillage hiérarchique de la région. Puis on imagine que les découpes sont des rivières, larges au début, puis de plus en plus étroites à mesure que les secteurs sont plus petits. Enfin, nous imaginons que nous construisons des ponts pour franchir les rivières, disposés à intervalles réguliers, plus fréquents sur les rivières les plus petites et moins fréquents sur les fleuves.

48Imaginons que le voyageur de commerce ne puisse franchir les rivières qu’en passant par des ponts. Il s’agit d’une contrainte forte qui donne beaucoup de structure aux tours. On peut alors rechercher le meilleur tour du voyageur de commerce passant par les ponts. Les rivières et les ponts réduisent considérablement le nombre de possibilités raisonnables et la structure hiérarchique des tours peut être exploitée pour trouver rapidement le meilleur possible. C’est là une méthode générale de l’algorithmique : ajouter des contraintes supplémentaires pour structurer la solution afin de faciliter l’algorithme de recherche.

49Mais cette approche a un défaut, c’est qu’elle ne trouve évidemment plus le tour optimal. De fait, si les villes sont mal placées par rapport au quadrillage, obligeant à faire de nombreux détours pour emprunter les ponts, il se pourrait que le tour obtenu soit nettement plus long que le meilleur tour possible.

50C’est là que l’aléatoire vient à la rescousse. Si le cadre carré de départ est non plus calculé au plus juste mais avec une marge, alors son centre peut être déplacé sans que les villes cessent d’être dans le cadre. Imaginons qu’au début le cadre soit décalé de façon à ce que son centre se trouve en un point placé au hasard dans un sous-cadre, grâce à un tirage aléatoire. Alors, en moyenne, le meilleur tour passant par les ponts aura une longueur quasiment égale à celle du meilleur tour possible ! Autrement dit, les détours nécessaires par les ponts pour franchir les rivières ont un coût négligeable ! Ceci montre bien à la fois la simplicité et la puissance de l’aléatoire, et c’est une idée utilisée dans de nombreux algorithmes d’approximation.

51En fait, dans le cas du problème du voyageur de commerce dans le plan, on peut trouver un algorithme d’approximation qui n’utilise pas l’aléatoire, mais le premier algorithme quasi optimal était basé sur l’aléa, et l’aléa a fourni l’intuition et les idées-clés.

  • 6 Voir par exemple : D. Easley et J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Hig (...)

52On a vu dans le problème des huit reines que l’aléatoire intervient en algorithmique pour concevoir des algorithmes plus simples et plus rapides. On a vu dans le problème du voyageur de commerce qu’il intervient pour trouver des solutions meilleures. On va maintenant voir qu’il peut également intervenir dans la modélisation. Il s’agit de l’algorithme PageRank utilisé par les moteurs de recherche6.

53Imaginez que vous faites une recherche d’informations sur Internet. Un algorithme dont nous ne parlerons pas ici a trouvé quelques centaines de pages qui correspondent à votre requête. Dans quel ordre doit-on vous montrer ces pages ? Quelles sont les pages qui ont le plus de « valeur », c’est-à-dire qui répondent le mieux à la requête ? Avant de répondre à ces questions, il faut d’abord comprendre ce qu’est une « bonne » page web. Le bon sens suggère que c’est probablement une page qui contient des informations correctes, pertinentes, claires, complètes, et bien organisées. Mais comment un algorithme va-t-il bien pouvoir avoir un tel discernement ? Le problème semble difficile.

54Pour le résoudre, l’idée est d’associer à chaque page une mesure de « popularité ». Les pages web contiennent des liens qui permettent de naviguer d’une page à l’autre. Lorsque nous créons une page sur la Toile, nous y associons généralement des liens vers les pages qui nous semblent pertinentes. Ainsi, nous sommes enclins à mettre un lien vers une « bonne » page web. Ainsi, on peut penser qu’une bonne page web sera davantage citée si les pages qui pointent vers elle sont elles-mêmes de « bonnes » pages. C’est l’intuition de génie de l’algorithme PageRank : au lieu de chercher à déterminer si une page est correcte, pertinente, claire, complète, et bien organisée, il suffit de faire confiance aux personnes qui ont créé le Web et de regarder tout simplement les liens pointant sur la page. Au lieu de chercher à comprendre des notions sémantiques complexes, il suffit de regarder la structure des liens entre les pages sur la Toile.

55Ainsi, on dira qu’une page est populaire si elle contient beaucoup de liens en provenance de pages qui sont elles-mêmes populaires. Pour calculer cette popularité, une méthode rapide est d’utiliser l’aléatoire. L’algorithme de calcul de popularité simule un utilisateur qui explore la Toile de la façon suivante : il part d’une page choisie au hasard, clique sur un de ses liens au hasard, puis sur un autre au hasard dans cette nouvelle page, et continue ainsi à faire une exploration au hasard, avec de temps à autre un saut vers une page prise au hasard sur la Toile. La fréquence avec laquelle cet utilisateur visite une page est proportionnelle à sa popularité.

56Enfin, pour répondre à la requête initiale de l’utilisateur, l’algorithme va lui montrer les pages sélectionnées par ordre de popularité. Ainsi, la popularité d’une page est fondée sur une définition qui correspond à un algorithme d’exploration de la Toile au hasard. L’aléatoire joue donc un rôle, d’une part dans l’intuition qui guide la modélisation, d’autre part dans la conception d’un algorithme rapide pour faire les calculs.

57L’idée de l’algorithme PageRank est d’obtenir des informations sur une page de la Toile à partir de la structure des liens entre les pages. Cela amène à un grand sujet de recherche actuel. La même idée peut s’appliquer, non pas à la toile du Web, mais à des utilisateurs d’un réseau social. « Dis-moi qui tu fréquentes, et je te dirai qui tu es. » Par exemple, imaginez que je suis propriétaire d’un appartement à louer. Un locataire se présente, dont le dossier est apparemment impeccable, mais dont le réseau social révèle qu’il a des amis mauvais payeurs : peut-être est-ce une raison de lui préférer un autre locataire... On ne fait actuellement qu’entre-apercevoir les possibilités redoutables ouvertes par ce genre d’analyse.

58Terminons cette présentation de l’idée de base de l’algorithme PageRank à ses débuts en mentionnant un élément un peu mystérieux : la popularité d’une page est indépendante de la requête. Ainsi, imaginons qu’une page parle de chameaux et de physique statistique. Elle apparaîtra dans la liste des réponses pour les utilisateurs qui recherchent des informations sur les chameaux, ainsi que dans la liste des réponses pour les utilisateurs qui recherchent des informations sur la physique statistique. Si elle est populaire, autrement dit, si c’est une « bonne » page, alors elle sera donnée en tête des réponses pour les deux sujets. L’idée est donc que si cette page est bien conçue sur le sujet des chameaux, alors elle sera également bien conçue sur le sujet de la physique statistique ! C’est une idée pour le moins hardie.

59Cependant, une page n’est pas un être humain. En fait, la plupart des pages sont centrées sur un seul sujet, ou sur quelques sujets liés entre eux, et c’est sans doute cela qui explique le succès de l’algorithme PageRank dès ses débuts. Pour tout dire, vous auriez peut-être du mal à trouver une page web qui parle à la fois de chameaux et de physique statistique. De plus, les versions actuelles des moteurs de recherche ont affiné l’algorithme initial et donnent maintenant, semble-t-il, des cotes de popularité qui dépendent du sujet traité.

60L’aléa est important pour concevoir des algorithmes simples et rapides. L’aléa peut guider la modélisation. Mais ce n’est pas tout. L’aléa aide aussi à analyser les algorithmes et à comprendre pourquoi ils fonctionnent bien dans certains cas.

61Revenons à l’exemple du voyageur de commerce dans le plan. Supposons que les villes sont représentées comme des points positionnés de façon aléatoire uniforme dans un carré de côté 1. Que peut-on dire du tour du voyageur de commerce ?

  • 7 Voir Richard M. Karp, « Probabilistic analysis of partitioning algorithms for the travelling-sales (...)

62Dans ce cas particulier, avec ces données uniformes, la solution est très simple : il suffit de subdiviser la région en petits carrés, chaque carré ne contenant que quelques points en moyenne (fig. 5). On calcule le meilleur tour du voyageur de commerce à l’intérieur de chaque petit carré, et on raccroche les morceaux par un circuit qui passe de carré en carré. Cette solution est quasi optimale7. En montrant qu’il y a une hiérarchie et qu’on peut résoudre le problème à petite échelle avant de passer à une plus grande échelle, elle a de plus servi d’intuition de départ à l’algorithme d’approximation avec ponts et rivières présenté plus haut.

Figure 5

Figure 5

Problème du voyageur de commerce par subdivision hiérarchique.

  • 8 Voir D. A. Spielman et S. H. Teng, « Smoothed analysis: an attempt to explain the behavior of algo (...)

63Au xxie siècle, l’analyse en moyenne a conduit à un raffinement moderne : l’analyse lisse. Prenez un problème et imaginez toutes les données possibles pour ce problème. Essayez votre algorithme préféré pour résoudre le problème. Si vous avez bien conçu l’algorithme, avec un peu de chance, il sera rapide sur la plupart des données. Mais si le problème est NP-difficile, on s’attend à ce qu’il y ait au moins quelques données dites « pathologiques » pour lesquelles l’algorithme aura une mauvaise performance. L’idée de l’analyse lisse, c’est de lisser les données d’entrée pour éviter les données pathologiques8.

64Imaginons par exemple qu’une donnée soit difficile si elle contient le nombre 14 – par exemple, à un moment du calcul l’algorithme soustrait 14 puis fait un calcul d’inverse. Dans la version lisse du problème, la donnée d’entrée ne sera pas exactement 14, mais 14 plus un bruit, ou une erreur de mesure, ou une incertitude : ce sera un nombre compris, disons, entre 13,5 et 14,5. Ce lissage permet alors d’éviter l’unique valeur pathologique et peut rendre l’algorithme efficace. L’analyse lisse suppose que les entrées contiennent une part d’aléatoire qui aide aux calculs en permettant d’éviter les cas pathologiques.

65Enfin, l’aléatoire permet d’étendre la famille des données faciles à gérer. Considérons un problème difficile sur presque toutes les données d’entrée. Mais imaginons qu’il y ait quelques cas particuliers qui soient faciles. Pour prendre un exemple élémentaire, il faut un certain temps pour trier n nombres (n log n comparaisons en général), mais c’est très rapide si ces nombres sont déjà triés puisqu’il suffit de vérifier que chaque nombre est plus petit que celui qui le suit. L’analyse de perturbation des données peut permettre de généraliser ce cas particulier facile. Si les données sont obtenues à partir d’un cas particulier facile en faisant de petites perturbations, il peut rester suffisamment de structure pour qu’un algorithme sache retrouver le bon résultat. Ainsi, si une liste de nombres est quasiment dans l’ordre, alors il est facile de finir de la trier. Il s’agit là de l’usage de l’aléatoire dans l’analyse de données perturbées. Cette approche suppose que les entrées soient proches d’un cas idéal mais contiennent en outre une part d’aléa, suffisamment faible pour ne pas trop perturber la solution.

66En somme, que ce soit pour la modélisation, la conception ou l’analyse, l’aléatoire est un outil précieux de l’algorithmique. Il semble que son rôle actuellement va croissant, en partie parce que les données sur lesquelles nous nous reposons de plus en plus sont incertaines, bruitées et évolutives.

La perspective algorithmique

67Ces quelques exemples donnent un aperçu de ce que peut être l’algorithmique, mais il faut éviter une interprétation réductrice.

68Donnons maintenant une définition un peu plus formelle du mot algorithme. Le dictionnaire dit : « Un algorithme est 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. » Le problème énoncé, c’est celui que nous formulons à l’issue de la phase de modélisation. Les règles opératoires, ce sont les briques de base simples, ce que nous savons déjà faire au départ. Le nombre fini d’opérations se rapporte à la notion du temps qu’il faut pour obtenir la solution.

69Sur la base des exemples présentés, on pourrait avoir l’impression que l’algorithmique consiste à prendre des problèmes issus de diverses applications, à emprunter aux mathématiciens des techniques ou outils issus de divers domaines des mathématiques, de mettre tout cela ensemble, de mélanger en faisant une petite cuisine avec les bons ingrédients, et le résultat est là (fig. 6).

Figure 6

Figure 6

La cuisine algorithmique.

Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.

70Cette interprétation n’est pas juste. Voyons pourquoi. Un même nombre peut être représenté de diverses façons, par exemple en chiffres romains ou en chiffres arabes (ou indo-arabes). La représentation avec des chiffres arabes a en particulier été utilisée par Al-Khwarizmi dans ses livres. L’un donnait des algorithmes de calcul pour des nombres écrits avec des chiffres arabes, en numération décimale, l’autre donnait des méthodes de résolution d’équations du premier ou du second degré. Une traduction latine fut faite au xiie siècle, commençant par « Dixit algorizmi ».

71Pour résoudre l’équation x2 = 40x – 4x2, vous commencez par ajouter 4x2 des deux côtés pour arriver à l’équation 5x2 = 40x. Al-Khwarizmi a expliqué cette méthode dans son livre, à ceci près qu’il n’y avait pas alors la notion de variable x ; il s’expliquait donc avec un texte dépourvu d’équations et parlait de « la chose ». Son livre sur l’arithmétique donnait les méthodes permettant d’additionner et de multiplier des nombres arbitrairement grands, méthodes que maintenant nous apprenons à l’école primaire.

72À la même époque, en Europe, on continuait à utiliser les chiffres romains, même pour faire de la comptabilité ! Mais la multiplication de deux nombres écrits en chiffres romains est extrêmement difficile. Une rumeur dit d’ailleurs que l’objectif de l’enseignement des mathématiques à l’époque était que, dans chaque monastère, il y eut au moins un moine qui fût capable de calculer la date de Pâques. Autant dire que les attentes en connaissances mathématiques étaient modestes.

73Grâce à la conquête musulmane de la péninsule Ibérique, les connaissances d’Al-Khwarizmi ont pu arriver en Europe, et Sylvestre II, mathématicien devenu pape, a voyagé à Barcelone où il a pu apprendre les règles du calcul selon Al-Khwarizmi, dont il a ensuite essayé de propager les idées.

74Malheureusement, il s’est heurté à une certaine méfiance. Les méthodes qu’il prônait étaient d’une telle efficacité qu’elles étaient jugées proprement stupéfiantes, voire magiques, donc peut-être sataniques. Victimes de leur succès, en somme. Cette réputation démoniaque a freiné l’avancée des chiffres arabes, et ce n’est qu’au xvie siècle que le système de numération décimale que nous connaissons a enfin triomphé.

75Du point de vue purement mathématique, douze, c’est un seul et même nombre, qu’il soit écrit en chiffres romains, en chiffres arabes ou de toute autre manière. Mais les deux représentations sont radicalement différentes du point de vue algorithmique. La notation décimale est adaptée aux calculs, elle permet une aisance de manipulation et une rapidité incomparables.

Figure 7

Figure 7

Adopter une perspective algorithmique.

Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.

76Adopter une perspective algorithmique (fig. 7), cela revient à regarder les problèmes en ayant toujours conscience de la dimension de calcul, et de la plus ou moins grande aisance avec laquelle ces objets peuvent être manipulés. Les représentations que l’on choisira, les modélisations que l’on définira, les objectifs que l’on se donnera, les contraintes que l’on s’imposera, tout sera conçu en restant toujours conscient des impacts de nos choix sur les algorithmes.

L’algorithme d’assignation des étudiants aux filières de l’enseignement supérieur

77Nous avons abordé la modélisation, la structure, et la rapidité des algorithmes, mais d’autres critères interviennent pour définir ce qui fait un « bon » algorithme. Voyons par exemple l’algorithme APB.

78L’algorithme d’admission post-bac (APB) est un algorithme conçu pour répartir les élèves, une fois qu’ils ont terminé leurs études secondaires, dans les divers établissements d’enseignement supérieur. Chaque année, sept à huit cent mille étudiants arrivent dans l’enseignement supérieur. Il existe environ dix à douze mille formations proposées à ces étudiants. Chaque formation a une certaine capacité. Chaque étudiant fait la liste d’une vingtaine de formations qui l’intéressent, par ordre de préférence, chaque formation détermine un ordre de priorité parmi les étudiants intéressés, puis l’algorithme APB s’exécute, et à la fin on obtient une affectation des étudiants aux formations universitaires, selon leurs capacités.

79Ce problème est similaire à un autre problème ayant une longue histoire algorithmique, celui de l’affectation des étudiants en médecine aux États-Unis pour déterminer dans quels hôpitaux ils feront leur internat.

80Autrefois, comme il y avait plus de postes que d’internes, il y avait une compétition entre hôpitaux. Ceux-ci faisaient des propositions aux étudiants, de plus en plus tôt, dès la troisième année d’études, voire lors de la deuxième année d’études.

81Puis est arrivée une période de régulation qui interdisait de recruter un interne avant sa quatrième année d’études. Les hôpitaux se sont alors mis à faire des propositions aux étudiants en leur laissant très peu de temps pour se décider, afin que l’hôpital puisse ensuite faire une offre au suivant sur la liste ; les délais sont devenus de plus en plus courts, jusqu’à être réduits à seulement quelques heures, ce qui devenait intenable.

82C’est alors que la décision a été prise de faire appel à un algorithme. Étudiants et hôpitaux devaient donner leur liste de préférences et un algorithme déterminait l’affectation. Le premier algorithme, en 1950, était très instable. À partir de 1952, le problème a été résolu en s’inspirant de l’algorithme suivant.

83Dans le problème des affectations, chaque étudiant fait la liste de toutes les formations par ordre de préférence, chaque formation fait la liste de tous les étudiants par ordre de préférence, puis un algorithme s’exécute, et à la fin, on obtient une affectation des étudiants aux formations universitaires, selon leurs capacités.

84Pour définir une bonne affectation, la notion de stabilité est importante. Prenons un exemple avec trois universités : Paris a deux places, Versailles a deux places, Lille en a une. Imaginons cinq étudiantes, Anne qui souhaiterait Paris en premier choix, Versailles en deuxième choix, et Lille en troisième choix. Voici les tableaux des préférences (ci-après).

Candidate

1er choix

2e choix

3e choix

Anne (A)

Paris

Versailles

Lille

Berthe (B)

Lille

Paris

Versailles

Claire (C)

Paris

Lille

Versailles

Douce (D)

Lille

Paris

Versailles

Emma (E)

Paris

Lille

Versailles

Université

1er

2e

3e

4e

5e

Paris (2 places)

A

D

C

B

E

Versailles (2 places)

A

C

D

B

E

Lille (1 place)

C

E

B

A

D

85Imaginez qu’on envoie Berthe et Douce à Paris, Claire et Emma à Versailles, et Anne à Lille. Cette affectation n’est pas bonne. En effet, Claire est envoyée à Versailles, mais elle préfèrerait être à Lille. L’université de Lille a recruté Anne, alors qu’elle aurait préféré avoir Claire comme étudiante : cela crée une instabilité. Claire va aller à Lille, qui va lui souhaiter la bienvenue ; quant aux autres, qu’elles se débrouillent ! Il n’est pas difficile d’imaginer pourquoi on parle du « problème de mariage stable » (fig. 8)...

Figure 8

Figure 8

Deux paires instables.

Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.

  • 9 David Gale et Lloyd S. Shapley, « College admissions and the stability of marriage », American Mat (...)

86Heureusement, il existe toujours une solution stable, c’est-à-dire sans instabilité, et elle peut être construite par l’algorithme conçu par Gale et Shapley9. La principale idée novatrice est que lorsqu’un étudiant présente sa candidature à une formation, celle-ci ne va pas répondre simplement « oui » ou « non ». Une troisième réponse est possible, « peut-être », qui laisse ouverte la possibilité d’un changement d’avis ultérieur. C’est un peu comme une sorte de fiançailles.

Algorithme

Tous les matins :

Chaque étudiant se présente à la première université

dont le nom n’a pas encore été barré de sa liste.

Tous les midis :

Chaque université regarde les possibilités qui se présentent à elle

répond « peut-être, on verra, revenez demain » à ses préférés jusqu’à capacité,

et rejette tous les autres.

Tous les soirs :

Chaque étudiant qui a été rejeté barre de sa liste

le nom de l’université qui l’a rejeté.

Lorsque plus personne n’est rejeté :

Chaque étudiant est affecté de façon définitive

à l’université qui était en train de le faire attendre.

87Avec cet algorithme, lundi matin les cinq étudiantes envoient leur candidature à leur premier choix, lundi midi, Paris choisit temporairement Anne et Claire et rejette Emma, cependant que Lille choisit temporairement Berthe et rejette Douce, et lundi soir, Douce et Emma barrent Lille et Paris de leur listes respectives. De même mardi, et ainsi de suite le reste de la semaine. Le vendredi, tout le monde a été temporairement accepté quelque part, il n’y a plus d’évolution à venir, et les affectations temporaires deviennent définitives.

88Cet algorithme est simple et assez rapide. De plus, il n’est pas nécessaire que les étudiantes et les universités communiquent les unes avec les autres tout au long de la semaine : en réalité, à partir du moment où chacune a dit ses préférences, on peut dérouler l’algorithme automatiquement, sans qu’il soit nécessaire d’attendre la fin de la semaine. Nous l’avons présenté de façon synchronisée pour simplifier, mais en fait cela importe peu, et les demandes auraient très bien pu se faire une par une, en activant les étudiants dans un ordre arbitraire ; cela n’aurait rien changé. Il s’agit donc d’un algorithme simple, rapide et assez robuste. Mais est-ce un « bon » algorithme ?

89Considérons l’affectation produite par l’algorithme. Quelles sont ses propriétés ? Elle est stable : pas de paire instable. De surcroît, elle est bonne pour les étudiantes, en ce sens que chacune d’entre elles a obtenu la meilleure université possible pour toute affectation stable ! En outre, elle encourage la sincérité : mentir sur son ordre de préférence ne permet à aucune étudiante d’améliorer son résultat. Pour toutes ces raisons, il s’agit d’un excellent algorithme.

90Le gouvernement a donc souhaité s’inspirer de l’algorithme de Gale et Shapley pour l’admission post-bac en France. Au départ, il s’agissait uniquement des classes préparatoires. Comme ce sont des formations sélectives, qui ont accès aux résultats scolaires des candidats et peuvent les utiliser pour les classer, l’algorithme des mariages stables s’y appliquait de façon naturelle.

91Puis s’y sont greffées des formations non sélectives, qui avaient plus de places que de candidats ; l’algorithme a pu être étendu à ce cadre.

92Enfin se sont ajoutées les formations non sélectives « en tension », qui ont moins de places que de candidats. Ces formations n’ont pas accès aux résultats scolaires, mais pour différencier les candidats les uns des autres, elles utilisent des critères géographiques (l’académie d’origine), ainsi que des critères dépendant des préférences des candidats.

93Malheureusement, à partir du moment où l’ordre de préférence des candidats entre en ligne de compte, toutes les belles propriétés de l’algorithme des mariages stables disparaissent. Il devient important pour les candidats d’exprimer des choix stratégiques ne reflétant pas nécessairement leurs préférences réelles : cela pénalise les candidats sincères !

94De plus, malgré cela, les formations n’ont pas assez de critères pour départager les candidats et ne peuvent produire de liste ordonnée, d’où l’usage du tirage au sort. Cette extension de l’algorithme, du point de vue mathématique, était catastrophique. Mais regardons la loi :

  • 10 Code de l’éducation, art. L. 612-3.

Le premier cycle est ouvert à tous les titulaires du baccalauréat et à ceux qui ont obtenu l’équivalence ou la dispense de ce grade [...]. Tout candidat [...] doit pouvoir, s’il le désire, être inscrit en fonction des formations existantes [...] dans un établissement [...] de l’académie où il a obtenu le baccalauréat […]. Lorsque l’effectif des candidatures excède les capacités d’accueil d’un établissement, [...] les inscriptions sont prononcées, [...] en fonction du domicile, de la situation de famille du candidat et des préférences exprimées par celui-ci10.

95C’est la loi elle-même qui dit que l’affectation peut se faire en fonction des préférences des candidats, et donc qui – indirectement – encourage la manipulation !

96Ainsi, la loi a défini les contraintes. Du point de vue algorithmique, on peut dire qu’il y a eu une erreur de conception. Pour éviter ce genre d’impasse, la législation devrait peut-être être définie en concertation avec les algorithmiciens.

Redécoupage électoral

97Comme dernier exemple, voyons le prochain défi pour lequel, sans apport de l’algorithmique, nous risquons d’aller dans l’impasse : le problème du découpage électoral. En France, il est question de réduire fortement le nombre de députés. Cela nécessitera de faire un redécoupage électoral. Aux États-Unis, il va y avoir un recensement en 2020, suivi, comme après chaque recensement, d’une mise à jour du découpage électoral. Le moment est donc critique. Les algorithmes peuvent-ils aider ?

98Actuellement certains districts aux États-Unis ont des formes très curieuses. On parle de gerrymandering lorsque le découpage en districts a été choisi de façon à favoriser indûment l’un des partis politiques. En théorie, il est possible à un parti qui a la minorité des voix de remporter tous les sièges sauf un. Imaginons que les partis soient identifiés par leurs couleurs, rose ou vert. Si le parti rose a 49 % des voix et le parti vert 51 % des voix, il suffit de créer un district contenant 2 % des électeurs, tous du parti vert, et ne contenant aucun électeur du parti rose ; après avoir ainsi écarté 2 % des électeurs, parmi les districts restants les électeurs roses sont en légère majorité, et il n’y a plus qu’à les répartir uniformément sur l’ensemble de ces districts, de façon que dans chaque district les roses soient en légère majorité. Le parti rose remportera alors tous les sièges sauf un.

99Cela peut-il survenir en pratique ? Considérons la Caroline du Nord après le redécoupage électoral de 2012 aux États-Unis : les démocrates, qui ont remporté 50,5 % des voix sur l’ensemble de l’État, se sont retrouvés avec seulement 4 des 13 représentants ! Il y a de quoi se poser des questions. Un découpage électoral menant à un tel résultat est-il légal ?

100Le principe de base du découpage électoral est que les représentants doivent représenter la volonté du peuple. Aux États-Unis, ce principe se traduit par quatre règles qui doivent être respectées par le découpage électoral mis à jour après chaque recensement.

101Le redécoupage électoral à venir suggère de nombreuses questions de recherche en algorithmique.

102Par exemple : puis-je concevoir un algorithme de découpage électoral qui exploite les ambiguïtés de la législation de façon à favoriser mon parti préféré tout en restant dans la légalité ? Il ne serait pas surprenant qu’il y ait des personnes qui travaillent là-dessus activement aux États-Unis depuis déjà quelques années.

103De façon complémentaire, on peut aussi se poser des questions sur les règles, par exemple : puis-je proposer une définition de la « compacité » d’un district, qui soit simple, intuitive, convaincante pour les législateurs, et qui permette d’éviter les découpages abusifs ? Un consortium de chercheurs aux États-Unis réfléchit actuellement à ce problème.

104On ne peut pas rester indifférent : quand on fait de l’algorithmique, il faut choisir son camp.

Conclusion

105Les algorithmes d’apprentissage profond n’ont pas été abordés. Il s’agit là d’une famille d’algorithmes qui sont récemment devenus très efficaces, grâce à l’accroissement du nombre de données disponibles et de la puissance de calcul des ordinateurs.

106Dans l’une des versions, il s’agit d’apprendre à partir d’exemples. Ainsi, pour distinguer par exemple une photo représentant un chien d’une photo représentant un chat, on calcule d’abord une fonction qui sépare au mieux les photos de chiens des photos de chats parmi les données disponibles. À la base, il peut simplement s’agir d’une fonction linéaire suivie d’une fonction de seuil, mais que l’on enrichit en répétant de ces deux opérations une quinzaine de fois pour obtenir une fonction plus complexe. Trouver la meilleure fonction signifie déterminer les meilleurs coefficients et le meilleur seuil. Il n’y a plus ensuite qu’à appliquer cette fonction à une nouvelle photo pour décider si elle représente un chat ou un chien, et on espère que le résultat sera correct.

107Si, au lieu de distinguer les chiens des chats, on souhaite traduire une phrase de français en anglais, l’algorithme sera essentiellement le même, à partir d’un corpus de phrases déjà traduites.

108Cet algorithme est très différent de ceux dont j’ai parlé aujourd’hui. Pour les problèmes dont j’ai discuté, la phase de modélisation est une étape importante, au cours de laquelle on doit décider des paramètres essentiels du problème, de notre objectif, et de la façon de simplifier sans perdre la structure la plus importante, puis on creuse cette structure pour découvrir ses propriétés mathématiques. En apprentissage profond, la modélisation est remplacée par le calcul des bons coefficients, calcul qui se fait automatiquement à partir d’exemples.

109La différence d’approche entre les algorithmes que j’ai présentés et l’apprentissage profond est un peu analogue à la différence entre la méthode syllabique et la méthode globale d’apprentissage de la lecture, l’apprentissage profond s’apparentant à la méthode globale, qui donne à mémoriser aux enfants un certain nombre de mots. À partir d’un certain nombre d’exemples de mots, les enfants sauront d’eux-mêmes repérer les combinaisons de lettres communes à certains mots et les sons qui leur sont associés, et en déduire la prononciation de mots nouveaux.

110Quant aux problèmes auxquels cette approche est adaptée, les résultats sont parfois spectaculaires. Mais en ce qui concerne la compréhension des raisons profondes de ces succès, la recherche en est encore à ses débuts.

111Les algorithmes ont un impact majeur sur la société. Les algorithmes de graphes aident les médecins à organiser les greffes de reins, quoique se posent des questions d’efficacité. L’algorithme APB a pu aider les étudiants à trouver des formations universitaires, quoique se posent des questions d’équité et de sincérité. Les algorithmes pourraient avoir un impact sur le découpage électoral ces prochaines années, quoique se posent alors des questions de représentativité.

112Bien que l’on observe parfois des dysfonctionnements, les algorithmes n’en sont pas directement responsables. Ils ne font que résoudre le problème qu’on leur donne, et ce problème n’a pas toujours été posé dans une perspective algorithmique. Les conséquences pour les individus peuvent être dramatiques. C’est pourquoi il faut espérer que la perspective algorithmique fera partie de la culture des adultes de demain.

Notes

1 C. Bradley Wallis, Kannan P. Samy, Alvin E. Roth et Michael A. Rees, « Kidney paired donation », Nephrology Dialysis Transplantation, vol. 26, no 7, 2011, p. 2091-2099.

2 Jack Edmonds, « Paths, trees, and flowers », Canadian Journal of Mathematics, vol. 17, 1965, p. 449-467.

3 Voir par exemple David J. Abraham, Avrim Blum et Tuomas Sandholm, « Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges », Proceedings of the 8th ACM conference on electronic commerce, ACM, 2007, p. 295-304.

4 Gilles Brassard et Paul Bratley, Algorithmics: Theory and Practice, Englewood Cliffs (N.J.), 1988.

5 Voir Vijay V. Vazirani, Algorithmes d’approximation, Paris, Springer, 2006.

6 Voir par exemple : D. Easley et J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge, Cambridge University Press, 2010.

7 Voir Richard M. Karp, « Probabilistic analysis of partitioning algorithms for the travelling-salesman problem in the plane », Mathematics of Operations Research, vol. 2, no 3, 1977, p. 209-224.

8 Voir D. A. Spielman et S. H. Teng, « Smoothed analysis: an attempt to explain the behavior of algorithms in practice », Communications of the ACM, vol. 52, no 10, 2009, p. 76-84.

9 David Gale et Lloyd S. Shapley, « College admissions and the stability of marriage », American Mathematical Monthly, vol. 69, no 1, 1962, p. 9-14. Voir aussi : Anna Karlin et Yuval Peres, Game Theory Alive, Providence, Rhode Island, American Mathematical Society, 2017.

10 Code de l’éducation, art. L. 612-3.

Table des illustrations

Titre Figure 1
Légende Greffe de reins : donneur et malade.
Crédits Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-1.png
Fichier image/png, 62k
Titre Figure 2
Légende Conception et analyse d’algorithme : problèmes, modèles, techniques.
Crédits Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-2.png
Fichier image/png, 263k
URL http://books.openedition.org/cdf/docannexe/image/5618/img-3.png
Fichier image/png, 13k
Titre Figure 3
Légende Gérer les problèmes NP-difficiles.Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-4.png
Fichier image/png, 66k
Titre Figure 4
Légende Problème du voyageur de commerce : regarder tous les chemins possibles prend trop de temps.
Crédits Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-5.png
Fichier image/png, 68k
Titre Figure 5
Légende Problème du voyageur de commerce par subdivision hiérarchique.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-6.png
Fichier image/png, 18k
Titre Figure 6
Légende La cuisine algorithmique.
Crédits Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-7.png
Fichier image/png, 162k
Titre Figure 7
Légende Adopter une perspective algorithmique.
Crédits Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-8.png
Fichier image/png, 86k
Titre Figure 8
Légende Deux paires instables.
Crédits Dessin reproduit avec l’aimable autorisation d’Itai Benjamini, 2018.
URL http://books.openedition.org/cdf/docannexe/image/5618/img-9.png
Fichier image/png, 493k

Auteur

Professeure invitée sur la chaire annuelle d’Informatique et sciences numériques (2017-2018)

© Collège de France, 2018

Conditions d’utilisation : http://www.openedition.org/6540