Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.
  • 1
  • 2

hamena314

Zerschmetterling

  • "hamena314" is male
  • "hamena314" started this thread

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

1

Sunday, April 17th 2011, 11:51pm

Diskrete Strukturen

Beim Online-Aufgabenblatt soll man die Partition p(9) berechnen. Hatten wir in der Übung eine direkte Formel / Beispiel dafür, oder muss man tatsächlich diese Partition als Teil-Partition betrachten?
Also quasi p(9) = p(9,9), eine Zerlegung in bis zu 9 Teile und dann rekursiv berechnen? Dann komme ich allerdings auf seltsame Werte.

p(n,k) ... wann wird dieser Ausdruck 1 bzw. 0?

Bei der Aufgabe:
"Die letzte Bestellung besteht aus 8 mal Mineralwasser. Die Gäste mögen kalte Getränke nicht so und wünschen höchstens 1 Würfel pro Glas. Auf wieviele Arten können Sie 9 Eiswürfel auf einmal loswerden?"
Ich würde ja schreiben "ich lege sie in die Sonne und lasse sie schmelzen" aber in das Feld kann man nur Zahlen eingeben, weswegen die Aufgabenstellung für mich gerade ein bisschen unklar ist. Oder ist das hier ein schlichter Trivialfall mit einer einfachen Lösung?

HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)
  • Send private message

Sebastian

Trainee

  • "Sebastian" is male

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

2

Monday, April 18th 2011, 10:25am

Vorweg: ich habe DS bei Erné gehört, könnte also sein, dass bei euch etwas anders gehandhabt wird.

Partition p(9):
ich gehe mal davon aus, dass p(9) die Anzahl der verschiedenen Partitionen einer 9-elementigen Menge sein soll (wenn nicht, dann alles folgende ignorieren).
Bei solchen Aufgaben ist es erstmal praktisch schrittweise vorzugehen und am Ende alles addieren (ich gehe davon aus dass p(n,k) bedeutet eine n-elementige Menge auf k Teilmengen aufzuteilen):
p(9,9) = 1
p(9,8) = (9 über 2)
p(9,7) = (9 über 3) + (9 über 2)*(7 über 2) * 1/2! (bin mir hier nicht mehr so sicher, lange her) // edit
...
p(9,1) = 1

***

p(n,k) = 0, wenn k>n oder k=0. Was bei k<0 passiert kommt darauf an, ob das überhaupt definiert ist. Wenn ja dann gehört das hier auch dazu.
p(n,k) = 1, wenn n=k oder k = 1

***

Knobelaufgabe: eigentlich 0, da du im Grunde p(8,9) berechest (s.o.).
try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}

This post has been edited 4 times, last edit by "Sebastian" (Apr 18th 2011, 1:26pm)

  • Send private message

hamena314

Zerschmetterling

  • "hamena314" is male
  • "hamena314" started this thread

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

3

Wednesday, April 20th 2011, 3:04pm

Ok, ich verstehe leider nicht so ganz warum du das k runterzählst.

Deine Berechnung auf der rechten Seite des Gleichheitszeichens kann ich nicht nachvollziehen. Wo kommt das her?
Wenn das die Berechnung für p(n,k) sein soll, bin ich verwirrt. Da komme ich auf folgendes:

p(n,k) = p(n-1, k-1) + p(n-k, k)

Also rekursiv berechnen:
p(9,8) = p(8,7) + p(1,8) ... p(1,8) = 0
p(8,7) = p(7,6) + p(1,7) ... p(1,7) = 0
usw. ...
Dann erhalte ich am Ende lediglich eine 1 für p(9,8) und kommt nicht auf 36, aus (9 über 2) wie du geschrieben hast.

HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)
  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

4

Wednesday, April 20th 2011, 5:59pm

Quoted from "hamena314"

p(n,k) = p(n-1, k-1) + p(n-k, k)

Also rekursiv berechnen:
p(9,8) = p(8,7) + p(1,8) ... p(1,8) = 0
p(8,7) = p(7,6) + p(1,7) ... p(1,7) = 0
usw. ...
Dann erhalte ich am Ende lediglich eine 1 für p(9,8) und kommt nicht auf 36, aus (9 über 2) wie du geschrieben hast.

Anschaulich ist 1 auch die richtige Lösung, denn eine andere Möglichkeit eine Partition von 9 in 8 Teilen zu schreiben als 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 gibt es nicht.
  • Send private message

