Wikipedia

Golomblinjal

Innen matematikken er en Golomblinjal ett sett merker på heltallsposisjoner langs en imaginær linjal, som er plassert slik at alle par av merker står med forskjellig avstand. Antallet markører på linjalen er dens orden, og den lengste distansen mellom to av markørene er dens lengde. Translasjon og refleksjon av en Golomblinjal anses som likegyldig, slik at den minste markøren starter som regel på 0, og den neste markøren settes som regel på den laveste av sine mulige verdier.

Golomblinjal med orden 4 og lengde 6. Denne linjalen er både optimal og perfekt.

Golomblinjalen har fått sitt navn etter Solomon W. Golomb, men har blitt uavhengig oppdaget av Sidon[1] og Babcock[2]

Det er ikke påkrevet at en Golomblinjal skal kunne gi alle distansene opp til dens lengde, men om den gjør det, så kalles den perfekt. Det har blitt bevist at det ikke eksisterer perfekte Golomblinjaler for fem eller flere markører[3]. En Golomblinjal er optimal om det ikke finnes kortere Golomblinjaler med samme orden (antall markører). Å lage Golomblinjaler er enkelt, men å finne den optimale Golomblinjalen for en gitt orden er beregningsmessig meget utfordrende. Distributed.net har gjennomført massivt distriuerte parallelle søk for optimale orden-24[4], orden-25[5], orden-26[6] og orden-27[7] Golomblinjaler, og har bekreftet de anslåtte optimale kandidatene[8][9] [10]. Distributed.net har også planlagt å finne/bekrefte en optimal Golomblinjal for orden-28. Det var forventet at Golomblinjalene for orden-27 og orden-28 tok kortere tid å finne/bekrefte enn de foregående prosjektene, grunnet oppdagelsen av forbedrede algoritmer[11].

En praktisk tilnærming til bruk av Golomblinjaler er innen design og utforming av faseordnede radioantenner slik som radioteleskop.

For tiden så er kompleksiteten i å finne en optimal Golomblinjal for en vilkårlig orden-n ukjent, men er oppfattet å være et NP-vanskelig problem[3]

Kjente optimale Golomblinjaler rediger

Den følgende tabellen inneholder alle kjente, verifiserte, optimale Golomblinjaler, hvor de som har markører i reversert orden er utelatt.

orden lengde markører Bevist[*] Bevis funnet av
1 0 0 1952[12] Wallace Babcock
2 1 0 1 1952[12] Wallace Babcock
3 3 0 1 3 1952[12] Wallace Babcock
4 6 0 1 4 6 1952[12] Wallace Babcock
5 11 0 1 4 9 11
0 2 7 8 11 		ca. 1967[13] John P. Robinson and Arthur J. Bernstein
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 		ca. 1967[13] John P. Robinson and Arthur J. Bernstein
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 		ca. 1967[13] John P. Robinson and Arthur J. Bernstein
8 34 0 1 4 9 15 22 32 34 1972[13] William Mixon
9 44 0 1 5 12 25 27 35 41 44 1972[13] William Mixon
10 55 0 1 6 10 23 26 34 41 53 55 1972[13] William Mixon
11 72 0 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72 		1972[13] William Mixon
12 85 0 2 6 24 29 40 43 55 68 75 76 85 1972[13] John P. Robinson
13 106 0 2 5 25 37 43 59 70 85 89 98 99 106 1981[13] John P. Robinson
14 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127 1985[13] James B. Shearer
15 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151 1985[13] James B. Shearer
16 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177 1986[13] James B. Shearer
17 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199 1983[13] W. Olin Sibert
18 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216 1993[13] W. Olin Sibert
19 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246 1994[13] Apostolos Dollas, William T. Rankin and David McCracken
20 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283 1997?[13] Mark Garry, David Vanderschel et al. (web project)
21 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333 8. mai 1998[14] Mark Garry, David Vanderschel et al. (web project)
22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 1999[13] Mark Garry, David Vanderschel et al. (web project)
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 1999[13] Mark Garry, David Vanderschel et al. (web project)
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 13. oktober 2004 distributed.net
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 25. oktober 2008 distributed.net
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 24. februar 2009 distributed.net
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 553 19. februar 2014 distributed.net

^ *  Den optimale linjalen ble oppdaget før denne datoen. Denne datoen representerer tidspunktet da linjalen ble funnet å være optimal (fordi alle andre varianter beviselig ikke var mindre).

Referanser rediger

  1. ^ S. Sidon, "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen", Mathematische Annalen 106 (1932), pp. 536–539
  2. ^ Wallace C. Babcock. "Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection", Bell System Technical Journal 31 (1953), pp. 63–73.
  3. ^ a b «Modular and Regular Golomb Rulers». 
  4. ^ «stats.distributed.net - OGR-24 Overall Project Stats». Besøkt 27. mars 2008. 
  5. ^ «stats.distributed.net - OGR-25 Overall Project Stats». Besøkt 22. september 2008. 
  6. ^ «stats.distributed.net - OGR-26 Overall Project Stats». Besøkt 2. mars 2009. 
  7. ^ http://blogs.distributed.net/2014/02/25/16/09/mikereed/
  8. ^ «distributed.net - .plan archives». Besøkt 27. mars 2008. 
  9. ^ «distributed.net - .plan archives 2». Besøkt 26. oktober 2008. 
  10. ^ «distributed.net - .plan archives 3». Besøkt 2. mars 2009. 
  11. ^ http://n0cgi.distributed.net/cgi/planarc.cgi?user=bovine&plan=2008-10-26.09:52
  12. ^ a b c d http://mathpuzzle.com/MAA/30-Rulers%20and%20Arrays/mathgames_11_15_04.html
  13. ^ a b c d e f g h i j k l m n o p q r «table of lengths of shortest known rulers». IBM. Arkivert fra originalen 16. april 2018. Besøkt 28. november 2013. 
  14. ^ «In Search Of The Optimal 20 & 21 Mark Golomb Rulers (archived)». Mark Garry, David Vanderschel, et al. Arkivert fra originalen 6. desember 1998. 

Se også rediger

Eksterne lenker rediger

Hentet fra «https://no.wikipedia.org/w/index.php?title=Golomblinjal&oldid=23313858»