Лінійка Голомба

Матеріал з testwiki
Перейти до навігації Перейти до пошуку
Лінійка Голомба 4-го порядку довжиною 6. Ця лінійка оптимальна і досконала.

Лінійка Голомба в теорії чисел — набір невід'ємних цілих чисел, розташованих у вигляді поділок на уявній лінійці таким чином, що відстань між будь-якими двома поділками є унікальною. Іншими словами, на всій довжині лінійки неможливо знайти два числа, різниця між якими повторювалася б двічі[1].

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

Визначення

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

Число поділок на лінійці Голомба називають її порядком, а найбільшу відстань між двома її поділками — довжиною. Наприклад, лінійка з поділками 0 1 4 9 11 є лінійкою п'ятого порядку довжини 11. Іноді лінійки Голомба описують відстанями між сусідніми поділками, а не абсолютними координатами поділок, тому наведена вище лінійка може виглядати як 1-3-5-2. Найбільше число пар, які можна скласти з поділок лінійки порядку n, дорівнює числу сполучень (n2)=n(n−1)2.

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

Лінійка Голомба не завжди придатна для вимірювання всіх цілочисельних відстаней у межах її довжини, проте якщо придатна, то таку лінійку називають досконалою (Шаблон:Lang-en, PGR). Досконалі лінійки існують тільки для порядків, менших від п'яти.

Лінійку Голомба називають оптимальною (Шаблон:Lang-en, 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 170 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 42 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 року Аткінсон (MD Atkinson) і Хассенкловер (A. Hassenklover). Доведення її оптимальності завершено за 3006 днів 24 жовтня 2008 року в рамках проєкту OGR-25[7].

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

Доведення оптимальності лінійки Голомба 27-го порядку завершено за тисячу вісімсот двадцять два дні 19 лютого 2014 року в рамках проєкту OGR-27[9].

Над доведенням оптимальності лінійки Голомба 28-го порядку працює проєкт OGR-28, який на 10 грудня 2020 року виконано на 78,41 %[10].

Також пошуком оптимальних лінійок Голомба займається проєкт розподілених обчислень yoyo@home.

Застосування

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

Примітки

Шаблон:Reflist

Див. також

Посилання

  1. ↑ Introduction To Golomb Rulers by Mark Garry
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Стаття
  4. ↑ Шаблон:Стаття
  5. ↑ Golomb ruler table Шаблон:WebarchiveШаблон:Ref-en
  6. ↑ Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite web
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Лінійка_Голомба&oldid=9105