hamena314

Zerschmetterling

  • "hamena314" is male
  • "hamena314" started this thread

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

5

Wednesday, April 20th 2011, 6:42pm

Jo, aber was meinst du mit der Zeile (9 über 2)?

Quoted from "Sebastian"


...
p(9,8) = (9 über 2)
...


HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)
  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

6

Wednesday, April 20th 2011, 6:43pm

Ich hab' das doch gar nicht geschrieben! ;)
  • Send private message

hamena314

Zerschmetterling

  • "hamena314" is male
  • "hamena314" started this thread

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

7

Wednesday, April 20th 2011, 9:02pm

Mist, hab mich von euren ähnlichen Namen verwirren lassen. Sorry! :D
Hast du vielleicht eine Ahnung was er meint?

Deinen Hinweis finde ich hilfreich, aber gibt es keine direkte Formel für p(x)?
Ist halt sehr umständlich p(x) immer auf p(x,x) zurückzuführen und quasi als Sonderfall zu betrachten.

HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)
  • Send private message

Sebastian

Trainee

  • "Sebastian" is male

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

8

Wednesday, April 20th 2011, 10:02pm

Nenene, lass dich nicht verwirren von falschen Aussagen (meine evtl. inbegriffen)!

Bastian redet (unwissentlich) von Äquivalenzklassen. Es gibt genau eine Äquivalenzklasse eine Menge von 9 Elementen in 8 Teilmengen aufzuteilen. In dieser Äquivalenzklasse sind aber 9 über 2 verschiedene Elemente enthalten (du wählst eben aus den 9 genau die 2 aus, die zusammen in einer Teilmenge sind).

Ansonsten wirfst du da die Formeln und Definitionen total durcheinander, z.B. "p(9) = p(9,9)", von daher kann ich dir jetzt nicht genau folgen. Deine rekursive Formel sieht auch sehr fehlerhaft aus, da würde ich nochmal in die Mitschrift schauen (p(9,8 ) = p(8,7) + p(1,8 ) ... p(1,8 ) = 0 ist falsch! das ist erstens nicht gleich 0 und zweitens machen alle Summanden außer der erste keinen Sinn).

Wenn du die genaue Aufgabenstellung, Definition von p(n) und p(n,k) und am besten die rekursive Formel postet dann schau ich nochmal rein :-)
try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}

This post has been edited 1 times, last edit by "Sebastian" (Apr 20th 2011, 10:02pm)

  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

9

Wednesday, April 20th 2011, 10:24pm

Ich denke schon, dass ich mit dem was ich geschrieben habe richtig liege. Siehe Wikipedia zur Partitionsfunktion und insbesondere die Mitschrift zur zweiten Übung.

Also ein Beispiel: p(4) = p(4,4) + p(4,3) + p(4,2) + p(4,1) = 1 + p(3,2) + p(1,3) + p(3,1) + p(2,2) + 1 = 1 + p(2,1) + p(1,2) + 0 + 1 + 1 + 1 = 1 + 1 + 0 + 0 + 1 + 1 + 1 = 5 (vgl. Wert im Wikipedia-Artikel)

This post has been edited 1 times, last edit by "Bastian" (Apr 20th 2011, 10:51pm)

  • Send private message

hamena314

Zerschmetterling

  • "hamena314" is male
  • "hamena314" started this thread

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

10

Wednesday, April 20th 2011, 11:04pm

Oha jetzt gehts durcheinander.

Quoted from "Sebastian"

...
Ansonsten wirfst du da die Formeln und Definitionen total durcheinander, z.B. "p(9) = p(9,9)", von daher kann ich dir jetzt nicht genau folgen.


Ich weiss nicht wie man p(n) berechnet! Ich habe keine Formel dafür zur Hand weil wir entweder keine gehabt haben, oder ich die passende Formel in den Unterlagen nicht finde.
Darum habe ich versucht mir herzuleiten wie man das berechnen könnte.
Dachte halt p(n,k) bedeutet eine Zerlegung in Teilmengen. Nimmt man alle diese Teilmengen zusammen, so erhält man p(n). <-- Das ist meine Frage, falls dem nicht so ist, brauche ich eine Formel für p(n)

Quoted from "Sebastian"

Deine rekursive Formel sieht auch sehr fehlerhaft aus, da würde ich nochmal in die Mitschrift schauen

p(n,k) = p(n-1, k-1) + p(n-k, k) ... die hab ich in meiner Mitschrift und in der von Kater ist sie auch so. Darum sollte die korrekt sein.

Quoted from "Sebastian"

(p(9,8 ) = p(8,7) + p(1,8 ) ... p(1,8 ) = 0 ist falsch! das ist erstens nicht gleich 0 und zweitens machen alle Summanden außer der erste keinen Sinn).


Die Formel ist ja rekursiv, bevor man also weiss was bei p(9,8) rauskommt, muss man p(8,7) + p(1,8) berechnen ... p(8,7) muss wieder rekursiv berechnet werden, p(1,8) ist jedoch 0 soweit ich das verstehe.
Das Schema für den hinteren Term zieht sich also durch die Rekursion, der hintere Term ist also immer 0:
p(9,8) = p(8,7) + p(1,8) = p(8,7)
p(8,7) = p(7,6) + p(1,7) = p(7,6)
p(7,6) = p(7,5) + p(1,6) = p(7,5)
...
p(2,1) = p(1,0) + p(1,1) ... p(1,0) ist 0 und p(1,1) ... nun geht man rekursiv nach oben und setzt die Ergebnisse jeweils ein. Dann erhält man für p(9,8) = 1.

Ich brauche halt einfach eine Formel für p(n).

@Sebastian: Vielleicht hilft es weiter wenn du erklärst wie du auf
p(9,8) = (9 über 2)
p(9,7) = (9 über 3) + (9 über 2)*(7 über 2) * 1/2! (bin mir hier nicht mehr so sicher, lange her) // edit

kommst.

Hoffe nun ist alles ein bisschen klarer. :)

HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)

This post has been edited 1 times, last edit by "hamena314" (Apr 20th 2011, 11:05pm)

  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

11

Wednesday, April 20th 2011, 11:09pm

Quoted from "hamena314"

Ich brauche halt einfach eine Formel für p(n).

Bitte sehr! :D

Quoted from "hamena314"

Dachte halt p(n,k) bedeutet eine Zerlegung in Teilmengen. Nimmt man alle diese Teilmengen zusammen, so erhält man p(n).

Die Zerlegung und anschließende Addition ist hier wohl wirklich das Mittel der Wahl.
  • Send private message

Sebastian

Trainee

  • "Sebastian" is male

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

12

Wednesday, April 20th 2011, 11:32pm

Tatsächlich. Höre lieber auf Bastian, ich bringe da irgendwas durcheinander :-), denn p(1, 4) = 5 laut Wiki, was nach "meiner Definition" 0 wäre.
try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}
  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

13

Wednesday, April 20th 2011, 11:48pm

Quoted from "Sebastian"

denn p(1, 4) = 5 laut Wiki, was nach "meiner Definition" 0 wäre.

Vorsicht, p(k, n) aus der Wikipedia ist etwas anderes als p(n, k) aus der Vorlesung:

Quoted from "Wikipedia"

Dies ist eine Abwandlung der Partitionsfunktion, in der verlangt wird, dass der kleinste Summand größergleich k ist. Die "normale" Partitionsfunktion ist somit p(n) = p(1,n)
  • Send private message

hamena314

Zerschmetterling

  • "hamena314" is male
  • "hamena314" started this thread

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

14

Saturday, April 30th 2011, 12:38pm

Habe bei Übungsblatt 3 (online) eine Frage:

[spoiler]
Bei der Uhren- / Larvenaufgabe soll man die Zeit finden, in der die Uhren erneut gemeinsam schlagen bzw. die Larven gemeinsam schlüpfen.
Mit dem kleinsten gemeinsamen Vielfachen komme ich auf 12600 Minuten für die Uhren, respektive 14586 Jahre für die Larven.
[/spoiler]

Allerdings habe ich 0 Ahnung wo in der Aufgabe Zykel sein sollen!? ?(
Wie berechnet man das also mithilfe von Zykeln?
Daher verstehe ich die Frage nach der Ordnung auch nicht. Eine Ordnung bei einem Zykel ist ja die Anzahl der benötigten Abbildungen, um den Zykel wieder auf sich selbst abzubilden (Identität).
Und der Zykeltyp ist die Anzahl der eingeklammerten Zahlen ... (1 2 3)(4 5 6)(7)(8)(9) hat also den Zykeltyp 5, weil es 5 Klammerpaare gibt.

Wer kann mich erleuchten? :D

HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)

