Algorithmen: Einführung¶
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)
(Nicht-formale) Definition eines Algorithmus¶
Eine wohldefinierte Prozedur, die eine Eingabe (Input) entgegen nimmt und daraus eine gewünschte Ausgabe (output) berechnet.
Beispiel:
Multiplikation zweier Ganzzahlen¶
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)
Performanzanalyse: Anzahl der primitiven Operationen¶
Analyse für die Performanz eines Algorithmus:
Wieviele primitive Operationen benötigt ein Algorithmus in Abhängigkeit von der Größe des Inputs ?
Schulmathematik-Algorithmus für die Multiplikation zweier Ganzzahlen¶
Beispiel: $x=5678$ und $y=1234$
5678
x 1234
--------
22712
17034
11356
5678
--------
7006652 Beachte:
- Der Algorithmus ist korrekt, d.h. er liefert immer das richtige Ergebnis.
- Der Algorithmus terminiert (keine Endlosschleife).
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$
- Operationen für Zwischenergebnis $\leq 2n^2$
- Operationen für jede Zeile des Zwischenergebnis $\leq 2n$:
- $n$ Multiplikationen
- $n$ Additionen (falls Übertrag vorhanden)
- $n$-Zeilen
- Operationen für jede Zeile des Zwischenergebnis $\leq 2n$:
- Addition des Zwischenergebnis $\leq 2n^2$
Matra des Algorithmendesigners¶
"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
Can we do better?¶
Können wir es besser machen?
Karatsuba Multiplikation (Teil 1)¶
Teile $x$ und $y$ in zwei Hälften: mit $x=5678$ und $y=1234$
- aus $x$: $a=56$ und $b=78$
- aus $y$: $c=12$ und $d=34$
- Schritt: $e_1 = a \cdot c = 56 \cdot 12 = 672$
- Schritt: $e_2 = b \cdot d = 78 \cdot 34 = 2652$
- Schritt: $e_3 = (a+b) \cdot (c+d) = 134 \cdot 46 = 6164$
- Schritt: $e_4 = e_3 - e_1 - e_2 = 6164-672-2652=2840$
- Schritt: $e = 10^4 \cdot e_1 + 10^2 \cdot e_4 + e_2 =\\ 6720000 + 284000 + 2652 = 7006652$
- Schritt liefert das Ergebnis der Multiplikation - auf den ersten Blick - auf "magische" Weise. Mehr dazu wie die Karatsuba Multiplikation funktioniert später.
$\rightarrow$ Verschiedene Algorithmen führen zum gleichen Ergebnis.
(einfacher) Rekursiver Algorithmus¶
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 (Teil 2): Erklärung¶
Karatsuba Multiplikation ist eine optimierte Version von RecIntMult:
- in
RecIntMultwerden vier Rekursionen vorgenommen. - in
Karatsubawerden 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:
- Berechne $a \cdot c$
- Berechne $b \cdot d$
- Berechne das Produkt $(a+b) \cdot (c+d)$
- Ziehe vom Ergebnis von Schritt 3 das Ergebnis von Schritt 1 und 2 ab. Dies entspricht $(a \cdot d + b \cdot c)$.
- Berechne eq. (1.1) mit den Ergebnissen aus Schritt 1, 2 und 4 und dem entsprechenden Auffüllen von Nullen ($10^n$ bzw. $10^{n/2})$
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.
Sortierverfahren¶
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:
Sortierproblem¶
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.
Aufgabe¶
Überlegen Sie sich ein Verfahren (ohne Recherche!), wie man das Sortierproblem algorithmisch lösen kann. Beschreiben Sie ihren Ansatz.
Der Aufwand wächst im durchschnittlichen und schlechtesten Fall bei Insertion Sort quadratisch mit der Länge des Arrays.
Geht das besser?
Merge-Sort¶
- Relativ alter ($>70$ Jahre), aber in der Praxis oft (in vielen Bibliotheken) verwendet.
- Kanonisches Beispiel für einen Divide and Conquer (Teile - und Herrsche) Algorithmus.
Teile und Herrsche - Divide and Conquer¶
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.
Idee von Merge Sort¶
- Wiederhole rekursiv bis die Länge des Arrays $\leq 1$: Teile das Array in zwei (fast) gleichgroße Hälften.
- Verschmelze die sortierten Arrays zu einem sortierten Array.
Beachte, dass ein Array mit nur einem Element sortiert ist.
