Ü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: G = \{ 10; \ 2; \ 8; \ 19;\ 12;\ 16\}
Lösung: Quicksort.pdf
2. Sortieren Sie die folgende Menge mit Mergesort Schritt für Schritt auf Papier: G = \{ 10; \ 2; \ 8; \ 19;\ 12;\ 16\}
Lösung: Mergesort.pdf
3.
a) Suchen Sie mit Hilfe der binären Suche (schriftlich auf Papier) das Element x = 16 aus folgender sortierter Liste: G = ( 2, \ 7, \ 8, \ 10,\ 12,\ 16,\ 19, \ 21)
Lösung: Binäre1.pdf
b) Suchen Sie mit Hilfe der sequenziellen Suche (schriftlich auf Papier) das Element x = 16 aus folgender sortierter Liste: G = ( 2, \ 7, \ 8, \ 10,\ 12,\ 16,\ 19,\ 21)
Lösung:Seq_Suche.pdf
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:
\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}
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:
\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\ 931\ 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}