AuK/Probabilistische Algorithmen SS09

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
====Einführung in proballistische Algorithmen====
lalala [[Einführung in probalistische Algorithmen]] lalala
====Effiziensverbesserung====
[["Zufallszahlen"]]

====Numerische probabilistische Algorithmen====

===Algorithmen===
====Las-Vegas-Algorithmus====
lalala [[Las-Vegas-Algorithmen]] lalala

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


<language>Scheme</language>
=====Multimengenvergleiche=====


<code>

(define multimenge
 (lambda (k anzahl)
  '()
  (cons
   (+ 1 (random k))
   (multimenge k (- anzahl 1))
   )))
</code>
<code hidden>
;(define m1 (multimenge 7 6))
;(define m2 (reverse m1))
;(define m3 (multimenge 7 6))
(define polynomwert
  (lambda (x nullstellenliste)
   (if (null? nullstellenliste))
     (polynomwert x (cdr nullstellenliste)))))
(define m-aequiv?
(lambda (m1 m2 r)
(let ((x (random r)))
(= (polynomwert x m1)(polynomwert x m2)))))
</code>
<eval>(multimenge 7 6)</eval>

=====Buffons Nadel=====

===Ausblick===
====Genetische Programmierung Gruppe 2====
lalala [[Schwarmalgorithmen]] lalala

===Quellen===
<code hidden>http://www.riskglossary.com/link/monte_carlo_method.htm</code>
<code hidden>(define random-maker
  (let* ((multiplier 48271)
         (modulus 2147483647)
         (apply-congruence
          (lambda (current-seed)
            (let ((candidate (modulo (* current-seed multiplier)
                                     modulus)))
              (if (zero? candidate)
                  modulus
                  candidate))))
         (coerce
          (lambda (proposed-seed)
            (if (integer? proposed-seed)
                (- modulus (modulo proposed-seed modulus))
                19860617))))  ;; an arbitrarily chosen birthday
  (lambda (initial-seed)
    (let ((seed (coerce initial-seed)))
      (lambda args
        (cond ((null? args)
               (set! seed (apply-congruence seed))
               (/ (- modulus seed) modulus))
              ((null? (cdr args))
               (let* ((proposed-top
                       (ceiling (abs (car args))))
                      (exact-top
                       (if (inexact? proposed-top)
                           (inexact->exact proposed-top)
                           proposed-top))
                      (top
                       (if (zero? exact-top)
                           1
                           exact-top)))
                 (set! seed (apply-congruence seed))
                 (inexact->exact (floor (* top (/ seed modulus))))))
              ((eq? (cadr args) 'reset)
               (set! seed (coerce (car args))))
              (else
               (display "random: unrecognized message")
               (newline))))))))

(define random (random-maker 19781116))</code>