|
ゴロム定規（ゴロムじょうぎ、）とは、想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺とも。マーク数を「次数 (order)」、2つのマーク間の距離のうち最大の距離を「長さ (length)」という。ゴロム定規の平行移動と鏡映は自明と考えられる。そのため慣例として、最小のマークを0とし、その次のマークは2つの可能な値のうち小さいほうを取る。 ソロモン・ゴロムが名前の由来だが、Sidon〔S. Sidon, "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen", ''Mathematische Annalen'' 106 (1932), pp. 536–539〕とBabcock〔Wallace C. Babcock. "Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection", ''Bell System Technical Journal'' 31 (1953), pp. 63–73.〕も独自に発見している。 ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全 (perfect)」ゴロム定規 (PGR) という。5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている。また、同一次数（マーク数）で最短のゴロム定規を「最短 (optimal)」ゴロム定規 (OGR) という。ゴロム定規を作るのは簡単だが、特定次数のゴロム定規を見つけるのは大変である。 特定次数における最短ゴロム定規の発見を分散コンピューティングを利用したプロジェクトとしてdistributed.netで進められている。distributed.netでは、次数24、次数25、次数26〔bovin's .plan archive 〕〔Distributed.net Projects 〕、次数27の最短ゴロム定規を求め、最短の候補を検証中である。distributed.netは次数28の最短ゴロム定規も探索しようと計画している。ただし、新たにアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している。2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていた〔bovine's plan, 24-Feb-2009 17:26 〕が、2014年2月に確定したと発表した。 最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。 今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難問題だと考えられている〔。 == 既知の最短ゴロム定規 == 下表は、全ての既知の最短ゴロム定規である。マークの配置が表にあるものと逆のもの（対称型）は省く。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ゴロム定規」の詳細全文を読む スポンサード リンク
|