Aus ProgrammingWiki
< AuK < Teile und Herrsche 1 SS11 Aufgaben
Archivierte Version vom 2011-05-02T19:48:10+00:00. Aktuelle Version

Übungsaufgaben

1.


Lösung:


2.


3.


4. Zu Beginn unserer Vorlesung wiesen wir die Effizienz von Teile-und-Herrsche-Algorithmen mit der Meister-Methode nach. Aufgabe ist es nun, die Effizienz iterativ nachzuweisen. Folgende Aufwandsbeziehungen gelten:

T_C \left( n \right) =\begin{cases} T_A \left( n \right), & \text{wenn } \ n \ \leq \ n_0, \\ 3 \cdot T_C \left( \frac{n}{2}\right), & \text{sonst } \end{cases}


Lösung:


5. Multiplizieren Sie schriftlich und ohne Taschenrechner die Zahlen 135\ 746\ 823\ 107 und 248\ 672\ 423\ 897 nach der Methode von Karatsuba. Als Basis verwenden Sie b = 10 .

Lösung: