Aufgaben - TuH2
Inhaltsverzeichnis |
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) - Algorithmus erweitern
Um eine Empirische Aufwandsanalyse durchführen zu können, benötigt man Messwerte. Diese erhält man in unserem Fall durch eine Erweiterung der Implementierung um einen Zähler an geeigneter Stelle.
Modifizieren sie die Implementierung ihrer Wahl (Java oder Scheme) entsprechend.
Aufgabe (c) - Empirische Analyse
Vergleichen sie das Ergebnis aus Aufgabe (a) mit dem Algorithmus überprüfen und nutzen sie die zusätzlich zur Verfügung gestellte Liste (bzw. für die Java Implementierung ein Array) Liste2 für einen weiteren Testlauf.
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