Algorithmen: Mathematik

[Kategorie:Informatik] [Kategorie:Algorithmen]

Im Wesentlichen werden bei Algorithmen zwei Aspekte mathematisch geprüft:

1. Laufzeit
2. Genauigkeit (oder Zuverlässigkeit)

Prüfung der Zuverlässigkeit: Konfidenzintervall und Wahrscheinlichkeit

Bei Simulationen lässt man einen Prozess 1000mal (oder öfter) laufen, und erhält entsprechend viele Ergebnisse.

Aus den Ergebnissen der Simulation kann man den Mittelwert bilden und erhält so eine Voraussage auf das tatsächliche Verhalten.

Daran schließt sich die Frage an: Wie genau ist diese Voraussage?

Eine 100prozentig genaue Voraussage wird man mit einer Simulation nie erreichen; stattdessen gibt man ein Konfidenzintervall und eine Wahrscheinlichkeit an, z.B.:

Mit einer Wahrscheinlichkeit von 99% ist das tatsächliche Ergebnis im Intervall [0,7745 | 0,7957].

Ermittlung des Konfidenzintervalls mithilfe von Mittelwert und Standardabweichung

Ergebnisse von Simulationen sind in der Regel normalverteilt, weil die einzelnen Durchläufe der Simulationen voneinander unabhängig sind.

D.h. die Ergebnisse der Simulation kann als Stichprobe angesehen werden, von der man auf die Gesamtheit schließt.

Von der Stichprobe (d.h. allen Simulationsergebnissen) ermittelt man folgende Werte:

• Den Mittelwert der Stichprobe: [math]\displaystyle{ \overline x = \frac{1}{n} \sum_{i=1}^n{x_i} }[/math] = \frac{1}{n} \sum_{i=1}^n{x_i}</math>
• Die (korrigierte) Standardabweichung: [math]\displaystyle{ s= \sqrt{\frac{1}{n-1} \sum \limits_{i=1}^n\left(x_i-\overline x\right)^2} }[/math]

Jetzt gilt (lt. Mathematik...):

• Mit 95% Sicherheit liegt das echte Ergebnis im Intervall [math]\displaystyle{ [\overline x - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \cdot{s} ] }[/math].
• Mit 99% Sicherheit liegt das echte Ergebnis im Intervall [math]\displaystyle{ [\overline x - 2,58 \cdot{s} ~ | ~ \overline x + 2,58 \cdot{s} ] }[/math].

Sonderfall: Bernoulli-Versuche

Bei Bernoulli-Versuchen (d.h. Versuchen, für die es als Ergebnis nur "0" oder "1" gibt), ist die Ermittlung von Mittelwert und Standardabweichung sehr einfach, denn die Ergebnisse von Bernoulli-Ketten sind "binominalverteilt". Deswegen kann man Mittelwert und Standardabweichung wie folgt berechnen:

• Mittelwert: [math]\displaystyle{ \overline x = p }[/math]
• (korrigierte) Standardabweichung: [math]\displaystyle{ s = \sqrt{\frac{p \cdot (1-p)}{n-1}} }[/math]

Beispiel: Ermittlung von PI

Es wird 10.000mal zufällig auf das Einheitsquadrat "geschossen": Als "Treffer" zählt es, wenn der Punkt im Einheitskreis liegt.
Von den 10.000 Schüssen sind 7851 Treffer, d.h. man hat eine Trefferwahrscheinlichkeit p=0,7851 .

Das ist eindeutig eine Bernoulli-Kette, denn

• die "Schüsse" haben das Ergebnis 1 (=im Einheitskreis) oder 0 (daneben),
• die "Schüsse" sind voneinander unabhängig.

• Mittelwert: [math]\displaystyle{ \overline x = 0,7851 }[/math]
• (korrigierte) Standardabweichung: [math]\displaystyle{ s = \sqrt{\frac{0,7851 \cdot (1-0,7851)}{n-1}} = 0,0041 }[/math]

Bestimmung des Konfidenzinterfalls für eine Wahrscheinlichkeit von 99%:

• [math]\displaystyle{ [\overline x - 2,58 \cdot{s} ~ | ~ \overline x + 2,58 \cdot{s} ] ~ = ~ }[/math]
  
  [math]\displaystyle{ [0,7851 - 2,58 \cdot{0,041} ~ | ~ 0,7851 + 2,58 \cdot{0,041} ]~ = ~ }[/math]
  
  [math]\displaystyle{ [0,7745 ~ | ~ 0,7957] }[/math]

Da man diese Simulation nur für einen Viertelkreis gemacht hat, muss man das Intervall noch mit 4 multiplizieren, um ein Konfidenzintervall für Pi zu erhalten:

Mit 99% Wahrscheinlichkeit liegt Pi im Intervall

[math]\displaystyle{ [4 \cdot 0,7745 ~|~ 4 \cdot 0,7957]~= }[/math]
[math]\displaystyle{ [3,098 ~|~ 3,1828] }[/math]