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.)




===2===

Setzen Sie sich an einem schönen Tag ins freie, und beobachten Sie Ameisten 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