Algorithmen sollen in einer Endlosschleife ein xi nach dem anderen lesen (Pseudocode)

Question

Aufgabe:

In dieser Aufgabe geht es um Algorithmen, die einen Strom von Eingabedaten x1, x2, x3, … bekommen, von denen statistische Kenngrößen berechnet werden. Wesentlich dabei ist, dass diese Algorithmen einen von der Zahl der Eingabedaten unabhängigen Speicherverbrauch haben sollen, insbesondere ist es nicht möglich, alle bisher gelesenen Daten zu speichern (somit handelt es sich um einen Online-Algorithmus! nicht ein Offline-Algorithmus, der erst alle Daten
liest und dann berechnet).

Die in einem Pseudocode zu schreibenden Algorithmen sollen in einer Endlosschleife ein xi nach dem anderen lesen (mit einer Methode getNextValue) und die Kenngrößen über den bisher gesehenen Teil der Daten ausgeben.

Der erste Algorithmus soll das arithmetische Mittel ¯x und die Varianz s^{~2} ausgeben.

Ich hab schon den Teil mit dem arithmetischem Mittel, aber ich weiß nicht wie ich das mit der Varianz machen kann.

Answer 1

Antwort mit KI erzeugt

Berechnung des arithmetischen Mittels und der Varianz in Echtzeit (Online-Algorithmus)

Um den Algorithmus für die Berechnung des arithmetischen Mittels \( \bar{x} \) und der Varianz \( s^{2} \) effizient und in Echtzeit zu gestalten, können wir uns auf Konzepte der Online-Algorithmen und inkrementeller Berechnungen stützen. Der Schlüssel hierbei ist, dass für jedes neue Element \( x_i \) das bisher berechnete Ergebnis angepasst wird, ohne alle vorherigen Datenpunkte speichern zu müssen.

Bei der Berechnung der Varianz in Echtzeit werden oft die Knuth-Formel oder ein ähnlicher Ansatz verwendet. Diese Methoden erlauben es, das arithmetische Mittel und die Varianz fortlaufend zu aktualisieren, während neue Daten einfließen, ohne dass alle Daten gespeichert werden müssen.

Pseudocode für arithmetisches Mittel und Varianz

Zunächst definieren wir den Pseudocode, der das arithmetische Mittel berechnet. Angenommen, dieser Teil ist bereits bekannt und implementiert:

plaintext
n = 0
mean = 0

while True:
    x = getNextValue()  // liest den nächsten Wert
    n = n + 1
    mean = mean + (x - mean) / n
    // Ausgabe des aktuellen arithmetischen Mittels
    print("Aktuelles arithmetisches Mittel:", mean)

Jetzt integrieren wir die Berechnung der Varianz, indem wir die Formel für die inkrementelle Berechnung der Varianz einfügen:

plaintext
n = 0
mean = 0
M2 = 0

while True:
    x = getNextValue()  // liest den nächsten Wert
    n = n + 1
    delta = x - mean
    mean = mean + delta / n
    delta2 = x - mean
    M2 = M2 + delta * delta2

    if n < 2:
        print("Varianz noch nicht definiert")
    else:
        variance = M2 / (n - 1)
        // Ausgabe des aktuellen arithmetischen Mittels und der Varianz
        print("Aktuelles arithmetisches Mittel:", mean, "Aktuelle Varianz:", variance)

Erklärung des Pseudocodes:

- n: Anzahl der gelesenen Elemente.
- mean: Das laufende arithmetische Mittel.
- M2: Eine Hilfsvariable, die notwendig ist, um die laufende Varianz zu berechnen.
- Für jedes neue x:
- Die Differenz (delta) zwischen dem neuen Wert und dem bisherigen Mittelwert wird berechnet.
- Das arithmetische Mittel wird mit dieser Differenz aktualisiert.
- Die Differenz zwischen dem neuen Wert und dem aktualisierten Mittelwert (delta2) wird für die Varianzberechnung verwendet.
- M2 wird aktualisiert, um die Summe der quadrierten Differenzen zu halten.
- Wenn mehr als ein Wert gelesen wurde, kann die Varianz berechnet werden.

Dieser Ansatz gewährleistet, dass der Speicherverbrauch unabhängig von der Anzahl der gelesenen Daten konstant bleibt, da zu keinem Zeitpunkt alle Datenwerte im Speicher gehalten werden müssen.