Probabilistische Algorithmen SS09

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2009-05-17T17:17:36+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.)


2

Setzen Sie sich an einem schönen Tag ins Freie, und beobachten Sie Ameisen bei der Futtersuche. Welche Beziehungen zu dem Ameisenalgorithmus können Sie erkennen? Welche Beispiele aus der Natur können noch einen Anreiz darstellen, sie als Vorbild für einen Algorithmus zu nutzen?


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

http://www.m-boehmer.de/pdf/Schwarmintelligenz_Artikel.pdf

Jörg Rothe - Komplexitätstheorie und Kryptologie