# 2 Algorithmenentwurf: Einfache Induktion

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\ra}{\rightarrow}
\newcommand{\O}{\mathcal{O}}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

## Einleitung
Wir haben in der ersten Lektion gesehen, wie wir Algorithmen entwerfen und analysieren wollen. Wir haben ein Analysemodell gesehen, das sehr grob ist: Einen Algorithmus, der $2n$ Schritte braucht, betrachten wir als gleich schnell wie einen der $10'000n+10^6$ Schritte braucht. Das ist natürlich sehr ungenau, aber der durchschlagende Erfolg der Algorithmik beruht darauf, dass diese Analyse oft sehr gut funktioniert.

Wir wollen heute nochmals Algorithmen entwerfen, die "gut" sind. Wie misst man denn die Qualität von Algorithmen?

- Korrektheit: Macht das Programm, was es soll. Hier machen wir das meist relativ informell.
- Effizienz: Zeit und Platz: Wie lange läuft der Algorithmus und wieviel Speicher verbraucht er dabei?
- Qualität der Lösung: Wie nahe kommen wir an das Optimum. Das haben wir bisher noch nicht gesehen. Daher ein Beispiel dazu:

## Beispiel Maximum Subarray
Betrachten wir folgende $n=14$ Zahlen

5 7 12 -48 9 36 -17 22 11 -49 49 -49 111 -117

Aus diesen Zahlen wollen wir ein Teilstück, ein Intervall, extrahieren, sodass die Summe darin maximal wird. Für so kleine Eingaben wie das Beispiel oben können wir problemlos alle Teilintervalle ausprobieren, doch für $n=10^6$ kann dies lange dauern.

Wir können das auch als Aktienkurs anschauen. Dann seien die Zahlen die Tagesänderungen und wir fragen uns im Nachhinein: Wann hätten wir am besten kaufen und wieder verkaufen sollen, um unseren Profit zu maximieren?

### Erste naive Lösung

for i = 1 to n do
	for j = i to n do
		S := 0
		for k = i to j do
			S := S + d_k
		merke maximales S

Wir betrachten also jedes mögliche Intervall $[i,j]$ und berechnen die entsprechende Summe $S$. Wie lange läuft dieser Algorithmus?

Maximale Laufzeit: Zählen wir die Anzahl Additionen sehr grosszügig: Jede Schleife wird maximal $n$ mal ausgeführt. Da die Schleifen ineinander verschachtelt sind, nehmen wir das Produkt, also $n\cdot n\cdot n = n^3$ in $\O(n^3)$.

Doch ist dieser Algorithmus wirklich so langsam oder haben wir einfach viel zu grob abgeschätzt? Schätzen wir die Laufzeit mal noch konservativ ab, zählen also eher zu wenig Additionen. Nehmen wir dazu nun an, dass sich der Anfang des Intervalls $i$ nur im ersten Drittel des Arrays bewegt und das Ende des Intervals $j$ nur im letzten Drittel des Arrays. Dann gilt für jedes Paar $i,j$, dass $k$ mindestens $\frac{n}{3}$ Werte annimmt. Insgesamt benötigen wir also auch unter dieser Annahme mindestens $\frac{n^3}{27}$ Schritte also in $\Omega(n^3)$.


Da wir die selbe, kubische untere und obere Schranke gezeigt haben, können wir also sagen, dass die Laufzeit unseres Algorithmus in $\Theta(n^3)$ liegt. Das ist nicht besonders schnell und wohl höchstens für ein paar hundert Börsentage praktikabel.

Was machen wir zuviel hier? Wir summieren immer wieder die selben Dinge auf. Können wir die Summe der Zahlen von i bis j nicht schneller bestimmen?

