Randomisierte Algorithmen - Exam

Aufgabe 1)

• Ein Wahrscheinlichkeitsraum ist ein Tripel \( \left(\Omega, \mathcal{F}, P \right) \).
• \( \Omega \): Ergebnismenge
• \( \mathcal{F} \): Sigma-Algebra von Ereignissen
• \( P \): Wahrscheinlichkeitsmaß
• Zufallsvariable ist eine messbare Funktion \( X: \Omega \to \mathbb{R} \).
• Verteilung von \( X \): \( P_X(B) = P(X \in B) \) für \( B \subseteq \mathbb{R} \).

a)

a) Gegeben sei der Wahrscheinlichkeitsraum \(\left(\Omega, \mathcal{F}, P\right)\) und die Zufallsvariable \(X\), wobei:

• \( \Omega = \{0, 1, 2, 3\} \)
• \( \mathcal{F} \) ist die Potenzmenge von \( \Omega \)
• \( P \) sei definiert durch:

P(\{0\}) = 0.1 P(\{1\}) = 0.2 P(\{2\}) = 0.4 P(\{3\}) = 0.3

Die Zufallsvariable \(X\) sei gegeben durch:

X(0) = 1 X(1) = 2 X(2) = 3 X(3) = 4

Berechne die Verteilung von \(X\).

Lösung:

• Ein Wahrscheinlichkeitsraum ist ein Tripel \( \left(\Omega, \mathcal{F}, P \right) \).
• \( \Omega \): Ergebnismenge
• \( \mathcal{F} \): Sigma-Algebra von Ereignissen
• \( P \): Wahrscheinlichkeitsmaß
• Zufallsvariable ist eine messbare Funktion \( X: \Omega \to \mathbb{R} \).
• Verteilung von \( X \): \( P_X(B) = P(X \in B) \) für \( B \subseteq \mathbb{R} \).

a) Gegeben sei der Wahrscheinlichkeitsraum \( \left(\Omega, \mathcal{F}, P\right) \) und die Zufallsvariable \(X\), wobei:

• \( \Omega = \{0, 1, 2, 3\} \)
• \( \mathcal{F} \) ist die Potenzmenge von \( \Omega \)
• \( P \) sei definiert durch:

P(\{0\}) = 0.1P(\{1\}) = 0.2P(\{2\}) = 0.4P(\{3\}) = 0.3

Die Zufallsvariable \(X\) sei gegeben durch:

X(0) = 1X(1) = 2X(2) = 3X(3) = 4

Berechne die Verteilung von \(X\).Um die Verteilung von \(X\) zu berechnen, betrachten wir die Werte, die \(X\) annehmen kann, und die entsprechenden Wahrscheinlichkeiten:

• \(X = 1 \Rightarrow X(0) = 1 \quad \Rightarrow P_X(\{1\}) = P(\{0\}) = 0.1\)
• \(X = 2 \Rightarrow X(1) = 2 \quad \Rightarrow P_X(\{2\}) = P(\{1\}) = 0.2\)
• \(X = 3 \Rightarrow X(2) = 3 \quad \Rightarrow P_X(\{3\}) = P(\{2\}) = 0.4\)
• \(X = 4 \Rightarrow X(3) = 4 \quad \Rightarrow P_X(\{4\}) = P(\{3\}) = 0.3\)

Die Verteilung der Zufallsvariablen \(X\) ist daher wie folgt:

P_X(\{1\}) = 0.1,  P_X(\{2\}) = 0.2, P_X(\{3\}) = 0.4,  P_X(\{4\}) = 0.3

b)

b) Betrachte eine Funktion \( g: \mathbb{R} \rightarrow \mathbb{R} \) definiert als \( g(x) = 2x \). Bestimme die Verteilung der Zufallsvariable \( Y = g(X) \), wobei \(X\) die Zufallsvariable aus Teil a) ist.

Lösung:

• Ein Wahrscheinlichkeitsraum ist ein Tripel \( \left(\Omega, \mathcal{F}, P \right) \).
• \( \Omega \): Ergebnismenge
• \( \mathcal{F} \): Sigma-Algebra von Ereignissen
• \( P \): Wahrscheinlichkeitsmaß
• Zufallsvariable ist eine messbare Funktion \( X: \Omega \to \mathbb{R} \).
• Verteilung von \( X \): \( P_X(B) = P(X \in B) \) für \( B \subseteq \mathbb{R} \).

b) Betrachte eine Funktion \( g: \mathbb{R} \rightarrow \mathbb{R} \) definiert als \( g(x) = 2x \). Bestimme die Verteilung der Zufallsvariable \( Y = g(X) \), wobei \(X\) die Zufallsvariable aus Teil a) ist. Um die Verteilung der Zufallsvariablen \(Y\) zu bestimmen, müssen wir die Werte betrachten, die \(Y\) annehmen kann, basierend auf der Funktion \(g(x) = 2x\), und die entsprechenden Wahrscheinlichkeiten finden.

• \(X(0) = 1 \rightarrow g(X(0)) = g(1) = 2 \Rightarrow Y(0) = 2 \Rightarrow P_Y(\{2\}) = P_X(\{1\}) = 0.1\)
• \(X(1) = 2 \rightarrow g(X(1)) = g(2) = 4 \Rightarrow Y(1) = 4 \Rightarrow P_Y(\{4\}) = P_X(\{2\}) = 0.2\)
• \(X(2) = 3 \rightarrow g(X(2)) = g(3) = 6 \Rightarrow Y(2) = 6 \Rightarrow P_Y(\{6\}) = P_X(\{3\}) = 0.4\)
• \(X(3) = 4 \rightarrow g(X(3)) = g(4) = 8 \Rightarrow Y(3) = 8 \Rightarrow P_Y(\{8\}) = P_X(\{4\}) = 0.3\)

Die Verteilung der Zufallsvariablen \(Y\) ist daher:

P_Y(\{2\}) = 0.1,  P_Y(\{4\}) = 0.2,  P_Y(\{6\}) = 0.4,  P_Y(\{8\}) = 0.3

Aufgabe 3)

In dieser Aufgabe werden wir die Eigenschaften und Anwendungen von randomisierten Datenstrukturen analysieren, insbesondere Skip-Listen und Treaps. Diese Datenstrukturen verwenden Zufall, um die Effizienz ihrer Operationen zu verbessern und die erwartete Laufzeit zu minimieren. Skip-Listen bestehen aus mehrdimensionalen Listen und führen Suchen, Einfügen und Löschen in erwarteter logarithmischer Zeit durch. Treaps kombinieren die Struktur von Binärbäumen und Heaps und nutzen zufällige Prioritäten, um die Baumstruktur aufrechtzuerhalten.

a)

Teilaufgabe 1: Gegeben sei eine Skip-Liste. Beschreibe den Algorithmus für das Einfügen eines Elements in die Skip-Liste und erkläre, wie die zufällige Höhe eines Knotens bestimmt wird. Berechne die erwartete Laufzeit für das Einfügen eines Elements in die Skip-Liste. Gehe dabei von einer Skip-Liste mit N Elementen aus.

Lösung:

• Teilaufgabe 1: Gegeben sei eine Skip-Liste. Beschreibe den Algorithmus für das Einfügen eines Elements in die Skip-Liste und erkläre, wie die zufällige Höhe eines Knotens bestimmt wird. Berechne die erwartete Laufzeit für das Einfügen eines Elements in die Skip-Liste. Gehe dabei von einer Skip-Liste mit N Elementen aus.

Beginnen wir mit dem Algorithmus zum Einfügen eines Elements in die Skip-Liste:

