www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algebra" - Reduktion von n Summen
Reduktion von n Summen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Reduktion von n Summen: Idee
Status: (Frage) beantwortet Status 
Datum: 21:37 So 31.10.2021
Autor: lord_haffi

Aufgabe
Implementiere folgende Wahrscheinlichkeitsverteilung:
[mm] P( n ) = \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} \underbrace{\sum_{i_1=1}^{M-1}i_1 \sum_{i_2=i_1}^{M-1}i_2\:...\sum_{i_{n-M}=i_{n-M-1}}^{M-1}i_{n-M}}_{n-M\text{ nested sums}} [/mm]
Ein Vereinfachen der verschachtelten Summen kann dabei hilfreich sein.


Tachchen,

erst mal vorweg:
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: []https://dev-community.de/threads/rekursion-vermeiden-abh%C3%A4ngige-summen-laufzeitanalyse.443/
Dort wurde mir dann auch dieses Forum empfohlen. Da es sich hierbei nicht um eine Uni-Aufgabe (eher weiterführendes Interesse) handelt, habe ich mir eine entsprechende Aufgabenformulierung zu dem, was ich erreichen möchte, ausgedacht. Dementsprechend ist auch die angegebene Zeitbegrenzung für dieses Thema irrelevant, da es mich wohl auch noch in nem Jahr aus dem Schlaf reißen wird, wenn ich dieses Ding nicht geknackt bekomm' :P

Mein Problem ist, dass die Anzahl der Summen variabel ist und diese auch noch voneinander abhängen. Leider hab ich keine Idee, wie man das vereinfachen könnte. Als erstes ist mir das Multinomial Theorem in den Sinn gekommen, jedoch funktioniert das nicht, da die Summen nicht alle immer bei [mm]1[/mm] anfangen.

Ich hab das ganze testweise mit Rekursion implementiert, dies ist jedoch viel zu langsam, als dass ich da sinnvoll Daten extrahieren kann.

Zum Kontext: Diese Verteilung beschreibt das Laufzeitverhalten eines Algorithmus, den ich mit einem anderen vergleichen will. Der Algorithmus soll dabei einen einfachen, ungerichteten (und ungewichteten) Graphen erzeugen, mit [mm]N[/mm] Knoten und [mm]M[/mm] zufällig verteilten Verbindungen. [mm]|E|_\text{max} = \frac{N\cdot (N-1)}{2}[/mm] ist dabei die maximale Anzahl an möglichen Verbindungen in einem einfachen, ungerichteten Graphen.
Der entsprechende Algorithmus zieht eine zufällige Verbindung (d.h. zwei zufällige Knoten) und setzt die Verbindung, falls sie noch nicht existiert. Andernfalls wird einfach neu gezogen; das ganze wird wiederholt, bis alle [mm]M[/mm] Verbindungen gesetzt wurden. Dieser Algorithmus wird logischerweise mit einem höheren Verhältnis zwischen [mm] \(M\) [/mm] und [mm] \(N\) [/mm] immer schlechter. Die Frage ist nur "wie schlecht" :) D.h. eigentlich interessiert mich im Endeffekt nur der Erwartungswert der Verteilung.

So, ich hoffe, ich habe euch hier nicht komplett zugetextet ^^ Wenn euch was gescheites einfällt, wäre ich sehr daran interessiert :)

Mfg

        
Bezug
Reduktion von n Summen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:33 Sa 06.11.2021
Autor: felixf

Moin!

> Implementiere folgende Wahrscheinlichkeitsverteilung:
>  [mm] P( n ) = \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} \underbrace{\sum_{i_1=1}^{M-1}i_1 \sum_{i_2=i_1}^{M-1}i_2\:...\sum_{i_{n-M}=i_{n-M-1}}^{M-1}i_{n-M}}_{n-M\text{ nested sums}} [/mm]
>  
> Ein Vereinfachen der verschachtelten Summen kann dabei
> hilfreich sein.

Eine gute Idee das symbolisch zu vereinfachen habe ich nicht, aber ausrechnen kann man das sehr effizient, also solange $n - M$ und $M - 1$ nicht zu gross sind (bis ein paar tausend ist kein Problem). Wobei auch bei so grossen Werten die Zahlen vermutlich schon so stark explodieren, dass die Anzahl der Rechenoperationen das kleinere Problem sind.

Und zwar kannst du dir folgende Teilausdrücke anschauen:
[mm] T(k, s) := \sum_{i_k=s}^{M-1} i_k \sum_{i_{k+1}=i_k}^{M-1} i_{k+1} \cdots \sum_{i_{n-M}=i_{n-M-1}}^{M-1} i_{n-M}$ [/mm]
mit $1 [mm] \le [/mm] k [mm] \le [/mm] n - M$ und $1 [mm] \le [/mm] s [mm] \le [/mm] M - 1$. Und zwar musst du ausnutzen, dass $T(k, s) = [mm] \sum_{i_k=s}^{M-1} i_k [/mm] T(k + 1, [mm] i_k)$ [/mm] ist.

Zuerst rechnest du in einer Schleife $T(n - M, s)$ für $s = 1, [mm] \dots, [/mm] M - 1$ aus. Das ist einfach, da $T(n - M, s) = s$ ist.

Dann rechnest du in einer Schleife $T(n - M - 1, s)$ für $s = 1, [mm] \dots, [/mm] M - 1$ aus. Dazu brauchst du die $T(n - M, s)$. Die Werte $T(n - m, s)$ kannst du danach wegwerfen, die brauchst du nicht mehr.

Danach rechnest du in einer Schleife $T(n - M - 2, s)$ für $s = 1, [mm] \dots, [/mm] M - 1$ aus. Danach kannst du die Werte $T(n - M - 1, s)$ wegwerfen.

So kämpfst du dich Schritt für Schritt weiter nach vorne, bis du schliesslich aus den $T(2, s)$ die Werte $T(1, s)$, $1 [mm] \le [/mm] s [mm] \le [/mm] M - 1$ ausrechnest. Dann kannst du schliesslich $P( n ) = [mm] \frac{(|E|_\text{max}-1)!}{|E|_\text{max}^{n-1}\cdot (|E|_\text{max}-M-1)!} [/mm] T(1, 1)$ ausrechnen.

(Also eigentlich bauchst du von den $T(1, s)$ nur $T(1, 1)$ auszurechnen, der Rest kann weg. Aber wenn du genauer hinschaust, kannst du sehen wie du allgemein die $T(k, s)$ für ein festes $k$ schneller ausrechnen kannst, als für jedes $s$ eine Schleife für die Summe zu berechnen... Dann weisst du warum es am einfachsten ist gleich alle davon auszurechnen.)

LG Felix


Bezug
                
Bezug
Reduktion von n Summen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:53 Di 09.11.2021
Autor: lord_haffi

Moin :)

Danke für deine Antwort, sie war sehr hilfreich! Hab auch schon drüber nachgedacht, wie ich zumindest den Schritt von $P(n) [mm] \rightarrow [/mm] P(n+1)$ bewerkstelligen könnte, da ich eh an der ganzen Verteilung interessiert bin. Hab mich da aber n paar mal selbst verwirrt mit den Summen ^^

Allerdings müsste $ T(n - M, s) = 1 $ sein und nicht $ T(n - M, s) = s $. Sonst hat man für  $ T(n - M-1, s) $ die Summanden quadriert.

> (Also eigentlich bauchst du von den [mm]T(1, s)[/mm] nur [mm]T(1, 1)[/mm]
> auszurechnen, der Rest kann weg. Aber wenn du genauer
> hinschaust, kannst du sehen wie du allgemein die [mm]T(k, s)[/mm]
> für ein festes [mm]k[/mm] schneller ausrechnen kannst, als für
> jedes [mm]s[/mm] eine Schleife für die Summe zu berechnen... Dann
> weisst du warum es am einfachsten ist gleich alle davon
> auszurechnen.)
>  
> LG Felix
>  

Ja ne, die Summe geh ich natürlich von oben nach unten nur einmal durch und summiere den jeweils letzten drauf ;) Für den interessierten Leser: $ T(k, s) = T(k, s+1) + s T(k + 1, s) $

Das hat die Ausführungszeit auf jeden Fall enorm gedrückt :) Das Explodieren der Zahlen hab ich dadurch verhindert, dass ich die $ [mm] |E|_\text{max}^{n-1} [/mm] $ im Nenner so gesplittet habe, dass nun in jeder Iteration einmal durch [mm] $|E|_\text{max}$ [/mm] geteilt wird. Also im Prinzip hab ich's in $ T(k,s) $ reingezogen.

Mfg

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de