Викия

Математика

Линейка Голомба

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Файл:GolombRuler-Order4.png

В статье, даны общие сведения о математическом понятии, «Линейка Голомба»[1], названном в честь американского профессора Соломона Голомба [2].

Общие сведения Править

В математике, линейкой Голомба, назван набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки, нельзя найти два числа, разность между которыми, повторялось бы дважды.

Число делений на линейке называют её порядком, а наибольшее расстояние между двумя её делениями — длиной. Например, линейкой пятого порядка и длиной одиннадцать, является последовательность чисел 0 1 4 9 11. В некоторых источниках, линейки Голомба характеризуются расстояниями между делениями, а не абсолютными координатами делений, поэтому приведенная линейка будет выглядеть как 1-3-5-2 (первый ноль обычно опускают). Максимальное число пар, которые можно составить из делений линейки порядка N, вычисляется формулой: N*(N-1)/2.

Линейки, образованные путём последовательного сдвига, например, 1 4 9 11, или линейки с эквивалентными расстояниями между делениями, но расположенными в обратном порядке (зеркально-отражённые), например 0 2 7 10 11, считаются тривиальными. Поэтому наименьшее деление обычно соответствует нулю, а следующее деление располагают от него на наименьшем, из двух возможных расстоянии.

Совсем не обязательно, чтобы линейка Голомба могла измерить все расстояния в пределах её длины, однако если это так, то такую линейку называют — совершенной (Perfect Golomb Ruler — PGR). (см. ремарку на вкладке «править»)

Линейку Голобма называют оптимальной (Optimal Golomb Ruler — OGR), если короче линейки того же порядка не существует. Другими словами, линейку называют оптимальной, если значение её последнего деления, минимально для заданного порядка.

Создать линейку Голомба достаточно легко, но обнаружение и доказательство оптимальности линейки, в вычислительном отношении, является очень трудоёмким процессом. В настоящее время, способ получения оптимальной линейки Голомба произвольной длины N неизвестен, однако полагают, что эта задача является NP-труднойen: NP-hard»).

Одним из практических применений линейки Голомба, является использование её в фазированной антенной решётке радио-антенны, например в радиотелескопах. Антенны с конфигурацией [0 1 4 6] можно встретить в базовых станциях сотовой связи стандарта CDMA.

Самые известные оптимальные линейки Голомба Править

Наиболее известны 150 оптимальных линеек Голомба[3], однако доказательство их оптимальности есть только у 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

1 ноября 2004 года была подтверждена оптимальность линейки Голомба 24 порядка, открытой в 1967 году Джоном П. Робинсоном (John P. Robinson) и Артуром Д. Бернштейном (Arthur J. Bernstein). Это было сделано объединенными усилиями более чем 40 тысяч человек со всего мира в течение 4 лет и 110 дней, с помощью технологии распределённых вычислений, в рамках проекта некоммерческой организации Distributed.net [4]. В настоящий момент(лето 2007 года), этой же организацией ведётся работа над подтверждением оптимальности линейки Голомба 25 порядка — OGR-25, открытой М. Д. Аткинсоном (M. D. Atkinson) и А. Хассенкловером (A. Hassenklover) в 1984 году.

Порядок Довжина Поділки
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

Сноски Править

  1. Introduction To Golomb Rulers by Mark Garry
  2. Solomon W. Golomb
  3. The web page is devoted to Golomb rulers
  4. Distributed.net: Проект OGR

Ссылки в русской Википедии Править

Ссылки в английской Википедии Править

Внешние ссылки на русском Править

Внешние ссылки на английском Править

sr:Голомбов лењир sv:Golomblinjal

Викия-сеть

Случайная вики