Aufgaben - TuH2

Aus ProgrammingWiki

Archivierte Version vom 2009-04-17T13:48:51+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufgaben zur Binären Suche
- 1.1 Aufgabe (a) - Durchrechnen
- 1.2 Aufgabe (b) - Empirische Analyse
2 Aufgaben zum Karatsuba Algorithmus
- 2.1 Aufgabe 1
- 2.2 Aufgabe 2 - Analyse der Schulbuchmethode
3 weitere Aufgaben
4 Lösungen

Aufgaben zur Binären Suche

Ziel der folgenden Aufgaben ist es, eine Empirische Aufwandsanalyse der Binären Suche durchzuführen.

Aufgabe (a) - Durchrechnen

Gegeben sei folgende Liste:

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 sie empirische Aufwandsanalyse ausserdem mit der Sequenziellen Suche durch, um einen Qualitätiven Vergleich anstellen zu können.

zzls - ZufallsZahlenListe

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

Aufrufbeispiel <eval>(zzls 0 50 20)</eval>

HINWEIS! Offensichtlich beherrscht die SchemeImplementation im Wiki nicht die Prozedur (random x). Deshalb erscheint hier ein Fehler. 
Zum Erstellen von Zufallszahlenlisten können Sie die Quellcode in ihre lokale DrScheme-Umgebung kopieren und dort als Sprache "Kombo"
auswählen. Anschließend sollte die Prozedur funktionieren und Sie können die definierten Listen benutzen.
Zusätzlich stellen wir schon ein paar Listen zur Verfügung

Vorgefertigte, unsortierte Listen

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

Diese Listen müssen für die Binäre Suche in Sortierter Form vorliegen. Dazu verwenden wir die Prozedur mv_mergesort teillisten2 und verbinden als Hilfsprozeduren von mv-mergesort.

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

Aufgaben zum Karatsuba Algorithmus

Aufgabe 1

Multiplizieren sie folgende Werte mit Hilfe Karatsubas Verfahren.

\begin{array}{lcc} 12 & \text{und} & 45 \\ 4536 & \text{und} & 6734 \\ 36727 & \text{und} & 345 \end{array}

Aufgabe 2 - Analyse der Schulbuchmethode

Tip:
Man sollte damit Beginnen sich zu überlegen aus welchen Operationen die Multiplikation zweier n-stelliger Zahlen besteht.
Dabei hilft mal ein Beispiel zu rechnen. Man erkennt eine bestimmte Anzahl von Multplikationen und Additionen! :-)

weitere Aufgaben

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