Regolo di Golomb

Regolo di Golomb di ordine 4 e lunghezza 6. Questo regolo è sia ottimale che perfetto.

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 [1], 25 [2], 26 [3] e 27 [3], confermando i candidati sospetti. Distributed.net sta inoltre cercando, da febbraio 2014, il regolo ottimale di ordine 28. [4]

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. [5]

En otros idiomas
Deutsch: Golomb-Lineal
English: Golomb ruler
español: Regla de Golomb
français: Règle de Golomb
日本語: ゴロム定規
Nederlands: Golomb-liniaal
српски / srpski: Голомбов лењир
svenska: Golomblinjal
Tiếng Việt: Thước Golomb