In der Mathematik ist ein Lineal von Golomb eine Reihe Zeichen an Positionen der ganzen Zahl entlang einem imaginären solchem Lineal, dass keine zwei Paare von Zeichen dieselbe Entfernung einzeln sind. Die Zahl von Zeichen auf dem Lineal ist seine Ordnung, und die größte Entfernung zwischen zwei seiner Zeichen ist seine Länge. Übersetzung und Nachdenken eines Lineals von Golomb werden trivial betrachtet, so wird das kleinste Zeichen gewöhnlich an 0 und das folgende Zeichen an den kleineren von seinen zwei möglichen Werten gestellt.

Das Lineal von Golomb wurde für Solomon W. Golomb genannt und unabhängig von Sidon und Babcock entdeckt.

Es gibt keine Voraussetzung, dass ein Lineal von Golomb im Stande sein, alle Entfernungen bis zu seiner Länge zu messen, aber wenn es tut, es wird einen vollkommenen Herrscher von Golomb genannt. Es ist bewiesen worden, dass kein vollkommenes Lineal von Golomb für fünf oder mehr Zeichen besteht. Ein Golomb Lineal ist optimal, wenn kein kürzeres Lineal von Golomb derselben Ordnung besteht. Golomb Schaffen-Lineale sind leicht, aber Entdeckung der optimalen Lineale von Golomb für eine angegebene Ordnung ist rechenbetont sehr schwierig. Distributed.net hat verteilt vollendet massiv passen Suchen nach optimalem Auftrag 24, Auftrag 25 und Auftrag 26 Lineale von Golomb an, den verdächtigten Kandidaten bestätigend. Distributed.net auch hat Pläne, optimale Lineale von Golomb (OGRs) des Auftrags 27 und Auftrags 28 zu finden. Jedoch, wie man erwartet, nehmen sie so lange die vorherigen Projekte wegen der Entdeckung eines verbesserten Algorithmus nicht. Distributed.net sucht nach dem optimalen Lineal des Auftrags 27 aktiv; im Mai 2009 die erwartete Zeit, um zu entdecken, wurde es in ungefähr sieben Jahren geschätzt. Die Berechnung, war nach 1063 Tagen (2.9 Jahre) der Arbeit um ungefähr 47 % abgeschlossen.

Zurzeit ist die Kompliziertheit, OGRs des willkürlichen Auftrags n zu finden (wo n unär eingereicht wird) unbekannt. In der Vergangenheit gab es etwas Spekulation, dass es ein NP-hard Problem ist. Wie man nachweisbar zeigt, sind mit dem Aufbau von Golomb Linealen verbundene Probleme NP-hard, wo es auch bemerkt wird, dass nicht bekanntes NP-complete Problem ähnlichen Geschmack zur Entdeckung von Golomb Linealen hat.

Definitionen

Lineale von Golomb als Sätze

Eine Reihe von ganzen Zahlen

ist ein Lineal von Golomb wenn und nur wenn

Die Ordnung solch eines Lineals von Golomb ist, und seine Länge ist. Die kanonische Form hat und, wenn,

Lineale von Golomb als Funktionen

Ein injective fungiert

damit und ist ein Lineal von Golomb wenn und nur wenn

Die Ordnung solch eines Lineals von Golomb ist, und seine Länge ist. Die kanonische Form hat

Optimality

Ein Golomb Lineal der Ordnung mit der Länge kann in jeder von zwei Hinsicht optimal sein:

• es kann optimal dicht sein, maximal für den spezifischen Wert von ausstellend
• es kann optimal kurz sein, minimal für den spezifischen Wert von ausstellend

Der allgemeine Begriff das optimale Lineal von Golomb wird gebraucht, um sich auf den zweiten Typ von optimality zu beziehen.

Praktische Anwendungen

Informationskorrektur der Theorie/Fehlers

Lineale von Golomb werden innerhalb der Informationstheorie verwendet, die mit dem Fehler verbunden ist, der Codes korrigiert.

Radiofrequenzauswahl

Lineale von Golomb werden in der Auswahl an Radiofrequenzen verwendet, um die Effekten der Zwischenmodulationseinmischung sowohl mit irdischen als auch mit außerirdischen Anwendungen zu reduzieren.

Radioantenne-Stellen

Lineale von Golomb werden im Design von aufeinander abgestimmten Reihe-Radioantennen wie Radiofernrohre verwendet. Antennen in [0,1,4,6] Lineal von Golomb Konfiguration können häufig an Zellseiten gesehen werden.

Methoden des Aufbaus

Mehrere Baumethoden erzeugen asymptotisch optimale Lineale von Golomb.

Aufbau von Erdős-Turan

Der folgende Aufbau, wegen Pauls Erdős und Pál Turán, erzeugt ein Lineal von Golomb für jeden sonderbaren ersten p.

Bekannte optimale Lineale von Golomb

Der folgende Tisch enthält alle bekannten optimalen Lineale von Golomb, derjenigen mit Zeichen in der Rückordnung ausschließend. Die ersten vier sind vollkommen.

Siehe auch

• Reihe von Costas
• Das spärliche Lineal
• Das vollkommene Lineal
• Folge von Sidon

Links

• Die Golomb Lineal-Seiten von James B. Shearer
• distributed.net: Planen Sie OGR
• Auf der Suche nach Den Optimalen 20, 21 & 22 Lineale von Mark Golomb
• "Lineale, Reihe und Schick" durch Ed Pegg den Jüngeren.
• Lineale von Golomb bis zur Länge von mehr als 200 (über das Internetarchiv)