Distribuovaný projekt našiel optimálne 25-prvkové Golombove pravítko

DSL.sk, 27.10.2008

Projekt distribuovaných výpočtov distributed.net našiel vo štvrtok po ôsmich rokoch výpočtov optimálne 25-prvkové Golombove pravítko.

Tzv. Golombove pravítko respektíve postupnosť o veľkosti N je taká postupnosť N prirodzených čísiel, u ktorej medzi žiadnymi dvomi dvojicami z nich nie je rovnaký rozdiel. Optimálnou postupnosťou pre dané N je taká Golombova postupnosť, ktorá končí na najmenšie možné číslo.

Optimálne Golombove postupnosti majú aplikáciu napríklad pri konštrukcii pola rádiových antén.

Optimálnu Golombovu postupnosť je možné zatiaľ hľadať len s exponenciálnou zložitosťou, projektu distributed.net s celkovým počtom 124 387 zapojených užívateľov v tomto projekte trvalo nájdenie a potvrdenie optimálnej 25-prvkovej postupnosti 3 006 dní.

Optimálnu postupnosť projekt našiel už v októbri 2007, až vo štvrtok po dokončení prehľadávania celého priestoru všetkých možností bola definitívne potvrdená optimálnosť nájdenej postupnosti. Optimálna postupnosť je len jediná, samozrejme s existujúcim zrkadlovým obrazom, a tvoria ju čísla 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.

Projekt zároveň ohlásil prípravu hľadania optimálnej Golombovej postupnosti o dĺžke 26, ktorej nájdenie by malo pre zlepšený algoritmus trvať kratšie. Projekt zatiaľ nemá k dispozícii klienta pre GPU.


Najnovšie články:



Diskusia:

dnes má meniny Sabina, zajtra Dobromila Od reg.: Rivale | Pridané: 27.10.2008 10:36 no fasa, nemam ani sajnu o com sa tu ide, mam pocit, ze tento text je len vygenerovany nejakym generatorom nahodnych textov. :)) takze z globalneho aspketu, teoreticky vzane, za podstatu veci, prakticky nemam paru o com sa tu ide. :)) Odpovedať Známka: 6.6 Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: FAbi2 | Pridané: 27.10.2008 10:44 Skús Wikipédiu... Pochopíš možno:] Odpovedať Známka: -2.0 Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: gidy | Pridané: 27.10.2008 10:44 :D tomu porozumie len asi moj profak matiky z vysky, ktory realny svet videl ako Neo z Matrixu. Ten chlapik si kazdy vecer otvoril zbierku nevyriesitelnych prikladov a pokusal sa ich riesit. :D Odpovedať Známka: 6.4 Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: ___ | Pridané: 27.10.2008 12:20 No ten moj ich aj vzdy vyriesil a na dalsom cviku uz som stal pri tabuli a riesil to ja Odpovedať Známka: 5.2 Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: mtf | Pridané: 27.10.2008 12:48 vivat matfyz! Odpovedať Známka: 3.8 Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: waveeee | Pridané: 27.10.2008 18:19 no ja som mal žemberiho a trokanovú a oni vyzerali ako neo a trinity ked prednasali... BTW: ale tomuto rozumiem aj ja. Normalne si zober hodciktore z tych cisiel oscitaj ho od hodciktoreho dalsieho z nich (okrem seba sameho) a ked sa vysledok bude rovnat nejakemu dalsiemu cislu z tých 25tich... tak si dám 100 korún :P Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: Pjetro de | Pridané: 27.10.2008 18:42 mas tam nekozmeticku chybycku v zavere vysvetlivky ....... (okrem seba sameho) a ked sa vysledok bude rovnat nejakemu lubovelnemu inemu takymto sposobom ziskanemu rozdielu tak si dám 100 korún ... porovnavaju sa totiz vsetky mozne rozdiely vsetkych moznych dvojic ... no a geometricka interpretacia rozdielu dvoch realnych cisel (resp. ich absolutnej hodnoty) je ich vzdialenost na realnej ciselnej osi ... takze preto pravitko ... Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: dElEtE | Pridané: 28.10.2008 1:50 no bud je ta definicia zla alebo som tomu nepochopil.. ale ked si vezmem z tych cisiel napr. 80 - 20 = 60 a dalsie dve 91 - 31 = tiez 60 A 60 sa medzi tymi cislami tiez nachadza kto mi da tych 100korun? :D Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: sam12 | Pridané: 28.10.2008 8:07 tieto cisla tam nie su Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: dElEtE | Pridané: 28.10.2008 17:15 aha uz som to asi pochopil.. som myslel, ze to je rad po sebe iducich samostatnych cisiel, ale tie medzery asi rozdeluju jednotlive cisla, cize to je cele cislo napr. 467 a za tym 480. Tak potom to uz dava zmysel ta definicia :) A takych cisiel moze byt dooost vela akurat zatial nevymysleli rychly sposob ako ich najst jedine skusat vsetky moznosti. Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: jegi | Pridané: 27.10.2008 19:00 tak to vyzera na Stavebnu zemberita si pamatam dal mi 3- Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: fallout | Pridané: 27.10.2008 21:00 žembery je starý týpek, však ho našli hrabať sa v kontajneroch opiteho. a trokanova je divná žienka :D Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: 3ton | Pridané: 28.10.2008 13:42 ...lol. nikdy nevies kde a kedy najdes riesenie. :) Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: waveeeee | Pridané: 29.10.2008 0:11 na stavebnej je vsetko po starom.. žembo ešte v poho, ale Halvoník ten ma už druhý rok ničí.. teda este som sa neodhodlal ani raz ist na skusku z toho betonu :P BTW: niekto hovoril ze tam mam chybicku.. ja so nechcel napisat celu definuciu toho Golomba, len som vybral jedno pravidlo BTW2: kto to našiel žemberiho v smetiaku ? :D stary mladenec si vyhodil z kopytka :D:D Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: waveeeeeeeeeeee | Pridané: 29.10.2008 0:13 a ked si zoberiem nejake cislo z toho radu napr. 72 a odpocitam ho od seba sameho tak dostanem 0... ked to spravim z inym tiez dostanem 0 takze ta moja zatvorka je v poriadku.. neserte !!!mňe!!! Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: Rivale | Pridané: 27.10.2008 12:59 podobneho profaka sme mali aj my, chodil spavat so zositom a zbierkou brutalistickych prikladov a rano potom s nami riesil, ten ktory "nadherny" priklad nad ktorym sa trapil a nedokazal ho vyriesit. napokon aj zena od neho zutekala. namiesto zeny sa venoval prikladom :)) Odpovedať Známka: 4.3 Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: ---- | Pridané: 27.10.2008 15:39 Zena je f(peniaze) s nepredvidatelnym priebehom :) Odpovedať Známka: 10.0 Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od: 4ndr3y | Pridané: 27.10.2008 22:37 lol Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: Pjetro de | Pridané: 27.10.2008 18:35 Asi budem (opat) raz trapny, co sa tyka matiky, ale comu konktretne nerozumies? Cely druhy odstavec definuje Golombovu postupnost - a to dokonca gramaticky, t.j. slovami. O dost hroznejsie by to vyzeralo matematickym zapisom. Ktorej ciarke, pismenu, slovu, alebo vete definecie konkretne nerozumies? Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: Rivale | Pridané: 27.10.2008 20:09 trapny, netrapny, no celkovo tomu nerozumiem, a to mam sice elektrotechnicku, a riesili sme kadeco, ale na toto si nejak nepamatam, to uz bude asi vekom, ze som stary krapek, takze na takuto postupnost si absolutne nepamatam. princip uz chapem, z diskusie, ale aj tak celkovo tomu clanku som aj tak nepochopil. to je jedno, ja to k svojej profesii nebudem potrebovat. :)) Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: Pjetro de | Pridané: 27.10.2008 21:27 tot zakladny problem dnesneho vzdelavania ... - spusta ludi robi nieco uplne ine ako vystudovali - dost velku cast veci zo skolskych lavic (encyklopedicke znalosti) v zivote nevyuzijeme ... cest vynimkam ako slovencina, obcianska nauka, nauka o spolocnosti, sexulana vychova ze ano :-) a ine zaujimave pre zivot asi najpraktickejsie predmety Odpovedať Hodnotiť:

