Permutation? < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:09 Mi 09.01.2013 | | Autor: | bandchef |
| Aufgabe | Gegeben sei ein Parallelrechner mit n>1 [mm] Prozessoren^{1} [/mm] und $k [mm] \in \mathbb [/mm] N$ voneinander nicht unterscheidbaren Jobs.
a) Wie viele Möglichkeiten gibt es, diese Jobs auf die einzelnen Prozessoren zu verteilen, wenn jedem Prozessor auch mehrere Jobs zugeteilt werden dürfen?
b) Bestimmen sie die Wahrscheinlichkeit, dass
b1) der erste Prozessor keinen
b2) jeder Prozessor mindestens einen,
b3) mindestens ein Prozessor keinen,
b4) genau ein Prozessor keinen
Job zugeteilt bekommt.
c) Bestimmen sie für n=4 und k=10 die Wahrscheinlichkeit, dass der erste Prozessor 3, der zweite 4, der dritte 2 und der vierte 1 Job(s) zugeteilt bekommt.
^{1} Prozessoren werden in der Aufgabe als voneinander unterscheidbar vorausgesetzt. |
Hi Leute!
Die Aufgabe a) hab ich wohl schon gelöst: Da sollte k! richtig sein.
Bei b1) hab ich nun Probleme:
Irgendwie kommt mir zu dieser Aufgabenstellung diese Formel in den Kopf: [mm] $\frac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_s!}$ [/mm] aber da es ja heißt "keinen Prozessor" müsste ich $n = 0$ setzen was zu [mm] $\frac{0!}{k_1! \cdot k_2! \cdot ... \cdot k_s!} [/mm] = [mm] \frac{1}{k_1! \cdot k_2! \cdot ... \cdot k_s!}$ [/mm] führt. Stimmt das so? Ich kanns mir irgendwie nicht vorstellen, da es schon bei recht geringer CPU Anzahl (4) eine ganz kleinen Wert gibt!
Bei b2) sehe ich das so: [mm] $\frac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_s!}$ [/mm] mit [mm] $k_1 [/mm] = [mm] k_2 [/mm] = ... = [mm] k_s [/mm] = 1$ Also bleibt quasi als Ergebnis $n!$ über. Stimmt das so?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:46 Mi 09.01.2013 | | Autor: | bandchef |
Ich sehe gerade, dass ich die Aufgabe b1 wohl von Haus falsch angegangen bin. Ich habe die Änderungen editiert. Würde mich freuen, wenn sich von euch jemand dazu äußert!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:42 Mi 09.01.2013 | | Autor: | luis52 |
Moin,
Die Aufgaben a) und c) haben sich schon erledigt.
wir hatten hier schon einmal mit der Multinomialverteilung zu tun.
Bezeichne [mm] $X_j$ [/mm] die Anzahl der Jobs, die Prozessor $j$, [mm] $j=1,\dots,n$, [/mm] zugeordnet werden. Dann ist
[mm] $p(x_1,\dots,x_n)=P(X_1=x_1,\dots,X_n=x_n)=\binom{k}{x_1,\dots,x_n}\frac{1}{n^k}$
[/mm]
fuer
[mm] $\mathcal{M}=\{(x_1,\dots,x_n)\mid x_j=0,1,\dots,k,x_1+\dots+x_n=k\}$
[/mm]
b1)
[mm] $\sum\{p(x_1,\dots,x_n)\mid(x_1,\dots,x_n)\in\mathcal{M}, x_1=0\}$
[/mm]
b2)
[mm] $\sum\{p(x_1,\dots,x_n)\mid(x_1,\dots,x_n)\in\mathcal{M}, \min(x_1,\dots,x_n)>0\}$
[/mm]
b3)
[mm] $\sum\{p(x_1,\dots,x_n)\mid(x_1,\dots,x_n)\in\mathcal{M}\,,\min(x_1,\dots,x_n)=0\}$
[/mm]
b4)
[mm] $\sum\{p(x_1,\dots,x_n)\mid(x_1,\dots,x_n)\in\mathcal{M}\,,\sum_{j=1}^n1_{\{0\}}(x_j)=1\}$
[/mm]
vg Luis
|
|
|
| |
|
Gut. Du hast Recht, was ähnliches hatten wir schon mal. Das heißt also, dass ich die Aufgab a) so lösen könnte:
[mm] $\mathbb [/mm] M(n,k) = [mm] \frac{n^k}{\binom{n}{k_1,k_2,...,k_s}}$ [/mm] Hier ist also n die Anzahl der CPU's und k die Anzahl der Jobs. Wenn ich also nun das Bsp. von 4 CPU's und 12 Jobs hätte, müsste ich wohl so einsetzen:
[mm] $\mathbb [/mm] M(2,4) = [mm] \frac{2^{4}}{\binom{2}{1,2,3,4}} [/mm] = [mm] 2^{4} \cdot \frac{1! \cdot 2! \cdot 3! \cdot 4!}{4!} [/mm] = 2304$
Das Ergebnis von 2304 erscheint mir für die gewählten Zahlen auch plausibel...
Mit deinem Beispiel könnte man das ganze auch so lösen:
$ [mm] P(K_1=k_1,\dots,K_s=k_s)=\frac{n!}{k_1!k_2!\cdot\ldots\cdot k_s!}p_1^{k_1}p_2^{k_2}\cdot\ldots\cdot p_k^{k_s} [/mm] = [mm] \frac{n!}{k_1!k_2!\cdot\ldots\cdot k_s!} \left( \frac{n_1}{n} \right)^{k_1}\left( \frac{n_2}{n} \right)^{k_2} \cdot [/mm] ... [mm] \cdot \left( \frac{n_s}{n} \right)^{k_s} [/mm] = ...$
Hier nun wieder obiges Beispiel mit n=2 und k=4 eingesetzt:
$... = [mm] \frac{2!}{1!2!\cdot\3!\cdot 4!} \left( \frac{1}{4} \right)^{1}\left( \frac{2}{4} \right)^{2} \cdot \left( \frac{3}{4} \right)^{3} \cdot \left( \frac{4}{4} \right)^{4} [/mm] = [mm] \frac{1}{150994944}$
[/mm]
Da es sich hier um eine Wahrscheinlichkeit handeln würde, müsste ich ja nur "1 durch" das Ergebnis rechnen. Aber es kommen unterschiedliche Werte raus. Was stimmt dann am zweiten Beispiel nicht?
Edit:
Ich hab nun durch ausprobieren herausgefunden, dass ich so auf das gleich Ergebenis nur eben mit "1 durch" weil es sich ja hier um eine Modellierung von Wahrscheinlichkeiten handelt. Ich verstehe aber dann nicht so ganz warum ich so auf das richtige Ergebnis komme; zumindestens nehme ich es an, dass es das richtige Ergebnis ist:
$... = [mm] \frac{2!}{1!2!\cdot\3!\cdot 4!} \left( \frac{2}{4} \right)^{2} [/mm] = [mm] \frac{1}{2304}$ [/mm] Wenn man hier nun noch [mm] $\left( \frac{1}{2304} \right)^{-1}$ [/mm] macht, dann hab ich das gleich wie oben. Nämlich die Anzahl aller Möglichkeiten [mm] $\mathbb [/mm] M$.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:25 Do 10.01.2013 | | Autor: | luis52 |
Moin bandchef,
ich weiss leider nicht, wovon du sprichst.
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:30 Do 10.01.2013 | | Autor: | bandchef |
Frage: Ist das die richtige Lösung der Aufgabe a) aus dieser Diskussion?
Lösung für a): $ [mm] \mathbb [/mm] M(n,k) = [mm] \frac{n^k}{\binom{n}{k_1,k_2,...,k_s}} [/mm] $
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:49 Do 10.01.2013 | | Autor: | luis52 |
> Frage: Ist das die richtige Lösung der Aufgabe a) aus
> dieser Diskussion?
>
> Lösung für a): [mm]\mathbb M(n,k) = \frac{n^k}{\binom{n}{k_1,k_2,...,k_s}}[/mm]
Hm, ich dachte, wir unser hier schon einig,
dass die Loesung [mm] $n^k$ [/mm] ist ... ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
vg Luis
|
|
|
| |
|
Oh, dann ist bei zwei unterschiedlichen Aufgaben das gleiche Ergebnis rausgekommen?
Der Aufgabentexte dieser Aufgabe hier lautet: voneinander nicht unterscheidbaren Jobs. Der Aufgabentext hier lautet aber: voneinander unterscheidbare Jobs.
Aber gut. Die richtige Lösung der Aufgabe a) aus dieser Diskussion lautet also ebenfalls [mm] n^k.
[/mm]
Entschuldige bitte die Verwirrung!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Sa 12.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:42 Do 10.01.2013 | | Autor: | bandchef |
Hallo luis52, ich hab eine weitere Frage angehängt, die mein Problem wesentlich genauer und kürzer beschreibt. Alles was ich in der einen umständlichen Frage, die du nicht verstanden hast, noch gefragt habe, hole ich nach.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Sa 12.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
