Géométrie algorithmique : quatre défis très concrets

Intervenant 10:00

Bonjour à tous et bienvenue dans Chetanal. Quel bonheur de retrouver les auditeurs aujourd'hui pour le podcast du magazine Tangente. On a une énergie débordante en studio parce que notre mission du jour est absolument fascinante.

Intervenant 20:12

Bonjour Evelyne. Eh oui, on va plonger dans un domaine vraiment captivant.

Intervenant 10:16

Exactement. Pour planter le décor, prenons le ciel au-dessus de l'Europe à cet instant précis. Des milliers d'avions commerciaux filent à près de 1000 km par heure dans toutes les directions.

Intervenant 20:27

C'est un vrai balai.

Intervenant 10:28

Voilà. Et la question, c'est comment un ordinateur, dans une tour de contrôle, fait-il pour s'assurer à la milliseconde près qu'aucun de ses points métalliques ne va entrer en collision ?

Intervenant 20:38

Surtout à cette vitesse.

Intervenant 10:39

C'est ça. Et la réponse ne réside pas dans la puissance brute des processeurs. Pas du tout. Ça repose sur une ruse mathématique totalement invisible et franchement brillante. La géométrie algorithmique.

Intervenant 20:51

Tout à fait. Et c'est une mission fondamentale dont on parle aujourd'hui, car le monde physique et le monde numérique parlent en fait deux langues diamétralement opposées.

Intervenant 11:00

C'est-à-dire ?

Intervenant 21:01

Ce qui est captivant ici, c'est l'évolution de la pensée géométrique. D'un côté, on a les mathématiciens grecs de l'Antiquité. Eux, ils faisaient déjà de la géométrie algorithmique, avec une règle et un compas, sans le savoir.

Intervenant 11:12

Comme Monsieur Jourdain faisait de la prose, en fait.

Intervenant 21:14

Exactement. Ils cherchaient des suites d'étapes logiques pour résoudre des problèmes. Mais le grand basculement, le moment où cette discipline est passée d'un jeu de l'esprit à un pilier de la civilisation moderne, ça s'est produit beaucoup plus tard, dans les années 1970.

Intervenant 11:29

Les années 1970, donc c'est le moment où les ordinateurs commencent à quitter les laboratoires pour entrer dans l'industrie, c'est bien ça ?

Intervenant 21:35

C'est ça, c'est la naissance de la CAO, la conception assistée par ordinateur. Du jour au lendemain, des ingénieurs ont voulu dessiner des carrosseries de voitures, des fuselages d'avions ou même des plans de bâtiments sur des écrans.

Intervenant 11:48

Ce qui devait être un défi technique complètement fou pour l'époque.

Intervenant 21:51

Ah, un défi intellectuel colossal. Parce que notre monde réel, il est continu, il est fluide, infini. Mais le monde dans mon ordinateur, lui, il est discret. Il est composé de pixels, de zéros, de 1.

Intervenant 12:05

D'accord, je vois.

Intervenant 22:06

Donc comment traduit-on la courbe élégante et continue d'une aile d'avion en une série de coordonnées qu'un processeur peut digérer ? Il a fallu inventer un dictionnaire, en quelque sorte, entre la continuité de l'espace et la logique hachée des machines.

Intervenant 12:19

C'est un peu comme essayer de dessiner un cercle parfait en n'utilisant que les petits carrés d'une feuille de papier millimétrée.

Intervenant 22:25

C'est une très bonne image.

Intervenant 12:27

On doit faire des approximations. Mais du coup, pour cartographier tout un univers numérique, par où on commence ? S'il faut apprendre à l'ordinateur à comprendre l'espace, c'est quoi la toute première leçon ?

Intervenant 22:38

La première leçon, c'est de lui apprendre ce qu'est une distance.

Intervenant 12:41

Ah, la base de la base.

Intervenant 22:42

Voilà. Imaginons un écran rempli d'un nuage de milliers de points aléatoires. Le premier grand problème historique s'appelle la quête des plus proches voisins.

Intervenant 12:51

Les fameux nearest neighbors.

Intervenant 22:52

Exactement. La question posée à la machine est hyper simple en apparence. Parmi tous ces points, trouve les deux qui sont les plus proches l'un de l'autre et fais-le instantanément.

Intervenant 13:01

Sauf que le cerveau humain fait ça très bien. On regarde l'image, on repère un amas de points et visuellement, paf, les deux plus proches sautent aux yeux.

Intervenant 23:10

Oui, mais un ordinateur n'a pas cette vue d'ensemble. Il ne voit qu'une liste interminable de coordonnées X et Y dans un fichier texte. C'est tout le problème. Du

