| retour à l'accueil | introduction le problème le programme le TIPE images bibliographie |
dernière mise à jour : 16 septembre 2006
|
Particules
Réalisé dans le cadre d'un TIPE de classe préparatoire (sorte de mini sujet de recherche pour ceux qui ne connaîtraient pas), ce logiciel a pour but de rechercher des solutions au problème de Thomson qui consiste à placer N points à la surface d'une sphère de la "meilleur" manière possible. Il faut donc avant tout définir ce qu'est la meilleurs manière.
Ce problème ce traite d'autant mieux d'un point de vue expérimental que des meilleures configurations de points à la surface de la sphère ne sont connues (avec démonstration à l'appuie) que pour quelques N particuliers (le plus grand d'entre eux étant 60). Ici je me suis surtout intéressé à des N grands (entre 100 et 10000). D'autre part, on peut considérer le problème avec toutes sortes de surface (thorique, cylindrique, etc.) mais on ne s'interessera ici qu'à la boule unité.
Sur un segment, il est très facile d'agencer de la meilleure manière possible N points. Il suffit de les répartir de manière équidistante. De même, sur un morceau de plan, il suffit de les répartir selon un pavage hexagonal. Mais à la surface d'une sphère ou d'une boule, il n'existe pas de telle configuration qui permette d'obtenir de manière claire une meilleure configuration de point (sauf pour les cas particuliers, où les points peuvent être agencés selon un polyèdre régulier). Il faut donc commencer par définir ce qu'est la meilleure configuration de points. Pour mon programme, j'ai retenu deux définitions qui permettent des modélisations intéressantes et qui donne des résultats utilisables (mais bien d'autres définitions sont possibles) : d'une part j'ai tenté de maximiser, pour un nombre N de points à la surface de la sphère donné, la distance minimum entre deux de ces points ; et d'autre part (et les résultats sont généralement différents) j'ai essayé de minimiser le potentiel de Coulomb du système qui serait constitué de particule chargées (portant toutes la même charge) astreintes à se déplacer sur la sphère (c'est ce critère qui donne son nom à mon programme).
Une fois la définition choisie, j'ai utilisé plusieurs méthodes pour trouver des configurations s'approchant des solutions. Globalement, on peut voir deux catégories d'algorithmes : ceux qui sont "mathématiques", qui s'appuient sur les distances entre les points, les propriétés de leur enveloppe convexe, etc. ; ou ceux qui sont "physique", c'est-à-dire qui s'appuie sur une modélisation physique du problème, particulièrement en modélisant le mouvement à la surface de la sphère de particules chargées qui s'y trouveraient.
Pour avoir plus d'information sur le problème et sur les algorithmes que j'utilise, le mieux est de télécharger le rapport du TIPE, disponible plus bas (ou ici), ainsi que de consulter le code source de mon programme qui contient d'autres algorithmes que je n'ais pas documenté.
J'ai écrit ce logiciel permettant de rechercher des meilleures configurations en C++ en utilisant les bibliothèque OpenGL (à la compilation, facultatif si vous ne souhaitez pas avoir de sortie graphique) et OpenMP (facultatif pour compiler). Il se compile sans trop de problèmes sous Windows (avec Visual C++ ou Dev C++) et sous Linux (avec GCC, mais avec quelques toutes petites fonctionnalités en moins).
Je n'ai pas testé le programme sous d'autre version de Windows que XP, il se peut qu'il fonctionne quand même (si quelques essaye, il peut m'écrire à ce sujet). Vous pouvez télécharger un installateur pour la version Windows du programme. Si vous ne souhaiter pas utiliser d'installateur (ce que je comprend, moi-même je déteste ça, mais certains programmes produit par Visual C++ en ont besoin), vous pouvez télécharger cette archive qui comprend une version du programme compilé avec Dev C++, mais qui est malheureusement beaucoup moins rapide.
Sous linux (ou sous Windows si vous le souhaitez, ce que je vous conseille de faire) vous devrez compiler le programme vous-même. Pour cela, sous Linux, vous devrez avoir installé les versions de développement des bibliothèques OpenGL avec glX (à ne pas confondre avec Xgl, qui n'a rien à voir).J'ai testé la compilation avec des versions 32 et 64 bits de Debian sans problèmes, sur d'autres distributions, ou avec des configurations différentes de la miennes vous aurez peut-être à modifier légèrement le makefile. Le code source est disponible ici, sous licence SectionPC. Sous Windows, OpenGL est déjà installé correctement donc vous n'aurez rien à faire. Les fichiers des bibliothèques nécessaires pour compiler sous Windows sont dans l'archive, mais vous pouvez les mettre à jour à partir de mon site si nécessaire.
Si vous compilez vous-même le programme, je vous conseille de regarder le fichier paramètres.h qui permet de modifier complètement le fonctionnement du programme (le type de mesure effectué, la dimension de l'espace dans lequel on travaille, les options par défauts, le type des graphismes, etc.).
Le TIPE :
Pour ceux qui sont intéressés par ce problème, vous pouvez en plus télécharger ici le rapport que j'ai écrit sur ce TIPE, un fichier Excel avec les valeurs numériques ayant servies à établir les graphismes du document précédant, ainsi qu'une page donnant rapidement des applications possibles des solutions de ce problème. Le premier de ces documents fournit des informations intéressantes sur le fonctionnement de mon programme et sur la résolution du problème si vous vous y intéressez pour une raison ou une autre.
Pour toutes questions, suggestions, remarques, critiques, etc. au sujet de ce programme, vous pouvez m'écrire à particules@sectionpc.info.
Ci dessous, quelques exemples de graphismes que l'on peut générer avec mon programme :
 Configuration à 500 particules après utilisation de la méthode d'éloignement. |
 Configuration optimisée à 800 particules avec visualisation de l'enveloppe convexe des particules (les zones de faible potentiel sont en clair et vice-versa). |
 Configuration optimisée à 12 particules. |
 La même, après ajout de particules aux milieux des arêtes de l'enveloppe convexe. |
 Idem, après ajout de particules aux milieux des faces de l'enveloppe convexe. |
 Configuration optimisée avec 50 particules. |
 Configuration à 800 particules, réparties en spirale. |
 Solution du problème avec 4 points. |
 Configuration optimisée à 600 particules avec visualisation du polygone dual de l'enveloppe convexe. |
 Configuration optimisée à 80 particules avec visualisation des défauts prévus par la formule d'Euler. |
 Configuration non optimale à 8 particules. |
 Solution du problème avec 8 points. |
 Configuration optimisée à 800 particules avec visualisation des cellules de Dirichlet. |
 Configuration non optimale à 800 particules. |