### Lösung mit Präfixsummen
Es genügt, lediglich alle Präfixsummen zu berechnen: Wir berechnen für jede Position $i$ die Summe $S_i$ = Summe der Zahlen bis und mit Position $i$. All diese $S_i$ Werte können wir für aufsteigende $i$ in linearer Zeit, also in $\O(n)$, berechnen: um eine Präfixsumme $S_i$ zu berechnen, genügt es die $i$-te Zahl zur bereits berechneten Summe $S_{i-1}$ dazu zu addieren. Danach ist die Summe von i bis j einfach $S_j - S_{i-1}$.


Wir können uns nun die innerste Schleife sparen:

// Berechne die Präfixsummen in O(n)
S[0] := 0
for i := 1 to n do
	S[i] := S[i-1]+d[i]
// Bilde die Summe für jedes Interval in O(n^2)
for i := 1 to n do
	for j := i to n do
		S := S[j]-S[i-1]
		merke maximales S

Wie viel schneller sind wir damit? Das Vorberechnen der Präfixsummen geht in $n$ Schritten. Danach können wir für jedes der $\O(n^2)$ Intervalle in konstant vielen Schritten die Summe berechnen. Somit resultieren $\O(n^2 + n) = \O(n^2)$ Schritte.

### Teile und Herrsche (Divide-and-Conquer)

Sind wir jetzt zufrieden? $\O(n^2)$ kann für viele reale Eingaben noch immer zu langsam sein. Doch anders als vorhin gibt es bei dieser Lösung nicht einen offensichtlich Engpass, den wir beheben können.

Um noch schneller zu werden, wollen wir nun noch einen weiteren Trick des Algorithmenentwurfs anschauen. Es ist eine mächtige Technik, die bereits die Römer kannten.

Wie gestern, versuchen wir eine induktive Lösung zu suchen. Hier werden wir nicht einfach ein Element wegnehmen (wie bei der Rektorin gestern), sondern in der Mitte teilen:


Wir teilen unsere Zahlenfolge in zwei Teile. Wo kann die Lösung, d.h. das Teilintervall mit der grössten Zahlensumme, liegen? Wir unterscheiden drei Fälle: Entweder liegt das gesuchte Intervall genau in der linken Hälfte, genau in der rechten Hälfte, oder es enthält Teile der rechten und der linken Hälfte. Genau diese drei Fälle wollen wir anschauen und für jeden Fall das maximale Intervall berechnen. Dann müssen wir nur noch aus den drei Intervallen jenes mit der grössten Summe wählen.

Eine solche Strategie, die das Problem in kleinere Portionen aufteilt und diese separat löst und wieder zusammensetzt, nennt man "Divide and Conquer". Hat uns diese Aufteilung hier was gebracht?

Die ersten beiden Fälle könne wir einfach behandeln, indem wir das die entsprechende Hälfte separat betrachten und die Lösung (rekursiv mit dem gleichen Verfahren) berechnen. Wie können wir aber die Lösung für den dritten Fall berechnen?
Wir suchen links das beste Teilstück, das am rechten Rand endet, und setzen es zusammen mit dem besten Teilstück im rechten Teil, das am linken Rand endet.
Wir müssen also die Präfixsummen der rechten und die Suffixsummen der linken Hälfte betrachten. Wir haben bereits gesehen, dass diese in linearer Zeit berechnet werden können. Wir addieren also die maximale Präfixsumme der rechten Hälfte und die maximale Suffixsumme der linken Hälfte. So können wir die Lösung für den dritten Fall in linearer Zeit ausrechnen.


Divide-and-Conquer Algorithmus:
: - falls höchstens ein Element:
- falls genau ein positives Element: nimm dieses Element
- sonst: 0
- falls mehrere Elemente:
- teile in der Mitte
- bestimme die optimalen Lösungen rekursiv für die beiden Teile $\ra$ gibt die beiden Lösungskandidaten $L_1$, $L_2$
- errechne die 2 besten Randstücke und setze sie zusammen $\ra$ gibt $L_3$
- Lösung ist $\max\{L_1,L_2,L_3\}$

**Analyse:**
Nun wollen wir die Laufzeit unseres Algorithmus analysieren, um zu sehen, ob wir überhaupt eine Verbesserung erzielen konnten.

