Navigation – Plan du site
Chaires annuelles

L’algorithmique

La restauration visuelle en perspectives
Claire Mathieu
p. 11

Notes de la rédaction

Extraits de la leçon inaugurale prononcée le 16 novembre 2017.

La chaire Informatiques et sciences numériques a été créée en partenariat avec l’Institut national de recherche en sciences du numérique (Inria).

L’intégralité de la leçon inaugurale est consultable sur le site www.college-de-france.fr, à la page du professeur.

La leçon inaugurale est publiée en coédition avec Fayard, coll. « Leçons inaugurales », no 273, mars 2018.

Texte intégral

1Qu’est-ce qu’un algorithme ? Sans le savoir nous connaissons des algorithmes depuis longtemps. On apprenait autrefois à lire avec la méthode syllabique, en apprenant d’abord à reconnaître les lettres puis en combinant les lettres pour former des syllabes, les syllabes pour former des mots, en alignant des mots pour former des phrases, les phrases pour former des textes. Lorsqu’un enfant peut lire un texte à haute voix, on espère qu’il peut également le comprendre. Cette 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 suit l’étape précédente en faisant un petit effort supplémentaire. C’est une façon de résoudre le problème de l’apprentissage de la lecture, en le décomposant en problèmes plus simples. 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

2Les algorithmes interviennent dans les contextes les plus variés, par exemple pour organiser les greffes de reins par dons croisés, de façon à satisfaire le maximum de malades en attente de greffe. On modélise ce problème, dans un premier temps, par un problème de théorie des graphes, celui du couplage maximum dans les graphes, et on le résout par l’algorithme d’Edmonds. Cela peut être amélioré par une modélisation affinée posant le problème de calcul du nombre maximum de triangles dans un graphe, qui est NP-difficile (donc ne peut être résolu de façon efficace si la conjecture affirmant que P est différent de NP est vraie), mais pour lequel il existe des heuristiques basées sur la programmation linéaire en entiers et qui sont assez efficaces sur ces cas en pratique. Que faire des problèmes NP-difficiles ?

3Le problème du voyageur de commerce en est l’exemple le plus célèbre. 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 durées des trajets. Il doit planifier son itinéraire pour se rendre à toutes les adresses de la liste, mais avec un parcours aussi court que possible. La solution la plus simple serait de regarder toutes les solutions possibles, calculer la longueur de chaque solution, et choisir la meilleure. Cet algorithme n’est pas rapide. S’il y a deux fois plus de lieux à visiter, combien de solutions examiner ? C’est le nombre de façons d’ordonner les lieux. Cela augmente énormément lorsque la taille du problème double, et ce n’est donc pas un algorithme raisonnable. Même pour un problème avec 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 des temps, ou du moins jusqu’à la fin de vie du soleil ! En pratique, il n’y a pas de différence entre un algorithme qui terminera son calcul à la fin des temps, et un algorithme qui exécuterait une boucle infinie et ne s’arrêterait 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-là est toujours présent : il faut obtenir le résultat après un temps raisonnable.

4Pour contourner l’obstacle formidable de la NP-difficulté, l’une des approches 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 on accepte ainsi une marge d’erreur sur la qualité du résultat, en compensation pour ce petit sacrifice, on obtient un algorithme qui peut être beaucoup plus rapide. C’est le domaine des algorithmes d’approximation.

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

6On observe parfois des dysfonctionnements, mais 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 tangibles, et c’est pourquoi il faut espérer que la perspective algorithmique fera partie de la culture des adultes de demain.

Haut de page

Pour citer cet article

Référence électronique

Claire Mathieu, « L’algorithmique », La lettre du Collège de France [En ligne], 42-43 | 2016-2017, mis en ligne le 01 juillet 2018, consulté le 13 novembre 2018. URL : http://journals.openedition.org/lettre-cdf/3769

Haut de page

Auteur

Claire Mathieu

Chaire Informatique et sciences numériques
2017 - 2018

Haut de page

Droits d’auteur

© Collège de France

Haut de page