Oficiální stránky českého teamu
Czech D.NET
 


Co je OGR-25?

(Následující text je volný překlad z popisu na serveru distributed.net)

Jeden známý matematický termín je Golombovo pravítko (Golomb Ruler). Je to pravítko, na kterém jsou rysky rozloženy tak, aby se každá vzdálenost kterékoliv dvojice rysek vyskytovala jen jednou. Pro každý počet rysek lze sestrojit nekonečný počet pravítek, ale ne každé z nich je optimální, t.j. nejkratší (Optimal Golomb Ruler = O.G.R.).

Dr. Solomon W. Golomb, po kterém se pravítko nazývá, je profesorem matematiky se zaměřením na kombinatorickou analýzu, teorii čísel, teorii kódů a komunikací. Zajímá se i o matematické hry, puzzle, přispívá do rubrik amerického vědeckého časopisu Mathematical Games. Vypočtené hodnoty pro OGR mají velké využití v praxi, například pro optimální umístění senzorů v X-loučové krystalografii nebo rozložení antén v radioastronomii atd.. Významnou roli hrají i v kombinatorice, teorii kódování a komunikaci. Dr. Golomb byl první, který problém popsal a analyzoval jeho využití v uvedených oblastech.

Pro lepší pochopení problému si ukážeme Optimální Golombovo Pravítko s pěti ryskami (OGR-5). Na obyčejném pravítku udělejme rysky na 0, 1, 4, 9 a 11 cm:

     | |     |         |   |
       1     4         9   11

První bod 0 má od ostatních vzdálenosti 1, 4, 9 a 11 cm, druhý bod 1 je od dalších vzdálen 3, 8 a 10 cm, za třetím bodem 4 jsou další body vzdálené 5 a 7 cm a konečně poslední dvojice má vzdálenost 2 cm. Žádná vzdálenost se nevyskytla dvakrát. Délka tohoto pravítka je 11 cm.

Ale pro pět rysek existuje víc řešení o délce 11 cm. Především zrcadlový obraz toho prvního, t.j. 0, 2, 7, 10, 11 ale i další s ryskami 0, 3, 4, 9, 11 a jemu zrcadlová posloupnost 0, 2, 7, 8, 11. Všimněme si, že u prvního řešení chybí vzdálenost 6, u druhého 10. Každé ze 4 uvedených řešení nazýváme OGR, ale protože vždy existují zrcadlové páry, říkáme, že pro 5 rysek existují 2 OGR.

Protože základní vlastnost OGR je, že žádná vzdálenost se neopakuje, používáme pro zápis řešení místo absolutních souřadnic posloupnost vzájemných vzdáleností sousedních rysek. Tedy výše popsaná řešení OGR-5 zapíšeme jako 1-3-5-2 a 3-1-5-2. A například momentálně známé OGR-21 je
      2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4.

James B. Sharer vytvořil seznam Golombových pravítek až do 150 rysek. V jeho seznamu je pro OGR-21 zrcadlový obraz výše uvedeného řešení. Bohužel, složitost hledání OGR roste s počtem rysek exponenciálně (tzv. Np úplný problém podobně jako známý "problém obchodního cestujícího").

I když kód pro hledání OGR obsahují klienti DNETC od verze v2.8002.446, servery distributed.net akceptují bloky pouze od v2.8009.460 a vyšší, zkontroluje proto číslo verze svého klienta a stáhněte si novou verzi.

Zpracování statistik by mělo na rozdíl od RC5 být podstatně rychlejší, protože kromě denní dávky probíhá i hodinové zpracování a na závěr dne se jen sečtou hodinové údaje. Spočítaný objem se neměří v blocích, ale "work units", co jsou u OGR "node", teda jedno "pravítko" u kterého váš počítač ověřil, zda je vůbec Golombovo a jestli náhodou není optimální. Jako kdyby se u RC5 místo bloků počítali ověřené klíče.

Tyto nody se grupují do větších jednotek (stubs, packets) se stejným začátkem (prvních 6 vzdáleností), který určuje server. Bohužel nelze dopředu spočítat, kolik se pro který "stub" musí ověřit kombinací (nodů), proto se ani nedá zjistit, kolik procent "stubu" už je spočítáno a kolik ještě zbývá. Známý je jen počet "stubů". Klient kromě prvních šesti vzdáleností ukazuje za "+" další 4 vzdálenosti, spolu dávají "statistickou jednotku". Podle jejich počtu lze získat i určitou představu o tom, jaká část "stubu" už je spočítána.

Jak že může OGR pomoci například v radioastronomii? Představte si 2 antény a velmi vzdálený zdroj rádiového signálu. Na každou z antén dopadá signál v jiné fáze. Podle vzájemné vzdálenosti antén, vlnové délky a fázového rozdílu signálů lze spočítat množiny bodů, ve kterých zdroj signálu může být. Pro jinak vzdálenou dvojici antén a jiný naměřený fázový rozdíl jsou tyto množiny jiné. Bod, ve kterém zdroj signálu skutečně je, leží někde v průniku těchto dvou množin. Čím víc dvojic, tím přesnější průnik, přesnější určení směru (zaostření) i vzdálenosti zdroje. Ovšem zajímavé jsou jen ty rozteče antén, které se neopakují. Pro 25 antén je to 300 dvojic. Ale jak je rozestavit, aby se vzdálenosti neopakovali?

Tož hledejme...

O projektu
RC5
OGR
fórum
Statistiky
lokální
distributed.net
odkazy
plzeňský team
distributed.net