Intervenant 13:18

coup, comment il procède ?

Intervenant 23:20

La méthode naïve, celle de la force brute, ce serait de dire à l'ordinateur, prends le premier point de la liste et calcule la distance avec le deuxième, puis avec le troisième, puis avec le quatrième, et ainsi de suite.

Intervenant 13:32

Mon Dieu, la corvée !

Intervenant 23:34

Et une fois fini, on passe au deuxième point et on recommence avec tous les autres.

Intervenant 13:37

C'est l'équivalent de chercher une paire de chaussettes identiques dans un panier de linge gigantesque.

Intervenant 23:43

C'est exactement ça.

Intervenant 13:44

Si on prend une chaussette noire et qu'on la compare physiquement avec chacune des autres chaussettes du panier, une par une, enfin le temps perdu est astronomique, on a envie de trier le panier avant, non ?

Intervenant 23:55

Alors, le calcul du temps perdu donne vraiment le vertige. Pour un nombre n de points, cette méthode force la machine à faire n x n-1, le tout divisé par deux calculs.

Intervenant 14:09

Ah oui, la fameuse complexité au carré.

Intervenant 24:11

C'est ça, une complexité de l'ordre de n au carré. Pour dix points, ça va, ça fait 45 petits calculs. N'importe quelle machine fait ça en un battement de cils. Mais pour un million de points, on exige soudainement près de 500 milliards d'opérations.

Intervenant 14:25

500 milliards !

Intervenant 24:27

Le processeur sature complètement. Il lui faut des minutes, voire des heures.

Intervenant 14:31

Mais si je me mets à la place de l'ingénieur, je me dis pourquoi ne pas simplement trier les points ? On demande à l'ordinateur de classer tous les points par ordre croissant sur l'axe horizontal de gauche à droite. Et comme ça, on ne compare que les voisins immédiats dans la liste, non ?

Intervenant 24:45

Alors, c'est une excellente piste et c'est très intuitive. Sauf que dans un espace à deux dimensions, cette astuce s'effondre.

Intervenant 14:53

Ah bon ? Pourquoi ?

Intervenant 24:55

Imaginez que deux points aient exactement la même position sur l'axe horizontal, disons au centre de l'écran. Mais l'un est tout en haut de l'écran et l'autre est tout en bas.

Intervenant 15:04

Ah oui, je vois.

Intervenant 25:05

Ils sont voisins dans la liste triée de gauche à droite. Mais en réalité physique, ils sont extrêmement éloignés. Mince. Donc ça ne marche pas. Mais l'idée de trier est quand même le point de départ de la véritable solution. Une méthode qu'on appelle « diviser pour régner ». C'est une approche récursive.

Intervenant 15:22

Comment ça fonctionne concrètement ? On coupe l'écran en morceaux ?

Intervenant 25:26

Précisément. On trace une ligne verticale imaginaire en plein milieu de notre nuage de points et on demande alors à l'algorithme « Trouve-moi les deux points les plus proches uniquement dans la moitié gauche ».

Intervenant 15:36

D'accord.

Intervenant 25:37

Ensuite, « Trouve-moi les deux points les plus proches uniquement dans la moitié droite ».

Intervenant 15:42

Attendez, il y a un piège évident ici. Que se passe-t-il si la paire de points la plus proche de tout l'écran est en fait à cheval sur cette ligne imaginaire ? Un point juste à gauche de la frontière et l'autre juste à droite. Ça arrive ça ?

Intervenant 25:56

C'est le nœud de la guerre et c'est là que la magie mathématique opère. Une fois qu'on a trouvé la plus petite distance à gauche et la plus petite distance à droite, on garde la plus petite des deux.

Intervenant 16:06

Ok, on appelle ça une distance de référence, disons d.

Intervenant 26:09

Appelons cette distance d, oui. On sait qu'il est impossible que deux points de la même moitié soient plus proches que d. La seule exception possible, c'est qu'un point à gauche et un point à droite de la ligne centrale soient séparés par une distance inférieure à d.

Intervenant 16:23

Donc, au lieu de retester absolument tous les points, on ne regarde qu'une toute petite zone.

Intervenant 26:29

Une bande de chaque côté de la ligne centrale d'une largeur égale à D. C'est brillant ! Exactement ! Et la géométrie nous prouve une chose merveilleuse ici. Dans cette petite zone frontière, on ne trouvera qu'une poignée de points.

Intervenant 16:42

Vraiment ? Pourquoi ça ?

Intervenant 26:43

Parce que sur le côté gauche de la bande, tous les points sont déjà espacés d'au moins la distance D les uns des autres, idem à droite.