Re: dnes má meniny Sabina, zajtra Dobromila Od reg.: Rivale | Pridané: 28.10.2008 7:55 s tym suhlasim, ale slovencinu beriem cisto iba ako gramaticku cast a slohovu, co sa tyka literatury, aj to bolo uplne zbytocne, len nam zatazovali mozgy hovadinami. a najhorsie bolo to, ze ma profacka silno presvedcala, ze to budem nutne potrebovat k zivotu. A pravdu povediac, pohyboval som sa v roznych spolocnostiach ani raz sa ma nikto na nic okolo spisovatelov a basni a kadejakych somarin neopytal. litiku som absolutne neznasal, bolo to o biflovani a nedavalo to aj tak ziaden vyznam, hlavne tie metafory a sprostosti. basnik sa zhulil, napisal basen o vtakovi nad tatrami, a napokon myslel na svoju staru, a kadejake zvasty :)) Odpovedať Hodnotiť:

GPU-klient Od: sitokurvavygoogluj.sk | Pridané: 27.10.2008 11:20 keby mali k dispozicii GPU klienta tak by to bolo uz daaaaaavno hotove Odpovedať Známka: 8.8 Hodnotiť:

anteny? Od reg.: Prof. Ing. 3losh DrSc. | Pridané: 27.10.2008 11:21 Nahodou je to celkom zaujimave vymysliet si taky priklad a snazit sa ho vyriesit. Ale silno pochybujem ze by sa toto pouzivalo pri konstrukcii anten. Odpovedať Známka: -2.0 Hodnotiť:

anteny? Od: hrivis | Pridané: 27.10.2008 11:36 nechapem preco by to nemohlo byt pouzite... ani ja ani ty neskladame anteny.. nevieme velmi o tom o akej problematike taketo konstrukcie pojednavaju.. cize tvrdenie ze "pochybujem ...." nie je na mieste pekny den Odpovedať Hodnotiť:

Re: anteny? Od: waveee | Pridané: 27.10.2008 18:21 že.. {inak odpovedať powa} Odpovedať Hodnotiť:

Re: anteny? Od reg.: Pjetro de | Pridané: 27.10.2008 18:44 zeby siet anten kazda od kazdej v inej vzdialenosti? dovody a poziadavka na taketo rozmiestnenie uz ponuka fyzika ... Odpovedať Hodnotiť:

Vysletlenie z wikipedie Od: yanick (offline) | Pridané: 27.10.2008 11:55 http://tinyurl.com/6hvvbd Na wikipedii je to vysvetlene na 4 prvkoch: 0 1 4 6: 1: 1 - 0 2: 6 - 4 3: 4 - 1 4: 4 - 0 5: 6 - 1 6: 6 - 0 Na tej 25 prvkovej by mali byt cisla od 1 po 480 Odpovedať Hodnotiť:

.................... Od: waveeee | Pridané: 27.10.2008 18:22 co si na tomto vysvetlil... keby si to aspon porovnal Odpovedať Hodnotiť:

Aj cez boinc Od: Mirec6666 | Pridané: 27.10.2008 12:23 Do projektu je mozne zapojit sa aj cez boinc pomocou projektu yoyo@home. Odpovedať Hodnotiť:

vyborne Od: ARnyXXX | Pridané: 27.10.2008 12:27 Konecne dalsi projekt distribuovanych vypoctov ktory sa uspesne dopatral k vysledku. Zatial to boli iba dva co viem a to je desifrovanie sprav v kode enigma a teraz toto. Dost ma mrzi ze podobne vysledky nedosahuju ovela vacsie projekty pri ktorych sa mi to zda ako uplne zbytocne plytvanie el. energiou lebo nikdy k nicomu nedospeju a to je aj to co ma na nich stve. Odpovedať Známka: 10.0 Hodnotiť:

