Hoofdcategorieën

[RSS] Index » Nieuws » Core » Wetenschap » Oplossing Rubik-kubus stapje versneld

Oplossing Rubik-kubus stapje versneld

Door Marco Hordijk, vrijdag 28 maart 2008 13:59
Submitter: Holoris, views: 35.691

Het is Tomas Rokicki gelukt om een stap dichterbij 'God's Number' te komen: hij heeft een manier gevonden om de Rubik-kubus altijd in 25 stappen op te lossen. Het oude record stond op 26 slagen.

Halverwege augustus vorig jaar wisten twee studenten van de universiteit in Boston een methode te ontwikkelen om de Rubik-kubus in maximaal 26 slagen op te lossen, ongeacht de beginstand. Wiskundige Tomas Rokicki heeft hun record echter aangescherpt met een verlaging van het maximumaantal slagen naar 25. Het minimumaantal stappen dat nodig is om elke verhusselde Rubik-kubus op te lossen, ook wel bekend als 'God's Number', zou volgens wetenschappers tussen de 20 en 25 liggen.

Rokicki heeft zijn record bewerkstelligd door alle mogelijke configuraties van de kubus in te delen in twee miljard verzamelingen, die ieder weer uit twintig miljard elementen bestaan. Een groot aantal verzamelingen kon dankzij symmetrie genegeerd worden, waardoor het totaal aantal mogelijke posities gereduceerd werd. Door oplossingen voor de overgebleven verzamelingen met zestien miljoen posities per seconde door te rekenen, kostte het de gebruikte computer een kleine 63 dagen om alle mogelijke oplossingen te beschouwen. Terwijl de onderzoekers uit Boston van een supercomputer gebruikmaakten, heeft Rokicki het rekenwerk weten te klaren met een workstation met 8GB aan geheugen en een Intel Core 2 Quad Q6600, die op 1.6GHz geklokt was. Wat de gedachte achter het onderklokken van de Q6600 is, is niet bekend.

Makkelijk oplosbare Rubik-kubus

Volgende 14:33
Vorige 13:19

Categorieën

Tags

Gerelateerde artikelen

Reacties

Flat modeFlat mode Sorteer aflopendSorteer aflopend Moderatie FAQModfaq
Niveaufilter: -1 Ongewenst: 77 reacties zichtbaar770 Neutraal: 54 reacties zichtbaar54+1 Meerwaarde: 9 reacties zichtbaar9+2 Verplicht leesvoer: 0 reacties zichtbaar0
«  1  2  3  »

Door Bever!, vrijdag 28 maart 2008 14:01

Score: 0
Gedachte achter het onderklokken zal het minimaliseren van rekenfoutjes zijn..

Door Rizon, vrijdag 28 maart 2008 14:09

Score: 0
Misschien durfde meneer een cpu geen 2maand laten draaien op volle lading (hallo folding? :p).
Of de cpu werktte gewoon niet op maximale belasting en underclockte naar 1.6 is ook een mogelijkheid.

Door Soze, vrijdag 28 maart 2008 14:16

Score: 0
Of domweg energiebesparing. Dikke kans dat het doorrekenen net zo snel werkt op 1.6 GHz omdat de FSB of het geheugen de bottleneck is voor dit probleem en niet de CPU snelheid...

Door Moe_Szyslak, vrijdag 28 maart 2008 14:31

Score: 0
Dat kan best kloppen ja. Ik heb ook een Q6600 en als hij niet genoeg belast word, dan clocked hij automatisch terug naar 1,6Ghz. Dit is in de BIOS in te stellen. Je kan het automatisch underclocken ook uit zetten, mocht je dat willen.

Door HenkEisjedies, vrijdag 28 maart 2008 15:21

Score: 0
Ik geloof dat bij supercomputers het belangrijker is de data snel genoeg toe en af te voeren naar/van de processor dan de kracht van de processor zelf. Misschien dat de verhouding tussen doorvoorsnelheid en processorkracht zo beter klopte?

