Aufgaben - TuH2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==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:

<!-- 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''
<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>
<eval>(zzls 0 50 20)</eval>


''mergesort''
<code>
;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)))))))
</code>

==Aufgaben zum Karatsuba Algorithmus==

===Aufgabe 1===

Multiplizieren sie folgende Werte mit Hilfe Karatsubas Verfahren.

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

===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]]