next up previous contents
Next: Stages Up: Informatique graphique Previous: Modèles physiques pour la

Géométrie Algorithmique en grande dimension (Alain Pajor)

tex2html_wrap_inline671

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



Dominique Perrin
Thu May 2 14:25:15 METDST 1996