AuK/Teile und Herrsche 1 SS11 Aufgaben/

Wiki-Quelltext dieser Seite.

==Übungsaufgaben==

1. 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:

<math>
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}
</math>



Lösung: 


2. 



3.



4.




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

Lösung: