Domnitorul Golomb

O riglă Golomb în teoria numerelor  este un set de numere întregi nenegative aranjate ca diviziuni pe o riglă imaginară în așa fel încât distanța dintre oricare două diviziuni să fie unică. Cu alte cuvinte, este imposibil să găsești două numere pe toată lungimea riglei, diferența dintre care s-ar repeta de două ori [1] .

Ele sunt numite după matematicianul american Solomon Golomb [2] , deși prima mențiune despre astfel de construcții poate fi găsită în publicațiile anterioare ale lui Sidon [3] și Babcock [4] .

Definiții

Numărul de diviziuni de pe rigla Golomb se numește ordinea sa , iar distanța cea mai mare dintre cele două diviziuni se numește lungime . De exemplu, o riglă cu diviziuni 0 1 4 9 11 este o riglă de ordinul al cincilea de lungime 11. Uneori, riglele Golomb sunt descrise prin distanțele dintre diviziunile adiacente și nu prin coordonatele absolute ale diviziunilor, așa că rigla de mai sus ar arată ca 1-3-5-2. Numărul maxim de perechi care se pot face din diviziuni ale unei rigle de ordinul n este egal cu numărul de combinații .

Riglele obținute de la una dată prin deplasarea fiecărei diviziuni cu un număr fix — de exemplu, 1 2 5 10 12 — sau prin enumerarea diviziunilor riglei în ordine inversă (oglindită) — de exemplu, 0 2 7 10 11 — sunt considerate echivalent. Prin urmare, în reprezentarea canonică a riglei Golomb, cea mai mică diviziune corespunde coordonatei zero, iar diviziunea care o urmează este situată la cea mai mică dintre cele două distanțe posibile.

Rigla Golomb nu este întotdeauna potrivită pentru măsurarea tuturor distanțelor întregi în lungimea sa, cu toate acestea, dacă este potrivită, atunci o astfel de riglă se numește perfect ( English  Perfect Golomb Ruler  (English) , PGR). Riglele perfecte există doar pentru comenzi mai mici de cinci.

O riglă Golomb se numește optim ( Eng.  Optimal Golomb Ruler  (English) , OGR) dacă nu există rigle mai scurte de același ordin. Cu alte cuvinte, o riglă este optimă dacă, în reprezentarea canonică, valoarea ultimei sale împărțiri este minimă posibilă.

Crearea unei rigle Golomb este relativ simplă, dar demonstrarea optimității unei rigle este un proces de calcul care necesită timp. În prezent, o metodă pentru obținerea unei rigle Golomb optime de lungime arbitrară n este necunoscută, dar se crede că această problemă este NP-hard .

Conducători Golomb optimi cunoscuți

Riglele Golomb până la ordinul 150 sunt cunoscute [5] , dar optimitatea a fost dovedită numai pentru conducătorii de ordin care nu depășesc 27. Tabelul următor conține toți conducătorii Golomb cunoscuți până în prezent în reprezentarea canonică pentru care optimitatea a fost dovedită.

Ordin Lungime Diviziuni goluri
unu 0 0 0
2 unu 0 1 unu
3 3 0 1 3 12
patru 6 0 1 4 6 1 3 2
5 unsprezece 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
opt 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
zece 55 0 1 6 10 23 26 34 41 53 55
unsprezece 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
paisprezece 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
cincisprezece 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
optsprezece 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
douăzeci 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 55

Găsirea guvernanților Golomb optimi

Rigla Golomb optimă de ordinul 24 a fost găsită în 1967 de John P. Robinson și Arthur J. Bernstein . Cu toate acestea, optimitatea sa a fost dovedită abia la 1 noiembrie 2004 prin eforturile conjugate a peste 40 de mii de oameni din întreaga lume timp de 4 ani și 110 zile, ca parte a proiectului de calcul distribuit OGR-24 [6] al non- organizaţie de profit distribuit.net .

Conducătorul Golomb optim al ordinului 25 a fost găsit în 1984 de către Atkinson ( MD Atkinson ) și Hassenklover ( A. Hassenklover ). Dovada optimității sale a fost finalizată în 3006 zile la 24 octombrie 2008 în cadrul proiectului OGR-25 [7] .

Dovada optimității riglei Golomb de ordinul 26 a fost finalizată în 24 de zile pe 24 februarie 2009, ca parte a proiectului OGR-26 [8] .

Dovada optimității riglei Golomb de ordinul 27 a fost finalizată în 1822 de zile pe 19 februarie 2014, ca parte a proiectului OGR-27 [9] .

Dovada optimității conducătorului Golomb de ordinul 28 este proiectul OGR-28 , care este 87,87% finalizat la 4 septembrie 2021 [10] .

Proiectul de calcul distribuit yoyo@home caută, de asemenea, rigle Golomb optime .

Aplicații

Una dintre aplicațiile practice ale riglei Golomb este utilizarea sa în rețele de antene în faze  - de exemplu, în radiotelescoape . Antenele cu configurația [0 1 4 6] pot fi găsite în stațiile de bază celulare CDMA .

Note

  1. ↑ Introducere la Golomb Rulers de Mark Garry
  2. ↑ Solomon W. Golomb (link indisponibil) . Data accesului: 28 iulie 2007. Arhivat din original la 28 iulie 2007. 
  3. ↑ S. Sidon. Ein Satzuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen  (germană)  // Mathematische Annalen  : magazin. - 1932. - Bd. 106 . - S. 536-539 .
  4. ↑ Wallace C. Babcock. Interferența de intermodulație în sistemele radio/Frecvența de apariție și controlul prin selecția canalului  //  Jurnal tehnic al sistemului Bell : jurnal. - 1953. - Vol. 31 . - P. 63-73 .
  5. ↑ Golomb ruler table Arhivat 16 aprilie 2018 la Wayback Machine 
  6. ↑ Statistica proiectului OGR-24 . Consultat la 22 decembrie 2007. Arhivat din original la 17 februarie 2016.
  7. ↑ Statistica proiectului OGR-25 . Consultat la 22 decembrie 2007. Arhivat din original la 17 octombrie 2013.
  8. ↑ Statistica proiectului OGR-26 . Consultat la 1 noiembrie 2008. Arhivat din original pe 29 decembrie 2014.
  9. ↑ Statistica proiectului OGR-27 . Data accesului: 8 ianuarie 2010. Arhivat din original la 9 ianuarie 2014.
  10. ↑ Statistica proiectului OGR-28 . Consultat la 26 februarie 2014. Arhivat din original la 21 iulie 2015.

Vezi și

Link -uri