Il Progetto OGR
il progetto OGR
i Clients ed i proxies che sono in grado di lavorare sull' OGR sono disponibili per quasi tutte le piattaforme HW. Scarica ed installa gli ultimi clients per participare a questo nuovo progetto.
Se hai domande di carattere tecnico riguardanti il funzionamento del tuo cLient distributed.net, clicca qui per mandare un'email all' help@distributed.net. Prima guarda nella FAQ-o-Matic per vedere se c'è già la riposta alla tua domanda.
Allora, cos'è un "Righello Golomb Ottimizzato"?
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.
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 | Distanza |
|---|---|---|
| 0 | 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.
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").
Links riguardanti gli OGR (in inglese)
- Greg Hewgill's technical OGR information page and his plan file
- The previous OGR Effort (OGR-20, -21, -22, and -23)
- James B. Shearer's list of best known Golomb rulers (up to 150 marks) and his main Golomb page
- Lloyd Miller's listing of more best known Golomb rulers and other information.
- William T. Rankin's web page describing his master's project involving the distributed search of OGR-17, -18, and -19
- Stephen Wayne Soliday's paper on a Genetic Algorithm for Near Optimal Golomb Rulers
- David Fowler's page on Genetic Sparse Rulers (similar to Golomb Rulers)
- D. Kent Freeman paper abstract on the Similarity of Maximizing Irregularity and Solving Golomb Rulers
- A CGI server that tests for golombness if you enter a 20 mark ruler. Based out of Switzerland's ROSE university, titled: Concours Bases de
l'algorithmique
Altri rimandi sullo studio degli OGR
- J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation," IEEE Trans. Inform. Theory, vol. IT-13, no. 1, pp. 106-113, 1967.
- M. D. Atkinson, N. Santoro, and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions On Communications, vol. Com-34, no. 6, pp. 614-617, June 1986.
- A. W. Lam and D. V. Sarwate, "On optimum time hopping patterns", IEEE Transactions on communications, vol. 36, no. 3, pp. 380-382, March 1988.
- A.Dollas, W.T.Rankin and D.McCracken published "A New Algorithm for Golomb Ruler Derivation and proof of the 19 Mark Ruler" in IEEE Transactions On Information Theory (January, 1998, Volume 44, Number 01).