A supercomputer is a device for turning compute-bound problems into I/O-bound problems. - Ken Batcher

Door TD-er, vrijdag 28 maart 2008 14:20

Score: 0
Mijn eerste idee was dat mogelijk de verhouding van het gebruikte geheugen en de bus-frequentie mogelijk iets beter op elkaar aansluit, waardoor het geheugen mogelijk net een fractie sneller zou kunnen voor deze specifieke toepassing.
Zo'n 70 dagen geleden was 2 GB 1066 MHz geheugen mogelijk wat minder goed verkrijgbaar?

[Reactie gewijzigd door TD-er]

Door fevenhuis, zaterdag 29 maart 2008 00:46

Score: 0
Wellicht probeerde men met het onderklokken het kacheleffect van een 100% load quadcore wat te verminderen. Je kunt er je kantoor er aardig mee verwarmen hoor.
Laat staan hoeveel herrie een gemiddelde ungetweakte machine produceerd onder lange load sessies, je zal dan toch echt wat harder door de telefoon moeten praten

Door MneoreJ, vrijdag 28 maart 2008 14:04

Score: 1
Wat de gedachte achter het onderklokken van de Q6600 is, is niet bekend.
Tja, wat is normaal de gedachte achter onderklokken? Ten eerste energiebesparing (lijkt me hier niet relevant), ten tweede het verhogen van de betrouwbaarheid. En dat laatste is best aannemelijk, want je hebt tenslotte geen zak aan het doorrekenen van een paar miljard scenario's om tot een maximum te komen als blijkt dat er hier en daar wel een paar foutjes gemaakt kunnen zijn die het resultaat waardeloos maken.

Maar natuurlijk kan de gast ook gewoon een tikfout hebben gemaakt, of zijn BIOS verkeerd afgesteld hebben...

Edit: maximum, geen minimum. Belangrijk detail. :)

[Reactie gewijzigd door MneoreJ]

Door bbob1970, vrijdag 28 maart 2008 16:54

Score: 0
betrouwbaarheid vraag ik me af. Intel cpu's zijn zelfs perfekt te overclocken dus kun je zelfs stellen dat ze zoals ze geleverd worden eigenlijk al standaard underclocked zijn.

Het lijkt me ook sterk dat er bij underclocken minder fouten zijn in vergelijking tot de standaard snelheid. Dit soort cpu's mogen dat soort fouten niet eens maken.

Door MneoreJ, vrijdag 28 maart 2008 17:49

Score: 1
Welnu, CPUs maken nou eenmaal fouten. Hoe hoger de termperatuur, hoe meer. Er is geen temperatuur waarbij je kan zeggen dat de CPU foutloos loopt; je kunt alleen zeggen dat het interval tussen fouten dan zo lang is dat het niet meer relevant is. Zelfs Intel zal jou niet snel de garantie geven dat je CPU foutloos functioneert, al mogen ze het ding diepvriezen en in twee meter lood installeren. Dat "perfect te overklokken" wordt meestal ook maar beperkt getest, hoor -- dat bijvoorbeeld je CPU SuperPI X minuten lang goed uitvoert bewijst nog niet dat alles goed werkt.

Als je vier cores meer dan een maand op volle belasting gaat draaien om een zeer discontinu probleem op te lossen is underclocken voor de zekerheid zo slecht nog niet. Hadden de cores het ook goed gedaan op volle snelheid? Waarschijnlijk wel, maar ik moet dan ook zeggen dat ik zoiets nog nooit heb geprobeerd.

Een alternatief zou zijn geweest om twee (of meer) onafhankelijke systemen hetzelfde te laten berekenen en de resultaten naast elkaar te leggen. Dat is beter dan één systeem zo betrouwbaar mogelijk maken.

Edit: "discontinu" is minder dubbelzinnig dan "discreet".

[Reactie gewijzigd door MneoreJ]

