Pagina 3 di 7
Optimum Golomb Ruler
Scopo del progetto
In matematica, il termine "Golomb Ruler" si riferisce ad un insieme di numeri interi, non negativi, tali che nessuna coppia distinta di numeri dell'insieme abbia la stessa differenza. Concettualmente, è simile ad un righello costruito in maniera tale che nessuna coppia di punti misuri la stessa distanza.
Il Righello Golomb Ottimale (d'ora in poi OGR) è il più corto Golomb Ruler possibile per un dato numero di punti. Comunque, trovare (e dimostrare) gli OGR diventa esponenzialmente più difficile quanto il numero dei punti aumenta, ed è per questa ragione che ci siamo rivolti al WEB per un aiuto a trovare gli OGR con 24 e più punti.
Breve spiegazione matematica
I righelli "Golomb" prendono il nome dal Dr. Solomon W. Golomb, un professore di Matematica con un interesse speciale nel calcolo delle combinazioni, teoria dei numeri, teoria della cifratura nelle comunicazioni. iL Dr. Golomb si interessa anche di giochi e puzzles matematici, ha collaborato a lungo con la rivista scientifica americana "Mathematical Games". GLi OGR hanno molte applicazioni, come il piazzamneto dei sensori per la cristallografia a raggi-X e la radio-astronomia. I righelli Golomb possono anche giocare un ruolo significante nella "matematica combinatoria", nella teoria della codificazione e delle comunicazioni, il Dr. Golomb è stato uno dei primi a studiarne l'utilizzo in questi campi.
Un Golomb ruler è un modo di mettere dei punti lungo una linea in modo che ogni paia di punti misuri un unica distanza lineare. Questo è un Golomb ruler con cinque punti:
| | | | |
0 1 4 9 11
Il numero sotto il punto rappresenta la distanza dal lato sinistro. la lunghezza di questo righello è 11, e capita che sia uno dei due righelli più corti tra quelli con cinque punti. L'altro righello ha i punti nelle posizioni 0, 3, 4, 9, e 11. (Le immagini speculari di questi due righelli, 0, 2, 7, 10, 11 e 0, 2, 7, 8, 11, sono anch'esse OGR. Di solito si menziona solo un'immagine speculare per righello.)
Puoi controllare che il righello sopra sia veramente "Golomb" scrivendone la tabella di tutte le coppie di punti e le loro rispettive distanze:
Punto 1 - Punto 2 - Distanza0 - 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
Nota che non ci sono distanze uguali nella terza colonna. Non c'è nemmeno la distanza 6, ma va bene così, perchè i Golomb rulers non devono misurare ogni distanza, ma solo quelle distinte.
Lo scopo dell'ottimizzazione dei righelli Golomb è quello di renderli il più corto possibile, senza duplicare nessuna distanza misurata. i Righelli a 5 punti sopra sono ottimali.
Lo scopo dell'ottimizzazione dei righelli Golomb è quello di renderli il più corto possibile, senza duplicare nessuna distanza misurata. i Righelli a 5 punti sopra sono ottimali.
I Golomb rulers sono solitamente caratterizzati dalle loro differenze, anziche dalle adistanze assolute com mostrato sopra nel diagramma. Perciò il righello di sopra sarà 1-3-5-2 (a volte è scritto 0-1-3-5-2 ma solitamente il primo 0 si toglie).
Per esempio, il più conosciuto righello a 21-punti è il seguente:
2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4
James B. Shearer ha compilato una lista di tutti i più copnosciuti Golomb rulers fino a 150 punti. Se confronti i righelli, noterai che il righello a 21-punti menzionato nella pagina di James è un'immagine speculare di quello di sopra.
Sfortunatamente, la ricerca degli OGR diventa esponenzialmente più difficile quanto il numero dei punti aumenta (similmente a quelli che i matematici chiamano problemi "non completi" ... come l'infame "Traveling Salesman optimization").
Sfortunatamente, la ricerca degli OGR diventa esponenzialmente più difficile quanto il numero dei punti aumenta (similmente a quelli che i matematici chiamano problemi "non completi" ... come l'infame "Traveling Salesman optimization").
Applicazioni disponibili
Sono disponibili applicazioni per:
Sono disponibili applicazioni per:
- OS Windows 32 bit
- OS Linux 32 e 64 bit
- OS MAC PPC e Intel
- PS3
- Solaris
Durata: da 5 a 25 ore (stima del tempo di elaborazione su un Q6600 a 3 GHz)
Deadline: da 14 a 21 giorni
Quorum = 1
Replicazione Iniziale = 1
Deadline: da 14 a 21 giorni
Quorum = 1
Replicazione Iniziale = 1
Problemi conosciuti
L'indicatore di progresso procede in modo non continuo ma con salti dell'12,5% circa.
L'indicatore di progresso procede in modo non continuo ma con salti dell'12,5% circa.
Alcuni anti-virus segnalano dei falsi positivi per l'applicazione. Qui ne trovate una lista.