Probabilistische Algorithmen SS09

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2009-05-15T08:31:47+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einführung in proballistische Algorithmen
2 Effiziensverbesserung
3 Numerische probabilistische Algorithmen
4 Algorithmen
- 4.1 Las-Vegas-Algorithmus
- 4.2 Monte-Carlo-Algorithmus Gruppe 2
  - 4.2.1 Multimengenvergleiche
  - 4.2.2 Buffons Nadel
5 Ausblick
- 5.1 Genetische Programmierung Gruppe 2
6 Quellen

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

Multimengenvergleiche

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

<eval>(random <script type="text/javascript">GetRandom( 0, 3 ); </script>)</eval>

Probabilistische Algorithmen SS09

Inhaltsverzeichnis

Einführung in proballistische Algorithmen

Effiziensverbesserung

Numerische probabilistische Algorithmen

Algorithmen

Las-Vegas-Algorithmus

Monte-Carlo-Algorithmus Gruppe 2

Multimengenvergleiche

Buffons Nadel

Ausblick

Genetische Programmierung Gruppe 2

Quellen

Suche