Comment contourner la difficulté de problèmes d'optimisation NP-difficiles? Pour tous les problèmes de type "reconstruction", une possibilité naturelle est de supposer que les données d'entrée sont une version bruitée d'une réalité idéale.

Deux exemples de tels problèmes de reconstruction seront étudiés : "clustering" et tournoi transitif.

• Le problème de "clustering" demande une partition des données qui soit au mieux compatible avec des informations de similarité et dissimilarité entre paires de données. Sous certaines hypothèses, la programmation semi-définie permet de reconstruire la partition sous-jacente idéale, avec grande probabilité. L'analyse utilise la dualité de programmes semi-définis et les propriétés des valeurs propres de matrices aléatoires.

• Le problème de tournoi transitif demande un ordonnancement des données qui soit au mieux compatible avec des informations comparant les paires de données. Sous certaines hypothèses, un programme dynamique simple permet de reconstruire l'ordre idéal, avec grande probabilité.

Le séminaire se terminera par une session de questions ouvertes qui se posent naturellement dans cette perspective: satisfiabilité, graphes planaires...