| dbo:abstract
|
- Ein Golomb-Lineal oder Golomb-Maßstab (häufig auch Golomb Ruler nach dem englischen Fachbegriff) ist in der Zahlentheorie ein Lineal, bei dem es keine zwei Markierungen an ganzzahligen Positionen mit dem gleichen Abstand zueinander gibt. Golomb-Lineale haben ihren Namen von Solomon W. Golomb, einem US-amerikanischen Professor für Mathematik und Elektrotechnik an der Universität von Südkalifornien. Golomb-Lineale werden anhand ihrer Ordnung und ihrer Länge kategorisiert. Die Ordnung eines Golomb-Lineals ist dabei definiert durch die Anzahl der Markierungen, die Länge durch den größten Abstand zweier Markierungen. Da Parallelverschiebung und Spiegelung bei Golomb-Linealen als triviale Operationen angesehen werden, wird die kleinste Markierung üblicherweise auf 0 gesetzt und die nachfolgende Markierung an der kleineren der beiden möglichen Positionen. Es ist nicht erforderlich, dass ein Golomb-Lineal alle Abstände bis zu seiner Länge messen kann, dass also alle Abstände zwischen allen Markierungen – aufsteigend geordnet – eine lückenlose Zahlenreihe (1,2,3,4,5,…) ergeben. Wenn das jedoch der Fall ist, wird es ein perfektes Golomb-Lineal genannt. Ein Golomb-Lineal ist optimal, wenn es keine kürzeren Lineale derselben Ordnung gibt. Optimale Golomb-Lineale für eine gegebene Ordnung zu finden ist, im Gegensatz zum Erstellen von Linealen mit Golomb-Eigenschaft, eine rechenintensive Aufgabe. Mittels verteilten Rechnens wurden bislang optimale Golomb-Lineale bis zur Ordnung 28 durch das distributed.net-Projekt bestätigt. Das Projekt bestätigte zuletzt nach einer Gesamtdauer von über 8 Jahren das bis dahin kürzeste bekannte Lineal für die Ordnung 28. Die Suche nach einem optimalen Lineal der Ordnung 29 ist derzeit von distributed.net nicht geplant, da der Aufwand zu hoch erscheint. (de)
- En matemática, una regla de Golomb es una serie de marcas en posiciones enteras entre sí a lo largo de una regla imaginaria de tal forma que ninguna de las marcas tienen entre sí distancias iguales. La regla de Golomb fue nombrada por el matemático e ingeniero estadounidense Solomon W. Golomb (n. 1932) y fue descubierta independientemente por Sidon (1932) y Babcock (1953). Uno de los resultados prácticos de las reglas de Golomb es el diseño de radio antenas múltiples por desfase de onda en configuraciones de radiotelescopios. Existen dos tipos de reglas de Golomb, unas perfectas u óptimas y otras aproximadas. Las perfectas son la [0,1], [0,1,3] y [0,1,4,6] que son los números más cortos para 2, 3 y 4 marcas respectivamente. Distributed.net ha realizado una búsqueda masiva en paralelo de reglas de 24 marcas: [9, 24, 4, 1, 59, 25, 7, 11, 2, 10, 39, 14, 3, 44, 26, 8, 40, 6, 21, 15, 16, 19, 22] La búsqueda de reglas de 28 marcas está de momento en desarrollo. (es)
- In mathematics, a Golomb ruler is a set of marks at integer positions along a ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. Golomb rulers can be viewed as a one-dimensional special case of Costas arrays. The Golomb ruler was named for Solomon W. Golomb and discovered independently by and . Sophie Piccard also published early research on these sets, in 1939, stating as a theorem the claim that two Golomb rulers with the same distance set must be congruent. This turned out to be false for six-point rulers, but true otherwise. There is no requirement that a Golomb ruler be able to measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proved that no perfect Golomb ruler exists for five or more marks. A Golomb ruler is optimal if no shorter Golomb ruler of the same order exists. Creating Golomb rulers is easy, but proving the optimal Golomb ruler (or rulers) for a specified order is computationally very challenging. Distributed.net has completed distributed massively parallel searches for optimal order-24 through order-28 Golomb rulers, each time confirming the suspected candidate ruler. Currently, the complexity of finding OGRs of arbitrary order n (where n is given in unary) is unknown. In the past there was some speculation that it is an NP-hard problem. Problems related to the construction of Golomb rulers are provably shown to be NP-hard, where it is also noted that no known NP-complete problem has similar flavor to finding Golomb rulers. (en)
- En mathématiques, une règle de Golomb, appelée ainsi en l'honneur du mathématicien Solomon W. Golomb, est une règle munie de marques à des positions entières, telle que deux paires de marques ne soient jamais à la même distance ; en d'autres termes, chaque couple de marques mesure une longueur différente des autres. Puisque n'importe quelle « translation entière » d'une règle de Golomb donne une règle de Golomb, la première marque est généralement portée sur 0. Par définition, l'ordre d'une règle de Golomb est le nombre de marques qu'elle porte ; la longueur d'une règle de Golomb est la plus grande distance entre deux de ses marques. Il n'est pas nécessaire qu'une règle de Golomb permette de mesurer toutes les distances entre 0 et la longueur de la règle mais si c'est le cas, on dit qu'il s'agit d'une règle de Golomb parfaite. La plus courte règle de Golomb pour un ordre donné s'appelle une règle de Golomb optimale. Construire une règle de Golomb n'est pas difficile mais trouver toutes les règles de Golomb d'un ordre donné est un défi informatique (voir distributed.net, un projet de calcul distribué actuellement en cours pour trouver des règles de Golomb optimales). Une des applications pratiques des règles de Golomb est la conception d'« antenne réseau à commande de phase » comme dans les radiotélescopes. L'application la plus courante de la règle de Golomb aux antennes est la répartition des antennes des réseaux cellulaires. (fr)
- In matematica, un regolo di Golomb, chiamato così da Solomon W. Golomb che fu il primo a descriverlo, è un insieme di tacche poste a posizioni intere su un immaginario regolo, tale che non ci sia alcuna coppia di tacche poste alla stessa distanza. Il numero di tacche nel regolo è il suo ordine, mentre la massima distanza tra due delle sue tacche è la sua lunghezza. Traslazione e riflessione di un regolo di Golomb sono considerate banali: per convenzione, quindi, la tacca più a sinistra è posta a 0 e quella successiva è il minore dei due valori possibili. Non è affatto richiesto che un regolo di Golomb possa misurare tutte le distanze da 1 alla sua lunghezza: nel caso che lo faccia, viene detto un regolo perfetto. È stato dimostrato che non può esistere un regolo di Golomb perfetto per cinque o più tacche. Un regolo di Golomb si dice ottimale se non esiste nessun regolo di Golomb dello stesso ordine e più corto. È facile creare un regolo di Golomb, ma trovare quelli ottimali è un compito computazionalmente complicato. Distributed.net ha completato la ricerca parallela di massa per i regoli ottimali di ordine 24, 25, 26 e 27, confermando i candidati sospetti. Distributed.net sta inoltre cercando, da febbraio 2014, il regolo ottimale di ordine 28. Un uso pratico dei regoli di Golomb è la progettazione di antenne radio in array di fase, come ad esempio i radiotelescopi. Presso le stazioni base dei cellulari, si possono spesso vedere antenne in una configurazione equivalente al regolo di Golomb [0,1,4,6]. Al momento non è nota la complessità di trovare regoli di Golomb ottimali di lunghezza arbitraria n, ma si pensa che sia un problema NP-difficile. (it)
- Een Golomb-liniaal is in de wiskunde een rij natuurlijke getallen die zo is samengesteld dat geen twee paren getallen uit de rij hetzelfde verschil hebben. Het aantal getallen heet de orde van de liniaal en het grootste voorkomende verschil de lengte. Qua concept lijkt dit op een liniaal die zo is gemaakt dat geen tweetal strepen dezelfde afstand heeft als een ander paar. De Golomb-liniaal is genoemd naar , een Amerikaanse hoogleraar wiskunde en elektrotechniek aan de universiteit van Zuid-Californië. De getallen op een Golomb-liniaal vormen een . Een Sidon-verzameling is een verzameling van natuurlijke getallen, waarvan elk verschil tussen twee verschillende elementen uniek is; of waarvan elke som van twee (niet noodzakelijk verschillende) elementen uniek is. Sidon-verzamelingen dateren van voor de Golomb-linialen; de Hongaarse wiskundige gebruikte ze bij zijn studie van Fourierreeksen in 1932. Verschuiven en spiegelen van een Golomb-liniaal geven in essentie dezelfde liniaal, zodat als kleinste getal gewoonlijk 0 wordt gekozen. Een Golomb-liniaal die alle afstanden tot aan z'n lengte kan meten wordt perfect genoemd. Zo een liniaal met markeringen is exact eenheden lang en kan de afstanden van 1 tot en met meten. Er bestaan geen perfecte Golomb-linialen voor groter dan 4. Een Golomb-liniaal heet optimaal als er geen kortere Golomb-liniaal is van dezelfde orde. De lengte van een optimale Golomb-liniaal met markeringen, voor is: Golomb-linialen zijn eenvoudig te maken, maar het vinden van de optimale linialen van een bepaalde orde is lastig en rekentechnisch tijdrovend. Let wel: het vinden (en bewijzen) van OGR's wordt exponentieel moeilijker naarmate het aantal markeringen toeneemt. Er is geen formule of algoritme bekend dat zegt wat het maximaal aantal markeringen is voor een Golomb-liniaal van gegeven lengte, of wat de kortst mogelijke Golomb-liniaal is met een gegeven aantal markeringen. Het berekenen van OGR's met veel markeringen kan worden gedaan door in parallel van een groot aantal beginreeksen te bepalen of er een OGR mee kan worden gemaakt. Op dit moment wordt dit voor een OGR met 28 markeringen gedaan in een zogenaamd distributed computing-project. Methoden om Golomb-linialen te construeren zijn besproken in een artikel van Konstantinos Drakakis. Optimale Golomb-linialen (OGR's) hebben veel toepassingsmogelijkheden waaronder sensorplaatsing bij röntgendiffractie, in de kristallografie en voor de plaatsing van antennes in de radio-astronomie. (nl)
- ゴロム定規（ゴロムじょうぎ、英: Golomb ruler）とは、想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺とも。マーク数を「次数 (order)」、2つのマーク間の距離のうち最大の距離を「長さ (length)」という。ゴロム定規の平行移動と鏡映は自明と考えられる。そのため慣例として、最小のマークを0とし、その次のマークは2つの可能な値のうち小さいほうを取る。 ソロモン・ゴロムが名前の由来だが、とBabcockも独自に発見している。 ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全 (perfect)」ゴロム定規 (PGR) という。5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている。また、同一次数（マーク数）で最短のゴロム定規を「最短 (optimal)」ゴロム定規 (OGR) という。ゴロム定規を作るのは簡単だが、特定次数のゴロム定規を見つけるのは困難である。 特定次数における最短ゴロム定規の発見を分散コンピューティングを利用したプロジェクトとしてdistributed.netで進められている。distributed.netでは、次数24、次数25、次数26、次数27の最短ゴロム定規を求め、最短の候補を検証中である。 2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていたが、2014年2月に確定したと発表した。 distributed.netは次数28の最短ゴロム定規を探索している。また、新たなアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している。2022年11月22日に、約8年半かかって探査が終了したと発表した。次数28の最短ゴロム定規の探査終了時点では、想定している規模や期間から、現時点では次数29の最短ゴロム定規を探索する予定はないが、今後も継続して検討するとしている。 最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。 今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難問題だと考えられている。 (ja)
- Лінійка Голомба в теорії чисел — набір невід'ємних цілих чисел, розташованих у вигляді поділок на уявній лінійці таким чином, що відстань між будь-якими двома поділками є унікальною. Іншими словами, на всій довжині лінійки неможливо знайти два числа, різниця між якими повторювалася б двічі. Названі на честь американського математика Соломона Голомба, хоча перші згадки подібних конструкцій зустрічаються в раніших публікаціях і . (uk)
- En Golomblinjal är en matematisk term för en uppsättning heltalspositioner längs en tänkt linjal där inga av avstånden mellan positionerna är lika. Antalet positioner benämns som Golomblinjalens grad och det längsta avståndet mellan två av dess positioner för dess längd. Den kortast möjliga linjalen för varje grad kallas den optimala Golomblinjalen. Optimala Golomblinjaler är användbara vid konstruktion av bland annat radioteleskop. En linjal som klarar att mäta samtliga avstånd upp till dess längd kallas perfekt. Det är bevisat att det inte existerar några perfekta linjaler med fem eller fler positioner. Optimala Golomblinjaler måste hittas numeriskt och det görs bland annat ett arbete av frivilligorganisationen Distributed.net. I nuläget är komplexiteten för att finna en golomblinjal av längd n okänd men problemet tros vara . (sv)
- Линейка Голомба в теории чисел — набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки нельзя найти два числа, разность между которыми повторялась бы дважды. Названы в честь американского математика Соломона Голомба, хотя первые упоминания подобных конструкций встречаются в более ранних публикациях и . (ru)
- 哥隆尺問題（Golomb ruler），是如何在一把尺上劃分刻度，使所有刻度彼此之間的距離都不相同。刻度的數目稱為階，而兩個刻度間最長的距離為長度。對哥隆尺做平移或鏡像並不影響結果，因此習慣上將最小刻度設為 0 。 哥隆尺是由Sidon和Babcock各自独立发现，并且以数学家所羅門·格倫布的名字命名。 哥隆尺不需要能够測量到其自身長度為止的所有距离，如果能夠的话，稱為完美哥隆尺。已經证明不存在五階以上的完美哥隆尺。最優哥隆尺則是同一階中長度最短的哥隆尺。生成哥隆尺是简单的，但是找到一个指定階的最优哥隆尺是的一个有挑战性的计算项目。 Distributed.net（页面存档备份，存于互联网档案馆）已经利用大規模分散式平行計算完成了对24階到27階最優哥隆尺的尋找。Distributed.net已於2014年2月開始尋找28階最優哥隆尺。 目前，尋找n階最優哥隆尺的複雜度是未知的，有人猜測這是NP困難問題。 (zh)
|
| rdfs:comment
|
- Лінійка Голомба в теорії чисел — набір невід'ємних цілих чисел, розташованих у вигляді поділок на уявній лінійці таким чином, що відстань між будь-якими двома поділками є унікальною. Іншими словами, на всій довжині лінійки неможливо знайти два числа, різниця між якими повторювалася б двічі. Названі на честь американського математика Соломона Голомба, хоча перші згадки подібних конструкцій зустрічаються в раніших публікаціях і . (uk)
- Линейка Голомба в теории чисел — набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки нельзя найти два числа, разность между которыми повторялась бы дважды. Названы в честь американского математика Соломона Голомба, хотя первые упоминания подобных конструкций встречаются в более ранних публикациях и . (ru)
- 哥隆尺問題（Golomb ruler），是如何在一把尺上劃分刻度，使所有刻度彼此之間的距離都不相同。刻度的數目稱為階，而兩個刻度間最長的距離為長度。對哥隆尺做平移或鏡像並不影響結果，因此習慣上將最小刻度設為 0 。 哥隆尺是由Sidon和Babcock各自独立发现，并且以数学家所羅門·格倫布的名字命名。 哥隆尺不需要能够測量到其自身長度為止的所有距离，如果能夠的话，稱為完美哥隆尺。已經证明不存在五階以上的完美哥隆尺。最優哥隆尺則是同一階中長度最短的哥隆尺。生成哥隆尺是简单的，但是找到一个指定階的最优哥隆尺是的一个有挑战性的计算项目。 Distributed.net（页面存档备份，存于互联网档案馆）已经利用大規模分散式平行計算完成了对24階到27階最優哥隆尺的尋找。Distributed.net已於2014年2月開始尋找28階最優哥隆尺。 目前，尋找n階最優哥隆尺的複雜度是未知的，有人猜測這是NP困難問題。 (zh)
- Ein Golomb-Lineal oder Golomb-Maßstab (häufig auch Golomb Ruler nach dem englischen Fachbegriff) ist in der Zahlentheorie ein Lineal, bei dem es keine zwei Markierungen an ganzzahligen Positionen mit dem gleichen Abstand zueinander gibt. Golomb-Lineale haben ihren Namen von Solomon W. Golomb, einem US-amerikanischen Professor für Mathematik und Elektrotechnik an der Universität von Südkalifornien. Die Suche nach einem optimalen Lineal der Ordnung 29 ist derzeit von distributed.net nicht geplant, da der Aufwand zu hoch erscheint. (de)
- In mathematics, a Golomb ruler is a set of marks at integer positions along a ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. Golomb rulers can be viewed as a one-dimensional special case of Costas arrays. (en)
- En matemática, una regla de Golomb es una serie de marcas en posiciones enteras entre sí a lo largo de una regla imaginaria de tal forma que ninguna de las marcas tienen entre sí distancias iguales. La regla de Golomb fue nombrada por el matemático e ingeniero estadounidense Solomon W. Golomb (n. 1932) y fue descubierta independientemente por Sidon (1932) y Babcock (1953). Uno de los resultados prácticos de las reglas de Golomb es el diseño de radio antenas múltiples por desfase de onda en configuraciones de radiotelescopios. La búsqueda de reglas de 28 marcas está de momento en desarrollo. (es)
- En mathématiques, une règle de Golomb, appelée ainsi en l'honneur du mathématicien Solomon W. Golomb, est une règle munie de marques à des positions entières, telle que deux paires de marques ne soient jamais à la même distance ; en d'autres termes, chaque couple de marques mesure une longueur différente des autres. Puisque n'importe quelle « translation entière » d'une règle de Golomb donne une règle de Golomb, la première marque est généralement portée sur 0. (fr)
- ゴロム定規（ゴロムじょうぎ、英: Golomb ruler）とは、想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺とも。マーク数を「次数 (order)」、2つのマーク間の距離のうち最大の距離を「長さ (length)」という。ゴロム定規の平行移動と鏡映は自明と考えられる。そのため慣例として、最小のマークを0とし、その次のマークは2つの可能な値のうち小さいほうを取る。 ソロモン・ゴロムが名前の由来だが、とBabcockも独自に発見している。 ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全 (perfect)」ゴロム定規 (PGR) という。5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている。また、同一次数（マーク数）で最短のゴロム定規を「最短 (optimal)」ゴロム定規 (OGR) という。ゴロム定規を作るのは簡単だが、特定次数のゴロム定規を見つけるのは困難である。 2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていたが、2014年2月に確定したと発表した。 最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。 (ja)
- In matematica, un regolo di Golomb, chiamato così da Solomon W. Golomb che fu il primo a descriverlo, è un insieme di tacche poste a posizioni intere su un immaginario regolo, tale che non ci sia alcuna coppia di tacche poste alla stessa distanza. Il numero di tacche nel regolo è il suo ordine, mentre la massima distanza tra due delle sue tacche è la sua lunghezza. Traslazione e riflessione di un regolo di Golomb sono considerate banali: per convenzione, quindi, la tacca più a sinistra è posta a 0 e quella successiva è il minore dei due valori possibili. (it)
- Een Golomb-liniaal is in de wiskunde een rij natuurlijke getallen die zo is samengesteld dat geen twee paren getallen uit de rij hetzelfde verschil hebben. Het aantal getallen heet de orde van de liniaal en het grootste voorkomende verschil de lengte. Qua concept lijkt dit op een liniaal die zo is gemaakt dat geen tweetal strepen dezelfde afstand heeft als een ander paar. De Golomb-liniaal is genoemd naar , een Amerikaanse hoogleraar wiskunde en elektrotechniek aan de universiteit van Zuid-Californië. (nl)
- En Golomblinjal är en matematisk term för en uppsättning heltalspositioner längs en tänkt linjal där inga av avstånden mellan positionerna är lika. Antalet positioner benämns som Golomblinjalens grad och det längsta avståndet mellan två av dess positioner för dess längd. Optimala Golomblinjaler måste hittas numeriskt och det görs bland annat ett arbete av frivilligorganisationen Distributed.net. I nuläget är komplexiteten för att finna en golomblinjal av längd n okänd men problemet tros vara . (sv)
|
