Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Лінійка Голомба в теорії чисел набір невід ємних цілих чисел розташованих у вигляді поділок на уявній лінійці таким чино

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

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

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

image
Лінійка Голомба 4-го порядку довжиною 6. Ця лінійка оптимальна і досконала.

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

Визначення

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

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

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

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

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

Створити лінійку Голомба відносно просто, але доведення оптимальності лінійки є трудомістким обчислювальним процесом. Нині спосіб отримання оптимальної лінійки Голомба довільної довжини n невідомий, проте вважають, що ця задача є NP-складною.

Відомі оптимальні лінійки Голомба

Відомі лінійки Голомба до 150-го порядку, однак оптимальність доведено тільки для лінійок порядку, що не перевищує 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 некомерційної організації distributed.net.

Оптимальну лінійку Голомба 25-го порядку знайшли 1984 року Аткінсон (MD Atkinson) і Хассенкловер (A. Hassenklover). Доведення її оптимальності завершено за 3006 днів 24 жовтня 2008 року в рамках проєкту OGR-25.

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

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

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

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

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

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

Примітки

  2. . Архів оригіналу за 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 (8 Juli). — S. 536—539.
  4. Wallace C. Babcock. Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection // [en] : journal. — 1953. — Vol. 31 (8 July). — P. 63—73.
  5. Golomb ruler table [ 16 квітня 2018 у Wayback Machine.](англ.)
  6. . Архів оригіналу за 17 лютого 2016. Процитовано 17 червня 2021.
  7. . Архів оригіналу за 17 жовтня 2013. Процитовано 17 червня 2021.
  8. . Архів оригіналу за 29 грудня 2014. Процитовано 17 червня 2021.
  9. . Архів оригіналу за 9 січня 2014. Процитовано 17 червня 2021.
  10. . Архів оригіналу за 21 липня 2015. Процитовано 17 червня 2021.

Див. також

