Aufgaben - TuH2

Aus ProgrammingWiki
Archivierte Version vom 2009-04-05T15:27:39+00:00. Aktuelle Version

Inhaltsverzeichnis

Aufgaben zur Binären Suche

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

Aufgabe 1 - 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 eine Implementierung (Java oder Scheme) ihrer Wahl entsprechend.

Lösungen - TuH2L

Aufgabe 2 - Messdaten erheben

Nehmen sie nun einige Werte und prüfen sie den Algorithmus.

Was fällt dabei auf?


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