Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Набор отметок вдоль линейки, таких что расстояние между любыми двумя парами отметок различно.
Set of marks along a ruler such that no two pairs of marks are the same distance apart
В математике линейка Голомба — это набор отметок в целочисленных позициях вдоль линейки, для которых расстояние между любыми двумя парами отметок различно. Количество отметок на линейке называется её порядком, а наибольшее расстояние между двумя отметками — её длиной. Трансляция и отражение линейки Голомба считаются тривиальными, поэтому наименьшая отметка обычно помещается в 0, а следующая — в меньшее из двух возможных значений. Линейки Голомба можно рассматривать как одномерный частный случай массивов Костаса. Линейка Голомба названа в честь Соломона В. Голомба, и независимо от него была открыта Софи Пиккар, которая также опубликовала ранние исследования этих множеств в 1939 году, сформулировав в виде теоремы утверждение о том, что две линейки Голомба с одинаковым набором расстояний должны быть конгруэнтны. Это оказалось неверным для линеек порядка шесть, но верно в остальных случаях. Не требуется, чтобы линейка Голомба могла измерять все расстояния до своей длины, но если это так, то она называется совершенной линейкой Голомба. Доказано, что совершенных линеек Голомба с пятью или более отметками не существует. В настоящее время сложность поиска оптимальных линеек Голомба (OGR) произвольного порядка n (где n задано в унарной системе) неизвестна. Ранее высказывались предположения, что это NP-трудная задача. Задачи, связанные с построением линеек Голомба, доказано являются NP-трудными, при этом отмечается, что ни одна известная NP-полная задача не имеет схожей природы с задачей поиска линеек Голомба.
In mathematics, a Golomb ruler is a set of marks at integer positions along a ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. Golomb rulers can be viewed as a one dimensional special case of Costas arrays. The Golomb ruler was named for Solomon W. Golomb and discovered independently by and Sophie Piccard also published early research on these sets, in 1939, stating as a theorem the claim that two Golomb rulers with the same distance set must be congruent. This turned out to be false for six point rulers, but true otherwise. There is no requirement that a Golomb ruler be able to measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proved that no perfect Golomb ruler exists for five or more marks. Currently, the complexity of finding optimal Golomb rulers (OGRs) of arbitrary order n (where n is given in unary) is unknown. In the past there was some speculation that it is an NP hard problem. Problems related to the construction of Golomb rulers are provably shown to be NP hard, where it is also noted that no known NP complete problem has similar flavor to finding Golomb rulers.
Выбор радиочастот
Линейки Голомба используются при выборе радиочастот для снижения влияния интермодуляционных помех в наземных и внеземных применениях.
Golomb rulers are used in the selection of radio frequencies to reduce the effects of intermodulation interference with both terrestrial and extraterrestrial applications.
Расположение радиоантенны
Изображения Голомба используются при проектировании фазированных антенных решеток. В радиоастрономии одномерные синтезированные массивы могут использовать конфигурацию линейки Голомба для достижения минимальной избыточности при дискретизации компонентов Фурье.
Golomb rulers are used in the design of phased arrays of radio antennas. In radio astronomy one dimensional synthesis arrays can have the antennas in a Golomb ruler configuration in order to obtain minimum redundancy of the Fourier component sampling.
Трансформаторы тока
Трансформаторы тока с несколькими коэффициентами трансформации используют линейки Голомба для определения точек отводов трансформатора.
Multi ratio current transformers use Golomb rulers to place transformer tap points.
Способы изготовления
Ряд методов построения создают асимптотически оптимальные линейки Голомба.
A number of construction methods produce asymptotically optimal Golomb rulers.
Строительство ErdősTurán
Следующая конструкция, предложенная Полом Эрдошем и Палом Тураном, позволяет построить линейку Голомба для любого нечётного простого числа p.
The following construction, due to Paul Erdős and Pál Turán, produces a Golomb ruler for every odd prime p.
Известные оптимальные линейки Голомба
В следующей таблице приведены все известные оптимальные линейки Голомба, за исключением тех, которые имеют отметки в обратном порядке. Первые четыре — идеальны.
The following table contains all known optimal Golomb rulers, excluding those with marks in the reverse order. The first four are perfect. Order Length Marks Proved Proof discovered by 1 0 0 1952 Wallace Babcock 2 1 0 1 1952 John P. Robinson and Arthur J. Bernstein 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 c. 1967 Mark Garry, David Vanderschel et al. (web project) 22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 1999 Mark Garry, David Vanderschel et al. (web project) 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 1999 Mark Garry, David Vanderschel et al. (web project) 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 distributed. net 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 distributed. net 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 distributed. net 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 distributed. net 28 585 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 585 distributed. net
The optimal ruler would have been known before this date; this date represents that date when it was discovered to be optimal (because all other rulers were proved to not be smaller). For example, the ruler that turned out to be optimal for order 26 was recorded on , but it was not known to be optimal until all other possibilities were exhausted on .
The following table contains all known optimal Golomb rulers, excluding those with marks in the reverse order. The first four are perfect. Order Length Marks Proved Proof discovered by 1 0 0 1952 Wallace Babcock 2 1 0 1 1952 John P. Robinson and Arthur J. Bernstein 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 c. 1967 Mark Garry, David Vanderschel et al. (web project) 22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 1999 Mark Garry, David Vanderschel et al. (web project) 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 1999 Mark Garry, David Vanderschel et al. (web project) 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 distributed. net 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 distributed. net 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 distributed. net 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 distributed. net 28 585 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 585 distributed. net
The optimal ruler would have been known before this date; this date represents that date when it was discovered to be optimal (because all other rulers were proved to not be smaller). For example, the ruler that turned out to be optimal for order 26 was recorded on , but it was not known to be optimal until all other possibilities were exhausted on .
Оптимальная линейка могла быть известна и до этой даты; указанная дата — это дата, когда она была *подтверждена* как оптимальная (поскольку все остальные линейки оказались не короче). Например, линейка, оказавшаяся оптимальной для порядка 26, была зарегистрирована , но её оптимальность была установлена только после того, как были исчерпаны все другие возможности .
The following table contains all known optimal Golomb rulers, excluding those with marks in the reverse order. The first four are perfect. Order Length Marks Proved Proof discovered by 1 0 0 1952 Wallace Babcock 2 1 0 1 1952 John P. Robinson and Arthur J. Bernstein 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 c. 1967 Mark Garry, David Vanderschel et al. (web project) 22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 1999 Mark Garry, David Vanderschel et al. (web project) 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 1999 Mark Garry, David Vanderschel et al. (web project) 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 distributed. net 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 distributed. net 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 distributed. net 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 distributed. net 28 585 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 585 distributed. net
The optimal ruler would have been known before this date; this date represents that date when it was discovered to be optimal (because all other rulers were proved to not be smaller). For example, the ruler that turned out to be optimal for order 26 was recorded on , but it was not known to be optimal until all other possibilities were exhausted on .