• Schritt 1: Bestimme die zufällige Höhe des neuen Knotens. Die Höhe wird oft durch wiederholtes Würfeln bestimmt. Starte mit Höhe 1 und erhöhe diese um 1 für jedes Mal, wenn das Würfeln (z.B. eine Münze werfen) 'Kopf' zeigt. Dieser Prozess endet sofort, wenn 'Zahl' geworfen wird oder eine maximale Höhe erreicht wird. Angenommen, es wird eine faire Münze verwendet, dann hat ein Knoten in einer Skip-Liste mit einer Wahrscheinlichkeit von 1/2 Höhe 1, mit einer Wahrscheinlichkeit von 1/4 Höhe 2, mit einer Wahrscheinlichkeit von 1/8 Höhe 3, und so weiter.
• Schritt 2: Finde die Positionen, an denen das neue Element eingefügt werden soll. Beginne bei der obersten Ebene und gehe nach unten. Innerhalb jeder Ebene bewege Dich nach rechts, bis Du die Position findest, an der das neue Element eingefügt werden soll.
• Schritt 3: Füge das neue Element in jede Ebene bis zu seiner Höhe ein. Dies geschieht, indem Du die Verbindungen in der entsprechenden Ebene aktualisierst.

Hier eine detaillierte Beschreibung der Einfügungslogik:

• Gegeben sei, dass wir ein Element x einfügen möchten.
• Berechne die zufällige Höhe h für x.
• Initialisiere ein Array update, um die Positionen zu speichern, an denen die Verbindungen für das neue Element in jeder Ebene aktualisiert werden müssen.
• Beginne beim Kopfknoten und bewege Dich für jede Ebene von der höchsten zur niedrigsten Ebene nach rechts, bis Du an einen Knoten gelangst, dessen nächster Knoten größer oder gleich x ist. Speichere diesen Knoten in update[i] für die entsprechende Ebene i.
• Füge das neue Element in jede betroffene Ebene ein, indem Du die in update gespeicherten Knoten verwendest.

Erwartete Laufzeit:

Die erwartete Laufzeit für das Einfügen eines Elements in eine Skip-Liste ist O(log N). Dies liegt daran, dass das Durchschnittsverhalten einer Skip-Liste durch die geometrische Verteilung der Ebenen kontrolliert wird. Da die Höhe eines Knotens mit einer exponentiell abnehmenden Wahrscheinlichkeit gewählt wird, kann die erwartete Anzahl der Ebenen, die überprüft werden müssen, als logarithmisch zur Anzahl der Elemente in der Liste betrachtet werden.

Mathematische Begründung:

Jeder Knoten hat eine Wahrscheinlichkeit von 1/2, auf der nächsten höheren Ebene vorhanden zu sein. Folglich beträgt die erwartete Höhe eines Knotens:

\[ E[H] = \sum_{k=1}^{\infty} k \left(\frac{1}{2^k}\right) = 1 \cdot \frac{1}{2} + 2 \cdot \frac{1}{4} + 3 \cdot \frac{1}{8} + 4 \cdot \frac{1}{16} + \ldots \]

Dies ist die Summe einer geometrischen Reihe, die konvergiert:

\[ E[H] = \sum_{k=1}^{\infty} k \left(\frac{1}{2^k}\right) = \textstyle 2 \]

Da die erwartete Höhe des höchsten Levels O(log N) ist, führt dies zur logarithmischen erwarteten Laufzeit für Einfügeoperationen.

b)

Teilaufgabe 2: Betrachte einen Treap, der n Elemente enthält. Beschreibe den Algorithmus für das Löschen eines Knotens aus dem Treap und gehe dabei auf die Rolle der zufälligen Prioritäten ein. Zeige, wie die zufälligen Prioritäten die erwartete Höhe des Treaps beeinflussen. Berechne die erwartete Höhe eines Treaps. Hinweis: Verwende die Tatsache, dass die Prioritäten zufällig und unabhängig voneinander verteilt sind.

Lösung:

• Teilaufgabe 2: Betrachte einen Treap, der n Elemente enthält. Beschreibe den Algorithmus für das Löschen eines Knotens aus dem Treap und gehe dabei auf die Rolle der zufälligen Prioritäten ein. Zeige, wie die zufälligen Prioritäten die erwartete Höhe des Treaps beeinflussen. Berechne die erwartete Höhe eines Treaps. Hinweis: Verwende die Tatsache, dass die Prioritäten zufällig und unabhängig voneinander verteilt sind.

Beginnen wir mit dem Algorithmus zum Löschen eines Knotens aus einem Treap:

