Golomb uralkodó

A Golomb-vonalzó a számelméletben  nemnegatív egész számok halmaza , amelyek egy képzeletbeli vonalzón osztásként vannak elrendezve oly módon, hogy bármely két osztás távolsága egyedi. Más szóval, lehetetlen két olyan számot találni a vonalzó teljes hosszában, amelyek közötti különbség kétszer megismétlődik [1] .

Nevét Solomon Golomb amerikai matematikusról kapták [2] , bár az ilyen konstrukciók első említése Sidon [3] és Babcock [4] korábbi publikációiban található .

Definíciók

A Golomb-vonalzón lévő osztódások számát sorrendnek , a két osztás közötti legnagyobb távolságot pedig hosszúságnak nevezzük . Például egy 0 1 4 9 11 osztású vonalzó egy ötödik, 11 hosszúságú vonalzó. Néha a Golomb-vonalzók leírása a szomszédos osztások távolságával történik, nem pedig az osztások abszolút koordinátáival, így a fenti vonalzó úgy néz ki, mint 1-3-5-2. Az n rendű vonalzó osztásaiból összeállítható párok maximális száma megegyezik a kombinációk számával .

Az egyes osztások fix számmal történő eltolásával (például 1 2 5 10 12) vagy a vonalzó osztásainak fordított sorrendben történő felsorolásával (tükrözéssel) - például 0 2 7 10 11 - kapott vonalzókat figyelembe kell venni. egyenértékű. Ezért a Golomb-vonalzó kanonikus ábrázolásában a legkisebb osztás a nulla koordinátának felel meg, az azt követő osztás pedig a két lehetséges távolság közül a legkisebben helyezkedik el.

A Golomb vonalzó nem mindig alkalmas a hosszán belüli összes egész távolság mérésére, de ha alkalmas, akkor az ilyen vonalzót tökéletesnek nevezzük ( English  Perfect Golomb Ruler  (English) , PGR). Tökéletes vonalzók csak az ötnél kisebb rendeléseknél léteznek.

Egy Golomb-vonalzót akkor nevezünk optimálisnak ( Eng.  Optimal Golomb Ruler  (angol) , OGR), ha nincsenek ugyanilyen sorrendű rövidebb vonalzók. Más szóval, egy vonalzó akkor optimális, ha a kanonikus ábrázolásban az utolsó osztás értéke a lehető legkisebb.

A Golomb-vonalzó létrehozása viszonylag egyszerű, de a vonalzó optimálisságának bizonyítása időigényes számítási folyamat. Jelenleg nem ismert módszer egy tetszőleges n hosszúságú optimális Golomb-vonalzó megszerzésére , de ez a probléma NP-nehéznek tekinthető .

Ismert optimális Golomb-vonalzók

A 150-es nagyságrendig terjedő Golomb-vonalzók ismertek [5] , de az optimalitást csak a 27-et meg nem haladó rendű vonalzók esetében igazolták. A következő táblázat tartalmazza az összes eddig ismert golomb-vonalzót a kanonikus ábrázolásban, amelyekre az optimalitás bebizonyosodott.

Rendelés Hossz Osztályok hézagok
egy 0 0 0
2 egy 0 1 egy
3 3 0 1 3 12
négy 6 0 1 4 6 1 3 2
5 tizenegy 0 1 4 9 11
0 2 7 8 11 		1 3 5 2
2 5 1 3
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 		1 3 6 2 5
1 3 6 5 2
1 7 3 2 4
1 7 4 2 3
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 		1 3 6 8 5 2
1 6 4 9 3 2
1 10 5 3 4 2
2 1 7 6 5 4
2 5 6 8 1 3
nyolc 34 0 1 4 9 15 22 32 34 1 3 5 6 7 10 2
9 44 0 1 5 12 25 27 35 41 44
tíz 55 0 1 6 10 23 26 34 41 53 55
tizenegy 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
tizennégy 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
tizenöt 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
tizennyolc 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
húsz 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
27 553 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 5

Optimális Golomb-vonalzók megtalálása

Az optimális 24. rendű Golomb uralkodót 1967-ben John P. Robinson és Arthur J. Bernstein találta meg . Optimalitása azonban csak 2004. november 1-jén igazolódott be a világ minden tájáról érkezett több mint 40 ezer ember 4 év és 110 napon át tartó összefogásával az OGR-24 elosztott számítástechnikai projekt [6] részeként. profitszervezet terjesztett.net .

A 25. rendű optimális Golomb uralkodót 1984-ben Atkinson ( MD Atkinson ) és Hassenklover ( A. Hassenklover ) találta meg. Optimitásának bizonyítása 3006 nap alatt készült el 2008. október 24- én az OGR-25 projekt keretében [7] .

A 26. rendű Golomb vonalzó optimalitásbizonyítása 2009. február 24-én 24 nap alatt készült el az OGR-26 projekt részeként [8] .

A 27. rendű Golomb vonalzó optimalitásbizonyítása 1822 nap alatt készült el 2014. február 19-én az OGR-27 projekt keretében [9] .

A 28. rendű Golomb uralkodó optimálisságának bizonyítéka az OGR-28 projekt , amely 2021. szeptember 4-én 87,87%-ban készült el [10] .

A yoyo@home elosztott számítástechnikai projekt optimális Golomb vonalzókat is keres .

Alkalmazások

A Golomb vonalzó egyik gyakorlati alkalmazása fázisos antennatömbökben  – például rádióteleszkópokban – való felhasználása . A [0 1 4 6] konfigurációjú antennák a CDMA cellás bázisállomásokban találhatók .

Jegyzetek

  1. ↑ Mark Garry Bevezetés a Golomb uralkodókhoz
  2. ↑ Solomon W. Golomb (a link nem érhető el) . Hozzáférés dátuma: 2007. július 28. Az eredetiből archiválva : 2007. július 28. 
  3. ↑ S. Sidon. Ein Satzuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen  (német)  // Mathematische Annalen  : magazin. - 1932. - Bd. 106 . - S. 536-539 .
  4. ↑ Wallace C. Babcock. Intermodulációs interferencia rádiórendszerekben / Előfordulás gyakorisága és vezérlés csatornaválasztással  // Bell System Technical  Journal : folyóirat. - 1953. - 1. évf. 31 . - 63-73 . o .
  5. ↑ Golomb vonalzó asztal Archivált : 2018. április 16. a Wayback Machine -nél 
  6. ↑ OGR-24 projekt statisztika . Letöltve: 2007. december 22. Az eredetiből archiválva : 2016. február 17..
  7. ↑ OGR-25 projekt statisztika . Letöltve: 2007. december 22. Az eredetiből archiválva : 2013. október 17..
  8. ↑ OGR-26 projekt statisztika . Letöltve: 2008. november 1. Az eredetiből archiválva : 2014. december 29.
  9. ↑ OGR-27 projekt statisztika . Hozzáférés dátuma: 2010. január 8. Az eredetiből archiválva : 2014. január 9..
  10. ↑ OGR-28 projekt statisztika . Letöltve: 2014. február 26. Az eredetiből archiválva : 2015. július 21..

Lásd még

Linkek