[Diskrete] Permutationen Gleichungen lösen?!

[AfI] Analysis für Informatiker
[Diskrete] Diskrete Strukturen
[LA] Lineare Algebra
[Stocha] Einführung in die angewandte Stochastik
[NumRech] Numerisches Rechnen

Permutationen Gleichungen lösen?!

Beitragvon Jonnsn » 04.02.10 16:27

Tag zusammen!

Folgendes Problem:
Ich habe eine Gleichung mit: a°b°x = y ... wobei y die Permutation ist, a und b jeweils Zyklen und x gesucht wird und ° Komposition sein soll.

z.B.: (1 7 6 3 8)°(4 2 5)°x = (1 7 6)(2 5 4)(3 8)

Nun gibt es ja folgenden Ansatz:

a*a^-1*b*b^-1*x = a^-1*y*b^-1 <=> x = a^-1*y*b^-1

SO funktioniert das ganze. Da kommt auch die richtige Lösung raus. Aber da die Komposition nicht kommutativ ist, frag ich mich, woher man weiß, was man vorne hinschreibt und welches hinten?

z.B.: y*a^-1*b^-1 liefert die falsche Lösung. Oder warum überhaupt a^-1 vor die Permutation schreibt versteh ich noch nicht so ganz. Oder wie würde dann das ganze mit 3 gegebenen Zyklen aussehen? Was muss ich vorne hinschreiben und was hinten?

Bei x=y*a^-1*b^-1 habe ich (1 3) als Ergebnis und bei x = a^-1*y*b^-1 (6 8), wobei letzteres das Richtige ist.

MfG und danke im Voraus. :)
Benutzeravatar
Jonnsn
 
Beiträge: 5
Registriert: 04.11.09 20:03
Wohnort: Aachen
Studiengang: Informatik (B.Sc.)
Studiert seit: SS 10
Anwendungsfach: Bio

Beitragvon fw » 04.02.10 16:34

Am besten du schreibst dir das mal in der Sprache von Abbildungen auf, dann ist es deutlich einfacher zu verstehen. Sagen wir mal du willst f \circ x = y nach x lösen. Da es sich um Permutationen (d.h. bijektive Abbildungen) handelt, steht da nichts anderes als f(x(i)) = y(i) für alle i. Das ist äquivalent zu x(i) = f^{-1}(y(i)). Und damit ist deine Aufgabe auch bereits gelöst. Aus wievielen Zykeln f besteht ist unerheblich, du musst nur aufpassen beim invertieren, weil sich da die Reihenfolge tauscht ((f \circ g)^{-1} = g^{-1} \circ f^{-1}).
Benutzeravatar
fw
 
Beiträge: 1356
Registriert: 17.05.06 19:37
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: Mathe

Beitragvon Jonnsn » 04.02.10 16:57

Vielen Dank für die schnelle Antwort. Ich werde es gleich mal versuchen.
Benutzeravatar
Jonnsn
 
Beiträge: 5
Registriert: 04.11.09 20:03
Wohnort: Aachen
Studiengang: Informatik (B.Sc.)
Studiert seit: SS 10
Anwendungsfach: Bio

Beitragvon MorcElf » 04.02.10 17:43

Also da es in Diskrete ja auf sehr einfachem Niveau bleibt finde ich den Ansatz viel zu übertrieben (natürlich wäre er bei schwereren problemen vielleicht nötig)

In deinem Beispiel :
(1 7 6 3 8 )°(4 2 5)°x = (1 7 6)(2 5 4)(3 8 )

schaust du dir einfach kurz an, welche Zahlen noch nicht richtig abgebilted werden auf der linken Seite (das dauert wenn du langsam bist 1 minute):

(254) ist gleich (425), 1,7 und 3 sind richtig,
also fehlen 6 und 8!
rechts wird aus 6->1 und aus 8->3
links aus 6->3 und 8->1 ... wenn du nun einfach x als (6,8 ) setzt, stimmt die Sache (8->6->3 und 6->8->1) und das Problem ist gelöst...

