Variationen berechnen, zählen < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:49 Sa 26.03.2011 | | Autor: | marco_neuber |
| Aufgabe | | Wie lässt sich die Anzahl der Variationen abhängig von der Anzahl der Wertewechsel allgemeingültig berechnen ? |
Hallo zusammen,
ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
![[]](/images/popup.gif) MatheBoard.de
Gegeben sind folgende Mengen [mm] F_{1},\ldots,F_{n}.
[/mm]
Jede Menge besitzt folgenden Wertebereich [mm] F_{i}=\left\{X_{ij},\ldots,X_{im}\right\}
[/mm]
Die Anzahl aller Variationen lässt sich über das kartesische Produkt der Mächtigkeit jeder einzelnen Menge [mm] \prod\limits_{k=1}^{n}\left|F_{k}\right| [/mm] bestimmen.
Die Anzahl der Variationen mit keinem Wertewechsel [mm] \left(W=0\right) [/mm] enspricht der Mächtigkeit der Durchschnittsmenge [mm] \left|D_{F}\right| [/mm] über alle Mengen F.
[mm] \left|D_{F}\right|=\left|F_{1}\cap\ldots\cap F_{n}\right|
[/mm]
Wie berechnet sich allgemeingültig die Anzahl der Variationen mit einem Wertewechsel [mm] W=0,1,2,\ldots,n-1 [/mm] ?
Ein einfaches Beispiel zur Verdeutlichung der Problemstellung:
Gegeben sind folgende Mengen
[mm] F_{1}=\left\{100,110,120,130,140\right\}
[/mm]
[mm] F_{2}=\left\{100,110,120,130,140\right\} [/mm]
[mm] F_{3}=\left\{100,110,120,130,140\right\}
[/mm]
Ich suche nun die Anzahl der Variationen, in denen
1. alle Werte gleich sind [mm] \left(W=0\right):
[/mm]
[mm] V\left(100,100,100\right),V\left(110,110,110\right)\ldots
[/mm]
2. die Werte nur einmal wechseln [mm] \left(W=1\right)
[/mm]
[mm] V\left(100,100,110\right),V\left(110,110,100\right)\ldots
[/mm]
NICHT aber [mm] V\left(100,110,100\right),V\left(110,100,110\right)\ldots!
[/mm]
3. die Werte zweimal wechseln [mm] \left(W=2=W_{\max}=n-1\right)
[/mm]
[mm] V\left(100,110,100\right),V\left(110,100,110\right)\ldots
[/mm]
Für Rückmeldungen wäre ich sehr dankbar.
Beste Grüße
Marco
|
|
| |
|
> Wie lässt sich die Anzahl der Variationen abhängig von
> der Anzahl der Wertewechsel allgemeingültig berechnen ?
> Hallo zusammen,
> ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
> MatheBoard.de
>
> Gegeben sind folgende Mengen [mm]F_{1},\ldots,F_{n}.[/mm]
> Jede Menge besitzt folgenden Wertebereich
> [mm]F_{i}=\left\{X_{ij},\ldots,X_{im}\right\}[/mm] (#1)
> Die Anzahl aller Variationen lässt sich über das
> kartesische Produkt der Mächtigkeit jeder einzelnen Menge
> [mm]\prod\limits_{k=1}^{n}\left|F_{k}\right|[/mm] bestimmen.
>
> Die Anzahl der Variationen mit keinem Wertewechsel
> [mm]\left(W=0\right)[/mm] enspricht der Mächtigkeit der
> Durchschnittsmenge [mm]\left|D_{F}\right|[/mm] über alle Mengen F.
>
> [mm]\left|D_{F}\right|=\left|F_{1}\cap\ldots\cap F_{n}\right|[/mm]
>
> Wie berechnet sich allgemeingültig die Anzahl der
> Variationen mit einem Wertewechsel [mm]W=0,1,2,\ldots,n-1[/mm] ?
>
> Ein einfaches Beispiel zur Verdeutlichung der
> Problemstellung:
> Gegeben sind folgende Mengen
> [mm]F_{1}=\left\{100,110,120,130,140\right\}[/mm]
> [mm]F_{2}=\left\{100,110,120,130,140\right\}[/mm] (#2)
> [mm]F_{3}=\left\{100,110,120,130,140\right\}[/mm]
>
> Ich suche nun die Anzahl der Variationen, in denen
>
> 1. alle Werte gleich sind [mm]\left(W=0\right):[/mm]
> [mm]V\left(100,100,100\right),V\left(110,110,110\right)\ldots[/mm]
>
> 2. die Werte nur einmal wechseln [mm]\left(W=1\right)[/mm]
> [mm]V\left(100,100,110\right),V\left(110,110,100\right)\ldots[/mm]
> NICHT aber
> [mm]V\left(100,110,100\right),V\left(110,100,110\right)\ldots![/mm]
>
> 3. die Werte zweimal wechseln
> [mm]\left(W=2=W_{\max}=n-1\right)[/mm]
> [mm]V\left(100,110,100\right),V\left(110,100,110\right)\ldots[/mm]
>
> Für Rückmeldungen wäre ich sehr dankbar.
>
> Beste Grüße
>
> Marco
Hallo Marco,
deine Fragestellung ist mir nicht recht klar.
Nach der Angabe bei (#1) könnten die Teilmengen [mm] F_i
[/mm]
ganz beliebig festgelegt sein, z.B. allesamt disjunkt
(ohne jegliche gemeinsame Elemente)
Wenn aber über den Inhalt dieser Mengen nichts Genaues
bekannt ist, ist wohl auch die gesamte Fragestellung sinnlos.
In deinem Beispiel (#2) nimmst du aber dreimal
dieselbe 5-elementige Menge.
In diesem Fall, wo man also wirklich nur die Variationen
einer bestimmten Menge betrachtet (geordnete
Stichproben der Länge k aus einer n-elementigen Grund-
menge, gesamte Anzahl [mm] V_{n,k}=n^k [/mm] ) , macht die Frage Sinn.
LG Al-Chw.
|
|
|
| |
|
Hallo Al-Chwarizmi,
danke für die Rückmeldung. Du hast die Aussage in (#1) richtig verstanden. Die Teilmengen $ [mm] F_i [/mm] $
ganz beliebig festgelegt sein, z.B. allesamt disjunkt
(ohne jegliche gemeinsame Elemente). Hierzu ein Beispiel:
Gegeben sind folgende Teilmengen:
[mm] F_{1}=\left\{130,140\right\}
[/mm]
[mm] F_{2}=\left\{100\right\} [/mm]
[mm] F_{3}=\left\{90,120\right\}
[/mm]
[mm] F_{4}=\left\{150\right\}
[/mm]
Dann gibt es "nur" folgende vier Lösungen:
$V(130,100,90,150),V(130,100,120,150),V(140,100,90,150),V(140,100,120,150)$
Diese vier Lösungen haben alle 3 Wertewechsel $W=3$. Es gibt für dieses Beispiel keine Variationen mit $W=0,1,2$.
Nun mal ein realitätsnahes Beispiel:
[mm] $F_{1} [/mm] = [mm] {60,70,\ldots,150,160}, |F_{1}|=11
[/mm]
[mm] F_{2} [/mm] = [mm] {110,120,\ldots,150,160}, |F_{2}|=6
[/mm]
[mm] F_{3} [/mm] = [mm] {100,110,\ldots,150,160}, |F_{3}|=7
[/mm]
[mm] F_{4} [/mm] = [mm] {40,50,\ldots,150,160}, |F_{4}|=13
[/mm]
[mm] F_{5} [/mm] = [mm] {60,70,\ldots,150,160}, |F_{5}|=11
[/mm]
[mm] F_{6} [/mm] = [mm] {110,120,\ldots,150,160}, |F_{6}|=6
[/mm]
[mm] F_{7} [/mm] = [mm] {100,110,\ldots,150,160}, |F_{7}|=7
[/mm]
[mm] F_{8} [/mm] = [mm] {100,110,\ldots,150,160}, |F_{8}|=7
[/mm]
[mm] F_{9} [/mm] = [mm] {100,110,\ldots,150,160}, |F_{9}|=7
[/mm]
[mm] F_{10} [/mm] = [mm] {110,120,\ldots,150,160}, |F_{10}|=6$
[/mm]
Die Menge aller Möglichkeiten beträgt $ [mm] \prod\limits_{k=1}^{n}\left|F_{k}\right|=11*6*7\ldots$
[/mm]
Das sind so viele Möglichkeiten, dass ich diese nicht alle berechnen kann. Deshalb suche über die Wertewechsel eine Teilmenge von Variationen, die sich in einer akzeptablen Zeit berechnen lassen. Wenn ich die Anzahl der Variationen je Wertewechsel kenne, kann ich vorher entscheiden, welche Teilmenge ich berechne. Deshalb der ganze Aufwand.
Wird meine Fragestellung jetzt klarer ?
LG Marco
|
|
|
| |
|
> Hallo Al-Chwarizmi,
>
> danke für die Rückmeldung. Du hast die Aussage in (#1)
> richtig verstanden. Die Teilmengen [mm]F_i[/mm]
> ganz beliebig festgelegt sein, z.B. allesamt disjunkt
> (ohne jegliche gemeinsame Elemente). Hierzu ein Beispiel:
> Gegeben sind folgende Teilmengen:
> [mm]F_{1}=\left\{130,140\right\}[/mm]
> [mm]F_{2}=\left\{100\right\}[/mm]
> [mm]F_{3}=\left\{90,120\right\}[/mm]
> [mm]F_{4}=\left\{150\right\}[/mm]
>
> Dann gibt es "nur" folgende vier Lösungen:
>
> [mm]V(130,100,90,150),V(130,100,120,150),V(140,100,90,150),V(140,100,120,150)[/mm]
>
> Diese vier Lösungen haben alle 3 Wertewechsel [mm]W=3[/mm]. Es gibt
> für dieses Beispiel keine Variationen mit [mm]W=0,1,2[/mm].
>
> Nun mal ein realitätsnahes Beispiel:
> [mm]$F_{1}[/mm] = [mm]{60,70,\ldots,150,160}, |F_{1}|=11[/mm]
> [mm]F_{2}[/mm] =
> [mm]{110,120,\ldots,150,160}, |F_{2}|=6[/mm]
> [mm]F_{3}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{3}|=7[/mm]
> [mm]F_{4}[/mm] =
> [mm]{40,50,\ldots,150,160}, |F_{4}|=13[/mm]
> [mm]F_{5}[/mm] =
> [mm]{60,70,\ldots,150,160}, |F_{5}|=11[/mm]
> [mm]F_{6}[/mm] =
> [mm]{110,120,\ldots,150,160}, |F_{6}|=6[/mm]
> [mm]F_{7}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{7}|=7[/mm]
> [mm]F_{8}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{8}|=7[/mm]
> [mm]F_{9}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{9}|=7[/mm]
> [mm]F_{10}[/mm] =
> [mm]{110,120,\ldots,150,160}, |F_{10}|=6$[/mm]
>
> Die Menge aller Möglichkeiten beträgt
> [mm]\prod\limits_{k=1}^{n}\left|F_{k}\right|=11*6*7\ldots[/mm]
>
> Das sind so viele Möglichkeiten, dass ich diese nicht alle
> berechnen kann. Deshalb suche über die Wertewechsel eine
> Teilmenge von Variationen, die sich in einer akzeptablen
> Zeit berechnen lassen. Wenn ich die Anzahl der Variationen
> je Wertewechsel kenne, kann ich vorher entscheiden, welche
> Teilmenge ich berechne. Deshalb der ganze Aufwand.
>
> Wird meine Fragestellung jetzt klarer ?
>
> LG Marco
Aha.
Dann haben wir wieder ein klar gestelltes Problem.
Da die Variationen ja geordnet sind, können Wertewechsel
ja nur jeweils zwischen einem Element [mm] x_i\in{F_i} [/mm] und dem
folgenden Element [mm] x_{i+1}\in{F_{i+1}} [/mm] stattfinden.
Es kommt deshalb jeweils (an jeder der (n-1) möglichen
Nahtstellen) nur darauf an, wieviele Elemente und wie
viele Elemente die Mengen [mm] F_i [/mm] , [mm] F_{i+1} [/mm] und ihre Schnittmenge
[mm] F_i\cap{F_{i+1}} [/mm] haben.
In deinem obigen Beispiel gilt noch speziell, dass stets
entweder [mm] F_i \subset F_{i+1} [/mm] oder [mm] F_{i+1}\subset F_i [/mm] oder allenfalls [mm] F_i=F_{i+1} [/mm] ist.
Ein Beispiel: [mm] F_3 \subset F_4 [/mm] , und es gilt:
$\ [mm] |F_{3}|=7\qquad |F_{4}|=13\qquad |F_{3}\cap F_4|=7$
[/mm]
Betrachtet man die Variationen nur, soweit sie die
Elemente [mm] x_3 [/mm] und [mm] x_4 [/mm] betreffen, so gibt es insgesamt
7*13=91 solche Zweier-Variationen. Davon sind nur
7 ohne Wertwechsel und folglich 7*12=84 mit Wertwechsel.
Daraus darf man wohl auch schließen, dass die Wahrschein-
lichkeit eines Wertwechsels an der Nahtstelle [mm] 3\curvearrowright4 [/mm]
gleich [mm] \frac{12}{13} [/mm] ist.
Ich befürchte aber, dass diese Art "Wertwechselwahr-
scheinlichkeiten" z.B. für benachbarte Nahtstellen,
etwa [mm] 3\curvearrowright4 [/mm] und [mm] 4\curvearrowright5 [/mm] nicht unabhängig voneinander sind.
Dies könnte eine Lösung des Problems doch wieder
recht schwierig machen.
LG Al-Chw.
|
|
|
| |
|
Hallo Al-Chwarizmi,
die beschriebenen Hintergrundinformation hilft sicherlich das Problem besser zu verstehen. Die Werte je Teilmenge [mm] $F_{i}$ [/mm] und benachbarter Teilmengen [mm] $F_{i+1}$ [/mm] bzw. [mm] $F_{i-1}$ [/mm] können unabhängig voneinander gewählt werden. Es exisiteren keine Wahrscheinlichkeiten für einen Wertwechsel. Damit sind die zu bildenden Variationen ebenfalls unabhängig voneinander.
Ergibt das für Dich eine neue Sicht auf das geschilderte Problem ?
LG Marco
|
|
|
| |
|
Hallo Al-Chwarizmi,
ich möchte noch einen Gedankengang eines Arbeitskollegen mit veröffentlichen:
"...Ein paar Gedanken zur Berechnung der Variationen für $W=1$:
Es gibt (n-1) verschiedene Wechselorte (zwischen [mm] $F_{1}$ [/mm] und [mm] $F_{2}, F_{3},F_{4},\ldots$). [/mm] Für jeden Wechselort kann man die [mm] $F_{j}$ [/mm] in zwei Gruppen G1, G2 aufteilen (vor/nach Wechsel).
Du kannst nun die Variationsanzahl [mm] $VAG_{j}$ [/mm] für jeweils eine Gruppe [mm] $G_{j}$ [/mm] berechnen, für den Fall berechnen in dem die Gruppen voneinander unabhängig sind. Dann berechnet sich die Gesamtanzahl nach
[mm] $AG_{1}*AG_{2}$
[/mm]
[mm] $AG_{2}$ [/mm] (Anzahl Variationen für [mm] $G_{2}$)
[/mm]
[mm] $AG_{1}$ [/mm] (Anzahl Variationen für [mm] $G_{1}$)
[/mm]
[mm] $AG_{1}$ [/mm] ist die Mächtigkeit der Durchschnittsmenge in [mm] $G_{1}$
[/mm]
[mm] $AG_{2}$ [/mm] ist die Mächtigkeit der Durchschnittsmenge in [mm] $G_{2}$
[/mm]
Da hierin auch die Varianten enthalten sind ohne Wertewechsel musst du die entsprechende Anzahl wieder abziehen. Also:
$VA = [mm] AG_{1}*AG_{2} [/mm] - [mm] D_{f}$
[/mm]
Die Variantenanzahl berechnet sich dann aus der Summe der Anzahl je Wechselort.
Das Verfahren lässt sich auch für W > 1 erweitern...."
Die spannende Frage ist, wie die Unabhängigkeit der Gruppen mit berücksichtigt werden kann.?
Denn Werte je Teilmenge können nicht unabhängig voneinander gewählt werden.
LG Marco
|
|
|
| |
|
Hallo Al-Chwarizmi,
ich möchte die Diskussion in das Literaturverzeichnis meiner Diss. aufnehmen. Darf ich Dich mit Deinem bürgerlichen Namen als Autor nennen, oder soll ich Deinen Benutzernamen nehmen?
Für den Fall, dass Du Dich nicht meldest, nehme ich Deinen Benutzernamen.
LG Marco
|
|
|
| |
|
> Hallo Al-Chwarizmi,
>
> ich möchte noch einen Gedankengang eines Arbeitskollegen
> mit veröffentlichen:
> "...Ein paar Gedanken zur Berechnung der Variationen für
> [mm]W=1[/mm]:
>
> Es gibt (n-1) verschiedene Wechselorte (zwischen [mm]F_{1}[/mm] und
> [mm]F_{2}, F_{3},F_{4},\ldots[/mm]). Für jeden Wechselort kann man
> die [mm]F_{j}[/mm] in zwei Gruppen G1, G2 aufteilen (vor/nach
> Wechsel).
>
> Du kannst nun die Variationsanzahl [mm]VAG_{j}[/mm] für jeweils
> eine Gruppe [mm]G_{j}[/mm] berechnen, für den Fall berechnen in dem
> die Gruppen voneinander unabhängig sind. Dann berechnet
> sich die Gesamtanzahl nach
> [mm]AG_{1}*AG_{2}[/mm]
> [mm]AG_{2}[/mm] (Anzahl Variationen für [mm]G_{2}[/mm])
> [mm]AG_{1}[/mm] (Anzahl Variationen für [mm]G_{1}[/mm])
>
> [mm]AG_{1}[/mm] ist die Mächtigkeit der Durchschnittsmenge in
> [mm]G_{1}[/mm]
> [mm]AG_{2}[/mm] ist die Mächtigkeit der Durchschnittsmenge in
> [mm]G_{2}[/mm]
>
> Da hierin auch die Varianten enthalten sind ohne
> Wertewechsel musst du die entsprechende Anzahl wieder
> abziehen. Also:
> [mm]VA = AG_{1}*AG_{2} - D_{f}[/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
dies entspricht meiner Berechnung im Beispiel mit
[mm] F_3 [/mm] und [mm] F_4 [/mm] :
$\ [mm] |F_3|*|F_4|-|F_3\cap F_4|\ [/mm] =\ 7*13-7\ =\ 84$
> Die Variantenanzahl berechnet sich dann aus der Summe ![[haee]](/images/smileys/haee.gif "[haee]")
> der Anzahl je Wechselort.
Da müsste doch anstatt "Summe" wohl eher "Produkt"
stehen - aber leider stimmt auch dies nicht, wie ich
an einem einfachen Beispiel mit W=2 berechnet habe.
> Das Verfahren lässt sich auch für W > 1 erweitern...."
>
> Die spannende Frage ist, wie die Unabhängigkeit der
> Gruppen mit berücksichtigt werden kann.?
>
> Denn Werte je Teilmenge können nicht unabhängig
> voneinander gewählt werden.
>
> LG Marco
>
Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:27 Mo 28.03.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
> Nun mal ein realitätsnahes Beispiel:
> [mm]$F_{1}[/mm] = [mm]{60,70,\ldots,150,160}, |F_{1}|=11[/mm]
> [mm]F_{2}[/mm] =
> [mm]{110,120,\ldots,150,160}, |F_{2}|=6[/mm]
> [mm]F_{3}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{3}|=7[/mm]
> [mm]F_{4}[/mm] =
> [mm]{40,50,\ldots,150,160}, |F_{4}|=13[/mm]
> [mm]F_{5}[/mm] =
> [mm]{60,70,\ldots,150,160}, |F_{5}|=11[/mm]
> [mm]F_{6}[/mm] =
> [mm]{110,120,\ldots,150,160}, |F_{6}|=6[/mm]
> [mm]F_{7}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{7}|=7[/mm]
> [mm]F_{8}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{8}|=7[/mm]
> [mm]F_{9}[/mm] =
> [mm]{100,110,\ldots,150,160}, |F_{9}|=7[/mm]
> [mm]F_{10}[/mm] =
> [mm]{110,120,\ldots,150,160}, |F_{10}|=6$[/mm]
>
> Die Menge aller Möglichkeiten beträgt
> [mm]\prod\limits_{k=1}^{n}\left|F_{k}\right|=11*6*7\ldots[/mm]
>
> Das sind so viele Möglichkeiten, dass ich diese nicht alle
> berechnen kann. Deshalb suche über die Wertewechsel eine
> Teilmenge von Variationen, die sich in einer akzeptablen
> Zeit berechnen lassen. Wenn ich die Anzahl der Variationen
> je Wertewechsel kenne, kann ich vorher entscheiden, welche
> Teilmenge ich berechne. Deshalb der ganze Aufwand.
Hallo Marco,
könntest du uns vielleicht noch verraten, welche "Realität"
denn eigentlich hinter der Fragestellung steckt ?
LG Al-Chw.
|
|
|
| |
|
Hallo Al-Chwarizmi,
gerne gebe ich weitere Informationen zum Realitätsbezug. Es handelt sich um Fahrzeitrechnungen für den Eisenbahnbetrieb. Für einen bestimmten Zug wird mit Hilfe eines physikalischen Modells die Fahrzeit zwischen zwei Halten berechnet. Die Fahrzeitrechnung benötigt u.a. ein Geschwindigkeitsprofil. Das Geschwindigkeitsprofil beschreibt für den Laufweg des betrachteten Zuges die zu fahrenden Geschwindigkeiten sowie die örtlich festgelegten Geschwindigkeitswechsel.
Die Geschwindigkeiten eines Geschwindigkeitsprofil werden von der Fahrzeitermittlung einfach "abgefahren".
Das Ergebnis der Fahrzeitrechnung ist eine Zeit-Wege-Funktion bzw. -Linie.
Mein Programm untersucht viele Geschwindigkeitsprofile. Das Ziel ist, eine unter allen Randbedingungen optimale Zeit-Wege-Funktion bzw. -Linie zu berechnen.
Über das Thema schreibe ich gerade meine Diss. Zur Laufzeitoptimierung möchte ich vor den Berechnungen wissen, wie viele Variationen jetzt gefunden und untersucht werden. Dies zu wissen ist notwendig, damit das Verfahren echtzeitfähig werden kann.
Der Zusammenhang zum genannten mathematischen Problem ist wie folgt. Jede Teilmenge [mm] $F_{i}$ [/mm] stellt einen bestimmten disjunkten Bereich des Geschwindigkeitsprofils dar. Die Werte der Teilmenge sind die zu untersuchenden Geschwindigkeiten innerhalb dieses Abschnittes. Geschwindigkeitswechsel gibt es zwischen benachbarten Abschnitten. Wenn die Geschwindigkeiten der Abschnitte unterschiedlich sind.
Die Menge der Geschwindigkeitswechsel in einem Geschwindigkeitsprofil sind u.a. ein Qualitätsmerkmal einer guten Lösung. Das Geschwindigkeitsband einer guten Lösung hat in der Regel wenig Geschwindigkeitswechsel. Das lässt sich dann draußen vom Triebfahrzeugführer auch leichter umsetzen.
War das genug Realität ?
LG Marco
|
|
|
|
