OGR-NG, Загальна інформація Налаштування

[Death]

Проект "OGR-NG"

 

Официальный сайт
Официальная статистика по команде "Ukraine"
Статистика по команде на free-dc
Статья на Wikipedia
Прогресс

 

Дата основания команды - 13.04.1999 Капитан - Daugava

 

О проекте:

Что такое Линейки Голомба?
В математике термин "Линейки Голомба" означает набор целых положительных чисел (т.е. натуральных), таких, что у всех возможных пар этих чисел разность отличается, т.е. разности этих чисел не повторяются. Это можно себе представить наглядно в виде линейки с делениями, построенной таким образом, что все расстояния между любыми делениями разные. Оптимальная Линейка Голомба (Optimal Golomb Ruler, OGR) - это самая короткая возможная линейка для заданного числа делений. Однако, сложность поиска (и доказательства) OGR растет экспоненциально с увеличением числа делений, поэтому в Distributed.net привлекли на помощь энтузиастов - пользователей интернет для поиска OGR с числом делений 26 и более.

Линейки Голомба названы в честь Соломона Голомба (Solomon W. Golomb) - профессора математики, специалиста по комбинаторике, теории чисел, теории кодирования и связи. Голомб также занимался математическими играми и головоломками, являлся постоянным автором колонки "Математические игры" журнала Scientific American. Оптимальные линейки Голомба имеют много приложений, включая расположение детекторов в рентгеновской кристаллографии и радиоастрономии.

Линейка Голомба - это способ расположения делений на линейке, при котором каждая пара делений измеряет уникальный интервал. Вот линейка Голомба с пятью делениями:

CODE

| |     |         |   |
0 1     4         9   11

Числа около делений означают расстояние от левого края. Длина этой линейки равна 11, и она является одной из двух самых коротких линеек Голомба с пятью делениями. Деления второй линейки стоят на отметках 0, 3, 4, 9, и 11. (Зеркальные отражения этих двух линеек, 0, 2, 7, 10, 11 и 0, 2, 7, 8, 11, также оптимальны. Обычно указывают только одну из симметричных линеек).

Вы можете убедиться, что показанная наверху линейка является линейкой Голомба, записав таблицу всех пар делений и соответствующие расстояния:

CODE

Деление 1      Деление 2      Расстояние
0                   1               1
0                   4               4
0                   9               9
0                  11               11
1                   4               3
1                   9               8
1                  11               10
4                   9               5
4                  11               7
9                  11               2

Заметьте, что в правом столбце расстояния не повторяются. Кроме того, отсутствует расстояние 6, но это неважно, т.к. линейка Голомба не должна измерять все расстояния, главное, чтобы они были все разные.

"Оптимизация" линеек Голомба означает найти самую короткую, не допуская повторения измеряемых расстояний. Две вышеприведенные линейки является оптимальными.

Линейки Голомба обычно характеризуются именно расстояниями - длиной делений, а не абсолютными координатами делений, как на вышеприведенной диаграмме. Приведенная линейка будет выглядеть как 1-3-5-2 (иногда это записывают 0-1-3-5-2, но первый ноль обычно опускают).

Например, вот известная оптимальная линейка с 21 делением:

CODE

2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4

Где могут пригодиться найденные OGR?
OGR имеют много практически приложений, такие как расположение сенсоров в рентгеноскопической кристаллографии, радиоастрономия и т.м. Они также играют важную роль в комбинаторике, теории кодирования и коммуникация. Доктор Голомб одним из первых проанализировал их использование в этих областях.

Це повідомлення відредагував egorio: Jan 24 2012, 10:17