Door Madrox, zaterdag 29 maart 2008 00:31

Score: 0
Lijkt me toch sterk wat je nu zegt. Volgens mij moet een CPU die Intel levert, die bijv. op 3 GHz is gecertificeert, foutlous werken. Ook op volle CPU-belasting.

Door MneoreJ, zaterdag 29 maart 2008 01:51

Score: 1
Natuurlijk, maar definieer "foutloos". Denk daar voor mijn part aan zoiets als "een kans van 50% op één enkelbitsfout per 1,000 jaar bij een temperatuur van 40 graden en een stralingsniveau van niet meer dan 1 mSv per jaar" of zoiets extreems, wat in de praktijk dus "foutloos" is omdat de chip allang gestorven is aan natuurlijke oorzaken voor die periode bereikt wordt. Ik heb geen idee van wat voor garanties Intel aflevert, trouwens.

Zo vaag als "100% correct" zal het in ieder geval niet zijn; je kunt natuurlijke processen nou eenmaal niet voor 100% beheersen. We denken graag dat CPU's perfecte machientjes zijn die alleen de fout in kunnen gaan als een of ander botte boer een ontwerpfout heeft gemaakt, maar zo is het natuurlijk niet. CPU's zijn wel opmerkelijk betrouwbaar, maar desondanks niet volmaakt. Een kans op fouten bestaat altijd; het gaat erom dat die kans bij normaal gebruik zo irrelevant mogelijk is.

Door CyBeR, zaterdag 29 maart 2008 22:18

Score: 0
Niks sterks aan. Waarom denk je dat ze in de ruimtevaart 200MHz processoren gebruiken? (En dan nog een speciale uitvoering ook). Om rekenfouten te voorkomen.

Die dingen maken fouten. Net als geheugen. Dat gebeurt niet vaak, maar 't gebeurt wel. (En meestal merk je 't aan een random crash.)

Door kimborntobewild, maandag 31 maart 2008 06:13

Score: 0
@CyBeR:
Omdat in de ruimte veel meer straling is. Moderne quad-core CPU's hebben veel minder weerstand tegen straling. Op aarde heb je daar niet zoveel last van, maar in de ruimte des te meer.
Bij 200Mhz chips zijn de schakelingen groter waardoor er veel minder kans is op schade door straling.

Door een_naam, vrijdag 28 maart 2008 14:04

Score: 0
Ik vind dat soort mensen die dit soort "problemen" oplossen echt geweldig, ik zou er zelf niet het geduld voor hebben om daar zo'n werk van te maken en waarschijnlijk ben ik er ook niet slim genoeg voor, maar voor de rest hulde aan Thomas _/-\o_ . Hopelijk komen mensen door zijn methode nog op ideeen om echt belangrijke zaken snel op te lossen (oplossingen voor ziektes etc).

Ik heb wel eens een documentaire gezien over autisten die heel goed in staat zijn om zich op bepaalde zaken enorm te concentreren, een "normaal" mens kan zo'n concentratie niet opbrengen. Einstein schijnt ook autistische trekken te hebben gehad, niet dat Thomas met Einstein vergeleken kan worden. Ik vraag me gewoon af of Thomas een normaal mens is waarmee je ook normaal een biertje kan drinken en gezellig mee in een kroeg kan zitten ofdat hij zo'n figuur is waarmee het heel moeilijk is communiceren vanwege een of andere autistische aanleg.

[Reactie gewijzigd door een_naam]

Door .biz, vrijdag 28 maart 2008 14:30

Score: 0
Ik dacht dat God's number 42 was?

In ieder geval, het oplossen van "nuttige zaken" zoals ziektes berust niet alleen op tijd en aandacht, maar ook op inzichten uit navenante onderzoeksgebieden. In dit geval is er dus een methodiek ontwikkeld waarmee wiskundig of statistisch een groot aantal oplossingen sneller kunnen worden doorgerekend. Als je weet hoe je een ziekte (oid) goed kunt modelleren, dan kun je dus ook sneller "de oplossing" doorrekenen, whatever that may be.

