AuK/Teile und Herrsche 2 WS13-14

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Autoren:
* [mailto:s3darich@stud.hs-zigr.de Daniel Richter]
* [mailto:s3addank@stud.hs-zigr.de Adrian Danker]

== Binäres Suchen ==

Wann immer ein Gegenstand oder eine Information gesucht werden muss, gibt es verschiedene Herangehensweisen. Um einen Eintrag im Duden oder eine Abfahrtszeit im Bahnfahrplan zu finden, kann durch einen Vergleich der vorangehenden oder nachfolgenden Einträge bereits nach einem Ausschlussverfahren vorgegangen werden. Hierbei handelt es sich allerdings schon um "sortierte Listen".
Sucht man dagegen etwas in einer "unsortierten Liste", wie etwa eine Schraube in einer "Restekiste" mit diversen Schrauben, prüft man elementeweise, ob das gesuchte Element (die Schraube) in der Liste (die Schraubenrestekiste) vorhanden ist. Ist im ungünstigsten Fall die gesuchte Schraube das letzte Element, ist der Aufwand $\mathcal{O}(n)$. Entsprechend hat die Suche einen linearen Aufwand und ist für besonders große Listen (Nadel im Heuhaufen) nicht zu empfehlen. Implementiert in Scheme würde eine solche Suche folgendermaßen aussehen:

<code id="526b9aa9f24d4">(define lineareUnsortierteSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Element ist nicht in der Liste enthalten")
      ((= element (car liste)) "Das Element ist in der Liste enthalten")
      (else
       (lineareUnsortierteSuche element (cdr liste))))))</code>
<run id="526b9aa9f2ba8">(lineareUnsortierteSuche 21 '(89 5 2 55 13 1 143 3 21 34 8 232))</run>

Die Nachteile dieses Suchalgorithmus liegen auf der Hand:
* Mit wachsender Anzahl der Elemente steigt der Aufwand linear
* Ist das Element nicht enthalten, wird in jedem Fall die Liste komplett durchsucht

In einer aufsteigend sortierten Liste erlaubt eine kleine Modifikation des Algorithmus den Abbruch der Suche, falls das Element nicht in der Liste vorhanden ist:

<code id="526b9aa9f25b9">(define lineareSortierteSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Element ist nicht in der Liste enthalten")
      ((< element (car liste)) "Element ist nicht in der Liste enthalten")
      ((= element (car liste)) "Das Element ist in der Liste enthalten")
      (else
       (lineareSortierteSuche element (cdr liste))))))</code>
<run id="526b9aa9f2c4d">(lineareSortierteSuche 13 '(1 2 3 5 8 13 21 34 55 89 143 232))</run>

Nach wie vor zeigt der Worst case (Das gesuchte Element ist immer das Letzte oder nicht vorhanden), dass hier ein linearer Aufwand vorliegt.

Um also einen geringeren Aufwand zu erreichen, soll bei der Suche nun systematisch vorgegangen werden. In dem Beispiel mit der Suche eines Wortes im Duden wird der Duden mittig aufgeschlagen und anschließend je nach Anfangsbuchstaben des gesuchten Wortes der Vordere oder hintere Teil des Dudens erneut halbiert bis die Zielseite gefunden ist. Der Suchraum wird auf diese Weise immer halbiert und die Zielseite wird deutlich schneller gefunden.

Für die binäre Suche reduzieren wir das Suchproblem auf eine Liste mit $n$ Elementen aus dem Zahlenbereich der ganzen Zahlen $\mathcal{\mathbb{Z}}$:

:$\mathcal{L=\{e_{1}, e_{2}, \dots ,e_{n}\}}$
:mit $\mathcal{e\in\mathbb{Z}}$
:und $\mathcal{n\in\mathbb{N}}$


Zuerst muss die Liste in zwei Teillisten geteilt werden. Bei einer ungeraden Anzahl von Listenelementen wird abgerundet (floor).
:$\mathcal{k=\left\lfloor\frac{n}{2}\right\rfloor}$
:mit $\mathcal{k}$ als mittigstem Listenelement der Liste $\mathcal{L}$

Anschließend gibt es eine linke und eine rechte Teilliste:
:$\mathcal{L_{l}=\{e_{1}, e_{2}, \dots , e_{k}\}}$
:$\mathcal{L_{r}=\{e_{k+1}, e_{k+2}, \dots , e_{n}\}}$

Ist $\mathcal{x}$ das gesuchte Element, wird $\mathcal{x}$ mit dem ersten Element der rechten Teilliste verglichen $\mathcal{x < e_{k+1}}$. Das Ergebnis entscheidet darüber, ob mit der rechten oder linken Teilliste fortgefahren wird. Die neue Teilliste wird so lange rekursiv verarbeitet, bis $\mathcal{x}$ gefunden wurde oder alle Teillisten untersucht wurden. Bestenfalls ist das erste Element $\mathcal{e_{k+1}}$ der Teilliste $\mathcal{L_{r}}$ bereits das gesuchte Element $\mathcal{x}$.

Die rekursive Bildungsvorschrift zur binären Suche kann folgendermaßen angegeben werden:

$$\mathcal{
\mathit{BiSu} = \begin{cases} {\mathit{BiSu}}\left(L_{1}\right), \ \mbox{$wenn$}\ x < e_{k+1} \\ 
\mathit{BiSu}\left(L_{r}\right), \ \mbox{$wenn$}\ x > e_{k} \\ 
\mathit{print}\left(e_{k}\right), \ \mbox{$wenn$}\ k = e_{k} \\ 
\mathit{nicht\ Enthalten}, \ \mbox{$wenn$}\ k < 0\ \mbox{$oder$}\ k > n \\ 
\mathit{nicht\ Enthalten}, \ \mbox{$sonst$}\end{cases}
}$$

Mit der binären Suche ist es möglich, in einem Duden mit 140.000 Stichwörtern und 1216 Seiten mit höchstens $\mathcal{17}$ ($\mathcal{\approx \log_2 140000}$) Wortvergleichen jedes Wort zu finden.

=== Scheme-Implementierung der binären Suche ===

Um eine Implementierung in Scheme zu realisieren, wird die bereits im Kapitel über Mergesort thematisierte Funktion "teillisten2" benötigt.

<code id="526e0e15e3044" hidden>(define teillisten2
  (lambda (ls)
    (let ((k (floor (/ (length ls) 2))))
      (letrec
          ((helfer
            (lambda (ls i)
              (if (= i 0)
                  (values '() ls)
                  (call-with-values
                   (lambda () (helfer (cdr ls) (- i 1)))
                   (lambda (links rechts)
                     (values (cons (car ls) links) rechts)))))))
        (helfer ls k)))))</code>

Scheme-Implementierung der binären Suche:
<code id="526e0e15e310d">(define binSuche
  (lambda (element liste)
    (call-with-values
     (lambda () (teillisten2 liste))
     (lambda (lls rls)
       (cond
         ((null? rls) "Element ist nicht in der Liste enthalten")
         ((= element (car rls)) "Element ist in der Liste enthalten")
         ((< element (car rls))
             (binSuche element lls))
         (else
          (if (null? (cdr rls))
              "Element ist nicht in der Liste enthalten"
              (binSuche element rls))))))))</code>

Zur Demonstration der korrekten Arbeitsweise des Algorithmus ist hier eine Liste explizit angegeben. Es können auch Prozeduren verwendet werden, die eine Liste mit Zufallszahlen ausgeben.

<run id="526e0e15e3471">(binSuche 34 '(1 2 3 5 8 13 21 34 55 89 143 232))</run>

Um nicht nur zu erfahren, '''dass''' das gesuchte Element gefunden wurde, sondern zusätzlich dessen Position ausgegeben zu bekommen, muss der Algorithmus erneut angepasst werden. Auch die Anzahl der Rekursionsschritte ist für eine Aufwandsanalyse sehr aussagekräftig, weshalb auch diese berücksichtigt wird. Zuerst müssen daher Zähler für die Aufrufe und Rekursionsschritte definiert und in den vorhandenen Code integriert werden.

<code id="526b9aa9f27c7">(define aufrufe 0)

(define rekursionsschritte 0)

(define binSuche2
  (lambda (element liste)
    (call-with-values
     (lambda () (teillisten2 liste))
     (lambda (lls rls)
       (cond
         ((null? rls) "Nicht gefunden!")
         ((= element (car rls)) 
          (and (and (set! rekursionsschritte (+ rekursionsschritte (length lls)))
                    (and (string-append "Gefunden - [Stelle: "
                                        (number->string rekursionsschritte) "] - [rekursive Aufrufe: "
                                        (number->string aufrufe) "]")))))
         ((< element (car rls))
          (if (null? lls)
              "Nicht gefunden"
              (and (set! aufrufe (+ aufrufe 1))
                   (binSuche2 element lls))))
         (else
          (if (null? (cdr rls))
              (string-append "Nicht gefunden. [Rekursionen: " 
                             (number->string aufrufe) "]")
              (and (set! aufrufe (+ aufrufe 1))
                   (and 
                    (set! rekursionsschritte (+ rekursionsschritte (length lls)))
                    (binSuche2 element rls))))))))))</code>

Eine weitere Prozedur wird zum Aufruf der binären Suche verwendet:

<code id="526b9aa9f2870">(define binSucheAufruf
  (lambda (element liste)
    (set! aufrufe 0)
    (set! rekursionsschritte 0)
    (binSuche2 element liste)))</code>

Ein Aufruf unserer neuen binären Suche ergibt dann das gewünschte Ergebnis.

<run id="526b9aa9f2dab">(binSucheAufruf 55 '(1 2 3 5 8 13 21 34 55 89 143 232))</run>

=== Vergleich sequenzielle und binäre Suche ===
<code id="526e0e15e31cb" hidden>
Da im vorangegangenen Teilabschnitt die Grundlage für eine empirische Analyse der binären Suche geschaffen wurde, soll das hier nun auch für die sequenzielle Suche getan werden. So wird die Möglichkeit geschaffen, die Aufwände der beiden Suchen zu vergleichen.

Zu implementieren ist eine Variable für die Anzahl der Aufrufe, die als Index verwendet werden kann:
</code>
<code id="526b9aa9f2943" hidden>(define sortierteSequenzielleSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Das gesuchte Element ist nicht in der Liste enthalten")
      ((< element (car liste)) "Das gesuchte Element ist nicht in der Liste enthalten")
      ((= element (car liste)) 
       (string-append "Das gesuchte Element ist in der Liste enthalten und befindet sich an der Position "
                      (number->string aufrufe) "."))
      (else       
       (set! aufrufe (+ aufrufe 1))
       (sortierteSequenzielleSuche element (cdr liste))))))</code>
<code id="526e0e15e328e" hidden>
Es wird eine Prozedur benötigt, die die Variable "aufrufe" zurücksetzt:
</code>
<code id="526b9aa9f2a02" hidden>(define sortierteSequenzielleSuche2
  (lambda (element liste)
    (set! aufrufe 0)
    (sortierteSequenzielleSuche element liste)))</code>
<code id="526e0e15e336c" hidden>
Nun funktioniert folgender Aufruf:

<run id="526b9aa9f2e6b">(sortierteSequenzielleSuche2 89 '(1 2 3 5 8 13 21 34 55 89 144 233))</run>
</code>

Warum ist also die binäre Suche effizienter als die sequenzielle Suche von $\mathcal{x}$ in einer aufsteigend sortierten Liste $\mathcal{G}$? 

Bei der sequenziellen Suche wird $\mathcal{x}$ mit den aus $\mathcal{G}$ stammenden Elementen verglichen, beginnend bei dem Kleinsten Element, bis $\mathcal{x}$ gefunden wurde. Würde man den Fall $\mathcal{x \notin G}$ miteinbeziehen, könnte die Suche im Fall, dass das erste Element $\mathcal{a_{i}}$ größer ist als $\mathcal{x}$, (erfolglos) beendet werden.

Für den Best Case $\mathcal{x = a_{1}}$ gilt $\mathcal{T(n) = O(1)}$. Im Worst- sowie im Average-Case werden $\mathcal{n}$ Durchläufe nötig, womit $\mathcal{T(n) = O(n)}$ gilt. 
Sollte jedes Element aus $\mathcal{G}$ mit gleicher Wahrscheinlichkeit mit $\mathcal{x}$ übereinstimmen, so könnte man den Aufwand wie folgt beschreiben:

:$\mathcal{\begin{array} {ccl}
T(n) = \frac {1} {n} \cdot \sum\limits_{i=1}^{n} i = \frac {n} {2n} (n+1) = \mathcal{O}(n)
\end{array}}$

Damit wird deutlich, weshalb der sequenziellen Suche die binäre Suche vorzuziehen ist.


=== Effizienzanalyse binäre Suche ===

Die Länge der Teillisten wird schrittweise halbiert. Besonders gut funktioniert das, wenn die Anzahl $\mathcal{n}$ der Elemente von $\mathcal{G}$ eine Zweierpotenz ist. Die Anzahl der rekursiven Aufrufe entspricht der Anzahl der Halbierungsschritte, also $\mathcal{log_2\ n}$ Stück. Wird für den in jedem Schritt stattfindenden Vergleich ein konstanter Aufwand $\mathcal{\mathcal{O}\left( c \right)}$ angenommen, beträgt der Gesamtaufwand

:$\mathcal{T\left(n\right) = \mathcal{O}\left(log_2 \ n\right)}$

Dies trifft für den Average- sowie für den Worst Case zu. Der Best Case benötigt dagegen nur einen einzigen Vergleich und arbeitet mit konstantem Aufwand 

:$\mathcal{T\left(n\right) = \mathcal{O}\left(c\right)}$

unabhängig von der Anzahl $\mathcal{n}$.

==== Best Case ====

Im besten Fall kommen beide Suchalgorithmen im ersten Schritt zum Ergebnis. Dabei ist das gesuchte Element bei der sequenziellen Suche das erste Listenelement und bei der binären Suche das erste Element der rechten Teilliste. Beide Suchen erreichen somit einen konstanten Aufwand 

:$\mathcal{T(n)=\mathcal{O}(c)}$

der unabhängig von $n$ ist.

==== Average- und Worst-Case ====

Die sequenzielle Suche benötigt im schlechtesten Fall $\mathcal{n}$ Durchläufe, d.h. $\mathcal{T(n)=\mathcal{O}(n)}$. Im mittleren Fall gilt das genauso. Geht man davon aus, das alle Listenelemente mit $\mathcal{x}$ mit gleicher Wahrscheinlichkeit übereinstimmen, ist der Aufwand der sequenziellen Suche 

:$\mathcal{T(n) = \frac {1} {n} \cdot \sum\limits_{i=1}^{n} i = \frac {n} {2n} (n+1) = \mathcal{O}(n)}$

Bei der binären Suche ist aufgrund der Arbeitsweise des Algorithmus erkennbar, dass sich die Länge der Teillisten in jedem Schritt halbiert, besonders dann, wenn die Anzahl der Listenelemente gerade ist. In diesem Fall stimmt die Anzahl der rekursiven Aufrufe mit der Anzahl der Halbierungen überein, also genau $\mathcal{\log_2 n}$. Für die Vergleichsoperationen in den einzelnen Zwischenschritten wird ein konstanter Aufwand $\mathcal{\mathcal{O}(c)}$ angenommen. Dadurch ergibt sich für die binäre Suche im mittleren und schlechtesten Fall ein Gesamtaufwand von $\mathcal{T(n)=\mathcal{O}(\log_2 n)}$

====Fazit====

In der Praxis kann nie vom Best Case ausgegangen werden, weshalb bei der Betrachtung der Algorithmen diese Fälle unbeachtet bleiben. Da der Aufwand der sequenziellen Suche linear und der Aufwand der binären Suche logarithmisch ist, ist die binäre Suche der sequentiellen Suche vorzuziehen.

Folgende Gegenüberstellung soll verdeutlichen, weshalb der Aufwand der binären Suche wesentlich geringer ist:

\begin{array}{|c|l r|r|r|r|r|r|r|r|}
\hline
f(n) & n= & 2 & 4 & 8 & 32 & 256 & 8192 & 2097152 & 17179869184\\
\hline\\
log_2 n & & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34\\
\hline\\
n & & 2 & 4 & 8 & 32 & 256& 8192 & 2097152 & 17179869184\\
\hline
\end{array}

== Multiplikation großer ganzer Zahlen ==

Die Multiplikation großer ganzer Zahlen nach Karatsuba und Ofman (1960) ist ein typisches Teile-und-Herrsche-Verfahren. Dabei wird die Verringerung des Rechenaufwandes im Vergleich zu der Schulmethode angestrebt, die mit einem quadratischen Aufwand arbeitet. Hierzu werden einige Multiplikationsvorgänge durch Additionsverfahren und Verschiebungen ersetzt, die linear arbeiten.

Um das Verfahren von Karatsuba und Ofman anwenden zu können, müssen zunächst einige Voraussetzungen gegeben sein:

:$x$ und $y$ haben die gleiche Stelligkeit $n$
:$n$ ist eine gerade Zahl
:$x$ und $y$ werden in einen High-Teil $x_1$, bzw. $y_1$ und einen Low-Teil $x_0$, bzw. $y_0$ halbiert
:$b$ ist die Basis der Zahlendarstellung, üblicherweise 10 (Dezimales Zahlensystem)

dadurch gilt

:${x = x_1 b^{\frac{n}{2}} + x_0}$
:${y = y_1 b^{\frac{n}{2}} + y_0}$

Beide High- bzw. Low-Teile sind durch die Halbierung gleich lang. Die Multiplikation der beiden Zahlen sähe nun folgendermaßen aus:

:$\mathcal{x\cdot y = \left(x_{1}\cdot y_{1}\right)b^{n} + \left(x_{0}\cdot y_{1} + x_{1}\cdot y_{0}\right)b^{\frac{n}{2}} + x_{0} \cdot y_{0}}$

Als Ergebnis liegen nun, statt einer Multiplikation zweier $n$-stelliger Zahlen, vier gleichartige Multiplikationen zweier $\frac{n}{2}$-stelliger Zahlen zuzüglich dreier Additionen von je zwei Zahlen, die keinesfalls mehr als $n$-stellig sind, vor.

Der Gesamtaufwand beträgt $\mathcal{T(n)=4\cdot T(\frac{n}{2})+\Theta(n)}$

Darauf kann die Meistermethode angewandt werden:

:$x=4$
:$y=2$

:$f(n)=n^{log_y x}$

:$f(n)=n^{log_2 4}$
:$=n^{\frac{\log 4}{\log 2}}$
:$=n^{2}$

Damit ergibt sich $T(n)=\mathcal{O}(n^{2})$.

Verglichen mit der Schulbuchmethode ist hier keine Verbesserung eingetreten, da nach wie vor ein quadratischer Aufwand vorliegt.
Die Verbesserung erfolgt in den nächsten Schritten. Durch die äquivalente Umformung

:$\mathcal{x_{0}\cdot y_{1}+ x_{1}\cdot y_{0}}$
:$\mathcal{=x_{1}\cdot y_{1}+ x_{0}\cdot y_{0} -\left(x_{0} - x_{1}\right) \cdot \left(y_{0} - y_{1}\right)}$

kann der resultierende Term in die obrige Formel eingesetzt werden. Das Resultat ist

:$\mathcal{x \cdot y = x_{1} \cdot y_{1}b^{n} + \left( x_{1} \cdot y_{1} + x_{0} \cdot y_{0} - \left( x_{0} - x_{1} \right) \cdot \left( y_{0} - y_{1} \right)\right)b^{\dfrac{n}{2}} + x_{0} \cdot y_{0}}$

Die Produkte $p := x_0 \cdot y_0$ und $q := x_1 \cdot y_1$ kommen jeweils zweimal vor. Sie werden mit einem Aufwand von $\mathit{T}\left(\frac{n}{2}\right)$ jeweils genau einmal berechnet und anschließend eingesetzt:

:$\mathit{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}$

Zu den beiden Multiplikationen von $p$ und $q$ kommt noch die Multiplikation von $\left( x_0-x_1\right) \cdot \left(y_0 - y_1  \right)$,  zwei je $\frac{n}{2}$-stelligen Zahlen sowie deren Addition (in $\Theta\left(n\right)$) hinzu.

Der daraus resultierende Gesamtaufwand beträgt:

:$\mathcal{T\left(n\right) = 3 \cdot T \left( \frac{n}{2}\right) + \Theta\left( n\right)}$

Nun führt die Anwendung der Meistermethode zu folgendem Ergebnis:

:$x=3$
:$y=2$

:$f(n)=n^{log_y x}$

:$f(n)=n^{log_2 3}$
:$=n^{\frac{\log 3}{\log 2}}$
:$=n^{1.58496}$

In $\mathcal{O}$-Notation:

:$\mathcal{T\left( n\right) = \mathcal{O}\left( n^{log_2 3}\right) \approx  \mathcal{O}\left( n^{1.58496}\right)}$

Die Multiplikation zweier $10^8$-stelliger Zahlen nach dieser Methode dauert mit einer 3GHz-CPU ($= 3*10^9$) weniger als eine halbe Stunde:

:$(10^8)^{1.582} / 3*10^9 / 60  = 26.57219927$

Die gleiche Berechnung nach der Schulmethode dauert mehr als 38 Tage:

:$(10^8)^{2} / 3*10^9 / 60  \approx 55555.555 \ / 60 / 24 \approx 38.5802469$

== Übungen ==

Multiplizieren Sie schriftlich und ohne Taschenrechner die Zahlen $579\ 244$ und $314\ 658$ nach der Methode von Karatsuba. Als Basis verwenden Sie $b = 10$.


<popup name="Lösung">

<center>
\begin{array}{ccl}
x & = & \underbrace{579}_{x_1}\ \underbrace{244}_{x_0}\\\\
y & = & \underbrace{314}_{y_1}\ \underbrace{658}_{y_0}\\\\\\\\

x_0 & = & 244\\\\
x_1 & = & 579\\\\
y_0 & = & 658\\\\
y_1 & = & 314\\\\\\\\

n & = & 6\\\\\\\\

x & = & x_1 b^{\frac{n}{2}} + x_0\\\\
  & = & 579 \cdot 10^3 + 244\\\\ 

y & = & y_1 b^{\frac{n}{2}} + y_0\\\\
      & = & 314 \cdot 10^3 + 658\\\\\\\\

p & = & x_0 \cdot y_0\\\\
  & = &  244 \cdot 658 \\\\
  & = & 160\ 552\\\\

q & = & x_1 \cdot y_1\\\\
 & = & 579 \cdot 314 \\\\
 & = & 181\ 806\\\\\\\\\

\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = & \left( 244 -579 \right) \cdot \left( 658 - 314 \right)\\\\
\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = & -335 \cdot 344\\\\
\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = &  -115\ 240\\\\\\\\

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 & = & 181\ 806  \cdot 10^{6} + \left( 181\ 806  + 160\ 552 + 115\ 240\right)\cdot 10^3 + 160\ 552\\\\
x \cdot y & = & 181\ 806  \cdot 10^{6} + 457\ 598 \cdot 10^3 + 160\ 552\\\\
x \cdot y & = & 182\ 263\ 758\ 552 \\\\\\\\
\end{array}
</center>

</popup>