Wir schreiben $T(n)$ für die Laufzeit mit $n$ Elementen. Für den rekursiven Fall können wir die Laufzeit so hinschreiben
$\begin{align}
T(n) &= \text{teilen + linke Lösung + rechte Lösung + Randstücke bestimmen}\\
&= 1 + T\left(\frac{n}{2}\right) + T\left(\frac{n}{2}\right) + a' \cdot n\\
&\leq 2 \cdot T\left(\frac{n}{2}\right)+ a \cdot n.
\end{align}$
Dabei sei $a'$ eine Konstante, die beschränkt wie aufwändig das Bestimmen der Lösung über die Mitte ist, $a = a'+1$ und für den Basisfall mit $n=1$ sei $T(1)=b$ für eine Konstante $b$.

Wie löst man eine solche Rekursionsgleichung? Wir machen, was wir bis jetzt immer gemacht haben. Wir setzten ein paar Mal ein und schauen, ob wir ein Gefühl für die Lösung kriegen.
$\begin{align}
T(n) &= 2 \cdot T\left(\frac{n}{2}\right) + a \cdot n \\
&= 2 \cdot \left(2 \cdot T\left(\frac{n}{4}\right)+a \cdot \frac{n}{2} \right) + a \cdot n = 4 T\left(\frac{n}{4}\right) + 2an\\
&= 2 \cdot \left(2 \cdot \left(2 \cdot T\left(\frac{n}{8}\right)+a \cdot \frac{n}{4}\right)+a \cdot \frac{n}{2}\right) + a \cdot n = 8 T\left(\frac{n}{8}\right) + 3an\\
&...\\
&= 2^i T\left(\frac{n}{2^i}\right) + i \cdot a \cdot n
\end{align}$

Das hier endet falls $n=2^i$ ist, also falls $i = \log_2 n$, denn dann benutzen wir $T(1)$ und die Rekursion endet.
Also vermuten wir sowas wie $T(n) = n\cdot b + a\cdot n\cdot logn$, was dann $T(n) \in \O(n log n)$ bedeuten würde.

Doch stimmt das auch? Um es zu beweisen wollen wir nie die $\mathcal{O}$-Notation verwenden, denn essentiellen Konstanten in einer Rekursionsgleichung zu verstecken kann gefährlich sein.

**Beweis mittels vollständiger Induktion:**
zu beweisen: Es gibt $c_1$ und $c_2$, s.d. $T(n) \leq c_1 n \log n + c_2$
Induktionsanfang: $T(1) \leq c_2$, wähle $c_2 \geq b$.
Induktionshyptohese (IH): Für $T\left(\frac{n}{2}\right)$ wissen wir bereits, dass $T\left(\frac{n}{2}\right) \leq c_1 \frac{n}{2} \log \left(\frac{n}{2}\right) + c_2$.
Induktionsschritt:
$\begin{align}
T(n) &\leq 2\cdot T\left(\frac{n}{2}\right) + a\cdot n \\
&\stackrel{\text{IH}}{\leq} 2\cdot \left(c_1\cdot \frac{n}{2}\cdot \log\left(\frac{n}{2}\right) + c_2\right) + a\cdot n\\
&= c_1\cdot n\cdot \log(n) - c_1 n + 2 c_2 + an \\
&\stackrel{!}{\leq} c_1\cdot n\cdot \log(n) + c_2
\underbrace{-c_1 n + c_2 + an}_{\stackrel{!}{\leq} 0}
\end{align}$
Können wir die letzte Ungleichung erfüllen? Wir haben noch etwas Spielraum, da wir $c_1$ noch nicht fixiert haben. Welche Bedingung muss für $c_1$ gelten?
$\begin{align}
-c_1 n + c_2 + an &\leq 0\\
(a-c_1) &\leq - \frac{c_2}{n}\\
\frac{c_2}{n} + a &\leq c_1
\end{align}$
Wähle dazu z.B. $c_1 = a+c_2$.
Damit wissen wir, dass unser Divide-and-Conquer Algorithmus in Zeit $\O(n\log(n))$ läuft.

