AuK/Teile und Herrsche 1 SS11 Aufgaben/

Wiki-Quelltext dieser Seite.

==Übungsaufgaben==

'''Um sich die einzelnen Verfahren zu verdeutlichen, sind folgende Aufgaben zu lösen.'''

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

Lösung: <document>Quicksort.pdf</document>



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


Lösung: <document>Mergesort.pdf</document>



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> 


Lösung: <document>S3romuel_Binäre.pdf</document>


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:<document>Seq_Suche.pdf</document>



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: