Aufgaben - TuH2

Aus ProgrammingWiki

Link zur Hauptseite: Teile_und_Herrsche_2

Inhaltsverzeichnis 1 Aufgaben zur Binären Suche 1.1 Aufgabe (a) - Durchrechnen 1.2 Aufgabe (b) - Empirische Analyse 1.3 Hilfsprozeduren 1.4 Aufgabe (c) - Modifikation der Binaeren Suche 2 Aufgaben zum Karatsuba Algorithmus 2.1 Aufgabe (a) 3 Strassen-Algorithmus 3.1 Aufgabe (a) 4 Lösungen

Aufgaben zur Binären Suche

Aufgabe (a) - Durchrechnen

Gegeben sei folgende Liste:

(2 3 5 8 9 11 13 20 32 33 38)

Gesucht ist das Element 13

Verdeutlichen sie sich die Arbeitsweise der binären Suche. Zeichnen sie den Suchbaum!

Aufgabe (b) - Empirische Analyse

Die modifizierte Variante der binären Suche in Scheme bietet mit ihrem Zähler die Möglichkeit für eine empirische Analyse. Führen Sie eine empirische Aufwandsanalyse durch. Um ausreichend Testfälle zu produzieren, stehen die Prozeduren zzls für die Generierung einer Zufallszahlenliste, sowie mv-mergesort (Bekannt aus Teile und Herrsche 1) zum Sortieren der generierten Liste zur Verfügung.

Führen Sie die empirische Aufwandsanalyse außerdem mit der Sequenziellen Suche durch, um einen qualitativen Vergleich anstellen zu können.

Der Scheme-Interpreter versteht das Sprachelement random zunächst noch nicht. Eine hier "versteckte" Prozedur definiert eine "Glücksrad-Fabrik", die im Folgenden verwendet wird, um einen Zufallszahlen-Generator (random) zu erzeugen.

Hilfsprozeduren

Der Scheme-Interpreter versteht das Sprachelement random zunächst noch nicht. Eine hier "versteckte" Prozedur definiert eine "Glücksrad-Fabrik", die im Folgenden verwendet wird, um einen Zufallszahlen-Generator (random) zu erzeugen.

Hinweis 2:
Wie in der Vorlesung "Probabilistische Algorithmen" im Kapitel Probabilistische_Algorithmen_2#.28Pseudo.29Zufallszahlen zu 
erfahren ist, ist die Bereitstellung von Zufallszahlen keinesfalls Trivial. Die Random-Prozedur stellt deshalb bei jedem Aufruf die gleichen 
"zufälligen" Zahlen her. In einer Lokalen DrScheme-Umgebung funktioniert dies besser. Für unsere Zwecke soll dies hier aber ausreichen

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

(list (random 10)(random 10)(random 10)(random 10)) ; Zufallszahl zwischen 0 und 9 (einschl. der Grenzen)

ausführen

Nun können wir eine Hilfsprozedur zur Erzeugung von Zufallszahlenlisten definieren.