Falls du lieber die FOrmeln magst ok, nur ich finde in Diskrete kann man sich oft mit etwas Nachdenken das sparen.
MorcElf
 
Beiträge: 8
Registriert: 23.04.09 14:01

Beitragvon emx » 04.02.10 17:59

In diesem Fall ist es mit etwas Nachdenken natürlich viel einfacher und schneller. Das Problem dabei ist nur, dass wir jeden Lösungsweg mehr oder weniger ausführlich aufschreiben müssen, sonst wird die Lösung nicht bewertet. Und da finde ich den Weg mit den Inversen dann einfacher, es sei denn man kann seine Gedanken klar und deutlich aufschreiben.

Was auch ein Problem bei dieser Nachdenk-Methode ist, dass es ziemlich schierig wird, wenn die Unbekannte in der Mitte steht. :)
emx
 
Beiträge: 71
Registriert: 23.01.10 19:45

Beitragvon Vion » 04.02.10 20:05

wenn ich mich richtig erinnere hatte der hanke die letzten Jahre nur ergebnis klausuren
mit einer einzigen schriftlichen aufgabe die komplett abzugeben war
Vion
 
Beiträge: 144
Registriert: 04.09.08 22:26
Wohnort: Aachen
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 08/09
Anwendungsfach: BWL

Beitragvon MorcElf » 04.02.10 20:16

schau dir doch die letzten klausuren mal an, da war immer nur 1 aufgabe schriftlich, und meiner meinung ist es eher schwierig diese aufgabe mit permutationen zu machen.

Und es ist nicht schwieriger wenn der gesuchte Zykel in der Mitte oder sonstwo ist...

Persönlich finde ich nur, dass man schon genug komische Formeln und so lernen muss, da kann man es sich bei sowas doch ruhig mal einfacher machen... aber jedem das seine, wollte nur eine einfachere Methode nennen
MorcElf
 
Beiträge: 8
Registriert: 23.04.09 14:01

Beitragvon emx » 04.02.10 21:27

Vion hat geschrieben:wenn ich mich richtig erinnere hatte der hanke die letzten Jahre nur ergebnis klausuren
mit einer einzigen schriftlichen aufgabe die komplett abzugeben war


Dieses Jahr ist es aber anders.

Und selbstverständlich wird es schwieriger, bzw. dauert es länger bei dieser Methode, je weiter die Unbekannte links steht...
emx
 
Beiträge: 71
Registriert: 23.01.10 19:45

Beitragvon MorcElf » 07.02.10 01:57

emx hat geschrieben:
Vion hat geschrieben:wenn ich mich richtig erinnere hatte der hanke die letzten Jahre nur ergebnis klausuren
mit einer einzigen schriftlichen aufgabe die komplett abzugeben war


Dieses Jahr ist es aber anders.

Und selbstverständlich wird es schwieriger, bzw. dauert es länger bei dieser Methode, je weiter die Unbekannte links steht...


Dieses Jahr war es 1 Schriftliche Aufgabe genau wie die letzten auch, wollt nur bescheid geben.
Und die Formel war unnötig gebracht, mit Nachdenken kam man nach etwa 1minute locker auf die Lösung dabei (obwohl der gesuchte term wirklich in der Mitte stand)

Naja hinterher weiss man immer mehr, nich wahr :P
MorcElf
 
Beiträge: 8
Registriert: 23.04.09 14:01

Beitragvon emx » 07.02.10 13:31

Naja, wärst du in den Diskussionsstunden mal da gewesen, hättest du auch die Info gehabt, dass wir zu jeder Aufgabe schriftliche Lösungen abgeben werden müssen. Soweit ich mich erinnern kann, wurde das auch in der letzten Globalübung nochmal gesagt. Keine Ahnung warum die sich plötzlich umentschieden haben.

Schön dass es in einer Minute geklappt hat bei dir. Mal sehen obs auch richtig ist, nich wahr
emx
 
Beiträge: 71
Registriert: 23.01.10 19:45


Zurück zu Mathematik