AuK/Probabilistische Algorithmen SS10

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''Autoren:'''

#Mateusz Zwierz     ([mailto:simazwie@stud.hs-zigr.de simazwie@stud.hs-zigr.de])
#Hans Markwart      ([mailto:sihamark@stud.hs-zigr.de sihamark@stud.hs-zigr.de])

==Einleitung==

==Pseudozufallszahlen==
<code id="4c02583ebf3d3" hidden>
	(require-library 'sisc/libs/srfi/srfi-19)
	(import srfi-19)
</code>

<code id="4c02956bc4d8f" 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
  (let ((seed (time-nanosecond (current-time))))
;    (display seed)
    (random-maker seed)))

(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)   ; stellt current-time usw. bereit

(define random (random-maker (time-nanosecond (current-time))))

(define a 
  (lambda (t el ls)
    (cond
         ((<= t 0) 0)
         ((=(car ls)el) (car ls))
         (else
          (a (- t 1) el (cdr ls))))))



(define search
  (lambda (ns t el ls)
  (cond
    ((= (a  (random t) el ls) 0) 'false)
    ((= (a (random t) el ls) el) 'true)
    (else( search (- ns 1) (random t) el ls)))))

(define ls '(1 2 3 6 6 6))</code>


<eval id="4c02956bc5556">
(search   2 6 1 ls)
</eval>
==Monte-Carlo-Algorithmen==

==Las-Vegas-Algorithmen==

==Ant Colony Optimization==