Ce projet peut être réalisé par un groupe de 2 à 4 étudiants. Contact : francois.clement@lip6.fr
La discrépance est une mesure de répartition des points dans l'espace [1]. Elle est caractérisée par une valeur entre 0 et 1. Pour un ensemble de points fixés dans [0,1), plus la discrépance est faible plus les points sont bien répartis et approximent la distribution uniforme. Malgré près d'un siècle d'efforts sur le sujet, les mathématiciens n'ont pas encore déterminé l'ordre de grandeur optimal pour la discrépance de n points en dimension d : entre O(log^((d-1)/2)(n)/n) et O(log^(d-1)(n)/n). On dispose de nombreuses constructions ayant une discrépance évoluant en O(log^(d-1)(n)/n) lorsque n augmente, mais on ne sait pas s'il est possible de faire mieux, même pour des ensembles où n est petit (100 points environ). De nombreuses questions comme: "Est-il possible d'avoir un ensemble de 7*d points ayant une discrépance de 0.25 en dimension d?" subsistent, et les résultats, même expérimentaux, manquent.
Des approches récentes ont montré qu'il était possible de ré-utiliser les séquences et ensembles à faible discrépance développés par les mathématiciens et de les étudier via des méthodes informatiques pour obtenir de meilleurs ensembles. Pour un ensemble de n points, notre approche est pour l'instant de trouver le meilleur sous-ensemble d'une taille fixée k (k<n), "meilleur" étant caractérisé par la discrépance du nouvel ensemble [2]. Malheureusement, notre approche actuelle est limitée par son temps d'exécution.
On s'intéressera ici à l'implémentation de nouvelles approches pour améliorer cette méthode, actuellement trop coûteuse pour être vraiment poussée. Ceci pourra être fait via des approximations de la discrépance ou de nouvelles heuristiques s'inspirant de la méthode existante. Pas de compétences mathématiques sont strictement requises, les formules existant déjà. Le code existant en C sera mis à la disposition des étudiants, que ce soit pour l'améliorer directement ou pour s'en inspirer s'il souhaitent travailler dans un autre langage. En parallèle, il serait appréciable que les étudiants puissent développer une interface permettant de regrouper le code produit et différentes versions du code existant et permettant un choix facile des paramètres du problème, ainsi qu'une bonne visualisation des ensembles de points obtenus.
[1] https://fr.wikipedia.org/wiki/Suite_%C3%A0_discr%C3%A9pance_faible Même si la définition peut paraître complexe, elle se résume à: une boîte doit contenir environ la même proportion de points que son volume occupe dans l'espace total.
[2] https://arxiv.org/abs/2306.15276 Heuristic Approaches to Obtain Low-Discrepancy Point Sets via Subset Selection, F. Clément, C. Doerr, L. Paquete