Prix Abel 2021 : Lovász, Widgerson, graphes et hasard

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente et bienvenue aux esprits curieux pour cette nouvelle exploration. Aujourd'hui, on se penche sur le prix Abel 2021, décerné par l'Académie norvégienne des sciences et des lettres.

Intervenant 20:12

Oui, un prix qui met à l'honneur l'informatique théorique et la théorie des graphes.

Intervenant 10:17

Bon, décortiquons tout ça, le Prix Abel a été créé en 2002 pour le bicentenaire du mathématicien Niels-Henrik Abel.

Intervenant 20:24

Abel qui a vécu de 1802 à 1829 d'ailleurs, et c'est une récompense qui couronne l'ensemble d'une carrière. C'est vraiment pensé comme un prix Nobel des mathématiques en fait.

Intervenant 10:34

C'est ça. Et pour bien comprendre l'importance de ce prix, il faut examiner les disciplines récompensées qui se trouvent pile au carrefour des mathématiques et de l'informatique.

Intervenant 20:43

Tout à fait. Et ce qui est fascinant ici, c'est le profil de Laszlo Lovász. Un brillant mathématicien hongrois. Exactement. Né en 1948, ses travaux de référence portent sur la combinatoire, les graves, l'algorithmique et bien sûr, la théorie de la complexité.

Intervenant 10:59

Alors la théorie de la complexité, on pourrait comparer ça au fait de chercher le chemin absolu le plus efficace dans un immense réseau routier, non ?

Intervenant 21:08

C'est une excellente analogie.

Intervenant 11:10

C'est très concret pour le

Intervenant 21:10

coup. Oui, ce n'est pas juste trouver un chemin, mais vraiment comprendre à quelle vitesse la difficulté de calcul explose quand le réseau s'agrandit de façon exponentielle.

Intervenant 11:19

Ah oui, je vois. Donc, si le premier lauréat cartographie ces fameux réseaux, le second étudie comment nous y naviguons en utilisant de manière un peu paradoxale la probabilité.

Intervenant 21:30

Oui, là, on parle de l'israélien Avi Widgerson.

Intervenant 11:34

Né en 1956, il a fait une grande partie de sa carrière outre-Atlantique et il a même eu le prix Nevan Lina en 1994. Et c'est là que ça devient vraiment intéressant. Pourquoi des algorithmes censés être des objets mathématiques hyper rigoureux utiliseraient-ils des procédés de décision aléatoires ?

Intervenant 21:52

Eh bien, si l'on relie cela à une perspective plus large, on touche à son domaine d'expertise qui est la dérandomisation.

Intervenant 11:59

La dérandomisation, donc le fait de retirer le hasard.

Intervenant 22:02

C'est ça. Il a expliqué comment construire des graphes expenseurs qui sont des objets purement déterministes.

Intervenant 12:08

D'accord.

Intervenant 22:09

Et le but, c'est de limiter l'intervention de ce hasard dans les algorithmes.

Intervenant 12:13

Tout en gardant la même efficacité de calcul.

Intervenant 22:15

Absolument. C'est là tout le génie de la chose.

Intervenant 12:18

Alors, qu'est-ce que tout cela signifie ? Au fond, ces travaux conjoints prouvent que des concepts mathématiques très purs façonnent vraiment le cœur de l'informatique moderne.

Intervenant 22:28

C'est indéniable et ça amène une vraie réflexion. Si les mathématiciens arrivent à créer des objets déterministes pour remplacer les décisions aléatoires, le hasard absolu est-il vraiment nécessaire en informatique ?

Intervenant 12:43

C'est la grande question.

Intervenant 22:45

Ou n'est-ce qu'une simple illusion mathématique destinée à pallier un manque temporaire de connaissances ?