Das Kefk Network Wiki befindet sich im Testbetrieb.
Golomb-Lineal
Aus Kefk.
Ein Golomb-Lineal (häufig auch Golomb Ruler nach dem englischen Fachbegriff) ist in der Mathematik ein Lineal, bei dem es keine zwei Markierungen mit dem gleichen Abstand zueinander gibt. 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 dies 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 verteiltem Rechnen wurde der bisher bekannte Kandidat für optimale Golomb-Lineale der Ordnung 24 durch das Distributed.net-Projekt bestätigt, das derzeit nach dem optimalen Golomb-Lineal der Ordnung 25 sucht.
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 24, wobei äquivalente Lineale (d. h. 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 |
Es wird erwartet, dass die momentane Suche nach dem optimalen Golomb-Lineal der Ordnung 25 das folgende 1984 von M. D. Atkinson und A. Hassenklover entdeckte Lineal bestätigt:
| Ordnung | Länge | Markierungen |
|---|---|---|
| 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 |
Weblinks
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Golomb-Lineal, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
