OGR-24 (beendet)

Aus Rechenkraft
(Weitergeleitet von OGR-24)
Wechseln zu: Navigation, Suche

OGR-24 war ein Projekt von Distributed.net, das einen optimalen Golomb-Maßstab (engl: Optimal Golomb Ruler) mit 24 Markierungen gesucht hat.

Inhalt

Definition

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 aufweist. 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) ist der kürzeste Golomb-Maßstab bei einer gegebenen Anzahl von Markierungen.

Name

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. OGRs werden an verschiedenen Orten eingesetzt, wie z.B. Radio-Astronomie oder Sensor-Platzierungen 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 Beispiel

Ein Golomb-Maßstab ist eine Möglichkeit, Markierungen entlang einer Linie so zu platzieren, dass jedes der Markierungspaare einen einzigartigen Abstand misst. 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 0 0 0 0 1 1 1 4 4 9
Markierung 2 1 4 9 11 4 9 11 9 11 11
Abstand 1 4 9 11 3 8 10 5 7 2

Anmerkung: Es stehen keine doppelten Abstände in der dritten Zeile. 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).

Ergebnis

Die Suche nach optimalen Golomb-Maßstäben mit 24 Markierungen wurde erfolgreich am 13.10.04 beendet.

Der als optimal bestätigte Maßstab hat die Länge 425 und liest sich
0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425.

Gefunden wurde er bereits 1967 von John P. Robinson und Arthur J. Bernstein, konnt aber erst 33 Jahre später mit diesem Projekt als optimal bestätigt werden.

Siehe auch:

  • OGR-25, das direkte Nachfolgeprojekt
  • OGR-NG, die Suche nach Maßstäben mit über 25 Markierungen


Projektübersicht

InfoIcon.png OGR-24
Name OGR-24
Kategorie Mathematik
Ziel Finden optimaler Golomb Maßstäbe aus 24 Markierungen
Kommerziell   nein
Homepage distributed.net/ogr


 
United States01.gif     Dieses Projekt wird in Alabama, USA durchgeführt.


Projektstatus

InfoIcon.png Projektstatus
Status   beendet
Beginn 13.07.2000
Ende 13.10.2004

Projektlinks

Clientprogramm

Betriebssysteme

Icon windows 16.png    Windows Checkbox 1.gif   
Icon linux 16.png    Linux Checkbox 1.gif   
Icon dos 16.png    DOS Checkbox 1.gif   
Icon macos 16.png    MacOS X Checkbox 1.gif   
Icon freebsd 16.png    BSD Checkbox 1.gif   
Icon solaris 16.png    Solaris Checkbox 1.gif   
Icon java 16.png    Java (betriebssystemunabhängig)  Checkbox 0.gif   

Client-Eigenschaften

Funktioniert auch über Proxy Checkbox 1.gif
Normal ausführbares Programm Checkbox 1.gif
Als Bildschirmschoner benutzbar Checkbox 1.gif
Kommandozeilenversion verfügbar Checkbox 1.gif
Personal Proxy für Work units erhältlich   Checkbox 1.gif
Work units auch per Mail austauschbar Checkbox 1.gif
Quellcode verfügbar Checkbox 0.gif
Auch offline nutzbar Checkbox 1.gif
Checkpoints Checkbox 1.gif

Besonderheiten des Clients

Installation, Konfiguration und Screenshots sind bei der Beschreibung des kombinierten Clients von distributed.net zu finden.


Eigene Werkzeuge