Golomb-Lineal

Golomb-Lineal

Ein Golomb-Lineal oder Golomb-Maßstab (häufig auch Golomb Ruler nach dem englischen Fachbegriff) ist in der Zahlentheorie ein Lineal, bei dem es keine zwei Markierungen an ganzzahligen Positionen mit dem gleichen Abstand zueinander gibt.

Golomb-Lineal der Ordnung 4 und Länge 6, das sowohl optimal als auch perfekt ist.
Demonstration, wie ein Konferenzraum mit den Proportionen des Golomb-Lineals [0, 2, 7, 8, 11] in 10 verschiedenen Größen konfiguriert werden kann.[1]

Golomb-Lineale haben ihren Namen von Solomon W. Golomb, einem US-amerikanischen Professor für Mathematik und Elektrotechnik an der Universität von Südkalifornien.

Golomb-Lineale werden anhand ihrer Ordnung und ihrer Länge kategorisiert. Die Ordnung eines Golomb-Lineals ist dabei definiert durch die Anzahl der Markierungen, die Länge durch den größten Abstand zweier Markierungen. Da Parallelverschiebung und Spiegelung bei Golomb-Linealen als triviale Operationen angesehen werden, wird die kleinste Markierung üblicherweise auf 0 gesetzt und die nachfolgende Markierung an der kleineren der beiden möglichen Positionen.

Es ist nicht erforderlich, dass ein Golomb-Lineal alle Abstände bis zu seiner Länge messen kann, dass also alle Abstände zwischen allen Markierungen – aufsteigend geordnet – eine lückenlose Zahlenreihe (1,2,3,4,5,...) ergeben. Wenn dieses jedoch der Fall ist, wird es ein perfektes Golomb-Lineal genannt. Ein Golomb-Lineal ist optimal, wenn es keine kürzeren Lineale derselben Ordnung gibt. Optimale Golomb-Lineale für eine gegebene Ordnung zu finden ist, im Gegensatz zum Erstellen von Linealen mit Golomb-Eigenschaft, eine rechenintensive Aufgabe. Mittels verteilten Rechnens wurden bislang optimale Golomb-Lineale bis zur Ordnung 26 durch das distributed.net-Projekt bestätigt. Es wird erwartet, dass das Nachfolgeprojekt für Ordnung 27 erstmals ein kürzeres als das derzeit bekannte Lineal findet. Nach derzeitigen Schätzungen wird dies jedoch drei Jahre benötigen (ca. 2014).[2]

Golomb-Lineale finden Anwendung beim Entwurf von Gruppenantennen wie beispielsweise Radioteleskopen. Antennen in [0,1,4,6] Golomb-Anordnung findet man häufig bei Mobilfunkmasten.

Bekannte optimale Golomb-Lineale

Die Tabelle zeigt die Werte für alle derzeit bekannten optimalen Golomb-Lineale bis zur Ordnung 26, wobei äquivalente Lineale (das heißt in umgekehrter Reihenfolge zu einem der angegebenen) nicht enthalten sind.

Ordnung Länge Markierungen
1 0 0
2 1 0 1
3 3 0 1 3
4 6 0 1 4 6
5 11 0 1 4 9 11
0 2 7 8 11
6 17 0 1 4 10 12 17
0 1 4 10 15 17
0 1 8 11 13 17
0 1 8 12 14 17
7 25 0 1 4 10 18 23 25
0 1 7 11 20 23 25
0 1 11 16 19 23 25
0 2 3 10 16 21 25
0 2 7 13 21 22 25
8 34 0 1 4 9 15 22 32 34
9 44 0 1 5 12 25 27 35 41 44
10 55 0 1 6 10 23 26 34 41 53 55
11 72 0 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72
12 85 0 2 6 24 29 40 43 55 68 75 76 85
13 106 0 2 5 25 37 43 59 70 85 89 98 99 106
14 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
15 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151
16 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
17 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
18 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
19 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246
20 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283
21 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333
22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356
23 372 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372
24 425 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425
25 480 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480
26 492 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492

Einzelnachweise

  1. Paul Erdős and Paul Turan. "On a problem of Sidon in additive number theory, and on some related problems," J. London Math. Soc, 16:212--215, 1941
  2. Distributed.net: Status Overview

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Golomb — Golomb: Solomon W. Golomb Golomb Lineal Golomb Code Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeichneter Begriffe …   Deutsch Wikipedia

  • Golomb-Lineale — Ein Golomb Lineal oder Golomb Maßstab (häufig auch Golomb Ruler nach dem englischen Fachbegriff) ist in der Zahlentheorie ein Lineal, bei dem es keine zwei Markierungen an ganzzahligen Positionen mit dem gleichen Abstand zueinander gibt. Golomb… …   Deutsch Wikipedia

  • Golomb-Maßstab — Ein Golomb Lineal oder Golomb Maßstab (häufig auch Golomb Ruler nach dem englischen Fachbegriff) ist in der Zahlentheorie ein Lineal, bei dem es keine zwei Markierungen an ganzzahligen Positionen mit dem gleichen Abstand zueinander gibt. Golomb… …   Deutsch Wikipedia

  • Lineal — Ein Lineal ist ein Hilfsmittel zum Zeichnen von Linien, insbesondere gerader Linien (Strecken). Für das Zeichnen von gekrümmten Linien gibt es Kurvenlineale z. B. für Parabeln (Parabelschablone) und Straklatten. Spezialfälle bzw. analoge… …   Deutsch Wikipedia

  • Solomon Golomb — Solomon Wolf Golomb (* 1932 in Baltimore) ist amerikanischer Mathematiker und Ingenieur. In der Unterhaltungsmathematik ist er als Entdecker der Polyominos populär. Des Weiteren erfand Golomb eine Variante von Schachdame. Der breiteren… …   Deutsch Wikipedia

  • Golomblineal — Ein Golomb Lineal oder Golomb Maßstab (häufig auch Golomb Ruler nach dem englischen Fachbegriff) ist in der Zahlentheorie ein Lineal, bei dem es keine zwei Markierungen an ganzzahligen Positionen mit dem gleichen Abstand zueinander gibt. Golomb… …   Deutsch Wikipedia

  • Distributed.net — (offizieller Name Distributed Computing Technologies, Inc. oder kurz DCTI) ist eine gemeinnützige Organisation mit Sitz in den USA. Ihr Ziel ist es, die Möglichkeiten des verteilten Rechnens weiter zu entwickeln und den Einsatz der entsprechenden …   Deutsch Wikipedia

  • distributed.net — (offizieller Name Distributed Computing Technologies, Inc. oder kurz DCTI) ist eine gemeinnützige Organisation mit Sitz in den USA. Ihr Ziel ist es, die Möglichkeiten des verteilten Rechnens weiterzuentwickeln und den Einsatz der entsprechenden… …   Deutsch Wikipedia

  • Stahlmaßstab — Ein Lineal ist ein Hilfsmittel zum Zeichnen von Linien, insbesondere gerader Linien (Strecken). Es gibt aber auch Kurvenlineale z. B. für Parabeln (Parabelschablone). Spezialfälle bzw. analoge Werkzeuge sind der Dreikantmaßstab, Geodreieck,… …   Deutsch Wikipedia

  • OGR — Die Abkürzung OGR steht für: Optimal Golomb Ruler, siehe Golomb Lineal OGR Bibliothek, siehe Geospatial Data Abstraction Library Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezei …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”