Project OGR

From distributed.net
Jump to: navigation, search

OGR

クライアントとプロキシは OGRプロジェクトへの対応 をほとんどのプラットホームで既に終えています。最新のクライアント を今すぐダウンロードしてインストールしてください。また、FAQ-o-Matic にOGR関係のFAQもご用意いたしました。数名の参加者から巨大なOGR-25スタブの存在が報告されていますが、これはかなり稀な例です。 この速度に関する詳細はOGR統計ページ にてご覧いただけます。

もしあなたがdistributed.netクライアントの操作などでテクニカルサポートが必要なら、help@distributed.net宛にメールを送信してください(英語)。その質問への回答が既になされている場合もありますので、 FAQ-o-Matic をチェックすることもお忘れなく。

ところで、ゴロム定規とは何か?

ゴロム定規(Golomb Ruler)とは、数学用語でいうと「2組の数字の差が同一であることはない」正の整数の集合を表します。この集合を定規に見立て考えれば、「2組のマーク間の距離が同一であることはない」という感じになります。「最短ゴロム定規(Optimal Golomb Ruler = OGR)とは、あるマーク数のもので一番短いゴロム定規を指します。しかしながら、OGRはマークの数が増加するにつれ、その発見(と証明)は指数オーダーで難しさが増していきます。逆に言えば、我々がこのWebを用いた試みを24マーク、そしてそれ以上のOGR探索へと進路を変更したことも、この困難さが故であるのです。

ゴロム定規は、組み合わせ分析や数論、符号理論、通信の分野へ特に関心を持つ数学者 Solomon W. Golomb博士の名前にちなんでつけられました。またゴロム博士は数学ゲームやパズルでも有名で、 Scientific American誌のコラム "Mathematical Games"にも寄稿しています。 OGRはX線結晶学や電波天文学におけるセンサー配置など、沢山の分野に応用されています。ゴロム定規は他にも順列組み合わせ論や符号理論、通信の分野でも有意な役割を果たし、これらの領域に適用するため、最初の分析の一翼を担ったのがゴロム博士です。

「ゴロム定規」とは、全てのマークの対が唯一の距離を測定するよう、ライン上にマークを置く方法のことを言います。以下に示すものは、5マークのゴロム定規です。

| |     |         |   |
0 1     4         9   11

マーク下の数字は、左端からの距離を表します。この定規の長さは「11」で、5マークの定規で最も短い配置である2つのうちのひとつです。もうひとつは [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

3列目の数字が重複していないことに注目してください。また、距離「6」が抜けていますが、ゴロム定規は全ての距離を測るためのものではなく、唯一の距離を示すことに着目しているため、問題はありません。

「最短の」ゴロム定規を探すということは、測ることのできる距離が重複しない範囲で、出来る限り最短のものを得るということです。上記2つの5マーク定規は最短のものです。

ゴロム定規は通常、上記のようにマークの絶対位置で記述するのではなく、マーク間の距離によって表され、例えば上のものは「1-3-5-2」です。(まれに「0-1-3-5-2」と表されることもありますが、通常0は省略されます。)

例えば、現在判明している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マークまで.挙げられています。もし上の21マークゴロム定規をJamesのページで確認する際には、これが対称型である事に注意してください。

さらに困ったことに、OGRはマークの数が増加するにつれ、その発見は指数オーダーで難しさが増していきます。(このような問題を、数学者は「NP完全」問題と呼んでいます … 「巡回セールスマン問題」などが有名ですね)

OGRに関するリンク集

その他、OGRに関する参考文献

  • J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation," IEEE Trans. Inform. Theory, vol. IT-13, no. 1, pp. 106-113, 1967.
  • M. D. Atkinson, N. Santoro, and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions On Communications, vol. Com-34, no. 6, pp. 614-617, June 1986.
  • A. W. Lam and D. V. Sarwate, "On optimum time hopping patterns", IEEE Transactions on communications, vol. 36, no. 3, pp. 380-382, March 1988.
  • A.Dollas, W.T.Rankin and D.McCracken published "A New Algorithm for Golomb Ruler Derivation and proof of the 19 Mark Ruler" in IEEE Transactions On Information Theory (January, 1998, Volume 44, Number 01).