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>Binäre1.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:


<math>
\begin{array}{ccl}
T(n) &=& 3 \cdot T_{c}(\frac{n}{2}) \\\\
T(n) &=& 3 \cdot (3 \cdot T_{c} (\frac{n}{4})) \\\\
T(n) &=& 3 \cdot (3 \cdot (3 \cdot T_{c} (\frac {n}{8})))\\\\
T(n) &=& 3 \cdot (3 \cdot (3 \cdot (3 \cdot T_{c} (\frac {n}{16}))))\\\\
T(n) &=& 3^4 \cdot T_{c}\left(\frac{n}{2^4}\right) \right) \\\\
T(n) &=& 3^{k} \cdot T_{c} (\frac {n}{2^{k}})\\\\
T(1) &=& T(\frac{n}{2^{k}})\\\\
1 &=&\frac{n} {2^{k}}\\\\
k &=& log_2{\ n}\\\\
T(n) &=& 3^{log_2{\ n}}\\\\
T(n) &=& n^{log_2 {\ n}}\\\\
\mathcal{O}(n) &=& n^{1.59}\\\\\\\\
\end{array}
</math>


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:


<center><math>
\begin{array}{ccl}
x & = & \underbrace{135\ 746}_{\text{\ High-Teil}}\ \underbrace{823\ 107}_{\text{\ Low-Teil}}\\\\
y & = & \underbrace{248\ 672}_{\text{\ High-Teil}}\ \underbrace{423\ 897}_{\text{\ Low-Teil}}\\\\\\\\

x_0 & = & 823\ 107\\\\
x_1 & = & 135\ 746\\\\
y_0 & = & 423\ 897\\\\
y_1 & = & 248\ 672\\\\\\\\

x & = & x_1 b^{\frac{n}{2}} + x_0\\\\
  & = & 135\ 746 \cdot 10^6 + 823\ 107\\\\ 

y & = & y_1 b^{\frac{n}{2}} + y_0\\\\
      & = & 248\ 672 \cdot 10^6 + 423\ 897\\\\\\\\

p & = & x_0 \cdot y_0\\\\
  & = &  823\ 107 \cdot 423\ 897 \\\\
  & = & 348\ 912\ 587\ 979\\\\

q & = & x_1 \cdot y_1\\\\
 & = & 135\ 746 \cdot 248\ 672 \\\\
 & = & 33\ 756\ 229\ 312\\\\\\\\\

\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = & \left( 823\ 107 -135\ 746 \right) \cdot \left( 423\ 897 - 248\ 672 \right)\\\\
\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = & 687\ 361 \cdot 175\ 225\\\\
\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = &  120\ 442\ 931\ 225\\\\\\\\

x \cdot y & = & q b^n + \left( q + p - \left( x_0-x_1\right) \cdot \left(y_0 - y_1  \right) \right)b^{\frac{n}{2}} + p\\\\
x \cdot y & = & 33\ 756\ 229\ 312  \cdot 10^{12} + \left( 33\ 756\ 229\ 312  + 348\ 912\ 587\ 979 - 120\ 442\ 831\ 225\right)\cdot 10^6 + 348\ 912\ 587\ 979\\\\
x \cdot y & = & 33\ 756\ 229\ 312  \cdot 10^{12} + 262\ 225\ 986\ 066 \cdot 10^6 + 348\ 912\ 587\ 979\\\\
x \cdot y & = & 33\ 756\ 491\ 538\ 334\ 978\ 587\ 979 \\\\\\\\
\end{array}
</math></center>