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

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

Линейка Голомба 4-го порядка длиной 6. Эта линейка оптимальна и совершенна.

Названы в честь американского математика Соломона Голомба[2], хотя первые упоминания подобных конструкций встречаются в более ранних публикациях Сидона[3] и Бэбкока[4].

Определения
Пример конференц-зала с перегородками на расстояниях пропорциональных делениям линейки Голомба [0, 2, 7, 8, 11], что позволяет получить залы 10 различных размеров.

Число делений на линейке Голомба называют её порядком, а наибольшее расстояние между двумя её делениями — длиной. Например, линейка с делениями 0 1 4 9 11 является линейкой пятого порядка длины 11. Иногда линейки Голомба описываются расстояниями между соседними делениями, а не абсолютными координатами делений, поэтому приведённая выше линейка будет выглядеть как 1-3-5-2. Максимальное число пар, которые можно составить из делений линейки порядка n, равно числу сочетаний .

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

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

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

Создать линейку Голомба относительно просто, но вот доказательство оптимальности линейки является трудоёмким вычислительным процессом. В настоящее время способ получения оптимальной линейки Голомба произвольной длины n неизвестен, однако полагают, что эта задача является NP-трудной.

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

Известны линейки Голомба до 150-го порядка[5], однако оптимальность доказана только для линеек порядка, не превышающего 27. Следующая таблица содержит все известные на сегодняшний день линейки Голомба в каноническом представлении, для которых доказана оптимальность.

Порядок Длина Деления Промежутки
1 0 0 0
2 1 0 1 1
3 3 0 1 3 1 2
4 6 0 1 4 6 1 3 2
5 11 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
8 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
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
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

Нахождение оптимальных линеек Голомба

Оптимальная линейка Голомба 24-го порядка была найдена в 1967 году Джоном Робинсоном (John P. Robinson) и Артуром Бернштейном (Arthur J. Bernstein). Однако её оптимальность была доказана лишь 1 ноября 2004 года объединёнными усилиями более чем 40 тысяч человек со всего мира в течение 4 лет и 110 дней в рамках проекта распределённых вычислений OGR-24[6] некоммерческой организации distributed.net.

Оптимальная линейка Голомба 25-го порядка была найдена в 1984 году Аткинсоном (M. D. Atkinson) и Хассенкловером (A. Hassenklover). Доказательство её оптимальности было завершено за 3006 дней 24 октября 2008 года в рамках проекта OGR-25[7].

Доказательство оптимальности линейки Голомба 26-го порядка было завершено за 24 дня 24 февраля 2009 года в рамках проекта OGR-26[8].

Доказательство оптимальности линейки Голомба 27-го порядка было завершено за 1822 дня 19 февраля 2014 года в рамках проекта OGR-27[9].

Доказательством оптимальности линейки Голомба 28-го порядка занимается проект OGR-28, который на 4 сентября 2021 года выполнен на 87,87%[10].

Также поиском оптимальных линеек Голомба занимается проект распределённых вычислений yoyo@home.

Применения

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

Примечания
  1. Introduction To Golomb Rulers by Mark Garry
  2. Solomon W. Golomb (недоступная ссылка). Дата обращения: 28 июля 2007. Архивировано 28 июля 2007 года.
  3. S. Sidon. Ein Satzuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen (нем.) // Mathematische Annalen : magazin. — 1932. — Bd. 106. — S. 536—539.
  4. Wallace C. Babcock. Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection (англ.) // Bell System Technical Journal : journal. — 1953. — Vol. 31. — P. 63—73.
  5. Golomb ruler table Архивная копия от 16 апреля 2018 на Wayback Machine (англ.)
  6. Статистика проекта OGR-24
  7. Статистика проекта OGR-25
  8. Статистика проекта OGR-26
  9. Статистика проекта OGR-27
  10. Статистика проекта OGR-28

См. также

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.