Algorithmen: Mathematik: Unterschied zwischen den Versionen
| Zeile 23: | Zeile 23: | ||
Von der Stichprobe (d.h. allen Simulationsergebnissen) ermittelt man folgende Werte: | Von der Stichprobe (d.h. allen Simulationsergebnissen) ermittelt man folgende Werte: | ||
* Den '''Mittelwert''' der Stichprobe: <math> \overline x = \frac{1}{n} \sum_{i=1}^n{x_i}</math> | * Den '''Mittelwert''' der Stichprobe: <math> <math> \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>s= \sqrt{\frac{1}{n-1} \sum \limits_{i=1}^n\left(x_i-\overline x\right)^2} </math> | * Die (korrigierte) '''Standardabweichung''': <math>s= \sqrt{\frac{1}{n-1} \sum \limits_{i=1}^n\left(x_i-\overline x\right)^2} </math> | ||
| Zeile 29: | Zeile 29: | ||
* Mit 95% Sicherheit liegt das echte Ergebnis im Intervall <math>[\overline x - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \cdot{s} ] </math>. | * Mit 95% Sicherheit liegt das echte Ergebnis im Intervall <math>[\overline x - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \cdot{s} ] </math>. | ||
* Mit 99% Sicherheit liegt das echte Ergebnis im Intervall <math>[\overline x - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \cdot{s} ] </math>. | * Mit 99% Sicherheit liegt das echte Ergebnis im Intervall <math>[\overline x - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \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> \overline x = n \cdot p </math> | |||
* (korrigierte) '''Standardabweichung''': <math> \overline x = \sqrt{\frac{p \cdot (1-p)}{n-1}}</math> | |||
Version vom 19. Januar 2017, 11:30 Uhr
[Kategorie:Informatik] [Kategorie:Algorithmen]
Im Wesentlichen werden bei Algorithmen zwei Aspekte mathematisch geprüft:
- Laufzeit
- 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{ \lt math\gt \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 - 1,96 \cdot{s} ~ | ~ \overline x + 1,96 \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 = n \cdot p }[/math]
- (korrigierte) Standardabweichung: [math]\displaystyle{ \overline x = \sqrt{\frac{p \cdot (1-p)}{n-1}} }[/math]