Français Anglais
Accueil Annuaire Plan du site
Accueil > News du laboratoire > Séminaire DIGITEO
Séminaire DIGITEO
Séminaire DIGITEO Séminaire DIGITEO
24 mai 2012

"Algorithmes pour l’optimisation avec données bruitées" par Claire Mathieu, Brown University & CNRS
24 mai 2012 - Supélec - Amphi F3-05 - 14h30

 

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...

 



Pour en savoir plus: http://www.digiteo.fr/code_edcplgzxsa
News
Un article de Isabelle Guyon sur la démocratisation de l'IA
19 mars 2018
Lien vers l'article paru dans le journal le monde :
http://www.lemonde.fr/acces-restreint/sciences/article/2018/04/08/a4544bd07cad09fe52980c0f82c08b34_5282548_1650684.html

Michèle Sebag a été élue membre de l'Academie des Technologies
13 avril 2018
Michèle Sebag, DR CNRS et Directrice Adjointe du LRI, a été élue membre de l'Academie des Technologies

https://www.academie-technologies.fr/members/454-michele-sebag

Lin Chen a reçu la médaille de bronze du CNRS
27 mars 2018
Lin Chen, membre de l'équipe GALAC (https://www.lri.fr/~chen/) a reçu la médaille de bronze du CNRS. Ses principaux travaux de recherche portent sur la modélisation, l'analyse théorique, et la conception des algorithmes et protocoles distribués innovants