Aufgaben - TuH2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Link zur Hauptseite: [[Teile_und_Herrsche_2]]
==Aufgaben zur Binären Suche==
===Aufgabe (a) - Durchrechnen ===
'''Gegeben''' sei folgende Liste:
<tt>(2 3 5 8 9 11 13 20 32 33 38)</tt>
'''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.
Hinweis 1:
Der Scheme-Interpreter versteht das Sprachelement <tt>random</tt> zunächst noch nicht. Eine hier "versteckte" Prozedur definiert eine "Glücksrad-
Fabrik", die im Folgenden verwendet wird, um einen Zufallszahlen-Generator (<tt>random</tt>) zu erzeugen.
Hinweis 2:
Wie in der Vorlesung [[Probabilistische_Algorithmen_2#.28Pseudo.29Zufallszahlen] "Probabilistische Algorithmen"]] im Kapitel [["(Pseudo)Zufallszahlen"]] zu erfahren ist, ist die Bereitstellung von Zufallszahlen
keinesfalls Trivial. Auch hier im Wiki gibt es einschränkungen. So stellt der Algorithmus bei mehrmaligen Ausführen leider immer die gleichen Zahlen
zur Verfügung. Diese Problematik soll hier aber nicht weiter stören.
<code 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 (random-maker 19781116))
</code>
<eval>
(list (random 10)(random 10)(random 10)(random 10)) ; Zufallszahl zwischen 0 und 9 (einschl. der Grenzen)
</eval>
Nun können wir eine Hilfsprozedur zur Erzeugung von Zufallszahlenlisten definieren.
=== Hilfsprozeduren ===
== zzls ==
<code>
;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))))
</code>
<eval>(zzls 2 10 100)</eval>
''zzls - ZufallsZahlenListe''
<!--<code>
;zzls für ZufallsZahlenListe. Generiert eine Liste mit n paarweise verschiedenen Ganzen Zahlen zwischen a und b.
;Beispielaufruf:
;>(zzls 10 100 1000) ; Zufallszahlenliste mit 1000 Zufallszahlen zwischen 10 und 100
;(define zzls
; (lambda (a b n)
; (if (= n 0)
; (list)
; (let ((x (random b)))
; (if (> x a)
; (append (list x)(zzls a b (- n 1)))
; (zzls a b n))))))
</code>-->
Aufrufbeispiel
<eval>(zzls 0 50 20)</eval>
HINWEIS! Offensichtlich beherrscht die SchemeImplementation im Wiki nicht die Prozedur (random x). Deshalb erscheint hier ein Fehler.
In einer Lokalen DrScheme-Umgebung sollte der Quellcode funktionieren, wenn als Sprache "Kombo" ausgewählt wird.
Für die Übung haben wir einige Beispiellisten vorgegeben, die Sie benutzen können.
Vorgefertigte, unsortierte Listen
<code>
(define u_liste1 '(37 1 26 29 9 3 44 4 24 9 20 11 16 30 16 48 39 28 25 46))
(define u_liste2 '(21 34 27 20 3 5 28 37 14 5 28 6 39 3 13 32 8 30 13 36))
(define u_liste3 '(14 27 16 30 22 5 10 30 13 47 36 12 44 43 2 45 11 49 3 46))
(define u_liste4 '(13 25 17 37 39 48 21 36 18 45 9 38 36 12 8 27 46 42 15 44))
(define u_liste5 '(19 22 9 49 28 26 46 9 27 31 8 19 36 48 36 49 14 38 9 8))
</code>
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.
<code hidden>
(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)))))))
</code>
Die sortierten Listen
<code>
(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))
</code>
Überprüfe, ob die Liste korrekt Sortiert wurde.
<eval>liste1</eval>
<code hidden>
(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)))
</code>
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:
<eval>(binaersuche2 44 liste1)</eval>
<code hidden>
(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."))))
</code>
Beispielaufruf Sequenzielle Suche:
<eval>(seqsuche 44 liste1)</eval>
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''
<code>
(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)))))
</code>
Ü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:
'''<tt>vector</tt>''': Definiert einen Vektor
<eval>(define v (vector 1 2 3 4 5 6 7 8))
v</eval>
'''<tt>vector?</tt>''': Überprüft, ob es sich um einen Vektor handelt
<eval>(vector? v)</eval>
'''<tt>vector-length</tt>''': gibt die Länge des Vektors zurück
<eval>(vector-length v)</eval>
'''<tt>vector-ref</tt>''': gibt das Element an einer bestimmten Stelle zurück
<eval>(vector-ref v 4)</eval>
'''<tt>vector->list</tt>''': Wandelt einen Vektor in eine Liste um
<eval>(define liste (vector->list v))
liste</eval>
'''<tt>list->vektor</tt>''': Wandelt eine Liste in einen Vektor um
<eval>(define v2 (list->vector liste))
v2</eval>
Genauere Erklärungen und ein paar mehr Sprachelemente finden Sie z.B. [http://www.cs.grinnell.edu/~stone/courses/scheme/spring-2000/vectors.xhtml HIER]
Versuchen Sie nun eine verbesserte Binäre Suche zu Implementieren. Sie können dafür diesen EVAL-Blog verwenden:
<eval>
;verbesserte Binaere Suche
</eval>
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.
<math>
\begin{array}{lcc}
12 & \text{und} & 45 \\
1236 & \text{und} & 4538 \\
36727 & \text{und} & 345
\end{array}
</math>
==Strassen-Algorithmus==
===Aufgabe (a) ===
Berechnen Sie folgendes Produkt mit Hilfe des Strassenalgorithmus. Verwenden Sie ein Computer-Algebra-System.
<math>
A =
\left(
\begin{array}{cccc}
5 & 3 & 8 & 1 \\
2 & 9 & 7 & 4 \\
5 & 1 & 7 & 3 \\
9 & 3 & 4 & 9 \\
\end{array}
\right)
</math>
<math>
B =
\left(
\begin{array}{cccc}
1 & 2 & 3 & 4 \\
8 & 7 & 6 & 5 \\
9 & 1 & 2 & 3 \\
7 & 6 & 5 & 4 \\
\end{array}
\right)
</math>
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]]