Randomisierte Algorithmen - Cheatsheet

Wahrscheinlichkeitsräume und Zufallsvariablen

Definition:

Wahrscheinlichkeitsräume definieren den Rahmen für Zufallsexperimente, Zufallsvariablen ordnen Ergebnissen der Experimente numerische Werte zu.

Details:

• 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} \).

Zentrale Grenzwertsätze

Definition:

Zentrale Grenzwertsätze (ZGW) sind fundamentale Resultate der Wahrscheinlichkeitstheorie, die sich mit der Verteilung von Summen unabhängiger Zufallsvariablen beschäftigen.

Details:

• Gesamtverhalten: Summe von unabhängigen, identisch verteilten Zufallsvariablen nähert sich einer Normalverteilung an, wenn die Anzahl der Variablen groß ist.
• Formel: Sei \(\text{X}_1, \text{X}_2, ..., \text{X}_n\) eine Folge von i.i.d. Zufallsvariablen mit Mittelwert \(\mu\) und Varianz \(\sigma^2\), dann gilt für die standardisierte Summe: \[ \frac{1}{\sqrt{n\sigma^2}} \sum_{i=1}^n (X_i - \mu) \xrightarrow{d} \mathcal{N}(0,1) \]
• Anwendung: Schätzung von Verteilungen in Randomisierten Algorithmen.

Randomisierte Datenstrukturen

Definition:

Datenstrukturen, die zufälliges Verhalten verwenden, um erwartete Laufzeit und Speicheranforderungen zu minimieren.

Details:

• \textit{Wahrscheinlichkeitsverteilungen} steuern die Struktur und Operationen.
• \textbf{Skip-Listen}: mehrdimensionale Listen, die \textit{Suchen}, \textit{Einfügen}, \textit{Löschen} in erwarteter logarithmischer Zeit durchführen.
• \textbf{Treaps}: Kombination von Binärbäumen und Heaps, Aufrechterhaltung der Baumstruktur basierend auf zufälligen Prioritäten.
• \textbf{Hashing} mit Zufall: Verwendung von \textit{zufälligen Hashfunktionen} zur Minimierung von Kollisionen.
• Erwartete Laufzeit oft besser als die schlimmste Laufzeit konventioneller Datenstrukturen.

Monte-Carlo-Methoden in der numerischen Linearen Algebra

Definition:

Monte-Carlo-Methoden nutzen Zufallszahlen zur Lösung oder Approximation von Problemen der linearen Algebra.

Details:

• Verwendung: Nützlich bei großen Matrizen oder schwer lösbaren Problemen.
• Prinzip: Wiederholtes Zufallssampling zur Näherung der Lösung.
• Häufige Anwendung: Näherung von Eigenwerten und Eigenvektoren großer Matrizen.
• Präzision: Erhöht sich mit der Anzahl der Stichproben.
• Zentrale Idee: Reduzierung der Dimension der Problemstellung durch zufällige Projektionen.
• Beispielmethode: Randomisierte SVD (Singulärwertzerlegung).

Beispiele für klassische Las-Vegas-Algorithmen

Definition:

Las-Vegas-Algorithmen sind randomisierte Algorithmen, die immer korrekte Ergebnisse liefern, aber deren Laufzeit eine Zufallsvariable ist.

Details:

• Quickselect (für das Finden der k-ten kleinsten Elemente in lineare Zeit)
• Der Monte-Carlo Baumsuchalgorithmus (für Spiele wie Schach)
• Der Algorithmus von Karger (für das Finden minimaler Schnittmengen in Graphen)
• Randomisierter Minimum-Spanning-Tree-Algorithmus (Verallgemeinerung von Borůvka oder Kruskal)
• Treap-Datenstruktur (kombiniert Heap und Binäre Suchbäume)

Vergleich von Monte-Carlo und Las-Vegas Algorithmen

Definition:

Vergleich von Monte-Carlo und Las-Vegas Algorithmen.

Details:

• Monte-Carlo: Ergebnisse können falsch, aber mit berechenbarer Wahrscheinlichkeit
• Las-Vegas: Ergebnisse immer richtig, aber Laufzeit zufallsabhängig
• Monte-Carlo: Fokus auf Laufzeitschranken \textit{(expected polynomial time)}
• Las-Vegas: Fokus auf resultierende Korrektheit
• Gemeinsamkeiten: Beide nutzen Zufall zur Optimierung
• App: Monte-Carlo zur Approximation, Las-Vegas zur exakten Lösung

Randomisierte Algorithmen in der Kryptographie

Definition:

Verwendung von Zufall in Algorithmen zur Erhöhung der Sicherheit und Effizienz kryptographischer Verfahren.

Details:

• Erzeugung kryptographischer Schlüssel mittels Zufallszahlen
• Probabilistische Verschlüsselung: erhöht Sicherheit, indem identische Nachrichten unterschiedlich verschlüsselt werden
• Monte-Carlo-Algorithmen in der Primzahlprüfung
• Zero-Knowledge-Protokolle: Nachweis von Wissen ohne Preisgabe der Information
• Wahrscheinlichkeit der Korrektheit bei randomisierten Algorithmen essentiell
• Beispiele: RSA Schlüsselgenerierung, probabilistische Algorithmen für faktorisierungsbasierte Kryptographie

Stochastische Prozesse und ihre Anwendungen

Definition:

Stochastische Prozesse sind mathematische Modelle für Systeme, die sich zufällig entwickeln. Diese werden in randomisierten Algorithmen verwendet, um probabilistische Entscheidungen zu treffen.

Details:

• Ein Prozess: Familie von Zufallsvariablen \(\{X_t\}_{t \in T}\), wobei \(T\) der Indexbereich ist
• Anwendungen: Monte-Carlo-Simulationen, Markov-Ketten
• Markov-Kette: \(P(X_{t+1}=x|X_0=x_0,...,X_t=x_t)=P(X_{t+1}=x|X_t=x_t)\)
• Erwartungswert und Varianz helfen bei der Analyse