• Schritt 1: Finde den Knoten, der gelöscht werden soll. Dies geschieht durch die Standard-Binärbaumsuche, bei der die Schlüsselwerte verglichen werden, um den Knoten zu lokalisieren.
• Schritt 2: Sobald der Knoten gefunden wurde, wird er gelöscht, indem er nach unten rotiert wird. Dies geschieht durch Vergleichen der Prioritäten der Kinderknoten und Anwenden einer Rotation (links oder rechts), um das Kind mit der höheren Priorität nach oben zu bringen. Der Prozess wird rekursiv fortgesetzt, bis der zu löschende Knoten ein Blattknoten wird.
• Schritt 3: Entferne den Blattknoten, der nun entfernt werden kann, ohne die Heap-Eigenschaft des Treaps zu verletzen.

Hier eine detaillierte Beschreibung der Rotationslogik:

• Wenn der Knoten x gelöscht werden soll, und y und z sind die Kinder von x:
• Vergleiche die Prioritäten von y und z. Wenn y die höhere Priorität hat, führe eine Rechtsrotation an x durch. Andernfalls, wenn z die höhere Priorität hat, führe eine Linksrotation an x durch. Dies bringt den Knoten mit der höheren Priorität nach oben.
• Wiederhole diesen Vorgang rekursiv, bis x ein Blattknoten ist. Entferne dann x.

Erwartete Höhe eines Treaps:

Die Prioritäten in einem Treap werden zufällig und unabhängig voneinander verteilt, wodurch der Treap als eine Art zufälliger Binärbaum fungiert. Die Höhe eines zufälligen Binärbaums mit n Knoten entspricht der Höhe eines Treaps.

• Ein zufälliger Treap hat ähnliche Eigenschaften wie ein zufälliger Binärbaum: Jeder Knoten hat eine zufällige Priorität, und wir wählen zufällig aus allen Permutationen der Knotenprioritäten.
• Die erwartete Höhe eines zufälligen Binärbaums mit n Knoten ist O(log n).

Mathematische Begründung:

Sei h die Höhe des Treaps und n die Anzahl der Elemente. Aufgrund der zufälligen Zuweisung von Prioritäten und der unabhängigen Verteilungen ergibt sich die erwartete Höhe wie folgt:

\[ E[h] = O(log n) \]

Der Grund hierfür liegt darin, dass jede Einfügung oder Löschung eine Reihe von Rotationen erfordert, die in Erwartung logarithmisch zur Anzahl der Elemente stehen.

Zusammenfassung:

Die zufälligen Prioritäten in einem Treap stellen sicher, dass die Struktur des Baums im Durchschnitt balanciert bleibt. Dadurch wird die Höhe des Treaps und somit die Laufzeit von Operationen wie Einfügen, Suchen und Löschen im Erwartungswert logarithmisch zur Anzahl der Elemente gehalten.

Aufgabe 4)

Gegeben sei eine große Matrix A, für die Eigenwert- und Eigenvektorberechnungen sehr zeitaufwändig sind. Du sollst Monte-Carlo-Methoden anwenden, um die Eigenwerte und Eigenvektoren dieser Matrix näherungsweise zu bestimmen. Die Monte-Carlo-Methoden basieren auf zufälligen Projektionen und mehrfachem Zufallssampling zur Erhöhung der Präzision.

a)

(a) Sei A eine Quadratmatrix der Dimension n x n, und v ein Zufallsvektor der Dimension n. Beschreibe den Algorithmus zur Bestimmung der approximativen größten Eigenwerts von A unter Verwendung der Monte-Carlo-Methode. Zeige die einzelnen Schritte und erkläre, wie Zufallsvektoren verwendet werden, um die Konvergenz zu gewährleisten.

Lösung:

Algorithmus zur Bestimmung des approximativen größten Eigenwerts einer Matrix A mittels der Monte-Carlo-Methode:

• Initialisierung:Wähle einen Zufallsvektor v der Dimension n. Normalerweise wird ein Vektor mit unabhängigen normalverteilten Zufallskomponenten gewählt.
• Iterationsprozess:Wiederhole die folgenden Schritte für eine bestimmte Anzahl von Iterationen (die Iterationszahl kann vorher festgelegt oder adaptiv bestimmt werden):
  • Berechne den neuen Vektor Av, indem Du die Matrix A auf den aktuellen Vektor v anwendest.
  • Normiere den neuen Vektor, um einen aktualisierten Vektor v_neu zu erhalten. Dies wird erreicht, indem Av durch seine Norm (z.B. die euklidische Norm) geteilt wird:

    v_neu = \frac{A v}{\text{Norm}(A v)}

  • Setze v = v_neu für die nächste Iteration.
• Eigenwertberechnung:Am Ende der Iterationen kann der größte Eigenwert λ_max approximativ berechnet werden, indem der Rayleigh-Quotient verwendet wird:

  λ_max = \frac{v^T A v}{v^T v}

• Konvergenz:Die Konvergenz ist gewährleistet, da der wiederholte Multiplikationsprozess den Einfluss des größten Eigenwerts auf den Vektor v verstärkt. Zufallsvektoren stellen sicher, dass der initiale Vektor mit hoher Wahrscheinlichkeit eine Komponente in Richtung des größten Eigenwerts hat.

Dieser Algorithmus ist eine Variante der Potenzmethode und nutzt Monte-Carlo-Methoden, um sicherzustellen, dass der initiale Zufallsvektor wahrscheinlich eine Komponente in Richtung des größten Eigenwerts hat, was die Konvergenz sicherstellt.

b)

(b) Implementiere den Algorithmus aus Teil (a) in Python. Füge Kommentare hinzu, die jeden Schritt des Algorithmus erklären.

 import numpy as np np.random.seed(42)  # Reproducibility def monte_carlo_eigenvalue_approx(A, num_samples):   n = A.shape[0]   max_eigenvalue = 0    for _ in range(num_samples):       v = np.random.randn(n)      v = v / np.linalg.norm(v)  # Normalisierung des ZufallsvektorsV          Av = np.dot(A, v)      eigenvalue = np.dot(v.T, Av)   # Rayleigh Quotient      if eigenvalue > max_eigenvalue:           max_eigenvalue = eigenvalue      return max_eigenvalue  # Test der Funktion mit einer BeispielmatrixA A = np.array([[4, 1], [2, 3]]) num_samples = 1000 approx_eigenvalue = monte_carlo_eigenvalue_approx(A, num_samples) print(f'Approximierter größter Eigenwert: {approx_eigenvalue}') 

Lösung:

Hier ist der Python-Code zur Implementierung des Algorithmus aus Teil (a) mit ausführlichen Kommentaren:

import numpy as np # Setze den Zufallsgenerator für die Reproduzierbarkeit zurücknp.random.seed(42) def monte_carlo_eigenvalue_approx(A, num_samples):    # Bestimme die Dimension der Matrix A    n = A.shape[0]     # Initialisiere den maximalen Eigenwert    max_eigenvalue = 0     # Wiederhole den Prozess num_samples Mal    for _ in range(num_samples):         # Erzeuge einen Zufallsvektor v der Dimension n         v = np.random.randn(n)          # Normalisiere den Zufallsvektor v         v = v / np.linalg.norm(v)          # Berechne den neuen Vektor Av         Av = np.dot(A, v)          # Berechne den Rayleigh-Quotienten zur Näherung des Eigenwerts         eigenvalue = np.dot(v.T, Av)          # Aktualisiere den maximalen Eigenwert, falls der aktuelle Eigenwert größer ist         if eigenvalue > max_eigenvalue:            max_eigenvalue = eigenvalue     # Gib den approximativen größten Eigenwert zurück    return max_eigenvalue # Teste die Funktion mit einer Beispielmatrix AA = np.array([[4, 1], [2, 3]])num_samples = 1000approx_eigenvalue = monte_carlo_eigenvalue_approx(A, num_samples)print(f'Approximierter größter Eigenwert: {approx_eigenvalue}')

In diesem Python-Code wird der Algorithmus zur approximativen Bestimmung des größten Eigenwerts einer großen Matrix A unter Verwendung der Monte-Carlo-Methode implementiert. Jeder Schritt des Algorithmus ist mit Kommentaren versehen, um die Funktionsweise zu erklären.