Yahoo Actualités Prix Abel 2021 : l'informatique théorique à l'honneur
Le Hongrois László Lovász partage le prix Abel 2021 avec l’Israélien Avi Wigderson. Tous deux ont fait des contributions majeures en informatique théorique, notamment dans le domaine de l’optimisation, de la complexité algorithmique et de la théorie des graphes.
C’est la seconde fois en 20 ans d’existence – il été décerné pour la première fois en 2003 – que ce prix va à des mathématiciens du discret (qui s'oppose au continu) et de l’informatique théorique – la première fois c’était en 2012, déjà avec le Hongrois Endre Szemerédi. Son compatriote László Lovász et l’Israélien Avi Wigderson, , ont eu tous deux des contributions majeures dans ce domaine assez peu reconnu en France, où l’on préfère les mathématiques « nobles », comme la géométrie algébrique ou la théorie des nombres.
"Construire des ponts"
László Lovász, né à Budapest en 1948, est une figure incontournable de la combinatoire et de l'informatique fondamentale. Multiprimé – il a déjà reçu notamment le prix Wolf et le prix Kyoto – il s’est illustré pour des travaux en combinatoire et en algorithmique, sur des travaux d’optimisation discrète et continue et sur les limites de graphes. Lovász est notamment le co-auteur de l’algorithme LLL (Lenstra, Lenstra et Lovász). Il s’agit de la généralisation à la dimension quelconque des travaux de l’Allemand Gauss qui, au XIXe siècle, met au point un algorithme qui permettant de trouver des points proches de l’origine sur un réseau en dimension 2 (le problème du plus court vecteur). Des dérivés de ces problèmes en dimension quelconque sont aujourd’hui utilisés pour des applications cryptographiques.
L’un de ses faits d’armes est la résolution d’une conjecture sur les graphes parfaits. Pour un graphe donné – un sommet relié par des arêtes –, on peut calculer le nombre de couleurs minimum nécessaires de telle sorte que 2 sommets adjacents soient toujours de couleurs différentes. C’est ce que les mathématiciens appellent le nombre chromatique. On savait que le nombre chromatique est supérieur ou égal aux nombres de sommets qui se voient deux à deux. Lorsqu’il y a égalité, le graphe est dit « parfait ». « Dans les années 1960, le Français Claude Berge avait conjecturé une condition sur les graphes pour qu’ils soient parfaits. Alors[...]
Lire la suite sur sciencesetavenir.fr
