AuK/Probabilistische Algorithmen SS09

Wiki-Quelltext dieser Seite.

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

[["Zufallszahlen"]]

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

====Monte-Carlo-Algorithmus Gruppe 2====




=====Multimengenvergleiche=====
<code>



</code>
<eval>()</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.)

























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