Aufgaben - TuH2

Aus ProgrammingWiki

Archivierte Version vom 2009-04-17T13:12:12+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))))))

mergesort

;mv-mergesort 
(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)))))))

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