;zzls für ZufallsZahlenListe. Generiert eine Liste mit n natürlichen Zahlen zwischen a und b. (define zzls (lambda (a e n) (letrec ((helper (lambda (k) (if (= k 0) '() (cons (+ a (random (+ 1 (- e a)))) (helper (- k 1))))))) (helper n))))

(zzls 2 10 100)

ausführen

Vorgefertigte, unsortierte Listen

(define u_liste1 (zzls 1 100 50)) (define u_liste2 (zzls 1 100 50)) (define u_liste3 (zzls 1 100 50)) (define u_liste4 (zzls 1 100 50)) (define u_liste5 (zzls 1 100 50))

u_liste1

ausführen

Diese Listen müssen für die Binäre Suche in Sortierter Form vorliegen. Zum Sortieren verwenden wir die Prozedur mv-mergesort welche in der Vorlesung Teile und Herrsche 1 behandelt wurde.

(define teillisten2 (lambda (ls) (let ((k (floor (/ (length ls) 2)))) (letrec ((helfer (lambda (ls i) (if (= i 0) (values '() ls) (call-with-values (lambda ()(helfer (cdr ls)(- i 1))) (lambda (links rechts) (values (cons (car ls) links) rechts))))))) (helfer ls k))))) (define verbinden (lambda (lls rls) (cond ((null? lls) rls) ((null? rls) lls) (else (let ((x (car lls))(y (car rls))) (if (< x y) (cons x (verbinden (cdr lls) rls)) (cons y (verbinden lls (cdr rls))))))))) (define mv-mergesort (lambda (ls) (if (or (null? ls)(null? (cdr ls))) ls (call-with-values (lambda () (teillisten2 ls)) (lambda (ls1 ls2) (verbinden (mv-mergesort ls1) (mv-mergesort ls2)))))))

Die sortierten Listen

(define liste1 (mv-mergesort u_liste1)) (define liste2 (mv-mergesort u_liste2)) (define liste3 (mv-mergesort u_liste3)) (define liste4 (mv-mergesort u_liste4)) (define liste5 (mv-mergesort u_liste5))

Überprüfe, ob die Liste korrekt Sortiert wurde.

liste1

ausführen

(define binhelfer (lambda (x ls) (call-with-values (lambda () (teillisten2 ls)) (lambda (lls rls) (cond ((null? rls) "Schluessel nicht enthalten") ((= x (car rls)) (and (and (set! index (+ index (length lls))) (and (string-append "Schluessel gefunden an Stelle " (number->string index) ". Anzahl Rekursionen: " (number->string calls)))))) ((< x (car rls)) (if (null? lls) "Schluessel nicht enthalten" (and (set! calls(+ calls 1)) (binhelfer x lls)))) (else (if (null? (cdr rls)) (string-append "Schluessel nicht enthalten. Anzahl Rekursionen: " (number->string calls)) (and (set! calls (+ calls 1)) (and (set! index (+ index (length lls)))(binhelfer x rls)))))))))) (define index 0) (define calls 0) (define binaersuche2 (lambda (x ls) (set! index 0) (set! calls 0) (binhelfer x ls)))

Somit haben wir alle Werkzeuge zur Hand, um die Empirische Analyse durchzuführen und den Aufwand der Binären Suche mit dem der Sequenziellen Suche zu vergleichen

Beispielaufruf Binaersuche:

(binaersuche2 44 liste1)

ausführen

(define seqsuche (lambda (x ls) (cond ((null? ls) "Schluessel nicht enthalten.") ((= x (car ls)) (string-append "Schluessel gefunden an der Stelle " (number->string calls) ". Anzahl Rekursionen " (number->string calls))) ((< (car ls) x)(set! calls(+ calls 1))(seqsuche x (cdr ls))) (else "Schluessel nicht enthalten."))))

Beispielaufruf Sequenzielle Suche:

(seqsuche 44 liste1)

ausführen

Von Interesse sind für die Analyse die Anzahl der Rekursionsschritte. Führen Sie nun die Aufwandsanalyse mit geeigneten Werten durch und fassen Sie Ihre Ergebnisse zusammen.

Aufgabe (c) - Modifikation der Binaeren Suche

Auf der Hauptseite wurde schon angemerkt, dass die Binäre Suche zwar im Prinzip Logarithmischen Aufwand besitzt, unsere Scheme-Implementation dies jedoch nicht erfüllt. Machen Sie sich klar, warum dies so ist. Betrachten Sie dazu auch den Quellcode der Prozedur teillisten2

(define teillisten2 (lambda (ls) (let ((k (floor (/ (length ls) 2)))) (letrec ((helfer (lambda (ls i) (if (= i 0) (values '() ls) (call-with-values (lambda ()(helfer (cdr ls)(- i 1))) (lambda (links rechts) (values (cons (car ls) links) rechts))))))) (helfer ls k)))))

Überlegen Sie sich eine Lösung für dieses Problem. Wie könnte man die Binäre Suche umgestalten? Ziehen Sie die Möglichkeiten von Vectoren in Scheme in Betracht. Scheme stellt unter anderem diese Sprachelemente zur Benutzung von Vectoren bereit:

vector: Definiert einen Vektor

(define v (vector 1 2 3 4 5 6 7 8)) v

ausführen

vector?: Überprüft, ob es sich um einen Vektor handelt

(vector? v)

ausführen

vector-length: gibt die Länge des Vektors zurück

(vector-length v)

ausführen

vector-ref: gibt das Element an einer bestimmten Stelle zurück

(vector-ref v 4)

ausführen

vector->list: Wandelt einen Vektor in eine Liste um

(define liste (vector->list v)) liste

ausführen

list->vektor: Wandelt eine Liste in einen Vektor um

(define v2 (list->vector liste)) v2

ausführen

Genauere Erklärungen und ein paar mehr Sprachelemente finden Sie z.B. HIER

Versuchen Sie nun eine verbesserte Binäre Suche zu Implementieren. Sie können dafür dieses Run-Element verwenden:

;verbesserte Binaere Suche

ausführen

Eine mögliche Lösung finden Sie auf der Lösungsseite

Aufgaben zum Karatsuba Algorithmus

Aufgabe (a)

Multiplizieren sie folgende Werte mit Hilfe Karatsubas Verfahren.

Strassen-Algorithmus

Aufgabe (a)

Berechnen Sie folgendes Produkt mit Hilfe des Strassenalgorithmus. Verwenden Sie ein Computer-Algebra-System.

Stellen Sie dabei auch speziell die Schritte heraus, in denen das Teilen und das Herrschen in diesem Algorithmus zum tragen kommt.

Lösungen

Damits nicht gleich ins Auge fällt haben wir die Lösungen auf eine seperate Seite gepackt! Die findet ihr hier: Lösungen - TuH2L