Le project OGR
Le projet OGR
Les clients et proxys capables de travailler sur le projet OGR sont disponibles dès à présent pour la plupart des plateformes. Téléchargez et installez les derniers clients. Par ailleurs, une section du FAQ-o-Matic est dédiée au projet OGR si vous souhaitez plus d'informations pratiques. Un petit nombre de personnes a reçu des blocs de calcul OGR-25 extrèmement grands, mais cela arrive relativement rarement.
Vous pourrez trouver davantage d'informations sur la puissance de calcul de notre réseau sur la page des statistiques OGR.
Si vous avez des questions techniques concernant l'utilisation de votre client d.net, veuillez utiliser le lien suivant pour envoyer un message à help@distributed.net. Assurez-vous que la question n'a pas déjà obtenu de réponse dans le FAQ-o-Matic.
Qu'est ce qu'une règle de Golomb ?
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 théorie du codage et aux communications. Le docteur Golomb s'intéresse aussi aux jeux et aux énigmes mathématiques : il est l'auteur de nombreux articles parus dans la rubrique "Jeux Mathématiques" de Scientific American. Les OGR ont de nombreuses applications dont entre autres : le positionnement des capteurs pour la cristallographie à rayons X, et la radioastronomie. Les règles de Golomb jouent également un rôle en combinatoire, en théorie du codage et dans les communications, et le docteur Golomb est l'un des premiers à avoir analysé leur utilité dans ces domaines.
Une règle de Golomb est une manière de placer des marques sur une droite de sorte que chaque couple de marques mesure une longueur différente des autres. Voici une règle de Golomb à cinq marques :
| | | | | 0 1 4 9 11
Le nombre situé sous la marque donne la distance 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 écrire la table de toutes les paires de marques possibles en indiquant pour chacune la distance correspondante :
| Marque 1 | Marque 2 | Distance |
|---|---|---|
| 0 | 1 | 1 |
| 0 | 4 | 4 |
| 0 | 9 | 9 |
| 0 | 11 | 11 |
| 1 | 4 | 3 |
| 1 | 9 | 8 |
| 1 | 11 | 10 |
| 4 | 9 | 5 |
| 4 | 11 | 7 |
| 9 | 11 | 2 |
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'est pas censée permettre de mesurer toutes les distances, mais seulement des distances différentes d'une paire de marques à l'autre.
Le but de l'"optimisation" des règles de Golomb est de les rendre aussi courtes que possible, tout en ne duplicant pas 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 ci-dessus.
Malheureusement, la complexité de la recherche d'OGR croît de manière exponentielle avec le nombre de marques ( de la même manière que ce que les mathématiciens décrivent sous l'appellation "problème NP complet" ... comme l'infâme "problème du voyageur de commerce")
Liens généraux relatifs aux Règles de Golomb
- la description des règles de Golomb selon MathWorld
- technical OGR information pageune page d'information technique sur les OGR] rédigée par Greg Hewgill ainsi que son fichier .plan
- le projet OGR précédent (OGR-20, -21, -22 et -23)
- la liste des meilleures règles de Golomb connues (jusqu'à 150 marques), mise à jour par James B. Shearer, ainsi que sa page principale sur les règles de Golomb
- encore davantage de meilleures règles de Golomb connues, compilées par Lloyd Miller, et autres informations.
- la page web de William T. Rankin's décrivant son projet de master qui comportait une recherche distribuée des OGR-17, -18 et -19
- l'article écrit par Stephen Wayne Soliday sur un algorithme génétique de recherche de règles de Golomb presque optimales
- le résumé de l'article de D. Kent Freeman sur la similarité entre la maximalisation d'irrégularité et la recherche de règles de Golomb
Autres références de recherche sur les OGR
(Ces documents ne sont pas disponibles en ligne et sont en anglais)
- J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation," IEEE Trans. Inform. Theory, vol. IT-13, no. 1, pp. 106-113, 1967.
- M. D. Atkinson, N. Santoro, and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions On Communications, vol. Com-34, no. 6, pp. 614-617, June 1986.
- A. W. Lam and D. V. Sarwate, "On optimum time hopping patterns", IEEE Transactions on communications, vol. 36, no. 3, pp. 380-382, March 1988.
- A.Dollas, W.T.Rankin and D.McCracken published "A New Algorithm for Golomb Ruler Derivation and proof of the 19 Mark Ruler" in IEEE Transactions On Information Theory (January, 1998, Volume 44, Number 01).