Посилання

  • Досконалі й оптимальні лінійки [ 13 вересня 2019 у Wayback Machine.] (рос.)
  • Perfect and Optimal Rulers [ 3 липня 2020 у Wayback Machine.] (англ.)
  • Mark Garry.
  • Ed Pegg Jr.
  • Weisstein, Eric W. Лінійка Голомба(англ.) на сайті Wolfram MathWorld.
  • James B. Shearer. Golomb ruler pages [ 25 грудня 2017 у Wayback Machine.]

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Linijka Golomba v teoriyi chisel nabir nevid yemnih cilih chisel roztashovanih u viglyadi podilok na uyavnij linijci takim chinom sho vidstan mizh bud yakimi dvoma podilkami ye unikalnoyu Inshimi slovami na vsij dovzhini linijki nemozhlivo znajti dva chisla riznicya mizh yakimi povtoryuvalasya b dvichi Linijka Golomba 4 go poryadku dovzhinoyu 6 Cya linijka optimalna i doskonala Nazvani na chest amerikanskogo matematika Solomona Golomba hocha pershi zgadki podibnih konstrukcij zustrichayutsya v ranishih publikaciyah en i ViznachennyaPriklad konferenc zalu z peregorodkami na vidstanyah proporcijnih podilkam linijki Golomba 0 2 7 8 11 sho dozvolyaye otrimati zali 10 riznih rozmiriv Chislo podilok na linijci Golomba nazivayut yiyi poryadkom a najbilshu vidstan mizh dvoma yiyi podilkami dovzhinoyu Napriklad linijka z podilkami 0 1 4 9 11 ye linijkoyu p yatogo poryadku dovzhini 11 Inodi linijki Golomba opisuyut vidstanyami mizh susidnimi podilkami a ne absolyutnimi koordinatami podilok tomu navedena vishe linijka mozhe viglyadati yak 1 3 5 2 Najbilshe chislo par yaki mozhna sklasti z podilok linijki poryadku n dorivnyuye chislu spoluchen n2 n n 1 2 displaystyle tbinom n 2 tfrac n n 1 2 Linijki otrimani z danoyi zsuvom kozhnoyi podilki na fiksovane chislo napriklad 1 2 5 10 12 abo perelichennyam podilok linijki v zvorotnomu poryadku dzerkalno vidbiti napriklad 0 2 7 10 11 vvazhayutsya ekvivalentnimi Tomu v kanonichnomu podanni linijki Golomba najmensha podilka vidpovidaye nulovij koordinati a nastupna podilka roztashovuyetsya na najmenshij z dvoh mozhlivih vidstanej Linijka Golomba ne zavzhdi pridatna dlya vimiryuvannya vsih cilochiselnih vidstanej u mezhah yiyi dovzhini prote yaksho pridatna to taku linijku nazivayut doskonaloyu angl Perfect Golomb Ruler PGR Doskonali linijki isnuyut tilki dlya poryadkiv menshih vid p yati Linijku Golomba nazivayut optimalnoyu angl Optimal Golomb Ruler OGR yaksho ne isnuye korotshih linijok togo zh poryadku Inshimi slovami linijka ye optimalnoyu yaksho v kanonichnomu podanni znachennya yiyi ostannoyi podilki minimalno mozhlive Stvoriti linijku Golomba vidnosno prosto ale dovedennya optimalnosti linijki ye trudomistkim obchislyuvalnim procesom Nini sposib otrimannya optimalnoyi linijki Golomba dovilnoyi dovzhini n nevidomij prote vvazhayut sho cya zadacha ye NP skladnoyu Vidomi optimalni linijki GolombaVidomi linijki Golomba do 150 go poryadku odnak optimalnist dovedeno tilki dlya linijok poryadku sho ne perevishuye 27 V tablici navedeno vsi vidomi nini linijki Golomba v kanonichnomu podanni dlya yakih dovedeno optimalnist Poryadok Dovzhina Podilki Promizhki1 0 0 02 1 0 1 13 3 0 1 3 1 24 6 0 1 4 6 1 3 25 11 0 1 4 9 11 0 2 7 8 11 1 3 5 2 2 5 1 36 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 37 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 38 34 0 1 4 9 15 22 32 34 1 3 5 6 7 10 29 44 0 1 5 12 25 27 35 41 4410 55 0 1 6 10 23 26 34 41 53 5511 72 0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 7212 85 0 2 6 24 29 40 43 55 68 75 76 8513 106 0 2 5 25 37 43 59 70 85 89 98 99 10614 127 0 4 6 20 35 52 59 77 78 86 89 99 122 12715 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 15116 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 17717 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 19918 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 21619 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 24620 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 28321 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 33322 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 35623 372 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 37224 425 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 42525 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 48026 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 49227 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 553Vidshukannya optimalnih linijok GolombaOptimalnu linijku Golomba 24 go poryadku znajshli 1967 roku Dzhon Robinson John P Robinson ta Artur Bernshtejn Arthur J Bernstein Odnak yiyi optimalnist dovedeno lishe 1 listopada 2004 roku spilnimi zusillyami bilsh nizh 40 tisyach osib z usogo svitu protyagom 4 rokiv i 110 dniv u ramkah proyektu rozpodilenih obchislen OGR 24 nekomercijnoyi organizaciyi distributed net Optimalnu linijku Golomba 25 go poryadku znajshli 1984 roku Atkinson MD Atkinson i Hassenklover A Hassenklover Dovedennya yiyi optimalnosti zaversheno za 3006 dniv 24 zhovtnya 2008 roku v ramkah proyektu OGR 25 Dovedennya optimalnosti linijki Golomba 26 go poryadku zaversheno za 24 dni 24 lyutogo 2009 roku v ramkah proyektu OGR 26 Dovedennya optimalnosti linijki Golomba 27 go poryadku zaversheno za tisyachu visimsot dvadcyat dva dni 19 lyutogo 2014 roku v ramkah proyektu OGR 27 Nad dovedennyam optimalnosti linijki Golomba 28 go poryadku pracyuye proyekt OGR 28 yakij na 10 grudnya 2020 roku vikonano na 78 41 Takozh poshukom optimalnih linijok Golomba zajmayetsya proyekt rozpodilenih obchislen ZastosuvannyaOdnim z praktichnih zastosuvan linijki Golomba ye vikoristannya yiyi u fazovanih antennih reshitkah napriklad u radioteleskopah Anteni z konfiguraciyeyu 0 1 4 6 mozhna zustriti v bazovih stanciyah stilnikovogo zv yazku standartu CDMA Primitki Arhiv originalu za 28 lipnya 2007 Procitovano 28 lipnya 2007 S Sidon Ein Satzuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier Reihen Mathematische Annalen magazin 1932 Bd 106 8 Juli S 536 539 Wallace C Babcock Intermodulation Interference in Radio Systems Frequency of Occurrence and Control by Channel Selection en journal 1953 Vol 31 8 July P 63 73 Golomb ruler table 16 kvitnya 2018 u Wayback Machine angl Arhiv originalu za 17 lyutogo 2016 Procitovano 17 chervnya 2021 Arhiv originalu za 17 zhovtnya 2013 Procitovano 17 chervnya 2021 Arhiv originalu za 29 grudnya 2014 Procitovano 17 chervnya 2021 Arhiv originalu za 9 sichnya 2014 Procitovano 17 chervnya 2021 Arhiv originalu za 21 lipnya 2015 Procitovano 17 chervnya 2021 Div takozhMasiv Kostasa en Paralelni obchislyuvalni sistemi Rozpodileni obchislennyaPosilannyaDoskonali j optimalni linijki 13 veresnya 2019 u Wayback Machine ros Perfect and Optimal Rulers 3 lipnya 2020 u Wayback Machine angl Mark Garry Ed Pegg Jr Weisstein Eric W Linijka Golomba angl na sajti Wolfram MathWorld James B Shearer Golomb ruler pages 25 grudnya 2017 u Wayback Machine

Дата публікації:
Топ