### Lineare Lösung

Geht es noch besser?
Nochmal von vorne: Versuchen wir nochmals eine Induktion von links nach rechts.


Als Invariante nehmen wir an, dass wir nach dem $i$-ten Schritt die optimale Lösung für die ersten $i$ Elemente kennen. Wenn wir nun das $(i+1)$-te Element dazunehmen, dann wollen wir rasch herausfinden, ob wir dieses neue Element zum besten Interval gehört. Dazu merken wir uns für den Teil bis $i$ nicht nur das Maximum sondern auch wieviel wir erreichen können, wenn wir am rechten Rand enden. Damit können wir dann leicht vergleichen, ob wir mit dem neuen Element ein neues Maximum erreichen können oder nicht.

Als Invariante nehmen wir an, dass wenn wir bis Position $i$ gekommen sind, bereits folgende Dinge kennen
* das Maximum im Bereich $1, \dots, i$,
* das Maximum, das bei $i$ endet.

randmax := 0
max := 0
for i = 1 to n do
	randmax := randmax + d[i]
	if randmax < 0 then randmax := 0
	if max < randmax then max := randmax

Dieses Verfahren hat nun gar nur lineare Laufzeit! Also $\O(n)$!

### Untere Schranke
Nun werden wir ehrgeizig und wollen es noch besser machen. Schaffen wir $\sqrt n$ oder gar $\log(n)$? Oder geht's gar nicht besser?

Folgende Überlegung zeigt, dass wir nicht besser als linear sein können: Angenommen wir haben einen Algorithmus, der nicht jedes Element anschauen muss. Dann ist er nicht korrekt:
- Berechnet der Algorithmus eine Lösung, die das nicht-angeschaute Element enthält, dann sei es einfach $-\infty$.
- Enthält die Lösung das nicht-angeschaute Element allerdings nicht, dann sei es einfach $\infty$, sodass es zwingend in der Lösung vorkommen sollte.

Demnach muss jeder korrekte Algorithmus alle Elemente mindestens einmal betrachten. Die Laufzeit liegt also in $\Omega(n)$. Da dies nicht eine Eigenschaft eines spezifischen Algorithmus ist, sondern für alle Algorithmen gilt, die das MaxSubarray-Problem lösen sprechen wir von der *Laufzeitkomplexität des Problems*.

Die Grösse des Inputs ist nicht immer eine untere Schranke für die Laufzeit. Erinnern wir uns an das Rektorinnen-Problem von gestern. Da war die Eingabegrösse quadratisch (jeder mit jedem), aber wir mussten nur linear viele Fragen stellen.

Fragen:
- Wie finden wir das Interval (und nicht nur dessen Summe)?
Antwort: Wir führen im Algorithmus immer die aktuellen Schranken von *max* und *randmax* mit und übergeben/aktualisieren diese bei jeder Änderung.
- Wie sieht es mit dem Speicherverbrauch aus?
Antwort: Wir unterscheiden zwei Speicherarten:
Speicher der das Programm benötigt (inklusive der Eingabe) und wie viel Speicher wir zusätzlich benötigen während der Laufzeit. So haben beispielsweise der erste und der letzte Algorithmus nur konstanten Zusatzspeicher für die Werte *S*, *randmax* und *max*. Sobald wir aber beispielsweise alle Präfixsummen vorberechnen, wie im zweiten Algorithmus, so brauchen wir linearen, also $\O(n)$, Zusatzspeicher.

Aufgabe fürs Wochenende: Wie viel Zusatzspeicher benötigt der Divide-and-Conquer-Algorithmus?^[Geschickt implementiert ist ein Aufruf mit $\O(1)$ Zusatzspeicher machbar und die Rekursionstiefe beträgt maximal $\log n$, also Zusatzspeicher in $\O(\log n)$.]