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]
• 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 - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \cdot{s} ] }[/math].