Teile und Herrsche 2 SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-04-05T18:17:45+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Zusammenfassung
2 Binäre Suche
3 die Multiplikation nach Karatsuba und Offman
4 die schnelle Matrix Multiplikation
- 4.1 praktische Probleme

Diese Seite stellt eine inhaltliche Fortsetzung des Themas Teile und Herrsche 1 dar.

Wichtig! Die Seite ist noch NICHT FINAL es können sich noch Fehler und unsauberkeiten finden lassen, erst wenn dieser Text
hier nicht mehr zu lesen ist, wird die Seite von Uns als fertig betrachtet!

Zusammenfassung

Auf dieser Seite soll versucht werden, die Algorithmen Binäre Suche, Strassens-Matrix-Multiplikation und den Multiplikations Algorithmus von Karatsuba in Hinblick auf die Arbeitsweisen und den Aufwand (Effiziensanalyse) der einzelnen Verfahren vorzustellen. Dabei findet ihr verschiedene Implementierungen der Algorithmen in Java und Scheme.

Die Übungsaufgaben zu diesen Themen findet ihr hier Aufgaben - TuH2. Ihr findet aber auch im Text Hinweise und Hilfestellungen zu etwaigen Problemen auf die man während der Bearbeitung stoßen könnte.

Binäre Suche

Wie funktionierts?

Jeder war bestimmt schon einmal in einer Situation, in der man aus einer großen Menge von Informationen eine Bestimmte wiederfinden musste. Als Beispiel dient das Suchen einer Seite anhand Ihrer Seitenzahl in dicken Büchern. Man schaut in das Inhaltsverzeichnis und erhält die Seitenzahl der gesuchten Information. Nun schlägt man das Buch in der Mitte auf und schaut ob die Seiteanzahl der Seite, auf der wir uns nun befinden, größer oder kleiner ist, als die Seitenzahl unserer gesuchten Seite. Abhängig vom Ergebnis nehmen wir die vordere oder hintere Hälfte des Buches und schlagen von dieser die Hälfte auf und vergleichen wieder... das wiederholen wir solange bis unsere gesuchte Seite auftaucht.

Der Trick besteht also darin, den Suchraum stets zu halbieren und festzustellen, in welcher Hälfte unsere gesuchte Information wohl zu finden ist. Diese Hälfte wird dann wieder halbiert und es wird wieder verglichen und so weiter... . Um nun auf einen konkreten Algorithmus und dessen Effizienzanalyse hinzuarbeiten, reduzieren wir das Problem auf eine aufsteigend sortierte Liste mit Integerzahlen.

Also nun zu unserer Liste:

$$L= \{ e_{1}, e_{2}, ... , e_{n} \}$$

Wie erwähnt, muss die Liste bereits zu begin geteilt werden, dies geschieht beim Element mit dem Index k, die Mitte der Liste ist also k = \frac{n}{2}. Wobei man ja davon ausgehen kann, das die Liste nicht zwangsläufig ungerad zahlig viele Elemente besitzt, sodass man ein Element in der Mitte ausmachen kann. Also müssen wir unser k folgendermassen korrigieren k = \lfloor\frac{n}{2}\rfloor somit nehmen wir bei der Division den ganzzahligen Wert, nach unten gerundet.

Nun haben wir eine linke Teilliste L_{l}=\{a_{1}, a_{2}, ... a_{k}\} und eine rechte Teilliste L_{r}=\{a_{k+1}, a_{k+2}, ... a_{n}\} oder anders dargestellt:

L = \underbrace{a_{1}, a_{2}, ... a_{k}}_{L_{\text{l}}}, \underbrace{a_{k+1}, a_{k+2}, ... a_{n}}_{L_{\text{r}}}

Jetzt wird unser Zielwert x mit dem ersten Element der rechten Liste x < a_{k+1} verglichen, abhängig vom Ergebnis wird mit L_{r} oder L_{l} weiter gearbeitet bzw. das Element ausgegeben. Natürlich kann bereits zu Begin der Elementarfall eintreten das a_{k} = x ist.

Fassen wir es noch einmal zusammen:

