Je leest:

Een optimale Golomb-liniaal van orde 25

Een optimale Golomb-liniaal van orde 25

Auteur: | 31 oktober 2008

Distributed.net heeft deze week het OGR-25-project afgerond. Dit project stond in het teken van het vinden van een zogeheten optimale Golomb-liniaal van 25 getallen. De zoektocht duurde ruim acht jaar; de Dutch Power Cows leverden daaraan de grootste bijdrage.

We zetten op een liniaal een aantal markeringen, op zo’n manier dat geen afstand tussen twee markeringen tweemaal voorkomt. Een dergelijke liniaal heet Golomb-liniaal. De reeks 0, 1, 4, 6 vormt een Golomb-liniaal: elke twee getallen uit de reeks hebben een ander verschil, zoals in onderstaande figuur is te zien. Golomb-linialen zijn voor uiteenlopende toepassingen als radioastronomie, de constructie van röntgendiffractiemicroscopen en cryptografie bruikbaar.

Een Golomb-liniaal is een reeks niet-negatieve gehele getallen waarbij geen twee getallen uit deze reeks hetzelfde verschil hebben. Hier zie je een optimale Golomb-liniaal (Engels: Optimal Golomb Ruler (OGR)) van orde 4 en lengte 6 (d.w.z.: 4 merktekens tussen de 0 en de 6)

Perfecte en optimale linialen

Bij de Golomb-liniaal 0, 1, 4, 6 komen de afstanden 1 tot en met 6 allemaal eenmaal voor. Deze mooie eigenschap geldt voor lang niet elke Golomb-liniaal. Bij langere linialen zullen er in het algemeen gaten vallen in de afstanden die voorkomen. Een liniaal die alle verschillen tussen 1 en zijn eigen lengte bevat, heet een perfecte Golomb-liniaal.

Een optimale liniaal is de kortste liniaal met n getallen (waarbij kortste betekent dat het laatste getal uit de reeks zo klein mogelijk is). De genoemde liniaal 0, 1, 4, 6 is behalve perfect ook optimaal.

Golomb-linialen zijn vernoemd naar Solomon W. Golomb (geboren 1932), een wiskundige die gespecialiseerd is in de combinatoriek, getaltheorie en coderingstheorie. Naast zijn wiskundig onderzoek heeft hij veel aan popularisering gedaan: hij verzorgde jarenlang de rubriek ‘Mathematical Games’ in de Scientific American.

Zoektocht via gedistribueerde berekeningen

Bij een gedistribueerde berekening wordt een groot probleem opgedeeld in kleine stukken die afzonderlijk door diverse computers kunnen worden opgelost. Het project OGR-25, de zoektocht naar een optimale Golomb-liniaal van orde 25, is een cryptografieproject van Distributed.net.

Onlangs is er een nieuwe optimale Golomb-liniaal gevonden. De optimale Golomb-liniaal van orde 25 heeft een lengte van 480 en bevat de volgende getallen: 0, 12, 29, 39, 72, 91, 146, 157, 160, 161, 166, 191, 207, 214, 258, 290, 316, 354, 372, 394, 396, 431, 459, 467, 480. Het duurde jaren rekenen met duizenden computers om te bewijzen dat deze Golomb-liniaal inderdaad de kortste is voor 25 getallen. De reeks zelf was overigens al in 1984 gevonden.

Voor het project OGR-25 van Distributed.net zijn 3006 dagen en 124.387 deelnemers nodig geweest

NP-volledig

Het vinden van optimale Golomb-linialen wordt ‘exponentieel moeilijker’ naarmate het aantal markeringen toeneemt. Wiskundigen spreken van een NP-volledig probleem. NP-volledigheid is een begrip uit de compexiteitstheorie. NP-volledige problemen behoren tot de moeilijkst oplosbare problemen. Daarom zoekt men naar lange optimale Golomb-linialen door middel van via internet gedistribueerde berekeningen; iedereen kan dan zijn steentje bijdragen en dan is het probleem toch nog behapbaar.

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 31 oktober 2008

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.