OGR-калькулятор
Personal proxy
Proxy сегодня
Если вы хотите видеть свою статистику даже когда Dnet лежит, настраивайтесь на этот прокси-сервер: rc5.pp.ru:2064 и увидите свои блоки сразу после отправки. Статистика по участникам за больший период обновляется раз в час.
Disclaimer
Ваш e-mail адрес, указанный в настройках dnetc.ini будет виден всем
на страницах со статистикой.
О проекте Distributed.Net
по поиску Оптимальных линеек Голомба (OGR-25)
Что такое Линейки Голомба?
В математике термин "Линейки Голомба" означает набор целых положительных чисел (т.е. натуральных), таких, что у всех возможных пар этих чисел разность отличается, т.е. разности этих чисел не повторяются. Это можно себе представить наглядно в виде линейки с делениями, построеннуой таким образом, что все расстояния между любыми делениями разные. Оптимальная Линейка Голомба (Optimal Golomb Ruler, OGR) - это самая короткая возможная линейка для заданного числа делений.Однако, сложность поиска (и доказательства) OGR растет экспоненциально с увеличением числа делений, поэтому в Distributed.net привлекли на помощь энтузиастов - пользователей интернет для поиска OGR с числом делений 24 и более.
Линейки Голомба названы в честь Соломона Голомба (Solomon W. Golomb) - профессора математики, специалиста по комбинаторике, теории чисел, теории кодирования и связи. Голомб также занимался математическими играми и головоломками, являлся постоянным автором колонки "Математические игры" журнала Scientific American. Оптимальные линейки Голомба имеют много приложений, включая расположение детекторов в рентгеновской кристаллографии и радиоастрономии.
Линейка Голомба - это способ расположения делений на линейке, при котором каждая пара делений измеряет уникальный интервал. Вот линейка Голомба с пятью делениями:
| | | | | 0 1 4 9 11
Числа около делений означают расстояние от левого края. Длина этой линейки равна 11, и она является одной из двух самых коротких линеек Голомба с пятью делениями. Деления второй линейки стоят на отметках 0, 3, 4, 9, и 11. (Зеркальные отражения этих двух линеек, 0, 2, 7, 10, 11 и 0, 2, 7, 8, 11, также оптимальны. Обычно указывают только одну из симметричных линеек).
Вы можете убедиться, что показанная наверху линейка является линейкой Голомба, записав таблицу всех пар делений и соответствующие расстояния:
| Деление 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 делением:
2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4
James B. Shearer собрал список все лучших известных Линеек Голомба до 150 делений.
К сожалению, трудоемкость поиск OGR возрастает экспоненциально с увеличением числа делений.
Интерес к соревнованию имеет несколько составляющих:
- Добровольные участники для повышения соревновательного интереса объединяются в команды. На сервере статистики Distributed.net ежедневно обновляется текущее положение команд. Здесь вы увидите более подробную статистику ведущих команд.
- Если команда, или просто несколько компьютеров работают через специальный собственный прокси-сервер (personal proxy), можно наблюдать за статистикой клиентов, работающих через него.
- Еще один аспект соревнования в проектах Distributed.net - конкуренция стран. Приятно осознавать, что твой личный вклад попадает не только в копилку команды и подкоманды, но и в общую копилку страны.
Какие при этом затраты и усилия участника? Практически никаких. Скачать
и установить программу-клиент, которая запускается с самым пониженным
приоритетом, т.е. в фоновом режиме. При этом можно заниматься своими обычными
делами на компьютере, а программа будет утилизировать неиспользуемое процессорное
время. Если вы запускаете какую-нибудь счетную задачу, которая использует
процессор - клиент dnet будет стоять и ждать. Можно даже играть в подвижные
трехмерные игры, вы вряд ли заметите присутствие этой программы.
Вскоре после начала счета и отправки первых блоков (утром следующего дня)
уже можно найти себя на сервере статистики, получить пароль, указать свою
страну, чтобы участвовать в соревновании стран, записаться в выбранную
команду, периодически следить за своим продвижением в рейтинге и т.д.
У начинающих, т.е. только что подключившихся участников часто возникает проблема правильной настройки клиента и учета блоков, в какой день сколько блоков было посчитано и отправлено. Самый простой способ - это настроиться на заведомо стабильно работающий прокси-сервер со статистикой. Например на этот rc5.pp.ru:2064. Можно посмотреть и текущее состояние прокси-сервера, сколько блоков во входном и выходном буферах. Настройки в dnetc.ini такие:
[networking] autofindkeyserver=no keyserver=rc5.pp.ru nofallback=true [misc] project-priority=OGR,RC5=0,CSC=0,DES=0
Ссылки по теме
- Greg Hewgill's technical OGR information page and his plan file
- The previous OGR Effort (OGR-20, -21, -22, and -23)
- James B. Shearer's list of best known Golomb rulers (up to 150 marks) and his main Golomb page
- Lloyd Miller's listing of more best known Golomb rulers and other information.
- William T. Rankin's web page describing his master's project involving the distributed search of OGR-17, -18, and -19
- Stephen Wayne Soliday's paper on a Genetic Algorithm for Near Optimal Golomb Rulers
- David Fowler's page on Genetic Sparse Rulers [similar to Golomb Rulers]
- D. Kent Freeman paper abstract on the Similarity of Maximizing Irregularity and Solving Golomb Rulers
- A CGI server that tests for golombness if you enter a 20 mark ruler. Based out of Switzerland's ROSE university, titled: Concours Bases de l'algorithmique
- Definition of NP-complete problems can be found at http://www.wikipedia.com/wiki/NP-complete.