AuK/Probabilistische Algorithmen SS11/

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==Übungen==

1. Implementieren Sie einen Generator für Pseudozufallszahlen nach der Kongruenzmethode.




<popup name="Lösung"> <code id="4dede3393b41b">

(define c 262144)

(define zufallszahlen
  (lambda (z)
    (let ((a 16807)(b 0))
      (if (eq? z 0) 
          4567
          (modulo (+ (* a (zufallszahlen (- z 1))) b) c)))))</code>

</popup>


2. Erstellen Sie ein probabilistisches Quicksort, welches das Pivotelement zufällig wählt.




<popup name="Lösung">

<code id="4dede3393b517">

(define select-random
  (lambda (ls)
    (let ((len (length ls)))         
      (list-ref ls (random len)))))  


(define (quicksort L)
    (if (null? L) L
    (letrec ((pivot (select-random L))
    (split
    (lambda (piv li return)
    (cond ((null? li) return)
    ((< (car li) piv)
    (split piv (cdr li) (cons (cons (car li) (car return))
    (cdr return))))
    (else
    (split piv (cdr li) (cons (car return)
    (cons (car li)
    (cdr return)))))))
    ))
    `(,@(quicksort (car (split pivot (cdr L) '(() . ())))) ,pivot
    ,@(quicksort (cdr (split pivot (cdr L) '(() . ())))))
    )
    )
    )
</code>

</popup>



3. Arbeiten Sie mit dem Primzahltest nach Fermat .


3.1. Teste die Zahlen <math>147, 286 , 313</math> ,und <math>353</math>  mit der <math>Basis \ 2</math>


3.2. Teste die Zahlen desweiteren mit <math>Basis \ 3</math>


<popup name="Lösung">3.1
<math>2^{146}\not \equiv 1\  mod \ 147</math>


<math>2^{285}\not \equiv 1\  mod \ 286</math>

        
<math>2^{312}\equiv 1\ mod   \ 313</math>


<math>2^{350}\not \equiv 1\ mod \ 351</math>

3.2


<math>3^{146} \not \equiv 1\  mod \ 147 </math>   


<math>3^{285}\equiv 1\  mod \ 286 </math>

        
<math>3^{312}\equiv 1\ mod   \ 313</math>

           
<math>3^{350}\not \equiv 1\ mod \ 351</math>


</popup>
 

[http://www.arndt-bruenner.de/mathe/java/rechnergz.htm Rechner für große Zahlen]