Bonus hier is dat hij het op een 'oud bakbeest' heeft gedaan, daar waar zijn conculega's dit op supercomputers moeten doen.

Met andere woorden, misschien kun jij ooit je Nintendo Wii inzetten om Hepatitis B 'op te lossen' ;)

Door Zyppora, vrijdag 28 maart 2008 15:09

Score: 0
Misschien dat je die 42 door 2 mag delen ivm. symmetrie van de kubus? :D

Door jaapstobbe, vrijdag 28 maart 2008 14:05

Score: 0
Beter in een keer goed na 63 dagen, dan steeds een foutje na 42 dagen

Door Rizon, vrijdag 28 maart 2008 14:12

Score: 0
Slaat op niet veel aangezien vele folders hun cpu's tot de grens overklokken. Op standaard clocks werkt folding gewoon overal foutloos.

Door Jeanpaul145, vrijdag 28 maart 2008 17:24

Score: 0
Folding kan je niet vergelijken met de inspanningen van 1 enkele losse computer. Om de resultaten van folding ook maar enigszins betrouwbaar te maken zal er zeker redundancy moeten optreden, oftewel ze hebben in de folding software ingebakken dat elke berekeninng uiteindelijk wel wordt geverifieerd door m opnieuw uit te voeren lijkt me.

Een losse computer heeft die resources niet, dus moet hij op een andere manier zn betrouwbaarheid vergroten.

Door burne, vrijdag 28 maart 2008 14:41

Score: 0
63 dagen blijft lang, zeker als je het vergelijkt met dit soort mensen:

http://www.maniacworld.com/one-handed-rubiks-cube.html

Door Boogerschmidt, vrijdag 28 maart 2008 14:52

Score: 0
Hoewel het ziekelijk indrukwekkend is, lost die kerel slechts 1 configuratie op in meer dan 25 stappen. Benieuwd hoe 'ie presteert als 'ie alle mogelijke configuraties in minder dan 26 stappen moet oplossen in 63 dagen.

[Reactie gewijzigd door Boogerschmidt]

Door sgaap, vrijdag 28 maart 2008 17:28

Score: 0
Haha vet, en dat met 1 hand... hij heeft er alleen wel ruim 40 stappen voor nodig...

Door g4wx3, vrijdag 28 maart 2008 18:29

Score: 0
Nu moet ie proberen 2 tegelijk op te lossen, heeft toch de andere hand vrij :p.

Ongelooflijk..

Door LOTG, vrijdag 28 maart 2008 14:06

Score: 0
Wat de gedachte achter het onderklokken van de Q6600 is, is niet bekend.
Of er een dikke FSB op zetten.

Maar het is toch opzich een snelle verbetering van het record vind ik. Als je bedenkt dat er toch wel wat tijd achter zit om het algoritme te bedenken en te testen.

[Reactie gewijzigd door LOTG]

Door waffels, vrijdag 28 maart 2008 14:09

Score: 0
Heeft er iemand enig idee hoeveel verschillende configuraties zo'n kubus in totaal kan hebben? Ik ga er vanuit dat dit getal zo groot is dat men ze niet allemaal kan nagaan om het gods number te berekenen?

Door Gamo, vrijdag 28 maart 2008 14:22

Score: 0
"Rokicki heeft zijn record bewerkstelligd door alle mogelijke configuraties van de kubus in te delen in twee miljard verzamelingen,..."

Hij heeft ze allemaal laten berekenen, en wat de oplossing daarvan dan is.

Door slow whoop, vrijdag 28 maart 2008 14:30

Score: 1
Aantal verschillende permutaties voor een 3x3x3 kubus = 43,252,003,274,489,856,000

[Reactie gewijzigd door slow whoop]

Door .oisyn, vrijdag 28 maart 2008 14:38

