nach Tim Roughgarden: Algorithms Illuminated (und T. Corman et al. Algorithms)
"I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships."
— Linus Torvalds (creator of Linux)
Eine wohldefinierte Prozedur, die eine Eingabe (Input) entgegen nimmt und daraus eine gewünschte Ausgabe (output) berechnet.
Beispiel:
Problem: Integer Multiplication
- Eingabe(Input): Zwei ganze Zahlen $x$ und $y$. Beide haben Länge $n$.
- Ausgabe(Output): Eine ganze Zahl $z = x\cdot y$ (Produkt der beiden Eingabewerte)
Analyse für die Performanz eines Algorithmus:
Wieviele primitive Operationen benötigt ein Algorithmus in Abhängigkeit von der Größe des Inputs ?
Beispiel: $x=5678$ und $y=1234$
5678
x 1234
--------
22712
17034
11356
5678
--------
7006652
Beachte:
Wieviele primitive Operationen erfordert der Algorithmus
in Abängigkeit von $n$?
$n$ ist hier die Länge der Zahlen.
$\text{Gesamtzahl der Operationen} \leq \text{Konstante} \cdot n^2$
hier: $\text{Konstante}=4$
"Perhaps the most important principle for
the good algorithm designer is to refuse to be content."
Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms, 1974
Können wir es besser machen?
Teile $x$ und $y$ in zwei Hälften: mit $x=5678$ und $y=1234$
$\rightarrow$ Verschiedene Algorithmen führen zum gleichen Ergebnis.
Teile die Inputs (Annahme: gerades $n$) in zwei Hälften:
$x = 10^{n/2} a+ b$
bzw.
$y = 10^{n/2} c+ d$
Die Multiplikationen $a \cdot c$, $a \cdot d$, $b \cdot c$ und $b \cdot d$ entsprechen bei der Rekursion dann den neuen $x$ und $y$.
Annahme: $n$ ist eine Potenz von $2$.
Ein einfacher "Hack", falls das nicht erfüllt ist: Fülle von links mit Nullen auf.
RecIntMult
¶Input: two $n$-digit positive integers $x$ and $y$
Output: the product $x \cdot y$
Assumption: $n$ is a power of $2$
if $n = 1$ then // base case
compute $x \cdot y$ in one step and return the result
else
$a, b :=$ first and second half of $x$
$c, d :=$ first and second half of $y$
recursively compute $ac := a \cdot c, ad := a \cdot d, bc := b \cdot c$ and $bd := b \cdot d$
compute $10^n ac + 10^{n/2} \cdot (ad+bc) + bd$ using
grade-school addition and return the result
Karatsuba Multiplikation ist eine optimierte Version von RecIntMult
:
RecIntMult
werden vier Rekursionen vorgenommen.Karatsuba
werden nur nur drei Rekursionen vorgenommen.Beachte: In RecIntMult
haben wir für $(a \cdot d + b \cdot c)$ zwei Multiplikationen durchgeführt.
Mit der Identität: $$(a \cdot d + b \cdot c) = (a+b) \cdot (c+d) - a\cdot c - b \cdot d$$
Können wir dies mit nur einer weiteren Multiplikation $(a+b) \cdot (c+d)$ berechnen, da wir $a\cdot c$ und $b \cdot d$ schon berechnet haben.
Hinweis: der Aufwand für die Addition (Schulalgorithmus) ist proportional zu $n$.
Berechungsschritte:
Karatsuba
¶Input: two $n$-digit positive integers $x$ and $y$
Output: the product $x \cdot y$
Assumption: $n$ is a power of $2$
if $n = 1$ then // base case
compute $x \cdot y$ in one step and return the result
else
$a, b :=$ first and second half of $x$
$c, d :=$ first and second half of $y$
compute $p:= a + b$ and $q := c + d$ using grade-school addition
recursively compute $ac := a\cdot c, bd := b \cdot d$ and
$pq := p \cdot q$
compute $adbc : = pq - ac - bd$ using grade-school addition
compute $10^n ac + 10^{n/2} \cdot adbc + bd$ using
grade-school addition and return the result
Beachte: Ein rekursiver Aufruf weniger bei Karatsuba
im Vergleich zu RectIntMult
Noch offene Frage: Ist Karatsuba Multiplikation besser (weniger elementare Operationen)?
Wird in Kapitel 4 mit der Master-Methode beantwortet.
Mittels eines Sortiertalgorithmus wird ein ungeordnetes Array bzw. eine Liste in eine geordnete Liste mit den gleichen Elementen überführt. Dabei muss eine Ordnung auf den Elementen mittels der Operatoren $=$, <, $\leq$, $\geq$ und $>$ definiert sein.
Kanonisches Beispiel eines Sortierproblems, welches mit einem Sortierverfahren gelöst werden kann:
Eingabe (Input): Ein Array mit $n$ Zahlen in beliebiger Ordnung.
Ausgabe (Output): Ein Array mit den gleichen Zahlen sortiert aufsteigend beginnend mit dem kleinsten Element.
Überlegen Sie sich ein Verfahren (ohne Recherche!), wie man das Sortierproblem algorithmisch lösen kann. Beschreiben Sie ihren Ansatz.
aus Algorithms, Coman et al.
Der Aufwand wächst im durchschnittlichen und schlechtesten Fall bei Insertion Sort quadratisch mit der Länge des Arrays.
Geht das besser?
Im Divide and Conquer Paradigma (in der Informatik) wird ein Problem in Unterprobleme zerlegt und die Teillösungen wieder zu einer Gesamtlösung vereint. Dies wird meist rekursiv (seltener iterativ) implementiert. Die Unterprobleme sind dabei ähnlicher Struktur aber kleiner.
Divide and Conquer Algorithmen bezeichnet dabei ein Typ von Algorithmen, die diesem Prinzip folgen.
Beachte, dass ein Array mit nur einem Element sortiert ist.
Mergesort
¶Input: Array $A$ aus $n$ unterschiedlichen Ganzzahlen
Output: Array mit denselben Zahlen sortiert.
$C :=$ sortiere rekursiv die erste Hälfte von $A$
$D :=$ sortiere rekursiv die zweite Hälfte von $A$
returnMerge
$(C, D)$
Merge
¶Input: Zwei sortierte Arrays $C$ und $D$ (der Länge $l/2$)
Output: Sortiertes Array $B$ (aus den Elementen von $C$ und $D$) mit Länge $l$
$i = 1$
$j = 1$
for $k := 1$ to $l$ do
if $C[i] < D[j]$ then
$B[k] := C[i]$
$i := i + 1$
else
$B[k] := D[j]$
$j := j + 1$
return $B$
Beachten Sie, dass der Code so nicht lauffähig wäre, da Details nicht geklärt sind. So
würde einer der Indizes über das Array hinauslaufen und der Vergleich nicht mehr möglich sein.
Beim Pseudocode werden solche Details ignoriert, da hier nur das Prinzip zählt. Bei der
Implementierung müssen Sie dagegegen solche Dinge unbedingt beachten.
Außerdem können bei der Implementierung weitere Optimierungen vorgenommen werden. Was kann man z.B. machen, wenn alle Elemente eines
Arrays ($C$ oder $D$) bereits in $B$ kopiert wurden.
Bei der folgenden Analyse gehen wir (vereinfacht) davon aus, dass die Länge $n$ eine Potenz von $2$ ist. So, sind die Arrays $C$ und $D$ immer gleich lang. Beachten Sie, dass dennoch die Argumentation im Wesentichen allgemeingültig ist.
Merge
¶i := 1
und j := 1
Ein Durchlauf der Subroutine Merge
benötigt also (etwa) $4 \cdot l + 2$ Operationen.
Da wir an der Laufzeit in Abhängigkeit von der Gesamtlänge interessiert sind (siehe unten):
Mit der Ungleichung für $l\geq 1$: $$ 4l + 2 \leq 6 l $$ haben wir eine obere Grenze $6l$.
Für jeden Input (sortiere Arrays $C$ und $D$) der Subroutine
Merge
mit Gesamtlänge $l$ (Summe der Längen von $C$ und $D$), benötige die SubroutineMerge
maximal $6l$ (primitive) Operationen.
Ein Lemma ist eine Aussage, die zum Beweis eines Theorems hilft. Meist hat sie unabhängig von zugeordneten Theorem keine wesentliche Bedeutung.
Ein Theorem (oder Satz) ist eine wichtige technische Aussage / Erkenntnis (, die in der Regel dem Verständnis eines Themas dient). Hier wird unser Theorem die Laufzeit des Merge Sort Algorithmus beschreiben.
Ein Korollar ist eine Folgerung, die sich einfach (trivial) aus einer anderen Aussage ergibt.
Aussagen, die nicht so wichtig wie Theoreme sind, werden Prepositionen genannt.
Bei jedem rekursiven Schritt
Beispiel: Rekursionsbaum der Tiefe 2
png_filename = "recursion_tree.png"; plot_recursion_tree(png_filename); Image(png_filename)
Wie tief ist der Baum bei einem Input zu MergeSort
als Funktion der Länge $n$, wenn $n$ eine Potenz von 2 ist?
Für die Rekursionsstufe $j$ des Baum:
Merge
vorgenommen werden. Wie viele primitive Operationen gibt es pro Teilarray.Also: der Aufwand pro Rekursionsstufe (level) ist 6$n$ unanhängig von $j$.
Im Merge Sort-Algorithmus werden für $n\geq1$ maximal $6n\log_2 n + 6n$ primitive Operationen benötigt.
Beweis mit Hilfe der Ergebnisse von oben
$\Rightarrow$ Obere Grenze für Anzahl der Operationen für Mergesort: $(\log_2 n + 1 ) 6n = 6n\log_2 n + 6n$
$\log_2 n$ vs. $n$:
xmax = 25; xmin=2; x = np.arange(xmin, xmax, 1)
plt.plot(x,x, 'k-', label="linear")
plt.plot(x,np.log2(x), 'b-', label="$log_2$")
plt.xlim(xmin, xmax); plt.xlabel("n"); plt.ylabel("f(n)"); plt.legend();
$n \log_2 n$ vs. $n^2$:
plt.plot(x,x**2, 'k-', label="$n^2$")
plt.plot(x,x*np.log2(x), 'b-', label="$n log_2 n $")
plt.xlim(xmin, xmax); plt.xlabel("n"); plt.ylabel("f(n)"); plt.legend();
Wir sind nicht interessiert
Gründe:
Wir sind meist nur interessiert an Laufzeitanalyse für große Inputs.
Beispiel $n^2$ vs $n\log(n)$ (einfache Sortierabgorithmen vs. Merge-Sort)
bei kleinen Werte von $n$:
xmax = 150; xmin=2; x = np.arange(xmin, xmax, 1)
plt.plot(x, 0.5*x**2, 'k-', label="$1/2 n^2$")
plt.plot(x, 6*x*np.log2(x)+6*n, 'b-', label="$6 n log_2 n + 6 n$")
plt.xlim(xmin, xmax); plt.xlabel("n"); plt.ylabel("f(n)"); plt.legend();
bei mittleren Werte von $n$:
xmax = 1500; xmin=2; x = np.arange(xmin, xmax, 10)
plt.plot(x, 0.5*x**2, 'k-', label="$1/2 n^2$")
plt.plot(x, 6*x*np.log2(x)+6*n, 'b-', label="$6 n log_2 n + 6 n$")
plt.xlim(xmin, xmax); plt.xlabel("n"); plt.ylabel("f(n)"); plt.legend();
Bei einem "schnellen" Algorithmus wächst die Bearbeitungszeit (in der worst-case Analyse) nur langsam mit der Länge $n$ des Inputs.
Komplexe Datenverarbeitungsszenarien bestehen oft aus vielen Schritten.
Sortierung gilt dabei als quasi for free, da es nur schwach super-linear wächst.