Golombov lenjir
Golombov lenjir, koji je dobio ime po Solomonu V. Golombu, je skup oznaka na celobrojnim pozicijama duž imaginarnog lenjira, takvih da nijedna dva para oznaka nisu na podjednakoj razdaljini. Broj oznaka na lenjiru predstavlja njegov red, a najveća razdaljina između dve oznake je njegova dužina. Translacija i refleksija Golombovog lenjira je trivijalna, pa se obično najmanja oznaka postavlja na 0 a sledeća na manju od njene dve moguće pozicije.
Nije obavezno da Golombov lenjir bude u mogućnosti da da meri sve razdaljine od 0 do svoje dužine, ali ako je u stanju, onda je to savršeni Golombov lenjir. Dokazano je da ne postoji savršen Golombov lenjir reda većeg od četiri. Golombov lenjir je optimalan ako nepostoji kraći Golombov lenjir istog reda. Pravljenje Golombovog lenjira je lako, ali nalaženje optimalnog lenjira datog reda je računski veoma zahtevan proces. Projekat Distributed.net je završio distribuiranu paralelnu potragu za optimalnim Golombovim lenjirima reda 24, potvrdivši pretpostavljenog kandidata, a trenutno traje potraga za optimalnim lenjirom reda 25.
Jedna praktična primena Golombovih lenjira je u dizajnu radio antena.
Trenutno nije poznata kompleksnost nalaženja optimalnog Golombovog lenjira proizvoljne dužine, ali se veruje da spada u red NP-teških problema.[1]
Poznati optimalni Golombovi lenjiri[uredi | uredi izvor]
Sledeća tabela sadrži sve poznate optimalne Golombove lenjire (isključujući one koje su ekvivalentne ovde navedenim sa oznakama u suprotnom redosledu). Tabela je kompletna, i sadrži lenjire do reda 24.
red | dužina | oznake |
---|---|---|
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 |
Literatura[uredi | uredi izvor]
- Gardner, Martin (1972). „Mathematical games”. Scientific American: 108—112.
- ^ Modular and Regular Golomb Rulers, Pristupljeno 31. 3. 2013.
Vidi još[uredi | uredi izvor]
Spoljašnje veze[uredi | uredi izvor]
- http://www.research.ibm.com/people/s/shearer/grule.html Arhivirano na sajtu Wayback Machine (25. decembar 2017)
- http://www.distributed.net/ogr/
- https://web.archive.org/web/19981203104221/http://members.aol.com/golomb20/
- https://web.archive.org/web/20041117013647/http://www.maa.org/editorial/mathgames/mathgames_11_15_04.html
- http://www.research.ibm.com/people/s/shearer/grtab.html Arhivirano na sajtu Wayback Machine (16. april 2018)
- http://www.luschny.de/math/rulers/prulers.html