AuK/Probabilistische Algorithmen SS09

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Java</language>
<language>Java</language>
<language>Java</language>
===Einführung in proballistische Algorithmen===
[[Einführung in probalistische Algorithmen]]

[["Zufallszahlen"]]

===Algorithmen===
[[Las-Vegas-Algorithmen]]

====Monte-Carlo-Algorithmus Gruppe 2====
Ein Monte-Carlo-Algorithmus ist ein Algorithmus welcher immer ein Ergebnis liefert, allerdings mit einer festlegbaren 
Wahrscheinlichkeit ein fehlerhaftes Resultat zurückliefert. Mithilfe von Monte-Carlo-Algorithmen lassen sich Probleme 
lösen die sonst nur schwer bis unlösbar sind.


=====Multimengenvergleiche=====
Wöllte man die Multimengen <math>$M_1=\{1,2,2,3,4,5\}$</math> und <math>$M_2=\{5,4,2,3,2,1\}$</math> auf Äquivalenz überprüfen 
müsste man die beiden Multimengen ordnen und dann auf Äquivalenz prüfen. Dies kostet im Mittel <math>$\mathcal{O}(n log n)$</math>, 
besser wäre allerdings<math> $\Theta(n)$</math>, dies vermag ein propabilistischer Algorithmus zu erreichen.
Es wird verabredet das jeder Multimenge <math>$M_m=\{x_1,x_2,...,x_n\}$</math> ein Polynom <math>$p_{M_m}$</math> zugeordnet wird.
Dieses Polynom wird nach folgendem Muster gebildet.
<math>$p_{M_m}(x)=(x-x_1)(x-x_2)...(x-x_n)$</math>
Nun werden folgende Regeln verabredet:

1. <math>$M_1\equiv M_2$</math>, wenn <math>$p_{M_1}(x)\ =\ p_{M_2}(x)$</math> für ''alle'' ganzen Zahlen <math>$x$</math> zutrifft.

2. <math>$M_1\not\equiv M_2$</math>, wenn in 1. beschriebenes Verfahren für mindestens ein <math>$x$</math> fehlschlägt.

Was bedeutet das für uns. Nunja, sobald wir auf ein <math>$x$</math> für welches die Funktionswerte der beiden Polynome unterschiedlich sind so ist ziemlich sicher das die Multimengen unterschiedlich sind. Um die Wahrscheinlichkeit zu erhöhen wird der Test für zufällige <math>$x$</math> wiederholt. 
Konkret schaut das dann wie folgt aus.

Wir haben die 3 Multimengen''' m1 ,m2 ,m3''' zur Verfügung. m2 ist die Spiegelung zu m1, m3 ist eine gänzlich andere Multimenge
Die Hilfsprozedur '''poly''' liefert den Polynomwert der Multimengen für einen gegebenen Wert.
<code>
(define poly
  (lambda (x nstls)
    (if (null? nstls)
        1
        (* (- x (car nstls))
           (poly x (cdr nstls))))))
(define m1 '(1 2 3 4 5))
(define m2 (reverse m1))
(define m3 '(2 3 5 4 3))
</code>
<eval>(poly 10 m1)
</eval>
Wenn man die Prozedur über alle 3 Multimengen laufen lässt bekommt man mit hoher Wahrscheinlichkeit verschiedene Werte.
Es kann aber auch vorkommen das für alle 3 Multimengen der gleiche Polynomwert herauskommt.
Man kann deshalb allerdings noch nicht von einer Äquivalenz ausgehen. Dafür sind mehrere Versuch mit zufälligen Eingabewerten notwendig.
Dafür verwenden wir die Prozedur '''m-aequiv?''' und die Hilfsprozedur '''m-aequiv*?''' welche die Wiederholungen für uns übernimmt.
<code>
 (define m-aequiv?
  (lambda (m1 m2 r)
    (let ((x (random r)))
      (= (poly x m1)(poly x m2)))))
(define m-aequiv*?
  (lambda (m1 m2 r wdh)
    (cond 
      ((= wdh 0) #t)
      ((m-aequiv? m1 m2 r)
       (m-aequiv*? m1 m2 r (- wdh 1)))
      (else
       #f))))
</code>
<eval>(m-aequiv*? m1 m2 3 10)</eval>

=====Solovay/Strassen=====
<code hidden>
(define jacobi-symbol
  (lambda (p q)
    (cond ((zero? p) 0)
          ((= 1 p) 1)
          ((odd? p)
           (if (odd? (quotient (* (- (modulo p 16)1)(- q 1)) 4))
                     (- (jacobi-symbol (modulo p q) p))
               (jacobi-symbol (modulo q p) p)))
          (else
           (let ((qq (modulo q 16)))
             (if (odd? (quotient (- (* qq qq) 1) 8))
                 (- (jacobi-symbol (quotient p 2) q))
                 (jacobi-symbol (quotient p 2) q)))))))

(define solovay-strassen-prim?
  (lambda (n wdh)
    (letrec
        ((helfer
          (lambda (i)
            (cond
              ((= i 0) #t)
              ((let ((a (zufall-a n)))
                 (= (modulo (jacobi-symbol a n) n) (potmod a (quotient (- n 1) 2) n)))
               (helfer (- i 1)))
              (else #f)))))
      (if (= n 2)
          #t
          (helfer wdh)))))
(define stp
  (lambda (n)
    (do((i 3 (+ i 2)))
      ((> i n) (newline))
      (if (solovay-strassen-prim? i 2)
          (printf "~a, " i)))))



(define zufall-a
  (lambda (n)
    (let ((a (+ 2 (random (- n 2)))))
      (if (> (gcd a n) 1) (zufall-a n)) a)))
 (define potmod
   (lambda (basis exponent mod)
     (letrec
         ((helfer
           (lambda (exponent resultat)
             (if(= exponent 0)
                resultat
                (helfer (- exponent 1) (modulo (* resultat basis) mod))))))
          (helfer exponent 1))))
</code>
<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)

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

mit

<math>z_0=4567\\a=9749\\b=0\\c=2^{18}=262144</math>


<code>  
(define seed1 12347899 )

(define zf
;Kongruenzmethode in Scheme
(lambda ()
(let ((seed2 (modulo (+ (* 9749 seed1) 0) 262144)))
(set! seed1 seed2)
seed2)))

</code>

<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? 




===3===

Entwerfen sie einen Quicksort-Algorithmus, welcher sein Pivot-Element zufällig wählt. Vergleichen sie die effizienz mit der Quicksort-Variante, welche immer das erste Element als Pivot-Element nutzt.














[[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