Score: 1
Simpel. Elk middelste blokje van een 3x3 vlak zit "vast" op de kubus. Je kunt ze wel roteren, maar daardoor verandert z'n positie niet. Je hebt 8 hoekpunten en 12 zijkanten, dus als je een kubus in elkaar zou zetten kun je (8! * 38) * (12! * 212) = 519.024.039.293.878.272.000 verschillende combinaties maken.

Echter, niet al die combinaties zijn mogelijk zonder blokjes van de kubus af te halen en er weer op te zetten. Zo kun je twee zijkanten niet omwisselen (combinaties / 4) en hoekpunten niet roteren (combinaties / 3). Je houdt dus 519.024.039.293.878.272.000 / (3*4) = 43.252.003.274.489.856.000 combinaties over :). In woorden: meer dan 43 triljoen mogelijkheden.

[Reactie gewijzigd door .oisyn]

Door RolfLobker, vrijdag 28 maart 2008 14:54

Score: 0
Daarom zei ik ook dat hij misschien ergens een foutje gemaakt heeft ;)
Bijvoorbeeld een onnodige conversie van big- naar lowendian of zo :Y)

[Reactie gewijzigd door RolfLobker]

Door g4wx3, zaterdag 29 maart 2008 09:20

Score: 0
Misschien een software fout, maar ze hadden beter de processor underclockt, omdat hij toch wel lang heeft moeten draaien

Door Neus, vrijdag 28 maart 2008 14:14

Score: 0
Gaaf! Kan ik ergens een PDF in kleur downloaden met alle mogelijke oplossingen? Heb nog een aantal gigabytes op mijn disk over en heb net nieuwe inktpatronen gekocht :+

Door RolfLobker, vrijdag 28 maart 2008 14:26

Score: 0
Algoritmes en oplossingen kan je ook op youtube vinden :)
Ziet er niet eens zo moeillijk uit zolang je maar goed kan onthouden en de tijd neemt om goed te oefenen / trainen.
Er zijn dan ook genoeg mensen die een rubix in een paar seconden op weten te lossen.

Door gersompie, vrijdag 28 maart 2008 14:32

Score: 0
Er staan inderdaad een boel filmpjes op youtube van kinderen van 5 die dat ding in minder dan een minuut oplossen |:(
Mijn record staat nog steeds op 1minuut en 11 seconden O-)

"Wiskundige Tomas Rokicki heeft hun record echter aangescherpt met een verlaging van het maximumaantal slagen naar 25."
Is er een oplosmethode waarmee dit altijd feilloos te bereiken is?

Door RedSoniq, vrijdag 28 maart 2008 14:32

Score: 1
De uiteindeljke oplossing ... daar is er geloof ik maar 1 van. :)

Alle variates mag je zelf uittekenen van me. ;)

Door _fool, vrijdag 28 maart 2008 15:40

Score: 1
Die uiteindelijke oplossing, daar zijn er eigenlijk meer van.

Sommige kubussen zijn met voor de grap met foto's bedrukt. Als je daarmee zou gaan puzzelen kom je voor een onaangename verrassing te staan: bij een opgeloste kubus kunnen de middenvlakken geroteerd zijn ten opzichte van de oorspronkelijke foto. De plek van de middenvlakjes is juist, maar de orientatie niet. Bij een originele rubik's kubus is dat verschil niet te zien omdat de vlakjes egaal zijn.

Met andere woorden: niet iedere "opgeloste" kubus bevindt zich in exact de oorspronkelijke staat.

Stel dat je een kubus wel altijd tot die oorspronkelijke staat zou willen terugbrengen, welke invloed zou dat hebben op God's Number? Misschien wil meneer Rokicki het nog een keertje narekenen...
«  1  2  3  »

Op dit item kan niet meer gereageerd worden.

Volgende 14:33
Vorige 13:19
VNU Media logo Powered by True

© 1998 - 2008 Tweakers.net - Alle rechten voorbehouden

Uitgever van: