De nouveaux modèles de calcul sont apparus, car les données, désormais trop massives pour tenir en mémoire en un seul lieu, sont d’accès plus difficile que dans les modèles classiques ; ou elles sont accessibles partiellement, modulo certaines incertitudes (algorithmes stochastiques). Pour les problèmes les plus difficiles, on apprend à se contenter de solutions approchées, ou de solutions qui ne marchent en temps raisonnable qu’en posant des hypothèses supplémentaires. Des méthodes de conception plus sophistiquées se sont également développées : méthodes de type Monte-Carlo, méthodes de type primal-dual de la programmation linéaire, ou hiérarchie de relaxations semi-définies. 

Biographie

Ancienne élève de l’ENS et titulaire d’une thèse en informatique de l’Université Paris-Sud, Claire Mathieu, actuellement directrice de recherche au CNRS, a travaillé comme chercheur CNRS à l’ENS-Lyon et comme professeur dans des institutions diverses : ENS (professeur attaché), Université Paris-Sud, École polytechnique, Université de Brown (USA). Elle fait de la recherche sur l’algorithmique, et en particulier sur la conception d’algorithmes pour trouver des solutions quasi optimales à des problèmes qui sont difficiles à résoudre exactement. Récemment, elle s’est intéressée à la modélisation de réseaux sociaux, à la reconstruction de graphes cachés, et aux graphes qui peuvent être dessinés dans le plan. En 2019, elle reçoit la médaille d'argent du CNRS.