OGR-27 - Distributed.net (Yoyo@home)

Adaptation à BOINC de l'application OGR-27 du projet Distributed.net

But du projet OGR-27 : Déterminer la façon optimale de placer 27 marques selon la règle de Golomb.

Les résultats pourront avoir des applications en radiocristallographie et en radio-astronomie (positionnement des capteurs)

INSCRIPTION    

Télécharger Boinc (tutorial)

URL du projet : http://www.rechenkraft.net/yoyo

Applications :  

Pour faire fonctionner l'application Sony Playstation 3, il faut installer Linux (suivre ce tutorial) et télécharger un Manager Boinc spécifique : boinc_client_ps3grid.tgz.

Yoyo@home est une plateforme multi-projet qui permet de faire fonctionner des programmes de recherches extérieurs à BOINC. Pour ce faire, Yoyo et son équipe de programmeurs adapte les applications au format BOINC.

Outre OGR-27, yoyo@home permet pour le moment de participer au choix à trois autres projets : Evolution@home (l'évolution des espèces),  Muon1 (Accélérateur de particules partagé) et ECM (factorisation en courbe elliptique de Lenstra pour trouver des facteurs de différents nombres)

Le choix des projets s'effectue dans ses préférences Yoyo@home (appuyer sur Edit yoyo@home preferences, puis cocher ou décocher les cases à souhait)

Distributed.net est le projet de calcul distribué le plus ancien, puisqu'il a été lancé en avril 1997 soit 2 ans avant Seti@home.

Au niveau des points, vous recevez des points Boinc pour chaque unité calculée comme sur n'importe quel projet BOINC, avec un classement spécifique au projet yoyo@home. Les points Distributed.net réalisés par le projet yoyo@home sont eux cumulés sur un seul compte : yoyo@home BOINC Wrapper

Qu'est-ce qu'OGR ? (source : Distributed.net)

Le projet OGR a été lancé le 13 juillet 2000 vers 22h00 UTC avec le lancement de la recherche OGR-24 (recherche des règles de Golomb d'ordre 24 optimales). La recherche OGR-25 a été lancée quelques semaines plus tard, le 1er Août 2000. Le 13 Octobre 2004, les derniers résultats de la recherche OGR-24 ont été retournés aux serveurs du projet. Après 4 ans de calcul, les participants ont permis de prouver que la façon optimale de placer 24 marques selon la règle de Golomb était bien celle prédite par John P. Robinson et Arthur J. Bernstein en 1967, c'est à dire une règle de longeur 425. 

La recherche OGR-25 s'est terminée le 26 octobre 2008, la recherche OGR-26 s'est quant à elle terminée récemment, le 24 février 2009. Là encore, les recherches OGR-25 et OGR-26 sont venus prouver, par une recherche exhaustive, que M. D. Atkinson et A. Hassenklover avaient bien découvert en 1984 la règle optimale d'ordre 25 (longueur 480) et d'ordre 26 (longueur 492)

Dans les deux cas, la recherche OGR a démontré que la règle optimale était unique.

Depuis le 24 février 2009, c'est la recherche OGR-27 qui a pris le relais. La règle susceptible d'être optimale a été découverte en 1984 par M. D. Atkinson et A. Hassenklover :

Il existe une forte probabilité pour que cette règle ne soit pas pas la véritable règle optimale, seule la recherche OGR-27 pourra nous la révêler

(Voir les statistiques du projet)

Qu'est-ce qu'une règle de Golomb ? (source : Distributed.net)

En mathématiques, le terme "règle de Golomb" désigne une suite d'entiers positifs disposés de telle sorte que les distances entre les éléments soient deux à deux distinctes. Concrètement, cela ressemble à une règle construite de telle façon que deux paires de marques ne soient jamais situées à la même distance l'une de l'autre. Une règle de Golomb optimale (OGR) est la plus courte règle possible pour un nombre donné de marques. Toutefois, la difficulté de trouver (et prouver) les OGR augmente de  manière exponentielle au fur et à mesure que le nombre de marques augmente, et c'est pour cette raison que le projet s'est tourné vers la toile afin que les ordinateurs individuels puissent les aider à trouver les OGR avec 24 marques et plus.

Les règles de Golomb doivent leur nom au docteur Solomon W. Golomb, un professeur de mathématiques qui s'est particulièrement intéressé à l'analyse combinatoire, à la théorie des nombres, à la cryptographie et aux outils de communication. Le docteur Golomb s'est également intéressé aux jeux et aux énigmes mathématiques : il est l'auteur de nombreux articles parus dans la rubrique "Jeux Mathématiques" de la revue Scientific American. Les OGR ont de nombreuses applications dont entre autres : le positionnement des capteurs en radiocristallographie ainsi qu'en radio-astronomie. Les règles de Golomb jouent également un rôle dans les théories combinatoires, dans l'amélioration des connaissances théoriques en matière de cryptographie et de sytèmes de communication. Le docteur Golomb est l'un des premiers à avoir analysé l'utilité des règles de Golomb dans ces domaines.

Une règle de Golomb est une manière de placer des marques sur une droite de telle sorte que deux paires de marques ne soient jamais à la même distance. Voici une règle de Golomb à cinq marques :

Le nombre situé sous la marque donne la distance par rapport au bord gauche. La longueur de cette règle est 11; il se trouve que cette règle est l'une des deux règles à cinq marques les plus courtes. L'autre règle est celle dont les marques se situent aux positions 0, 3, 4, 9 et 11. (les images inversées de ces deux règles, 0, 2, 7, 10, 11 et 0, 2, 7, 8, 11 constituent également des règles de Golomb optimales. On ne mentionne habituellement qu'un représentant de chaque paire d'images inversées.)

Pour vérifier que la règle ci-dessus est effectivement une règle de Golomb, on peut construire un tableau résumant toutes les paires de marques possibles en indiquant pour chacune leurs distances respectives :

Notez que la troisième colonne ne contient aucune répétition. La distance 6 n'apparaît pas non plus, mais ce n'est pas grave : une règle de Golomb n'a pas pour objectif de mesurer toutes les distances, mais seulement des distances différentes entre chaque couple de marques.

Le but de "l'optimisation" des règles de Golomb est de les rendre aussi courtes que possible, sans dupliquer les distances mesurées. Les deux règles à cinq marques données ci-dessus sont optimales.

On caractérise habituellement les règles de Golomb par l'espacement entre les marques plutôt que par la position absolue des marques, comme c'est le cas sur le diagramme ci-dessus. La règle ci-dessus s'écrirait ainsi 1-3-5-2 (ou encore 0-1-3-5-2, mais on oublie souvent le 0 initial).

Par exemple, voici la plus petite règle à 21 marques connue :

2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4

James B. Shearer a compilé une liste des plus petites règles de Golomb connues jusqu'à 150 marques. Si vous comparez les règles, vous constaterez que la règle à 21 marques mentionnée sur la page de James est l'image inversée de celle présentée ci-dessus.

Malheureusement, la complexité de la recherche OGR croît de manière exponentielle avec le nombre de marques ( c'est ce que les mathématiciens décrivent sous l'appellation "problème NP complet" ... comme l'infâme "problème du voyageur de commerce")