Aufgaben - TuH2

Aus ProgrammingWiki

Archivierte Version vom 2009-04-17T14:00:21+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. 
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

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

Der Code der modifizierten Binären Suche aus der Hauptwikiseite:

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

Beispielaufruf: <eval>(binaersuche2 44 liste1)</eval>

Code der Sequenziellen Suche <hidden></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."))))

Beispielaufruf: <eval>(seqsuche 44 liste1)</eval>

Von Interesse sind Jeweils

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