| rdfs:comment
| - В математике, линейкой Голомба, назван набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки, нельзя найти два числа, разность между которыми, повторялось бы дважды. Совсем не обязательно, чтобы линейка Голомба могла измерить все расстояния в пределах её длины, однако если это так, то такую линейку называют — совершенной (Perfect Golomb Ruler — PGR). (см. ремарку на вкладке «править»)
|
| abstract
| - В математике, линейкой Голомба, назван набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки, нельзя найти два числа, разность между которыми, повторялось бы дважды. Число делений на линейке называют её порядком, а наибольшее расстояние между двумя её делениями — длиной. Например, линейкой пятого порядка и длиной одиннадцать, является последовательность чисел 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.
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)