This post has been edited 1 times, last edit by "hamena314" (Apr 30th 2011, 12:38pm)

  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

15

Saturday, April 30th 2011, 2:26pm

Quoted from "hamena314"

Habe bei Übungsblatt 3 (online) eine Frage:

[spoiler]
Bei der Uhren- / Larvenaufgabe soll man die Zeit finden, in der die Uhren erneut gemeinsam schlagen bzw. die Larven gemeinsam schlüpfen.
Mit dem kleinsten gemeinsamen Vielfachen komme ich auf 12600 Minuten für die Uhren, respektive 14586 Jahre für die Larven.
[/spoiler]

Allerdings habe ich 0 Ahnung wo in der Aufgabe Zykel sein sollen!? ?(
Wie berechnet man das also mithilfe von Zykeln?

Am Bespiel der Larven vielleicht so:

pi = (1 2 3 ... 34) (35 ... 73) (74 ... 139)

Dann wäre pi^14586 = (1) (2) (3) ... (139), da der Zykeltyp (66, 39, 34) ist und das KGV von den drei Zahlen eben 14586 ist.

Quoted from "hamena314"

Daher verstehe ich die Frage nach der Ordnung auch nicht. Eine Ordnung bei einem Zykel ist ja die Anzahl der benötigten Abbildungen, um den Zykel wieder auf sich selbst abzubilden (Identität).

Ist das nicht je zweimal das selbe Ergebnis?

Quoted from "hamena314"

Und der Zykeltyp ist die Anzahl der eingeklammerten Zahlen ... (1 2 3)(4 5 6)(7)(8)(9) hat also den Zykeltyp 5, weil es 5 Klammerpaare gibt.

Ne, der Zykeltyp wäre hier (3, 3, 1, 1, 1).
  • Send private message

SIMPSON

Toni

  • "SIMPSON" is male

Posts: 88

Date of registration: Oct 15th 2010

Location: Hannover

16

Monday, May 2nd 2011, 8:34pm

Sind für den Test eigtl. Hilfsmittel erlaubt?
  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

17

Monday, May 2nd 2011, 8:40pm

Quoted from "SIMPSON"

Sind für den Test eigtl. Hilfsmittel erlaubt?


ein handbeschriebendes blatt, aber KEINE taschenrechner

mfg Finn
Regierungen der industriellen Welt,...
  • Send private message

Kanubis

Praktikant

Posts: 18

Date of registration: May 2nd 2011

18

Monday, May 2nd 2011, 9:19pm

Testat Morgen

Hallo,

ich hoffe mal ihr seid alle für Morgen vorbeireitet^^
Ich hätte da noch ein paar Fragen zu Blatt 3
Es geht um die Aufgabe 3 bzw um alle Aufgaben ab da. Die mit den Uhren die gleichzeitig Schlagen und den Insekten.
Was versteht man unter der Ordnung einer Permutation mit dem Zykeltyp (72,50,42,30) ?

MfG

Stephan
  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

19

Monday, May 2nd 2011, 9:32pm

Quoted from "Kanubis"

Hallo,

ich hoffe mal ihr seid alle für Morgen vorbeireitet^^
Ich hätte da noch ein paar Fragen zu Blatt 3
Es geht um die Aufgabe 3 bzw um alle Aufgaben ab da. Die mit den Uhren die gleichzeitig Schlagen und den Insekten.
Was versteht man unter der Ordnung einer Permutation mit dem Zykeltyp (72,50,42,30) ?

MfG

Stephan


hallo,

zykeltyp gibt die größe der zykel in der permutation an...

eine permutation ( 1 3 5 6)(2 4)(7) hätte zB den zykeltyp (4, 2, 1)

naja und ordnung ist dann der größte kleinste gemeinsame vielfache der zykelgröße...

edit: also ordnung gibt an, wie oft man eine permutation hintereinander ausführen muss, bis man die identität bekommt (also die zahl die man "rein steckt")

verstanden, oder soll ich das nochmal genauer ausführen??

mfg Finn
Regierungen der industriellen Welt,...

This post has been edited 2 times, last edit by "Finn" (May 2nd 2011, 9:36pm)

  • Send private message

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

20

Monday, May 2nd 2011, 9:34pm

Quoted from "Finn"

naja und ordnung ist dann der größte gemeinsame vielfache der zykelgröße...

Nein, es ist das KGV, also das kleinste gemeinsame Vielfache. ;)
  • Send private message
  • 1
  • 2