AuK/Teile und Herrsche 1 SS11

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Autoren:
* Maik Linke ([mailto:s3malink@stud.hs-zigr.de s3malink@stud.hs-zigr.de])
* Romy Müller ([mailto:s3romuel@stud.hs-zigr.de s3romuel@stud.hs-zigr.de])



== Die Idee ==
=== Teile und Herrsche ===
Bei der systematischen Programmentwicklung und für die unmittelbare Ableitung von Aufwandsaussagen sind verschiedene Entwurfsmethoden für Algorithmen hilfreich. 
Zu den Entwurfsmethoden gehören zum Beispiel:
# Teile und Herrsche
# [[Greedy-Algorithmen]]
# [[dynamisches Programmieren]]

Teile und Herrsche (engl. "divide and conquer", lat. "divide et impera") ist die Entwurfsmethode für Algorithmen die wir nachfolgend genauer betrachten wollen.

Diese Methode hat seinen Ursprung als Redewendung und Strategie in der Kriegsführung. Bereits um 500 v. Chr. erwähnte  [http://de.wikipedia.org/wiki/Sunzi Sunzi], ein chinesischer General, sinngemäß "Teile und Herrsche" als Strategie der chinesischen Kriegskunst. Mit ''divise pour régner'' (frz. für "teilen, um zu herrschen") wurde sie als Ausspruch des frz. Königs [http://de.wikipedia.org/wiki/Ludwig_XI. Ludwig XI.] (*1423 †1483) bekannt. Des Weiteren ist die Strategie in der römischen Außenpolitik zu Zeiten [http://de.wikipedia.org/wiki/Gaius_Iulius_Caesar Julius Caesars] wieder zu erkennen. In Bezug auf Kriegsführung besteht die Taktik darin, die Gegner durch gezieltes gegeneinander Ausspielen in kleine Gruppen zu spalten und somit leichter besiegen zu können.


Das Prinzip ist in der Informatik das Gleiche/ Selbe (!?), wenn auch weniger grausam. Die Methode löst Probleme, indem es
# in Teilprobleme zerlegt wird ("divide")
# die Teilprobleme gelöst und 
# die Lösungen der Teilprobleme wieder zusammengesetzt werden ("conquer").

=== Effizienzbetrachtung von Teile und Herrsche ===
Wir wollen feststellen, ob mit Algorithmen, die nach der Methode "divide and conquer" entworfen wurden, eine Effizienzverbesserung erzielt werden kann. Wir betrachten einen Algorithmus <math> A </math>, der unser Problem in <math> \mathcal{O} \left( n \right) </math>, d.h mit <math> T_A \left(n\right) \leq c \cdot n^2 </math> löst. Der Algorithmus <math> T_B </math> bearbeitet drei Probleme der Größe <math> \frac{n}{2} </math> mittels der Prozedur <math> A </math>. Der Gesamtaufwand von unserem Algorithmus <math> T_B </math> fasst die Teillösungen mit einem Aufwand <math> \mathcal{O} \left( n \right) </math> zusammen.


<center><math>
\begin{array}{ccl}
T_B \left( n \right) & = & 3 \cdot T_A \cdot\left(\left\ \lceil\frac{n}{2}\right\ \rceil \right) + d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n+1}{2}\right) ^2 + d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n+1}{2}\right) \left( \frac{n+1}{2}\right) +d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n^2 + 2n + 1}{4}\right) + d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n^2}{4} + \frac{2n}{4} + \frac{1}{4}\right) + d \cdot n\\\\
                 & \leq     & \frac{3cn^2}{4} + \frac{6cn}{4} + \frac{3c}{4} + d \cdot n\\\\
                 & \leq     & \frac{3}{4}cn^2 + \frac{3}{2}cn + \frac{3}{4}c + d \cdot n\\\\
                 & \leq     & \frac{3}{4}cn^2 + \left(\frac{3}{2}c + d\right) \cdot n + \frac{3}{4} c\\\\
\end{array}
</math>
</center>


Das Ergebnis zeigt, dass eine Effizienzverbesserung von 25 % festgestellt werden kann. Der Aufwand ist jedoch nach wie vor quadratisch, wie der Exponent der Funktion zeigt. Das bedeutet, dass für größere <math> n </math> keine große Verbesserung in der Effizienz erzielt werden kann.  
Die Betrachtung eines Algorithmus <math> C </math> , der die drei Teilprobleme mit Rekursion löst, verdeutlicht, dass wir uns mit diesem Ergebnis nicht zufrieden geben müssen. Der Basisfall <math> n \leq n_0 </math> wird weiterhin vom Algorithmus <math> A </math> übernommen. Es entstehen folgende Aufwandsbeziehungen:

<center><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>
</center>

Diese Rekursionsgleichung lösen wir mit dem 1. Fall der Meistermethode. 


<center><math>
\begin{array}{ccl}
T_C \left( n \right) & = & 3 \cdot T_C \left( \frac{n}{2} \right)\\\\
                          & = & n^{log_2 3}\\\\
                          & = & n^{1,59}\\\\ 
                          & = & \mathcal{O}\left( n^{1.59} \right)

\end{array}
</math>
</center>


Die Lösung zeigt, dass durch eine rekursive Lösung die Effizienz dem quadratischen Aufwand gegenüber deutlich verbessert werden kann. Dies veranschaulicht, dass Teile-und-Herrsche-Verfahren immer rekursive Lösungen der gebildeten Teilprobleme enthalten müssen. Die Teilprobleme haben eine geringere Problemgröße bei gleicher Problematik, als das zu lösende Ausgangsproblem. Zur rekursiven Lösung gehört ein allgemeiner Fall wie auch ein Basisfall. Je nach Problem kann es aber auch mehrere Basisfälle geben.

== Quicksort ==
=== Verfahren ===
Quicksort (schnelles Sortieren) wurde 1962 von dem britischen Informatiker [http://de.wikipedia.org/wiki/Tony_Hoare Charles Anthony Richard Hoare] (* 11. Januar 1934) entwickelt. 
Die Idee des Algorithmus besteht darin, die Gesamtliste <math> G = (a_1, a_2, ...,a_n) </math> in eine linke und eine rechte Teilliste zu zerlegen, so dass alle Elemente von <math>L </math> kleiner und von <math>R</math> größer sind als das Vergleichsobjekt <math> v  \in G </math>. 

Wir vereinbaren, dass die Elemente von <math> G </math> paarweise verschieden sind, also für alle <math> i \not = j</math> gilt <math> a_i \not = a_j</math>.  Diese Einschränkung ist nicht notwendig, aber sinnvoll, da es sich um Schlüssel zur Identifikation von Datensätzen handelt. Wir verabreden des Weiteren, dass es sich um natürliche Zahlen handelt.
Zusätzlich legen wir fest, dass wir das am weitesten links stehende Element aus <math> G </math> als Vergleichselement <math> v </math> verwenden, also <math> v = a_1 </math>. Die Listen <math> L_{sortiert} </math>, <math> v </math> und <math> R_{sortiert} </math> bilden die sortierte Gesamtliste <math> G_{sortiert} </math> genau in dieser genannten Reihenfolge. Aus Effizienzgründen werden die Teillisten mit Quicksort sortiert. 

Es gibt zwei Basisfälle: <math> G </math> ist leer oder besteht aus nur einem Element, dann ist <math> G = G_{sortiert} </math>. Wenn man <math> G </math> in die Teillisten <math> L </math> und <math> R </math> zerlegt, entstehen durch die Entnahme von <math> v </math> Listen, die mindestens ein Element weniger enthalten als <math> G </math>. Somit wird nach endlich vielen Zerlegungen einer der Elementarfälle erreicht.


<center>
[[File:QuickSort.png|QuickSort]] 
</center>



=== Funktionsorientierte Beschreibung ===


==== traditionelles Quicksort ====

Bestimmen des Vergleichselements, das erste Element der ungeordneten Liste

<code id="4db7e59001e72">

(define vergleichselement 
  (lambda (ls)
    (if (null? ls)
        ('())
        (car ls))))

</code>

Erzeugen der linken Teilliste

<code id="4db866e41ac90">
(define linke_liste 
  (lambda (ls v)
    (cond
      ((null? ls) '())
      ((< (car ls) v) (cons (car ls) (linke_liste (cdr ls) v)))
      (else
       (linke_liste (cdr ls) v)))))

</code>

Erzeugen der rechten Teilliste

<code id="4db866e41ad80">
(define rechte_liste 
  (lambda (ls v)
    (cond
      ((null? ls) '())
      ((= (car ls) v) (cons (car ls) (rechte_liste (cdr ls) v)))
      ((> (car ls) v) (cons (car ls) (rechte_liste (cdr ls) v)))
      (else
       (rechte_liste (cdr ls) v)))))

</code>

Prozedur in der die linke und rechte Teilliste zusammengefügt werden.
Die linke und rechte Liste werden sortiert und dann anschließend zusammengefügt. 
Das geschieht in der Form linke Liste, Vergleichselement, rechte Liste.       
<code id="4db866e41aee9">
(define trad_quick
  (lambda (ls)
    (cond
      ((null? ls) '())
      (else
      (append (trad_quick (linke_liste (cdr ls) (vergleichselement ls))) (list (vergleichselement ls))  
 (trad_quick (rechte_liste (cdr ls) (vergleichselement ls))))))))

</code>
<run id="4db7e5cb8e762"> (trad_quick '(46 21834 3 678 46 54678 36 615 93 23049))</run>

==== Multiple-Value-Quicksort ====

<code id="4db283168df28">
(define teillisten
  (lambda (ls v)
    (if (null? ls)
        (values '() '())
        (call-with-values
         (lambda () (teillisten (cdr ls) v))
         (lambda (links rechts)
           (let ((x (car ls)))
             (if(< x v)
                (values (cons x links) rechts)
                (values links ( cons x rechts)))))))))
</code>

<run id="4db5ac985af6c">
(teillisten '(1 2 3 4 5 6 7 8 9) 5)
</run>

<code id="4db5ac985ae6e">
(define my-quicksort
  (lambda (ls)
    (if (null? ls)
        '()
        (call-with-values
         (lambda () (teillisten (cdr ls) (car ls)))
         (lambda (links rechts)
           (append (my-quicksort links) (list (car ls)) (my-quicksort rechts)))))))
</code>

<run id="4db5ac985aff7">
(my-quicksort '(5 6 7 -2 0 11 6 5 4 3 2 21 3 4 5 6 7 8 45))
</run>

=== Effizienzbetrachtung von Quicksort ===
==== Best Case ====
Am Besten arbeitet Quicksort, wenn die Teillisten ungefähr gleich groß sind. Es ergibt sich die Lösung von


<center><math>
\begin{array}{ccl}
T\left(0\right)  & = & 0 \\\\
T\left(n\right) & = &  2 \cdot T \left(\frac{n}{2} \right) + c \cdot n\\
\end{array}
</math>
</center>


einem Aufwand <math> T\left( n\right) = \mathcal{O} \left( n \log_2  n \right) </math>. Zur Lösung der Rekursionsgleichung haben wir die Meistermethode verwendet. Die in der allgemeinen Form 

<center>
<math> 
T\left( n \right) = a \cdot T \left(\frac{n}{c} \right) + f\left( n \right) 
</math>
</center>

vorkommenden Variablen enthalten für Teile- und Herrsche-Verfahren besondere Bedeutung. Die Variable <math> a </math> steht für die Anzahl der Teilprobleme und <math>\frac{n}{c} </math> für die Größe eines Teilproblems, wobei die Zerlegung immer aufgehen sollte.

====Worst Case ====
Den Worst Case des Verfahrens kennzeichnet eine vollständig sortierte Liste. 

Eigentlich wäre der Sortieraufwand somit gleich null, da das Ergebnis bereits vorliegt. 
Die Rekursionsgleichung für <math>T(n) </math>


<center><math>
\begin{array}{ccl}
T(0) &=& 0\\
T(n) &=& \underbrace {T(0)}_{0} + T(n-1) + c n
\end{array}
</math>
</center>

Mit der Iterationsmethode kann die Gleichung leicht gelöst werden.

<center><math>
\begin{array}{ccl}
T(n-1)  &=& T(n-2) + c(n-1)\\\\
T(n-2) &=& T(n-3) + c(n-2)\\\\
\vdots &   & \vdots\\\\
T(n-k) &=& T(0) +c(n-k)\\\\
\end{array}
</math>
</center>
Das in die Summenschreibweise übertragen

<center><math>
\begin{array}{ccl}
T(n) &=& c \cdot  \sum\limits_{k=0}^{n-1} (n-k)\\\\
&=& c\cdot\sum\limits_{k=0}^{n-1} n - \sum\limits_{k=0}^{n-1} k\\\\
&=& c\cdot(n^2 - \frac {n+(n-1)^2-1}{2})\\\\
&=& c\cdot(n^2 - \frac {n+(n^2 -2n +1)-1}{2})\\\\
&=& c\cdot(n^2 - \frac {n^2 -n}{2})\\\\
&=& c\cdot(\frac {n^2} {2} + \frac {n} {2})
\\\\\\
T(n) &=& \mathcal{O}(n^2)\\\\
\end{array}
</math>
</center>

====Average Case ====
Gehen wir davon aus, dass jede der <math> n </math> Teillistenlängen mit der gleichen Wahrscheinlichkeit von <math> \frac {1} {n} </math> auftritt, dann sprechen wir von dem Average Case.

Dann gilt

<center><math>
\begin{array}{ccl}
T(i) =  T(n-i-1) = \frac {1}{n} \cdot \sum\limits_{j=0}^{n-1} T(j)\\\\
\underbrace{T(i)}_{linke\ Teilliste} + \underbrace{T(n-i-1)}_{rechte\ Teilliste} + \underbrace{c \cdot n}_{Teillistenbildung}\\\\

\end{array}
</math>
</center>

Setzt man dies ein, so ergibt das

<center><math>
\begin{array}{ccl}
T(n) = \frac {2}{n} \sum\limits_{j=0}^{n-1} T(j) + c \cdot n\\\\
\end{array}
</math>
</center>

Jetzt wollen wir das Summenzeichen beseitigen, indem wir die Differenz bilden

<center><math>
\begin{array}{ccl}
nT(n) &=& 2 \sum\limits_{j=0}^{n-1} T(j) + c \cdot n \\\\
(n-1)T(n-1) &=& 2 \sum\limits_{j=0}^{n-2} T(j) + c \cdot (n-1)^2 \\\\
\\\\

nT(n) - (n-1)T(n-1) &=& 2T(n-1) + 2cn - c \mid -c\ \text{entfaellt fuer}\ n \rightarrow \infty\\\\
\frac{T(n)}{n+1} &=& \frac{T(n-1)}{n} + \frac{2c}{n+1}\\\\
\frac {T(n-1)}{n} &=& \frac{T(n-2)}{n-1} + \frac{2c}{n}\\\\
\vdots &   & \vdots\\\\
\frac{T(2)}{3} &=& \frac{T(1)}{2} + \frac{2c}{3}\\\\
\\\\
\frac{T(n)}{n+1} &=& \underbrace{\frac{T(1)}{2}}_{=0, da\ T(1) =0} + 2 \sum\limits_{i=3}^{n+1} \frac{1}{i}\\\\
\end{array}
</math>
</center>
Mit den Harmonischen Zahlen <math> H(n) = \sum\limit_{k=1}^{n} \frac{1}{k} </math> und deren bekannten Schranken <math> \frac {\lfloor log_{2} n \rfloor +1}{2} < H_{n} < \lfloor log_{2} n \rfloor +1 </math> ergibt sich dann

<center>
<math>
\frac {T(n)}{n+1} = \Omicron (log_{2} n)\curvearrowright T(n) = \Omicron (n \cdot log_{2} n)
</math>
</center>

== Interne Suchverfahren ==
darauf wird an dieser Stelle nicht eingegangen.

== Mergesort ==
=== Verfahren ===
Quicksort und Mergesort sind eng verwandt. Merge bedeutet soviel wie "zusammenführen" oder "einfädeln", ähnlich wie es im Straßenverkehr geschieht, wenn zwei Fahrspuren zusammengeführt werden. Die Übersetzung "Sortieren durch Mischen" trifft nicht zu. 
Die zu sortierende Gesamtliste 


<center><math>
G = \left(l_1, l_2,... , l_n, r_1,r_2,..., r_m \right)
</math></center>


wird zunächst mit <math> n = \left| G \right | \div 2 = m\div2 </math>  in zwei etwa gleich große Teillisten geteilt.


<center><math>
L = \left( l_1, l_2,... , l_n \right) \text{ und } R = \left( r_1,r_2,..., r_m \right)
</math> </center>


Es erfolgen im Gegensatz zu Quicksort also keine Vorsortierungen oder Vergleiche.  <math> \div </math> steht für die ganzzahlige Division, sodass entweder <math> m = 2n </math> oder <math> m = 2n + 1 </math> gilt. 
Im Conquer-Schritt sollen <math> L </math> und <math> R </math> rekursiv durch Mergesort sortiert werden. Es gelten die gleichen Elementarfälle wie bei Quicksort. Die dadurch entstandenen sortierten Teillisten werden nach dem Reißverschlussprinzip zusammengeführt.
Die jeweils ersten Elemente der Teillisten werden miteinander verglichen. Ist <math> l_i < r_j </math> so wird <math> l_i </math> an die nächste Stelle der neuen Gesamtliste gestellt. Ansonsten rutscht <math> r_j </math> nach,  während <math> l_i </math> noch einmal mit dem nächsten Element von <math> r </math> also <math> r_{j+1} </math> verglichen wird. Das jeweils kleinere Element wird an das vorhergehende "aussortierte" hinten angestellt.

==== Datenfluss bei Mergesort ====
<center>
[[Bild:S3romuel_Mergesort_algorithm_diagram.png]]
</center>

=== Funktionsorientierte Beschreibung ===
<code id="4db7f11f32df1">
(define mergesort
  (lambda (ls)
    (if(or (null? ls)(null? (cdr ls)))
       ls
       (call-with-values
        (lambda() (teillisten2 ls))
       (lambda (ls1 ls2)
         (verbinden
          (mergesort ls1)
          (mergesort ls2)))))))
</code>

Die folgende Funktion teillisten2 ist der Prozedur teillisten aus Quicksort nachempfunden. Sie teilt die als Parameter übergebene Liste in der Mitte und erhält so 2 Teillisten, die gleich groß sind, bzw. bei einer ungeraden Anzahl an Elementen der Ausgangsliste, die linke Liste um 1 kleiner ist als die Rechte. Aufgrund von floor() funktioniert das, welches nur die Ganzzahl zurückgibt.

<code id="4db7f9e8c21b9">
(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>

Die Prozedur führt jetzt beide sortierten Teillisten zusammen und bildet daraus die gesamte sortierte Liste.

<code id="4db866e41b004">
(define verbinden
  (lambda (lls rls)
    (cond
      ((null? lls) rls)
      ((null? rls) lls)
      (else
       (let (( x (car lls)) ( y (car rls)))
         (if (< x y)
             (cons x (verbinden (cdr lls) rls))
             (cons y (verbinden lls (cdr rls)))))))))
</code>
<run id="4db7f11f32e5d">(mergesort '(9 2 7 12 8 24 78 3 77 1))</run>

=== Effizienzbetrachtung von Mergesort ===
Da Mergesort jede Liste, ob sortiert oder unsortiert, halbiert und abarbeitet, ist die Effizienz von Mergesort im best, worst und average case immer gleich. 
Es ergeben sich folgende Aufwandsbeziehungen


<center><math>
\begin{array}{ccl}
T\left(0\right) & = & 0 \\\\
T\left(1\right) & = & 0 \\\\
T\left(n\right) & = & 2 \cdot T \left( \frac{n}{2}\right) + \Theta\left(n\right)
\end{array}
</math></center>

Wir nehmen vereinfachend an, dass die Anzahl der Elemente <math>n</math> eine Zweierpotenz ist. 
Durch Anwendung des zweiten Falles der Meistermethode ergibt sich folgende Lösung.

<center><math>
\begin{array}{ccl}
f\left(n\right) & = & n^{log_2{2}}\\\\
f\left(n\right) & = & n^1\\\\
f\left(n\right) & = & n\\\\
T\left(n\right) & = & \Theta\left(n\  log_2\ n\right)\\\\

\end{array}
</math></center>

== Binäres Suchen ==
=== Das Verfahren ===
Neben dem Sortieren von Schlüsseln ist das effiziente Suchen von großer Bedeutung, insbesondere für das Gebiet ''information retrieval'' ("Wiederauffinden/ Wiedergewinnung von Informationen"). Praktische Anwendungsgebiete für die binäre Suche sind Auskunftssysteme aller Art, wie zum Beispiel das Telefonbuch. Eine ineffiziente Suche kann viel Ressourcen in Anspruch nehmen. Um das aufwändige Umspeichern von Daten zu vermeiden verwendet man eine Indexliste und Schlüssel, zur Identifizierung von Datensätzen. 
Die Suche von <math> x </math> in einer aufsteigend sortierten Gesamtliste

<center><math>
G = \left( a_1,a_2,..., a_k, a_{k+1},...,a_n \right)
</math></center>

erfolgt durch die Suche in den beiden Teillisten <math> L = \left(  a_1,a_2,..., a_k \right)</math> und <math>R = (a_{k+1}, a_{k+2},..., a_n \right)</math>. Der Divide-Prozess der Zerlegung erfolgt mit <math>k = n\div2 </math>. Wir gehen vereinfachend davon aus, dass <math> n </math> eine Zweierpotenz ist. In der Implementation wird <math>k = \lfloor \frac{n}{2} \rfloor </math> verwendet.


Bei der Suche wird <math>x </math> immer mit dem ersten Element <math> a_{k+1</math> aus der rechten Teilliste <math> R </math> verglichen. Ist <math> x = a_{k+1} </math> ist die Suche bereits beendet. Ist <math> x<a_{k+1} </math> wird die Suche in der linken Teilliste <math> L </math>, ist <math> x> a_{k+1} </math> in der rechten Teilliste <math>R </math> fortgesetzt. Die Fortsetzung der Suche erfolgt jedoch nur, wenn die zu durchsuchende Liste nicht leer ist.

=== Funktionsorientierte Beschreibung mit Multiple-value-context ===
<code id="4db7f48ae5d04">
(define binaersuche
  (lambda (x ls)
    (call-with-values
     (lambda () (teillisten2 ls))
     (lambda (lls rls)
       (cond
         ((null? rls) "Schluessel nicht enthalten")
         ((= x (car rls)) "Schluessel gefunden")
         ((< x (car rls))
          (if (null? lls) "Schluessel nicht enthalten"
          (binaersuche x lls)))
          (else
           (if (null? (cdr rls)) "Schluessel nicht enthalten"
               (binaersuche x rls))))))))
</code>
<run id="4db7f48ae5d80"> (binaersuche 25 (mergesort '(19 27 3 46 72 66 5 25 36 53 8)))</run>

=== Effizienzanalyse ===
Die Länge der Teillisten wird in jedem Schritt halbiert, insbesondere wenn die Anzahl <math>n</math> der Elemente von <math> G </math> eine Zweierpotenz ist. Die Anzahl der rekursiven Aufrufe entspricht der Anzahl der Halbierungsschritte, also <math> log_2 n</math> Stück. Setzt man für den in jedem Schritt stattfindenden Vergleich einen konstanten Aufwand <math> \mathcal{O}\left( c \right) </math> ein, erhält man den Gesamtaufwand

<center><math>
T\left(n\right) =  \mathcal{O}\left( log_2 \ n\right) \text{.}
</math></center>


Die trifft für alle drei Fälle zu. Der best case benötigt nur einen einzigen Vergleich und arbeitet mit konstantem Aufwand <math> T\left(n\right) = \mathcal{O}\left(c\right)</math> , unabhängig von der Anzahl <math> n</math>.


==== Vergleich zur sequenziellen Suche ====

Es ist nur schwer zu erkennen das die Binärsuche effizienter sein soll als die sequenzielle Suche von <math> x </math> in einer aufsteigend sortierten Liste <math> G </math>. 

Bei der sequenziellen Suche vergleicht man <math> x </math> mit den aus <math> G </math> stammenden Elementen, beginnend beim kleinsten. Dies wird so lange durchgeführt bis <math> x </math> gefunden wurde. Würde man den Fall <math> x \notin G </math> miteinbeziehen, so könnte die Suche im Fall das dass erste Element <math>a_{i}</math> größer ist als <math>x</math> (erfolglos) beendet werden.

Wir gehen dabei wieder von paarweise verschiedenen Listenelementen aus:

<code id="4db927be6bc49">
  (define seq-suche
  (lambda (x ls)
    (cond
      ((null? ls) "Schluessel nicht enthalten")
      ((= x (car ls)) " Schluessel gefunden.")
      ((< (car ls) x )(seq-suche x (cdr ls)))
      (else "Schluessel nicht enthalten."))))
</code>

<run id="4db927be6bde9"> (seq-suche 5 '(1 2 3 4 5 6 7 8 9 0))</run>

Im Falle dass <math> x = a_{i} </math> gilt <math> T(n) = \Omicron(1) </math>. Das wäre ohne Frage der Best-Case. Im Worst- sowie im Average-Case werden <math>n</math> Durchläufe nötig womit <math>  T(n) = \mathcal{O}(n) </math> gilt. 
Sollte jedes Element aus <math>G</math> mit gleicher Wahrscheinlichkeit mit <math>x</math> übereinstimmen so könnte man den Aufwand wie folgt beschrieben

<center>
<math>
\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}
</math>
</center>

Damit ist klar das man der der sequenziellen Suche die Binärsuche vorzieht.

== Multiplikation großer ganzer Zahlen ==
Die Multiplikation großer ganzer Zahlen ist ein Verfahren welches 1960 von Karatsuba und Ofman entwickelt wurde. Sie ist eine typisches Teile-und-Herrsche-Verfahren. Die Idee die sich dahinter verbirgt, ist die Verringerung des Rechenaufwandes im Vergleich zu der Schulmethode die mit einem quadratischen Aufwand arbeitet. Hierzu werden einige Multiplikationsvorgänge, die mit einem quadratischen Aufwand arbeiten durch Additionsverfahren und Verschiebungen, die linear arbeiten, ersetzt. 

Wir verabreden zunächst, dass <math> x </math> und <math> y </math> die gleiche Stelligkeit <math> n </math> haben und <math> n </math> eine gerade Zahl ist. Wir halbieren die beiden zu multiplizierenden Zahlen in einen High-Teil <math> x_1 </math> und <math> y_1 </math>  und einen Low-Teil <math> x_0 </math> und <math> y_0 </math>. Es gilt somit 

<center><math>
\begin{array}{ccl}
x & = & x_1 b^{\frac{n}{2}} + x_0\\\\
y & = & y_1 b^{\frac{n}{2}} + y_0\\\\
\end{array}
</math></center>


<math> b</math> ist die Basis der Zahlendarstellung, z.B. <math> b \ = \ 10 </math>. Die beiden High- und Low-Teile sind infolge der Halbierung gleich lang.  
Die Lösung der Multiplikation erfolgt mit 


<center><math>
x \cdot y = \left( x_1 \cdot y_1\right) b^n + \left( x_0 \cdot y_1  +  y_0 \cdot x_1\left) b^{\frac{n}{2}} + x_0 \cdot y_0
</math></center>


Auf diese Art und Weise entsteht die Multiplikation zweier <math>n</math>-stellige Zahlen durch 4 gleichartige Multiplikationen zweier <math>\frac{n}{2}</math>-stelliger Zahlen und drei Additionen maximal <math>n</math>-stelliger Zahlen. Der Aufwand der Addition beträgt <math> \Theta \left(n\right)</math>. Das ergibt einen Gesamtaufwand von


<center><math>
T\left(n\right) = 4 \cdot T \left( \frac{n}{2}\right) + \Theta\left( n\right) \text{.}
</math></center>


Die Anwendung der Meistermethode ergibt:


<center><math>
\begin{array}{ccl}
T\left(n\right) & = & \mathcal{O}\left( n^{log_2 4}}\right) \\\\
                          & = & \mathcal{O}\left(n^2\right)
\end{array}
</math></center>


Im Vergleich zur Schulmethode ist das keine Verbesserung, da beide Verfahren mit quadratischem Aufwand arbeiten. Um eine  Verbesserung zu erzielen ist die Umformung von <math> x_0 \cdot y_1  +  y_0 \cdot x_1</math> erforderlich. 


<center><math> 
x_0 \cdot y_1  +  y_0 \cdot x_1 = x_1 \cdot y_1 + x_0 \cdot y_0 - \left( x_0-x_1\right) \cdot  \left( y_0 - y_1\right)
</math></center>


Diese Umformung setzen wir in unsere Gleichung wieder ein. Es entsteht somit:


<center><math>
 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^{\frac{n}{2}} + x_0 \cdot y_0
</math></center>


In diesem Ausdruck kommen zwei Produkte doppelt vor. Diese werden mit einem Aufwand von <math> T\left(\frac{n}{2}}\right) </math> einmal berechnet und anschließend an die betreffenden Stellen nur noch eingesetzt. 


<center><math>
\begin{array}{ccl}
p & = & x_0 \cdot y_0\\\\
q & = & x_1 \cdot y_1\\\\
\\\\
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
\end{array}
</math></center>


Zu den beiden Multiplikationen von <math> p </math> und <math> q </math> kommt noch die Multiplikation von <math>\left( x_0-x_1\right) \cdot \left(y_0 - y_1  \right) </math>,  zwei je <math> \frac{n}{2} </math>-stelligen Zahlen sowie deren Addition (in <math>\Theta\left(n\right) </math>) hinzu.
Es ergibt sich somit ein Gesamtaufwand von 


<center><math>
T\left(n\right) = 3 \cdot T \left( \frac{n}{2}\right) + \Theta\left( n\right) \text{.}
</math></center>


Die Anwendung der Meistermethode ergibt


<center><math>
\begin{array}{ccl}
T\left( n\right) & =  & \mathcal{O}\left( n^{log_2 3}\right)\\\\
                           & \approx & \mathcal{O}\left( n^{1.585}\right)
\end{array}
</math></center>


Die Multiplikation zweier <math> 10^6 </math>-stelliger Zahlen nach dieser Methode dauert somit ca. 5.2 Minuten (Nebenrechnung: <math> (10^6)^{1.582} / 10^7 / 60  = 5.2</math>). Die gleiche Berechnung nach der Schulmethode dauert mehr als 1 Tag und 3 Stunden. (Nebenrechnung: <math> (10^6)^{2} / 10^7 / 60   \approx 1666.667 \ / 60 \approx 27.778 </math>)

=== Ein kleines Beispiel ===
Wir wollen uns die Multiplikation großer ganzer Zahlen einmal am Beispiel anschauen. 
Wir multiplizieren die Zahlen <math> 123\ 456\ 789\ 123</math> und <math> 246\ 812\ 357\ 432</math>. Beide Zahlen sind 12-stellig. <math> n </math> ist somit <math> 12 </math>. Unsere Basis <math> b = 10 </math> 


<center><math>
\begin{array}{ccl}
x & = & \underbrace{123\ 456}_{\text{\ High-Teil}}\ \underbrace{789\ 123}_{\text{\ Low-Teil}}\\\\
y & = & \underbrace{246\ 812}_{\text{\ High-Teil}}\ \underbrace{357\ 432}_{\text{\ Low-Teil}}\\\\\\\\
x_0 & = & 789\ 123\\\\
x_1 & = & 123\ 456\\\\
y_0 & = & 357\ 432\\\\
y_1 & = &  246\ 812\\\\\\\\
x & = & x_1 b^{\frac{n}{2}} + x_0\\\\
  & = & 123\ 456 \cdot 10^6} + 789\ 123\\\\ 
y & = & y_1 b^{\frac{n}{2}} + y_0\\\\
      & = & 246\ 812 \cdot 10^6 + 357\ 432\\\\\\\\
p & = & x_0 \cdot y_0\\\\
  & = & 789\ 123 \cdot 357\ 432 \\\\
  & = & 282\ 057\ 812\ 136\\\\
q & = & x_1 \cdot y_1\\\\
 & = & 123\ 456 \cdot 246\ 812 \\\\
 & = & 30\ 470\ 422\ 272\\\\\\\\\
\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = & \left( 789\ 123 - 123\ 456\right) \cdot \left( 357\ 432 - 246\ 812\right)\\\\
\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = & 665\ 667 \cdot 110\ 620\\\\
\left( x_0 - x_1\right)\cdot \left( y_0 - y_1\right) & = & 73\ 636\ 083\ 540\\\\\\\\
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 & = & 30\ 470\ 422\ 272 \cdot 10^{12} + \left( 30\ 470\ 422\ 272 + 282\ 057\ 812\ 136 - 73\ 636\ 083\ 540\right)\cdot 10^6 + 282\ 057\ 812\ 136\\\\
x \cdot y & = & 30\ 470\ 422\ 272 \cdot 10^{12} + 238\ 892\ 150\ 868 \cdot 10^6 + 282\ 057\ 812\ 136\\\\
x \cdot y & = & 30\ 470\ 661\ 164\ 432\ 925\ 812\ 136\\\\\\\\
\end{array}
</math></center>

== Quellenverzeichnis ==
*[http://de.wikipedia.org/wiki/Divide_et_impera Wikipedia - Divide et Impera]
*[http://de.wikipedia.org/wiki/Karatsuba-Algorithmus Wikipedia- Karatsuba-Algorithmus]

* Christian Wagenknecht: ''Algorithmen und Komplexität'', Fachbuchverlag Leipzig, 2003, 
* Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: ''Algorithmen - Eine Einführung'', Oldenbourg Verlag München Wien, 2. Auflage, 2007