Rubikwürfel Gottes Zahl lautet 20
Seite 2/2:
Google spendierte Rechenzeit von zusammengenommen 35 Jahren
Vor 15 Jahren untersuchte der US-Amerikaner Michael Reid die sogenannte Superflip-Position, bei der die Ecken des Würfels und die Plättchen in der Mitte der Seiten bereits stimmen. Die Flächen an den Kanten zwischen den Ecken sind aber gerade so vertauscht, dass jeweils die Farbe der Nachbarseite zu sehen ist. Für eine solche Ausgangslage, fand Reid heraus, braucht man mindestens 20 Züge.
Das amerikanisch-deutsche Viererteam hat nun bewiesen, dass alle 43 Trillionen Würfelstellungen mit höchstens 20 Verdrehungen zu meistern sind. Da sich so viele verschiedene Ausgangslagen selbst mit dem schnellsten Computer nicht durchprobieren lassen, benutzten die vier Forscher algebraische Methoden, um jeweils knapp 20 Milliarden Stellungen zu einem Problem zusammenzufassen. Dadurch mussten sie nur noch etwas mehr als zwei Milliarden Aufgaben lösen. Weil viele Ausgangspositionen zueinander symmetrisch sind, konnten sie diese Anzahl noch mal auf knapp 56 Millionen verringern.
Diese 56 Millionen Fälle arbeiteten sie einen nach dem anderen ab. Die von der Firma Google spendierte Rechenzeit addierte sich dabei auf 35 Jahre. Die Computer suchten nicht für jede Startstellung eine optimale Lösung, sondern nur eine, die mit höchstens 20 Zügen auskam. Denn eine Position, die 20 Verdrehungen erfordert, war ja schon bekannt. Dadurch konnten sie die Rechenzeit erheblich verkürzen.
Ausgangslagen, die in nicht weniger als 20 Zügen zu lösen sind, gibt es den Forschern zufolge relativ selten. Nur eine von mehr als einer Milliarde Stellungen erwies sich als nicht mit weniger Verdrehungen zu sortieren. Doch sind das immerhin noch mehr als Hundert Millionen Anordnungen des Würfels.
Übersicht zu diesem Artikel
- Seite 1 Gottes Zahl lautet 20
- Seite 2 Google spendierte Rechenzeit von zusammengenommen 35 Jahren
Anzeige
- Datum 10.08.2010 - 11:39 Uhr
- Seite 1 | 2 | Auf einer Seite lesen
- Quelle ZEIT ONLINE
- Kommentare 39
- Versenden E-Mail verschicken
- Empfehlen Facebook, Twitter, Google+
- Artikel Drucken Druckversion | PDF
-
Artikel-Tools präsentiert von:
ist da Frage dann nicht die nach den maximalen Zügen die gebraucht werden um jeden beliebigen Würfel zu lösen?
:-)
Ich kann da meinen Vorrednern nur zustimmen. Nach der jetztigen Überschrift passt jede Zahl >= 20 als Antwort :)
Außerdem würde ich es noch feiner Definieren: "Wie viele Drehungen braucht man maximal für jede erdenkliche Position?"
Züge bestehen - für mein Verständnis - aus einer Abfolge von mehreren Drehungen. Man sagt ja auch: "Du musst jetzt diesen oder jenen Zug anwenden".
Nur weil ich weiß dass 1 1 eine natürliche Zahl (formal: aus N) ist, kann ich nicht schlussfolgern, dass 1 n, für n aus N wieder aus N ist. Dafür gibt es 0 Punkte! Soetwas kann sich höchstens Beweis nennen, wenn das Team nachweisen kann, dass der angewendete Algorithmus zum Lösen des Problems optimal ist. Und auch dann ist der Satz immer noch Quatsch, weil wie im Text beschrieben, approximiert wird und damit sehr wohl Probleme existieren die, wie ebenfalls im Text erwähnt, NICHT in 20 Schritten gelöst werden können. Unter der Vorraussetzung eines optimalen Algorithmus kann dann nur gesagt werden, dass mit einer gewissen Wahrscheinlichkeit, die hier sehr hoch ist, sich ein Problem in höchstens 20 Schritten lösen lässt.
Induktionsvoraussetzung: (1*n) € N für 1 € N und n € N
Induktionsanfang: 1*1 = 1 € N
Induktionsschluss: 1* (n 1) = 1*n 1*1, also (1*n) € n und (1*1) € n, somit (1*n 1*1) € n.
Es wurden alle möglichen Stellungen des Rubiks Cube in 20 oder weniger Schritten gelöst. Wenn das kein Beweis ist, was dann?
Und bevor jetzt noch ein Kommentar kommt in dem Sie behaupten, dass irgendwas approximiert wird, lesen Sie sich den Artikel lieber nochmal in Ruhe durch.
"Die Computer suchten nicht für jede Startstellung eine optimale Lösung, sondern nur eine, die mit höchstens 20 Zügen auskam. Denn eine Position, die 20 Verdrehungen erfordert, war ja schon bekannt."
Induktionsvoraussetzung: (1*n) € N für 1 € N und n € N
Induktionsanfang: 1*1 = 1 € N
Induktionsschluss: 1* (n 1) = 1*n 1*1, also (1*n) € n und (1*1) € n, somit (1*n 1*1) € n.
Es wurden alle möglichen Stellungen des Rubiks Cube in 20 oder weniger Schritten gelöst. Wenn das kein Beweis ist, was dann?
Und bevor jetzt noch ein Kommentar kommt in dem Sie behaupten, dass irgendwas approximiert wird, lesen Sie sich den Artikel lieber nochmal in Ruhe durch.
"Die Computer suchten nicht für jede Startstellung eine optimale Lösung, sondern nur eine, die mit höchstens 20 Zügen auskam. Denn eine Position, die 20 Verdrehungen erfordert, war ja schon bekannt."
"Zum Vergleich: Würde man 43 Trillionen Rubikwürfel aufeinander schichten, ergäbe sich ein Turm, der weit über 200 Lichtjahre ins Weltall hinein ragen würde."
Bei diesem Vergleich musste ich lachen - jetzt ist mir die Dimension klar geworden ;-).
Aber...
"Die von der Firma Google spendierte Rechenzeit addierte sich dabei auf 35 Jahre."
...was sagt dieser Vergleich aus? Denn Google hat ja nicht 35 Jahre seiner kompletten Rechenzeit geopfert, sondern die Rechenkapazität, die 35 Jahren der Rechenzeit eines Vergleichssystems entspricht - welches allerdings nicht genannt wird. 35 Jahre Rechenzeit eines Abakus sind dann doch eine andere Größenordnung als 35 Jahre eines C64 oder 35 Jahre einer Cray.
35 Jahre hätte die Kalkulation mit der Goole-Power benötigt bevor die Mathematiker die zu berechnenden Kombinationen weiter einschränkten. So hab ich das zumindest verstanden.
Ich interpretiere die 35 Jahre als tatsächliche Rechenzeit auf den tatsächlichen Prozessoren oder Prozessorkernen, addiert.
35 Jahre hätte die Kalkulation mit der Goole-Power benötigt bevor die Mathematiker die zu berechnenden Kombinationen weiter einschränkten. So hab ich das zumindest verstanden.
Ich interpretiere die 35 Jahre als tatsächliche Rechenzeit auf den tatsächlichen Prozessoren oder Prozessorkernen, addiert.
35 Jahre hätte die Kalkulation mit der Goole-Power benötigt bevor die Mathematiker die zu berechnenden Kombinationen weiter einschränkten. So hab ich das zumindest verstanden.
der Googledienst lahm gelegen. ;-)
"Die von der Firma Google spendierte Rechenzeit addierte sich dabei auf 35 Jahre." - Es geht wohl schon um die tatsächlich gespendete Rechenzeit für die Berechnung der 56 Millionen Fälle.
Es fehlt das Maß für die Rechenleistung pro Jahr. Bei einem "Mannjahr" geht es um die Arbeitsleistung einer Person in einem Jahr. Bei einem "Rechnerjahr" kann es um die Rechnerleistung in einem Jahr gehen. Diese ist allerdings nicht genannt und abhängig vom verwendeten Rechner auch extrem unterschiedlich. Die Aussage entspricht also ungefähr der Aussage: "X spendete 35 Geldscheine."
der Googledienst lahm gelegen. ;-)
"Die von der Firma Google spendierte Rechenzeit addierte sich dabei auf 35 Jahre." - Es geht wohl schon um die tatsächlich gespendete Rechenzeit für die Berechnung der 56 Millionen Fälle.
Es fehlt das Maß für die Rechenleistung pro Jahr. Bei einem "Mannjahr" geht es um die Arbeitsleistung einer Person in einem Jahr. Bei einem "Rechnerjahr" kann es um die Rechnerleistung in einem Jahr gehen. Diese ist allerdings nicht genannt und abhängig vom verwendeten Rechner auch extrem unterschiedlich. Die Aussage entspricht also ungefähr der Aussage: "X spendete 35 Geldscheine."
Lieber Herr Schwarz,
im Untertitel zu diesem Artikel steht das Wort "Zug" synonym für "Drehung".
Es ist richtig, dass maximal 20 Züge (oder eben Drehungen) nötig sind, um jede mögliche Würfelkombination zurück in den Ursprungszustand zu überführen.
Grüße aus der Wissen-Redaktion
1) "Wie viele Züge sind mindestens notwendig, um einen irgendwie verdrehten Würfel zu ordnen?"
2) "..hat sich für die minimale Anzahl ein unbescheidener Name eingebürgert"
3) "Für eine solche Ausgangslage, fand Reid heraus, braucht man mindestens 20 Züge."
1) "Wie viele Züge sind mindestens notwendig, um einen irgendwie verdrehten Würfel zu ordnen?"
2) "..hat sich für die minimale Anzahl ein unbescheidener Name eingebürgert"
3) "Für eine solche Ausgangslage, fand Reid heraus, braucht man mindestens 20 Züge."
Ich interpretiere die 35 Jahre als tatsächliche Rechenzeit auf den tatsächlichen Prozessoren oder Prozessorkernen, addiert.
Bitte melden Sie sich an, um zu kommentieren