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"> </popup>


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




* <popup name="Lösung"> </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"><math>2^{146} \equiv 1\  mod \ 147</math>
        
<math>2^{285}\equiv 1\  mod \ 286</math>

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

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

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