+- Speedcube.de Forum (https://forum.speedcube.de)
+-- Forum: Sonstiges (https://forum.speedcube.de/forumdisplay.php?fid=14)
+--- Forum: Off-Topic (https://forum.speedcube.de/forumdisplay.php?fid=16)
+--- Thema: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie (/showthread.php?tid=4751)
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - davidk - 04.04.2012
Moin, ich habe eine Frage zum selben Thema auch zur Gruppentheorie und irgendwie hake ich an einer Stelle: Die Cube-Gruppe hat ja die Ordnung 4,3*10^19 oder irgendwie so. Jetzt habe ich aber gelesen, dass der Zug R U2 D' B D' die Ordnung 1260 hat. Das mag sein, aber dann stand da auch, dass es keinen Zug mit größerer Ordnung gibt und das erscheint mir irgendwie unlogisch, dass müsste ja bedeuten, dass die Permutationsgruppe des Cubes nur in Untergruppen geteilt werden kann, die eine Ordnung kleiner, oder gleich 1260 haben. Wäre lieb wenn mir einer von euch helfen würde... geht nämlich um meine Abipräsentation
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - loose - 04.04.2012
Du verwechselst Ordnung einer Gruppe mit der Ordnung einer Permutation. Letzteres ist die Zahl der benötigten Hintereinanderausführungen um wieder die Identität zu erreichen.
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - Sébastien - 04.04.2012
Du musst in der Mathematik auf die Details achten. Eine Gruppe und eine Permuation von Gruppenelementen sind verschiedene Konstrukte, dementsprechend bedeutet auch der Begriff Ordnung bei beiden etwas unterschiedliches.
Interessant dürfte für dich der Satz von Lagrange sein (wenn du den nicht eh schon betrachtest): Demnach ist nämlich die Ordnung jeder Permuation von Gruppenelementen ein Teiler der Gruppenordnung.
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - davidk - 05.04.2012
Ja an dem Satz von Lagrange bin ich schon dran
Aber ist es nicht so, dass das Hintereinanderausführen einer Permutation eine Untergruppe erzeugt, die gleich der Ordnung der Permutation ist? Das hieße dann doch, dass die Permutation, die durch den Zug R U2 D' B D' erreicht wird eine Untergruppe der Cube-Gruppe erzeugt, die die Ordnung von 1260 hat. Und wenn sich kein Zug mit einer größeren Ordnung findet, dann gibt es doch auch keine Untergruppen größer 1260, oder? ... So ein Mist, ich glaube ich habe es immer noch nicht verstanden...
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - moritz - 05.04.2012
die einzige aussage die du gemacht hast ist: untergruppen die sich als <"algo"> schreiben lassen, können keine größere ordnung als 1260 haben.
aber eine untergruppe kann ja auch von mehreren elementen erzeugt werden. z.b. <R,U> wird von zwei zügen erzeugt. (ich hab das grad nicht nachgerechnet aber ich behaupte mal die ordnung ist größer als 1260)
und dann gibt es ja auch noch ganz andere untergruppen wie z.b. alle positionen die mit einer geraden anzahl an 90°-drehungen erreicht werden können.
(oder die gruppe selbst ist auch immer ne untergruppe :ugly: )
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - davidk - 21.04.2012
Okay ich habe es inzwischen. Die Rubiks-Cube-Gruppe ist ja keine zyklische Gruppe. Das mit dem Gottesalg hatte mich irritiert, weil ich dachte das von einer Permutation die Rede ist, die alle anderen erzeugt, aber beim Gottesalg geht es ja darum einen Alg zu finden, nach dessen schrittweiser Ausführung irgendwann die Identität erreicht ist.
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - davidk - 21.04.2012
Mal eine ganz - oder nicht ganz - andere Frage. Man hat ja nun bewiesen, dass Gotteszahl nicht etwa drei ist wie die Theologen behaupten
sondern 20. Kann mir jemand erklären, wie der Herr Kociemba und seine Kollegen das bewiesen haben? Ich weiss, dass sie seinen Zwei-Phasen-Algorithmus benutzt haben und ich weiss, dass dabei Nebenklassen Untergruppen und Symmetrien eine wichtige Rolle gespielt haben. Aber besonders am Zwei-Phasen-Alg hackt es noch bei mir. So wie ich es verstanden habe eine bestimmte Würfelkonfiguration erst in die Gruppe G1= <U,D,R2,L2,F2,B2> transformiert und die Zuglänge dafür abgeschätzt. In der zweiten Phase wird dann die erreichte Konfiguration aus G1 in den Ausgangszustand des Würfels gebracht. Das leuchtet mir noch ein: Statt die optimale Lösung zu suchen, reicht es zu zeigen, dass man weniger, als zwanzig Züge braucht, um den Würfel zu lösen (Das ist doch der Trick, oder?) Was mir noch unklar ist, ist wieso es reicht bestimmte Nebenklassen, oder Untergruppen zu untersuchen. Und was passiert wenn man tatsächlich eine Konfiguration, wie den Superflip hat, der 20 Züge bis zur Identität erfordert? Dann sucht sich dieser Zwei-Phasen Algorithmus doch tot, oder? Herbert Kociemba schreibt außerdem, dass wenn die in Phase 1 ermittelte Zuglänge bis G1 und die in Phase zwei ermittelte Zuglänge bis zum gelösten Würfel eine bestimmte Anzahl an Zügen übersteigt, der Zug von der Ausgangskonfiguration bis zu einem Element von G1 verlängert wird, um so Phase zwei zu verkürzen. Wieso versucht man nicht Phase eins zu verkürzen? Und warum ist, wenn Phase zwei eine Zuglänge von 0 ergibt die Lösung optimal (so schreibt es Kociemba), dass muss doch nicht zwangsläufig so sein, oder? diese Nebenklassen und Untergruppen nutzt er doch irgendwie aus, um nicht äquivalente Konfigurationen doppelt zu untersuchen, also z.B. nicht die Konfiguration, die durch den Algorithmus R2 erreicht wird und die Konfiguration U2, oder? Aber wie stellt er das an und wie nutzt er dabei die Nebenklassen und Untergruppen aus?Problem ist ich habe ihn gefragt, ob ich ihn mal anrufen kann und ihn ein paar Sachen fragen kann, aber ich glaube, wenn er solche trivialen (für mich leider nicht) hört legt er gleich wieder auf ^^ (hoffe die Frage ist hier nicht fehl am Platz, passt ja zu Gruppentheorie und Gotteszahl, deswegen wusste ich nicht so richtig wohin damit) LG
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - tim - 21.04.2012
Die Idee, wie früher die oberen Grenzen für die maximale Zuganzahl abgeschätzt wurden, ist in etwa folgende:
Nimm ein paar Untergruppen vom Würfel (im Fall vom Zwei-Phasen-Alg eben zwei) und berechne für jede Untergruppe die optimale Lösung (die Anzahl der Züge reicht) aller Stellungen. Da die Untergruppen viel kleiner sind als die gesamte Würfelgruppe, kann man das wirklich berechnen. Und dann kommt zum Beispiel raus:
maxZüge(G1) = 10
maxZüge(G2) = 12
Jetzt weiß man also, dass jede Stellung in 10 + 12 = 22 Zügen lösbar ist. Es kann aber auch besser gehen. Dann nämlich, wenn jeder Würfel, der bei Phase I 10 Züge braucht und bei Phase II 12, sich optimal in < 22 Zügen lösen lässt. All diese Würfel könnte man sich jetzt schnappen und für die die optimale Lösung berechnen. Das werden in der Regel nicht all zu viele sein und mit etwas Geduld und Rechenpower kriegt man für die dann raus, dass sie alle <= 20 Züge brauchen. Dann wäre man also bei 21 Zügen als Grenze. Nun könnte man diese Würfel... und so weiter.
Wie genau sie jetzt die 20 ausgerechnet haben bzw. welche Würfelstellungen sie durchgerechnet haben, weiß ich nicht. Aber es war auf jeden Fall kein einfacher Beweis auf dem Papier, sondern stupides Durchrechnen lassen (wie für die alten Grenzen auch schon).
(21.04.2012, 16:02)davidk schrieb: Und warum ist, wenn Phase zwei eine Zuglänge von 0 ergibt die Lösung optimal (so schreibt es Kociemba), dass muss doch nicht zwangsläufig so sein, oder?
Weil der Algorithmus jede Phase optimal lösen kann. Nimm dir zum Beispiel die Phase I, die beim Würfel alle Kanten löst und die Phase II, die den Rest (alle Ecken ohne die Kanten kaputt zu machen) löst. Wenn du dem Algorithmus jetzt einen Würfel gibst, der bei Phase I 0 Züge braucht (alle Kanten sind also schon gelöst), dann brauchst du jetzt nur noch bei der Phase II die optimale Lösung nachschauen, denn die kennt man ja (bzw. kann man berechnen). Und somit kannst du den ganzen Würfel optimal lösen.
(21.04.2012, 16:02)davidk schrieb: Problem ist ich habe ihn gefragt, ob ich ihn mal anrufen kann und ihn ein paar Sachen fragen kann, aber ich glaube, wenn er solche trivialen (für mich leider nicht) hört legt er gleich wieder auf ^^
Was du fragst, klingt nicht dumm. Ich kann dir aber auch nicht sagen, wie der Herr Lehrer drauf ist, wenn man ihn Dinge fragt.
/edit: Ah, du hast ihn ja schon gefragt. Wenn er ja gesagt hat, hilft er sicher gerne und legt nicht auf.
(21.04.2012, 16:02)davidk schrieb: dass Gotteszahl nicht etwa drei ist wie die Theologen behaupten
Wäre auch was neues, wenn etwas stimmt, was...
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - Pfefferkuchen - 16.05.2012
Hey, ich bin gerade über die Deffiniton einer "möglichen" Position gestoßen und verstehe gerade nicht, wieso die Bedingung "(a) sgn(rho) = sgn(sigma)" erfüllt sein muss. Würde mich über eine kleine Erläuterung sehr freuen.
lg
RE: Facharbeit Mathe: Rubiks Cube und die Gruppentheorie - Hubi - 16.05.2012
Zuerst mal: was ist rho, was ist sigma? (ich schätze, dass rho die Permutation der Kanten, sigma die der Ecken ist - oder umgekehrt)
Und: Definition? Was bei Positionen möglich und was unmöglich ist, ist doch darüber definiert, ob die Position mit Drehungen erreicht werden kann, oder nicht?
Wenn du eine Untersuchung über die Eigenschaften von möglichen Positionen machen willst, einen Beweis für das von dir Erwähnte (und noch deutlich mehr) gibts z.B. in Bandelows "Einführung in die Cubologie". Das Buch hab ich zwar nicht hier in Zürich, aber ich kanns nach dem Wochenende mal raussuchen.