Aufgaben - TuH2

Aus ProgrammingWiki

Archivierte Version vom 2009-06-28T20:15:02+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufgaben zur Binären Suche
2 Aufgaben zum Karatsuba Algorithmus
- 2.1 Aufgabe (a)
3 Strassen-Algorithmus
- 3.1 Aufgabe (a)
4 Lösungen

Link zur Hauptseite: Teile und Herrsche 2

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.

Hinweis 1:
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

<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.

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

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

<eval> u_liste1 </eval>

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.

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. <eval>liste1</eval>

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>

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

(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 <eval>(define v (vector 1 2 3 4 5 6 7 8)) v</eval>

vector?: Überprüft, ob es sich um einen Vektor handelt <eval>(vector? v)</eval>

vector-length: gibt die Länge des Vektors zurück <eval>(vector-length v)</eval>

vector-ref: gibt das Element an einer bestimmten Stelle zurück <eval>(vector-ref v 4)</eval>

vector->list: Wandelt einen Vektor in eine Liste um <eval>(define liste (vector->list v)) liste</eval>

list->vektor: 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. HIER

Versuchen Sie nun eine verbesserte Binäre Suche zu Implementieren. Sie können dafür diesen EVAL-Blog verwenden: <eval></eval>

verbesserte Binaere Suche

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.

\begin{array}{lcc} 12 & \text{und} & 45 \\ 1236 & \text{und} & 4538 \\ 36727 & \text{und} & 345 \end{array}

Strassen-Algorithmus

Aufgabe (a)

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

A = \left( \begin{array}{cccc} 5 & 3 & 8 & 1 \\ 2 & 9 & 7 & 4 \\ 5 & 1 & 7 & 3 \\ 9 & 3 & 4 & 9 \\ \end{array} \right)

B = \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 8 & 7 & 6 & 5 \\ 9 & 1 & 2 & 3 \\ 7 & 6 & 5 & 4 \\ \end{array} \right)

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