BinSuch = \left\{% \begin{array}{ll} BinSuch(L_{\text{l}}) &\textrm{wenn }x<a_{k},\\ BinSuch(L_{\text{r}}) &\textrm{wenn }x>a_{k},\\ print(a_{k}) &\textrm{wenn } x = a_{k}, \\ \textrm{"nicht Enthalten"} &\textrm{sonst }} \end{array}% \right

Vergleich mit der herkömlichen sequenziellen Suche

Betrachten wir nun noch die einfachste Art des Suchens. Man nimmt eine Liste L mit der Länge n, ein gesuchtes Element x und beginnt dieses mit jedem Element der Liste zu vergleichen. Dieses Verfahren besitzt linearen Aufwand. Wobei davon auszugehen ist, das die Wahrscheinlichkeit, das x mit dem Element a aus L übereinstimmt für jedes Element gleich ist.

Wie sieht der Algorithmus aus?

Im folgenden wird der Algorithmus, im Code als BinSuch betitelt, in Scheme und Java gezeigt. Man kann den Algorithmus in iterativer und rekursiver Form angeben.

Java - iterativ

// Eine Hilfe um mal schnell ein Array beliebiger Länge, zu füllen
int[] erzeugeFeld(int length) {
	int[] field = new int[length];
	for (int i = 0; i < field.length; i++) {
		field[i] = i;
	}
	return field;
}

// die Sequenzielle Suche für den Vergleich
int sequenzSuch(int[] field, int x){
		int element= -1;
		
		for(int i = 0; i < field.length; i++){
			if(field[i] == x) 
				element = i;
		}
		return element;
		
	}


// Die eigentliche Such Methode, diese Liefert die Position an der das Element zu finden ist,
// das Ergebnis -1 signalisiert das das Element nicht enthalten ist!
int binSuch(int[] field, int x){
		int start = 0;
		int ende = field.length-1;
		int mitte = (start + ende)/2;
		
		while(start <= ende && field[mitte] != x){
			if(field[mitte] < x){
				start = mitte + 1;
			}else ende = mitte - 1;
			mitte = (ende + start)/2;
		} 
		
		if(start > ende){
			return -1;
		}else return mitte;
		
	}

<eval> System.out.println("An welcher Stelle ist das Element zu finden? Position:" + binSuch(erzeugeFeld(10), 3)); </eval>

Java - rekursiv

Coming soon...

Scheme - rekursiv

;zzls für ZufallsZahlenListe. Generiert eine Liste mit n paarweise verschiedenen Ganzen Zahlen zwischen a und b.
;Beispielaufruf: 
;>(zzls 10 100 1000) ; Zufallszahlenliste mit 1000 Zufallszahlen zwischen 10 und 100

(define zzls
  (lambda (a b n)
    (if (= n 0)
        (list)
        (let ((x (random b)))
          (if (> x a)
              (append (list x)(zzls a b (- n 1)))
              (zzls a b n))))))

Komplexitätsverhalten

Best Case

Es liegt nahe dass es sich bei beiden Suchalgorithmen im besten Fall um einen konstanten Aufwand \mathcal{O}(1) handelt. Beim sequenziellen Suchen finden wir das Element am Anfang der zu durchsuchenden Liste und bei der binären Suche in der Mitte der Liste.

Diese Erkenntnis ist für die Praxis eher irrelevant von daher sollte man sich das Verhalten im Average- und Worst Case genauer betrachten.

Average Case & Worst Case

Wir wollen in diesem Abschnitt die Binäre Suche in der iterativen als auch rekursiven Variante Untersuchen.

Bei der sequenziellen Suche fällt bereits durch scharfes Hinsehen auf, das es sich um linearen Aufwand handelt, egal ob im Durchschnitt oder schlechtestem Fall. Den die Laufzeit hängt von der Länge n der Liste ab. Also \mathcal{O}(n).

Betrachten wir die Größe des Intervalls welches wir mit dem binären Verfahren untersuchen wollen, zu beginn enthält unser Intervall n Elemente. Unsere Variablen für die Positionen im zu durchsuchenden Feld verantwortlich sind haben folgende Belegungen:

\begin{array}{lcl} \text{Feldleange zu Begin} & = & \text{start} + \text{Ende} \\ \text{Feldleange nach 1. Vergleich} & = & \text{Ende} - \text{Mitte} + 1 \end{array}

die Multiplikation nach Karatsuba und Offman

Wir kennen die Multiplikation aus der Schule und haben die sog. Russische Bauernmultiplikation (Multiplikation à la Russe) kennengelernt. Infolge dessen, wollen wir hier noch ein anderes Multiplikationsverfahren analysieren. Zunächst ist die Frage interessant warum man überhaupt noch einen Multipliaktionsalgorithmus benötigt, wir haben ja alle in der Schule eine ganz brauchbare Lösung kennengelernt. Doch leider hat dieser Quadratischen Aufwand sprich \mathcal{O}(n^2). Das heißt konkret das wir für die Multiplikation von sehr sehr großen Zahlen Unmengen von Operationen benötigen. Wir gehen an dieser Stelle nicht weiter darauf ein in der Übung könnt ihr mit der Analyse der Schulbuchmultiplikation auseinander setzen.

Wie funktionierts?

Wir nehmen 2 Zahlen a und b, wir vereinbaren das deren Stelligkeit n gleich und gerade ist. Dann zerlegen wir diese beiden Zahlen in jeweils 2 gleiche Teile. Im einfachsten Fall n = 1 haben entsprechend nur eine Operation nämlich a \cdot b. Betrachten wir n = 2, als Beispiel dienten uns die Zahlen 14 und 73. Die beiden Faktoren werden wie folgt zerlegt,

x = x_{1} \cdot B + x_{0}

Wobei B für die Basis der Zahlendarstellung steht. In unserm Fall 10.

a = 14 =1 \cdot 10 + 4 b = 73 = 7 \cdot 10 + 3

Im nächsten Schritt schau wir uns an wie die Multiplikation von a und b mit Hilfe der Ziffern aussieht.

\begin{array}{ccl} a \cdot b & = & (a_{1} \cdot 10 + a_{0}) \cdot (b_{1} \cdot 10 + b_{0}) \\ & = & (a_{1} \cdot b_{1}) \cdot 100 + (a_{1} \cdot b_{0} + a_{0} \cdot b_{1}) \cdot 10 + a_{0} \cdot b_{0}\\ & = & (1 \cdot 7) \cdot 100 + (1 \cdot 3 + 4 \cdot 7) \cdot 10 + 4 \cdot 3 \\ & = & 1022 \end{array}

Ruft man sich das Verfahren ins Gedächtnis, welches wir einmal in der Schule gelernt haben, stellen wir schnell fest das uns unser neuer Algorithmus kein besseres Verfahren liefert.

Wir haben nach wie vor lediglich 4 Multiplikationen und die Addition der Ergebnisse. Die Trick den Karatsuba entdeckt hat sieht wie folgt aus, er nutzt lediglich 3 Multiplikationen um folgende Werte zu berechnen,

An dieser Stelle wird auch die Absicht deutlich die Karatsuba verfolgt!
Die aufwendigeren Multiplikations Operationen in weniger Aufwendige Additions bzw. Subtraktions-
Operationen aufzuspalten. Dies ist aber noch nicht alles was den Algorithmus so beschleunigt!

\begin{array}{ccl} m & = & a_{1} \cdot b_{1}\\ n & = & (a_{0} - a_{1}) \cdot (b_{0} - b_{1}) \\ o & = & a_{0} \cdot b_{0} \end{array}

Zusätzliche Betrachtung

Nehmen wir uns die Aufwände der eben genannten Multiplikationsverfahren noch einmal zu Brust um zu sehen wie diese sich verhalten.

Aufwand für die Schulbuchmultiplikation = \mathcal{O}(n^2)
Aufwand für Multiplikation à la Russe = \mathcal{O}(n^2)
Aufwand für Karatsubas Algorithmus \Theta(n^{1,585})

Wie kann man Karatsubas Idee Programmieren?

die schnelle Matrix Multiplikation

Auch Strassens Algorithmus zur Matrixmultiplikation genannt, bietet eine Alternative zur herkömlichen Matrixmultiplikation.

praktische Probleme

testest