Re: vyborne Od: buri | Pridané: 27.10.2008 13:30 ...nikdy k nicomu nedospeju.. Co je to apatia neviem a ani ma to nezaujima ? :-) Kazdopadne aj vysledky tychto "malych" projektov mi pridu povzbudive. Odpovedať Hodnotiť:

Re: vyborne Od: ---- | Pridané: 27.10.2008 15:43 Veda bola vzdy o pokusoch postavenych na nerealnych predstavach ;) Odpovedať Hodnotiť:

Re: vyborne Od reg.: Domapracujuci | Pridané: 27.10.2008 16:20 Sorry, ja by som to upresnil: Veda je o pokusoch postavenych na fantazii a predstavach vznikajucich (v genialnych) v hlavach mudrych ludi, ktoré su v danom case pre vacsinu ostatnych ludi absolutne nerealne a nepredstavitelne aj ked su uplne realne co dokaze vedec svojou zatatostou a pracou (vacsinou poriadne dlhou a narocnou aj ked su aj vynimky) :-)) Odpovedať Hodnotiť:

Re: vyborne Od reg.: Pjetro de | Pridané: 27.10.2008 18:38 hmm, zalezi aka veda ... fyzika a chemia su experimentalno-naucne vedy, medicina observativno-naucna (pri troche morbidnosti aj experimentalna ze ano), matika cista abstraktna, rigorozna a deduktivna veda ... Odpovedať Hodnotiť:

Re: vyborne Od reg.: Domapracujuci | Pridané: 27.10.2008 21:13 Veda je vzdy Veda. Ale suhlasim s tebou, ze v niektorych vednych disciplinach resp. odboroch je tych pokusov (v chapani ako experiment) viac a inde menej. Pod pokusom som ale chapal nielen experiment ale aj akukolvek cestu k rieseniu zvoleneho problemu. A sme pri dalsom postulate vedcov, skor ako sa vedecky zacneme "bavit" musime si definovat terminologiu. Ale to uz je asi daleko od povodnej temy.. Odpovedať Hodnotiť:

Strach Od reg.: Extraterrenista | Pridané: 27.10.2008 13:56 Ako dobre,že som nerozumel ani slovo,inak by som sa už začal báť. Odpovedať Hodnotiť:

Re: Strach Od: ARnyXXX | Pridané: 27.10.2008 15:41 Hmm tak ta budem strasit CERNom bu bu bu ;) Odpovedať Známka: 7.5 Hodnotiť:

Re: Strach Od reg.: Don Mums | Pridané: 31.10.2008 13:23 http://www.youtube.com/watch?v=j50ZssEojtM&eurl http://osel.cz/index.php?obsah=6&clanek=3962 a pozri si aj obidve. :D Odpovedať Hodnotiť:

pravitko Od: aleluja | Pridané: 27.10.2008 15:55 A ja som sa tesil ze tu uvidim nejake hitech pravitko a nic :( Odpovedať Známka: 9.0 Hodnotiť:

hlupaci Od: Meno musí mať dĺžku aspoň | Pridané: 27.10.2008 23:30 pri konštrukcii pola rádiových antén. ty hlupak jeden bratislavsky, nevies napisat makcen??? poľa sa to pise spravne. bodaj by ta vyhodili Odpovedať Známka: -5.0 Hodnotiť:

Re: hlupaci Od: buri | Pridané: 28.10.2008 20:26 Takymto typo nazi som nikdy nerozumel, nic v zlom ale co Ta vedie k takejto reakcii ? Ved este aj v slove mekcen Ti chyba mekcen . Odpovedať Hodnotiť:

Re: hlupaci Od: poihu | Pridané: 29.10.2008 9:58 ale si mu to natrel :D Odpovedať Hodnotiť:

ach joo Od: hmm | Pridané: 30.10.2008 22:16 Ked zatrepem co najviac odborych slov, ktorych poriadne ani nepoznam vyznam tak som vyhral ? // v BA tak hovori, no co , nebudeme riesit 3.14coviny (mam prvy bod za to pi) Odpovedať Hodnotiť:

Pridať komentár