Ce cours abordera les problemes suivants: comment tester l'inclusion de deux corps convexes de grande dimension, comment approcher un corps par un ellipsoïde, comment calculer son volume? On montrera qu'il n'existe pas d'algorithmes polynomiaux qui permettent de resoudre ces problemes. Au coeur de ces questions, le probleme suivant: comment generer la distribution uniforme (un point au hasard) en grande dimension? On abordera les recents develeppoments utilisant des algorithmes polynomiaux randomises. Références: Grötschel, Lovasz, Schrijver, Geometric Algorithms and combinatorial optimization, Springer, Berlin Heidelberg.
Duree : 10 H