Projekt OGR

From distributed.net
Jump to: navigation, search

Projekt OGR

Clients und Proxies, die in der Lage sind, an OGR zu arbeiten, sind schon für die meisten Plattformen verfügbar. Ladet euch den neuesten Client herunter und installiert ihn noch heute als Vorbereitung auf den Start des Wettbewerbs. Wenn Du irgendwelche Fragen an den technischen Support über den Betrieb Deines distributed.net Clients hast, klicke bitte hier, um eine eMail an help@distributed.net zu schicken. Schaue auch in den FAQ-o-Matic, um zu sehen, ob Deine Frage schon beantwortet wurde.

Was ist eigentlich ein Optimaler Golomb-Maßstab?

In der Mathematik ist der Golomb-Maßstab ein Satz von nicht negativen ganzen Zahlen, bei denen kein Paar der Zahlen die gleiche Differenz zueinander aufweisen. Grundsätzlich ist das mit einem Lineal zu vergleichen, auf dem keiner der Abstände zwischen zwei Markierungen gleich groß ist. Ein Optimaler Golomb-Maßstab (auf Englisch: Optimal Golomb Ruler, OGR) ist der kürzeste Golomb-Maßstab bei einer gegebenen Anzahl von Markierungen. Allerdings steigt die Schwierigkeit des Findens (und Beweisens) eines OGR exponentiell mit der Anzahl der Markierungen an. Deswegen haben wir uns für Hilfe bei der Suche nach OGRs mit 24 und mehr Markierungen ins Web gewandt.

Golomb-Maßstäbe werden benannt nach Dr. Solomon W. Golomb, einem Professor der Mathematik mit speziellem Interesse an kombinatorischer Analysis, Zahlentheorie, Verschlüsselungstheorie und dem Kommunikationswesen. Dr. Golomb hat auch Interessen in mathematischen Spielen und Puzzles und war ein Schreiber vieler Beiträge der Mathematischen Spiele im Scientific American. OGRs werden an verschiedenen Orten eingesetzt, wie z.B. Radio-Astronomie oder Sensor-Plazierungen für Röntgenkristallographie. Golomb-Maßstäbe spielen auch eine wichtige Rolle in der Kombinatorik, Verschlüssselungstheorie und dem Kommunikationswesen und Dr. Golomb war einer der ersten, der ihren Nutzen in diesen Bereichen untersucht hat.

Ein Golomb-Maßstab ist eine Möglichkeit, Markierungen entlang einer Linie so zu plazieren, daß jedes der Markierungspaare einen einzigartigen Abstand mißt. Hier ein Golomb-Maßstab mit fünf Markierungen:

| |     |         |   |
0 1     4         9   11

Die Zahl unter der Markierungen ist der Abstand von der linken Kante. Die Länge dieses Maßstabs beträgt 11 und er stellt einer der beiden kürzesten dieser Maßstäbe mit fünf Markierungen dar. Der andere Maßstab hat Markierungen bei 0, 3, 4, 9 und 11. (Die Spiegelbilder dieser zwei Maßstäbe, 0, 2, 7, 10, 11 und 0, 2, 7, 8, 11 sind ebenfalls Optimale Golomb-Maßstäbe. Normalerweise wird nur eins jedes Spiegelpaars erwähnt.)

Du kannst überprüfen, ob der obige Maßstab wirklich Golomb ist, indem Du eine Tabelle mit allen Markierungspaaren und ihren zugehörigen Abständen erstellst:

Markierung 1 Markierung 2 Abstand
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

Anmerkung: Es stehen keine doppelten Abstände in der dritten Spalte. Außerdem gibt es auch keinen Abstand 6, aber das ist in Ordnung, da Golomb-Maßstäbe nicht jeden Abstand messen müssen, nur unterschiedliche Abstände.

Das Ziel der Optimierung von Golomb-Maßstäben liegt darin, sie so kurz wie möglich zu machen, ohne irgendwelche Abstände zu duplizieren. Die beiden Maßstäbe mit 5 Markierungen oben sind optimal.

Golomb-Maßstäbe werden normalerweise durch ihre Unterschiede, anstatt über ihre absoluten Abstände wie in dem obigen Diagramm, charakterisiert. Also wäre der obige Maßstab 1-3-5-2 (was manchmal auch als 0-1-3-5-2 geschrieben wird, aber die führende Null wird oft weggelassen).

Zum Beispiel ist der bekannteste Maßstab mit 21 Markierungen der folgende:

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

James B. Shearer hat eine List aller meistbekannten Golomb-Maßstäbe bis zu 150 Markierungen zusammengestellt. Anmerkung, wenn Du Maßstäbe vergleichen möchtest: Der 21er-Maßstab, der auf der Seite von James aufgeführt steht, ist das Spiegelbild des obigen.

Unglücklicherweise steigt die Schwierigkeit der Suche nach OGRs exponentiell mit der Anzahl der Markierungen an (in etwa so, wie etwas, daß die Mathematiker "Np-vollständige" Probleme nennen ... so wie das berüchtigte Problem des Handelsreisenden).

Allgemeine Links über OGR

Weitere OGR Forschungsunterlagen in Buchform

  • J. P. Robinson und A. J. Bernstein, "A class of binary recurrent codes with limited error propagation," IEEE Trans. Inform. Theory, Bd. IT-13, Nr. 1, S. 106-113, 1967.
  • M. D. Atkinson, N. Santoro und J. Urrutia, "Integer sets with distinct sums and differences und carrier frequency assignments for nonlinear repeaters", IEEE Transactions On Communications, Bd. Com-34, Nr. 6, S. 614-617, Juni 1986.
  • A. W. Lam und D. V. Sarwate, "On optimum time hopping patterns", IEEE Transactions on communications, Bd. 36, Nr. 3, S. 380-382, März 1988.
  • A.Dollas, W.T.Rankin und D.McCracken veröffentlichten "A New Algorithm for Golomb Ruler Derivation and proof of the 19 Mark Ruler" in IEEE Transactions On Information Theory (Januar 1998, Band 44, Nummer 01).