OGR-20 bis 23 (beendet)
Man hatte schon 1967 und 1984 Golombmaßstäbe der Länge 20 bis 23 gefunden, von denen man vermutete, dass sie optimal waren. Erst mit diesem Projekt war es aber möglich den kompletten Suchraum zu überprüfen und so konnten Ende der 90er Jahre die bekannten Maßstäbe als optimal bestätigt werden.
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).
Projektübersicht
 OGR-20 bis 23
| |
|---|---|
| Name | OGR-20 bis 23 |
| Kategorie | Mathematik |
| Ziel | Finden optimaler Golomb-Maßstäbe |
| Kommerziell | nein |
| Homepage | members.aol.com/golomb20 |
Es ist uns leider nicht bekannt, wo auf der Welt dieses Projekt zu Hause ist.
Projektstatus
Projektlinks
Clientprogramm
Betriebssysteme
| Windows | ||
| Linux | ||
| DOS | ||
| MacOS X | ||
| BSD | ||
| Solaris | ||
| Java (betriebssystemunabhängig) |
Client-Eigenschaften
| Funktioniert auch über Proxy | 
|
| Normal ausführbares Programm |
|
| Als Bildschirmschoner benutzbar |
|
| Kommandozeilenversion verfügbar |
|
| Personal Proxy für Work units erhältlich |
|
| Work units auch per Mail austauschbar |
|
| Quellcode verfügbar | 
|
| Auch offline nutzbar |
|
| Checkpoints |
|
Veröffentlichte Versionen
- 30.11.1999: 7.10
