Голомбов лењир

С Википедије, слободне енциклопедије
Голомбов лењир реда 4 и дужине 6. Овај лењир је и оптималан и савршен.

Голомбов лењир, који је добио име по Соломону В. Голомбу, је скуп ознака на целобројним позицијама дуж имагинарног лењира, таквих да ниједна два пара ознака нису на подједнакој раздаљини. Број ознака на лењиру представља његов ред, а највећа раздаљина између две ознаке је његова дужина. Транслација и рефлексија Голомбовог лењира је тривијална, па се обично најмања ознака поставља на 0 а следећа на мању од њене две могуће позиције.

Није обавезно да Голомбов лењир буде у могућности да да мери све раздаљине од 0 до своје дужине, али ако је у стању, онда је то савршени Голомбов лењир. Доказано је да не постоји савршен Голомбов лењир реда већег од четири. Голомбов лењир је оптималан ако непостоји краћи Голомбов лењир истог реда. Прављење Голомбовог лењира је лако, али налажење оптималног лењира датог реда је рачунски веома захтеван процес. Пројекат Distributed.net је завршио дистрибуирану паралелну потрагу за оптималним Голомбовим лењирима реда 24, потврдивши претпостављеног кандидата, а тренутно траје потрага за оптималним лењиром реда 25.

Једна практична примена Голомбових лењира је у дизајну радио антена.

Тренутно није позната комплексност налажења оптималног Голомбовог лењира произвољне дужине, али се верује да спада у ред НП-тешких проблема.[1]

Познати оптимални Голомбови лењири[уреди | уреди извор]

Следећа табела садржи све познате оптималне Голомбове лењире (искључујући оне које су еквивалентне овде наведеним са ознакама у супротном редоследу). Табела је комплетна, и садржи лењире до реда 24.

ред дужина ознаке
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

Литература[уреди | уреди извор]

  1. ^ Modular and Regular Golomb Rulers, Приступљено 31. 3. 2013.

Види још[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Голомбов_лењир&oldid=26852861”