AuK/Probabilistische Algorithmen WS13-14

Wiki-Quelltext dieser Seite.

=Einleitung=
=Zufall=
==Was ist Zufall?==
Auf der Suche nach der Definition des Begriffes Zufall liegt es nahe,
die Wortbedeutung im Duden nachzuschlagen. Hier ist der Zufall als "etwas, was man nicht vorhergesehen hat, was unerwartet geschah" definiert.
Hieraus ergibt sich die Fragestellung, ob das eingetretene Ereignis niemals vorausgesagt werden kann, oder nur in einem speziellen Fall nicht vorhergesehen werden konnte.
Ein Beispiel:
Wir betrachten den Wurf einer Münze, genauer gesagt den Zeitpunkt t, an welchem die Münze wieder beginnt, abwärts zu fallen.
Das Ergebnis des Wurfes erscheint zufällig. Doch für einen begabten Mathematiker mit entsprechender Rechentechnik wäre
es zum Zeitpunkt t durchaus möglich, anhand der Rotation, Umweltbedingungen und weiterer Parameter eine Vorhersage bezüglich des Ergebnis zu treffen.
Er steht allerdings vor dem Problem, dass er das Ergebnis vor dem Auftreffen der Münze berechnen muss (Zeitfrage).
Demnach ist eine Differenzierung nötig, da augenscheinlich sowohl die Perspektive des Betrachters eine Rolle spielt, als auch der Stand der Wissenschaft.
Es existieren Ereignisse, von denen bewiesen werden konnte, dass sie keine kausale Ursache haben. Ein Beispiel hierfür ist der Zerfallszeitpunkt eines (radioaktiven) Atoms.
Außerdem ist es möglich, dass man zwar alle Einflussfaktoren kennt, die ein Ergebnis bestimmen, diese aber weder ändern noch messen kann. Offensichtlich trifft dies bei Zufallsexperimenten zu. Betrachtet man den Wurf eines Würfels kann man sich leicht vorstellen, wovon das Ergebnis abhängt: Der angewendeten Kraft, dem Auftreffwinkel auf dem Untergrund,
das Material des Untergrundes und des Würfels usw. Bevor man dies alles berücksichtigt hat, steht das Ergebnis schon fest. Dies entspricht auch dem Beispiel 1.
Desweiteren kann es sein, dass die Ursache nicht erkennbar ist, aber existiert. Hierbei spricht man auch vom Pseudozufall. Dies findet in Programmiersprachen bei der Benutzung bestimmter Methoden Anwendung. Sie geben eine für den Betrachter ( = Programmierer) zufällige Zahl aus, unterliegen aber einer deterministisch definierten Berechnung.

==Zufallszahlen erzeugen==
Für die Erzeugung von Zufallszahlen gilt es also, die obigen Erkenntnisse zu berücksichtigen. Da man hierbei auf Beschränkungen trifft, haben erzeugte Zufallszahlen eine gewisse Güte.
Es liegt nahe, bewiesene zufällige Ereignisse zu Verwenden, um Zufallszahlen von höchster Güte zu erzeugen. Diese sind allerdings immer physisch und nicht ohne Weiteres anwendbar, theoretisch gesehen ist allerdings die Verwendung beispielsweise des Atomzerfalls bestens geeignet. Ebenfalls physisch, leichter verwendbar und nur mit leicht geringerer Güte sind beispielsweise die Benutzung einer Lottomaschine oder das Werfen von Würfeln. Es ist offensichtlich, das diese Verfahren bei einer großen Zahl an gewünschten Zufallszahlen an (zeitliche) Grenzen stoßen. Um dieses Problem zu lösen, gibt man sich mit Zufallszahlen geringerer Güte zufrieden und arbeitet mit dem Pseudozufall. 
<!--
quelle suchen:radioaktiver zerfall für zufall hoher güte:
http://www.business-on.de/radioaktiver-zerfall-atomen-kernumwandlung-zerfallsreihe-halbwertszeit-_id31049.html
lottoziehung, warum echt zufällig


 -->

=Numerisch probabilistische Algorithmen=
==Definition==

Numerisch probabilistische Algorithmen haben als Ergebnis eine Näherungslösung mit wählbarer Genauigkeit, in Folge dessen kann der Nutzer selbst durch Wahl seiner Eingaben bestimmen wie genau das gewünschte Ergebnis sein soll.
Weiterhin ist diese Art von Algorithmen nichtdeterministisch, dass bedeutet das bei mehrfacher Ausführung mit dem gleichen Wert unterschiedliche Lösungen zurückgegeben werden können.

<language>Java</language>
==Beispiel: Zufallsregen==

Eine einfache Art der Bestimmung eines Näherungswertes für <math>\pi</math> ist die Methode des sogenannten Zufallregens.<br>
[[Bild:S3damuel_Regen-pi-sw2.png]]<br>
Man werfe dabei eine beliebige Anzahl an "Regentropfen" auf das oben abgebildete Quadrat mit Innenkreis, wobei der Radius des Innenkreises den Wert 1 besitzt. Um <math>\pi</math> zu bestimmen, werden zwei Arten von aufkommenden Tropfen gezählt: die Tropfen innerhalb des Kreises <math>T_{Kreis}</math> und die Tropfen innerhalb des Quadrates <math>T_{Quadrat}</math>. Um die Genauigkeit der Berechnung zu erhöhen, betrachtet  man nur die Tropfen im ersten Quadranten der Quadrates. Damit ein Punkt innerhalb des Kreises liegt gelten für ihn folgende Bestimmungen: $x^2+y^2 \le 1$, wobei x,y reelle Zahlen im Bereich $0 < x,y \le 1$.<br>
Die Annäherung an $\pi$ ergibt sich dann aus folgenden Überlegungen:<br><math>\frac{A_{Kreis}}{A_{Quadrat}} = \frac{\pi r^2}{4r^2} \approx \frac{T_{Kreis}}{T_{Quadrat}}</math><br>
Da zunächst nur das Auftreffen im ersten Quadranten betrachtet wurde, ergibt sich nun nach folgender Operation der Näherungswert für $\pi$: <br>
<math>\pi = 4 * \frac{T_{Kreis}}{T_{Kreis}+T_{Quadrat}}</math>.<br>
Es wurde ja definiert, dass numerisch probabilistische Algorithmen eine wählbare Genauigkeit besitzen, in diesem Beispiel kann die Genauigkeit durch steigende Tropfenanzahl verbessert werden.
<!-- <code>	void rain(int anzahl) {
		double roundpi = 0;

		Random a = new Random(System.currentTimeMillis());

		double t_k = 0;
		double t_q = 0;

		for (int i = 0; i < anzahl; i++) {
			double x, y;
			x = a.nextDouble();
			y = a.nextDouble();

			if ((x * x + y * y <= 1)) {
				t_k = t_k + 1;
			} else {
				t_q = t_q + 1;
			}

		}

	//	System.out.println(t_k + "kreis");
	//	System.out.println(t_q + "quadrat");

		roundpi = 4*(t_k / anzahl);
System.Out.Println( roundpi);

	}</code>
<run>rain(50);</run>
-->

=Las-Vegas-Algorithmen=
=Monte-Carlo-Algorithmen=
==Prinzahltest nach Fermat==
==Primzahltest nach Solovay und Strassen==



=Probabilistische Analyse=
==Indikatorfunktion==

=Literaturverzeichnis=
* Wagenknecht, Christian: Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003
* Ziegenbalg, Jochen: Algorithmen, Spektrum Akademischer Verlag, 1996
* Mathar, Rudolph; Pfeifer, Dietmar: Stochstik für Informatiker, B.G. Teubner Verlag, 1990
* Wanka, Rolf: Approximationsalgorithmen, B.G. Teubner Verlag, 2006
* Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007
* Gumm, Heinz; Sommer, Manfred: Einführung in die Informatik, Oldenbourg Verlag, 2006