AuK/Teile und Herrsche 1 SS11 Aufgaben/

Wiki-Quelltext dieser Seite.

==Übungsaufgaben==

1. Sortieren Sie die folgende Liste mit Quicksort Schritt für Schritt auf Papier: <math> G = \{ 10; \  2; \ 8; \ 19;\ 12;\ 16\}</math> 
 

Lösung: 



2. Sortieren Sie die folgende Liste mit Mergesort Schritt für Schritt auf Papier: <math> G = \{ 10; \  2; \ 8; \ 19;\ 12;\ 16\}</math> 


Lösung:



3. 

a) Suchen Sie mit Hilfe der binären Suche (schriftlich auf Papier) das Element <math> x = 16 </math> aus folgender sortierter Liste: <math> G = \{ 2; \  7; \ 8; \ 10;\ 12;\ 16;\ 19; \ 21}</math> 


b) Suchen Sie mit Hilfe der sequenziellen Suche (schriftlich auf Papier) das Element <math> x = 16 </math> aus folgender sortierter Liste: <math> G = \{ 2; \  7; \ 8; \ 10;\ 12;\ 16;\ 19; \ 21}</math> 



Lösung:




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:

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


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: