Probabilistische Algorithmen SS09

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2009-05-17T17:06:21+00:00. Aktuelle Version

Inhaltsverzeichnis

Einführung in proballistische Algorithmen

Einführung in probalistische Algorithmen

"Zufallszahlen"

Algorithmen

Las-Vegas-Algorithmen

Monte-Carlo-Algorithmus Gruppe 2


Multimengenvergleiche

<eval>()</eval>

Solovay/Strassen

<eval>(stp 50)</eval>

Buffons Nadel

Ausblick

Genetische Programmierung

Schwarmalgorithmen


Aufgaben

1

Implementieren Sie einen Generator für Pseudozufallszahlen nach der Kongruenzmethode. (Buch S. 124)

z_{n}=(a*z_{n-1}+b)mod\ c

mit

z_0=4567\\a=9749\\b=0\\c=2^{18}=262144


<eval>(zf)</eval>

(Um einen zufälligen Startwert anzunehemn gibt es zwar auch Sprachelemente in Scheme, jedoch funktionieren diese hier in der Wiki nicht.)


Aufgabenverteilung

Quellen

http://www.riskglossary.com/link/monte_carlo_method.htm

Oliver Lau "Faites vos jeux! - Zufallszahlen erzeugen, erkennen und anwenden" (c't 2009, Heft 2)

http://www.addison-wesley.de/Service/Krueger/kap12006.htm

Schickinger, Steger - Diskrete Strunkturen - Band 2 - Wahrscheinlichkeitstheorie und Statistik

Juraj Hromkovič - Algorithmics for Hard Problems

Juraj Hromkovič - Randomisierte Algorithmen