Project OGR

From distributed.net
< OGR
Jump to navigationJump to search

Project OGR

Clients en proxies die in staat zijn met OGR te werken zijn beschikbaar voor de meeste platforms. Download en installeer de meest recente clients vandaag nog om mee de doen aan dit project! Er is een sectie voor OGR in onze FAQ-o-Matic. Een klein aantal deelnemers heeft extreem grote OGR-25 stubs (engels) toegewezen gekregen, maar dat komt erg weinig voor.

Je kunt meer informatie over onze netwerksnelheid vinden op onze OGR statistieken pagina.

Als je technische vragen hebt over het functioneren van je distributed.net client, klik van hier om een email te sturen aan help@distributed.net. Zorg er zeker voor dat je eerst kijkt in de FAQ-o-Matic om er zeker van te zijn dat je vraag niet al beantwoord is.

==Wat is een Golomb Ruler eigenlijk?

In de wiskunde refereert de term "Golomb Ruler" aan een reeks van niet-negatieve natuurlijke getallen die zo is samengesteld dat geen paar van nummers uit de reeks hetzelfde verschil hebben. Qua concept lijkt dit op een lineaal die zo is gemaakt dat geen paar van het verschil tussen twee strepen dezelfde afstand vormen. Een Optimale Golomb Lineaal (Optimal Golomb Ruler (OGR)) is de kortst mogelijke Golomb Ruler uit een gegeven aantal markeringen. Let wel: het vinden (en bewijzen) van OGR's wordt exponentieel moeilijker naarmate het aantal markeringen toeneemt en dat is er de reden voor dat we nu het web gaan gebruiken voor het vinden van OGR's met 24 en meer markeringen. Golomb Rulers zijn genoemd naar Dr. Solomon W. Golomb, een hoogleraar in de wiskunde met een speciale interesse in combinatie analyse, nummer theorie, coderings theorie en communicatie. Dr. Golomb was ook geinteresseerd in wiskundige spelletjes en puzzels; hij was dan ook verantwoordelijk voor vele columns in de Scientific American "Mathematical Games". OGR's hebben veel toepassingsmogelijkheden waaronder sensorplaatsing voor Rontgen crystallografie en radio astronomie. Golomb Rulers kunnen ook een significante rol spelen in de combinatiekunde, de coderingstheorie en de communicatie. Dr. Golomb was een van de eersten die analyses maakte voor de toepassing van OGR's in deze vakgebieden.

Een Golomb ruler is een manier om merktekens zo op een lijn te zetten dat ieder paar merktekens een unieke lineaire afstand hebben. Dit is een Golomb ruler met vijf merktekens:

| |     |         |   |
0 1     4         9   11

Het getal onder het merkteken is de afstand van dit merkteken tot de linkerzijde. De lengte van deze "meetlat" is 11 en het is een van de twee kortste "meetlatten" met vijf merktekens. De andere meetlat heeft markeringen op positions 0, 3, 4, 9, and 11 (de gespiegelde varianten van deze meetlatten 0, 2, 7, 10, 11 en 0, 2, 7, 8, 11, zijn eveneens Optimal Golomb rulers. Normaal wordt slechts een van het paar vermeld).

Je kunt controleren of de bovenstaande meetlat inderdaad een Golomb meetlat is door een tabel uit te schrijven met alle paren van merktekens en hun onderlingen afstanden:


merk1 merk2 afstand
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

Merk op dat er geen dubbele afstanden in de derde kolom voorkomen. Er is overigens ook geen afstand '6', maar dit is geen probleem omdat Golomb rulers niet iedere afstand hoeven kunnen meten, slecht verschillende afstanden.

Het doel van "optimalizeren" van Golomb rulers is om ze zo kort mogelijk te maken zonder dubbele intervallen. Beide 5-merkteken rulers zijn "optimaal".

Golomb rulers worden meestal gekenmerkt door hun relatieve afstanden in tegenstelling tot de absolute afstanden die hierboven weergegeven zijn. De eerdere meetlat is eigenlijk 1-3-5-2 (soms is de notatie 0-1-3-5-2 maar de eerste 0 wordt veelal weggelaten)

Momenteel is de best bekende 21-merkteken meetlat de volgende:

2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4

James B. Shearer heeft een lijst samengesteld van alle best bekende Golomb rulers tot 150 merktekens. Wanneer je de meetlatten vergelijk zie je dat de 21-merkteken meetlat in James' lijst de gespiegelde variant van bovenstaande is.

Helaas wordt het zoeken naar OGR's exponentieel complexer met het toenemen van het aantal markeringen (naar analogie van wat wiskundigen het "Np complete" probleem noemen... met als het beruchte 'handelsreiziger' probleem).

algemene links over OGR

l'algorithmique

Andere alleen in boekvorm te verkrijgen OGR research referenties

  • J. P. Robinson en 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, en 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 en 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 en 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).