OGR-NG

OGR-NG (NG für Next Generation) ist ein Projekt von Distributed.net und das nächste Projekt in der OGR-Projektreihe (OGR-24, OGR-25).

Ziel dieses Projekts ist das Finden von optimalen Golomb-Maßstäben (engl. Optimal Golomb Ruler) mit 26 und mehr Markierungen. Die Berechnungen bauen aufeinander auf, daher wurde zuerst von Oktober 2008 bis Februar 2009 der OGR-26, bis Februar 2014 der OGR-27 gesucht. Bei OGR-27 wurde, der 1984 von M. D. Atkinson und A. Hassenklover entdeckte optimale Maßstab bestätigt. Zur Zeit wird der OGR-28 gesucht. Der bisher bekannte kürzeste ist:

0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 524 547 554 585

bzw. in Differenznotation

  3 12 26 25 29  2   9  36  10  68   1   4  17  53  35   8  16  28   6  14  13  71  18  19  23   7  32

Er hat somit eine Länge von 585.

OGR-NG/Liste bekannter OGR

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).

Siehe auch:

• yoyo@home, die BOINC-Version des Projekts
• distributed.net, die durchführende Plattform des Projekts

Projektübersicht

OGR-NG
Name	OGR-NG
Kategorie	Mathematik
Ziel	Finden optimaler Golomb-Maßstäbe mit mehr als 25 Markierungen
Kommerziell	nein
Homepage	distributed.net/ogr

	Dieses Projekt wird in Alabama, USA durchgeführt.

Projektstatus

Projektstatus
Status	aktiv
Beginn	26.10.2008
Ende	noch aktiv

Projektlinks

• Hintergrundinfos
• Download
• FAQ
• Support
• Projektstatus
• Externe Projektstatistiken
• IRC-Channel

Statistiken

Wo	Übersicht	Top Teams	Top User
Distributed.net	Übersicht	Top Teams	Top User
stats.free-dc.org	Übersicht	Top Teams	Top User

Clientprogramm

Betriebssysteme

	Windows
	Windows 64bit
	Linux
	Linux 64bit
	Linux on ARM
	Android
	Raspberry Pi
	DOS
	MacOS X
	MacOS X 64bit
	BSD
	CUDA
	OpenCL
	OpenCL
	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

Besonderheiten des Clients

• Installation, Konfiguration und Screenshots sind bei der Beschreibung des kombinierten Clients von distributed.net zu finden.
• Das Projekt kann auch unter BOINC unterstützt werden. Das Projekt yoyo@home verteilt OGR-work units.

Client-Benchmarks

Client-Version	CPU	Takt	Betriebssystem	GigaNodes/sec (pro Kern)
v2.9110.519b	Intel CoreDuo T2300	1,66Ghz	Windows 32bit	21,2
v2.9110.519b	Intel Core2Duo 6400	2,13Ghz	Windows 32bit	35,6
v2.9110.519b	Intel Core2Duo T7350	2,00Ghz	Windows 64bit	42,5
v2.9110.519b	Intel Core2Duo P8700	2,54Ghz	Windows 64bit	54,4
v2.9110.519b	Intel Core2Duo T9600	2,80Ghz	Windows 64bit	60,4
v2.9110.519b	Intel i7 3770	3,40Ghz	Windows 64bit	85,6

Meldungen

• 07.04.2012: OGR-27 50% completion

• 24.02.2009: OGR-26 finished

Qualitätssicherung

18.05.2020 - Projektstatus überprüft