# 1 Einführung, Algorithmenentwurf, Güte von Algorithmen

[TOC]

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

$\newcommand{\N}{\mathbb{N}}
\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).

## Was ist ein Algorithmus?
Wenn man in der Zeitung liest, ist ein Algorithmus eher ein böses Ding, das einem empfiehlt rote Kugelschreiber zu kaufen, weil man kürzlich blaue Kugelschreiber gekauft hat. Wir als Informatiker verstehen darunter was anderes: eine systematische Anleitung.

Ein Beispiel: Multiplikation von zwei Zahlen nach der Primarschulmethode, Ziffer für Ziffer:

62*37
--------
14
42
6
18
--------
2294

In dieser Vorlesung studieren wir Eigenschaften solcher Algorithmen. Ist die Multiplikationsmethode korrekt? Ist sie clever? Schnell?

Die *ACM* (die grössten Vereinigung von Informatikern) gibt folgende Definition:

Was ist Informatik?

: "Computer Science *is* the systematic study of algorithms and data structures, specifically:

- their formal properties (correctness and efficiency, was wir hier machen)
- their linguistic + mechanical realization (was wir in Eiffel gelernt haben)
- their applications (der Rest des Studiums)"

Diese formalen Eigenschaften sollen uns begeistern. Ziel der Vorlesung ist, dass sie gar nicht mehr anders können als darüber nachzudenken

Warum ist das wichtig? Wir wollen unterscheiden zwischen *sein* und *nicht sein*. Lösbarkeit und Unlösbarkeit. Ein Beispiel:

### Staubsaugerproblem


Wir kennen den Grundriss unseres Wohnzimmers und wollen die Steckdosen in unserem Zimmer so platzieren, dass wir mit einem Staubsauger, der ein Stromkabel einer gewissen Länge hat, die ganze Wohnung putzen können. Wieviele Steckdosen brauchen wir dafür? Wie platzieren wir sie am besten? Das sind typische Fragestellungen, die wir in dieser Vorlesung beantworten wollen.

Heute gibt es aber auch Staubsauger, die ohne Kabel auskommen und wie Roboter den Raum abfahren. Statt Steckdosen brauchen diese Roboter Ladestationen, die sie erreichen müssen bevor die Batterie leer ist. Auch dabei stellen sich interessante Fragen: Wie verteilen wir die Ladestationen optimal? Was ist eine gute Putzroute für den Roboter? Das Suchen einer solchen optimalen Putzrundreise ist ähnlich zu folgendem bekannten Problem:

### Das Rundreiseproblem (TSP)
Ein Handlungsreisender möchte jede Stadt in einem Land möglichst rasch besuchen. Wir suchen also die kürzeste Tour durch alle Städte. Das ist eines der bekanntesten Probleme der theoretischen Informatik und heisst *Traveling Salesman^[Oder politisch korrekt: Traveling Salesperson Problem] Problem*, kurz *TSP*.


Ein Art das Problem zu lösen ist alle möglichen Reihenfolgen auszuprobieren. Für jede Permutation der Städte berechnen wir die Kosten und merken uns das Minimum. Nun haben wir also bereits einen ersten Algorithmus für TSP. Doch ist er gut oder schlecht?

Für $n$ Städte müssen wir so alle $n!$ Reihenfolgen ausprobieren. Das Überprüfen einer Reihenfolge dauert dann nochmals $n$ Schritte. Wenn wir ein bisschen genauer hinschauen, können wir einen Faktor $n$ einsparen, da wir die selbe Rundtour bei jeder Stadt einmal beginnen.

Wie grosse Probleme können wir mit so einem Algorithmus lösen? 100 Städte? Dazu müssten wir $100!$ Permutationen testen. Das sind sicher mehr als $2^{100}$ viele. Ist das viel? Stellen wir uns ein Blatt Papier vor. Falten wir es $100$ Mal, dann ist der resultierende Stapel $2^{100}$ Papierlagen dick. Das ist gerade etwa so gross wie das bekannten Universums![^Papierfalten]

[^Papierfalten]: Die Grösse des beobachtbaren Universums ist etwa [$2^{80}$ Kilometer](http://www.wolframalpha.com/input/?i=size+of+the+universe).
Der Weltrekord für das Falten von Papier liegt bei $13$ Mal. 2002 hat die Maturandin [Britney Gallivan](https://en.wikipedia.org/wiki/Britney_Gallivan) ein Stück Papier zwölf mal gefaltet. Selbst dazu war schon eine Klopapierrolle von über einem Kilometer Länge nötig [[Details]](http://pomonahistorical.org/12times.htm).
Seither gab es mehrere Versuche den Rekord zu brechen. 2012 hat es eine Gruppe Schüler am MIT geschafft $13$ mal zu falten [[Artikel]](https://www.newscientist.com/blogs/nstv/2012/01/paper-folding-limits-pushed.html) und auch ein Team der BBC hat sich daran versucht [[Video]](https://www.youtube.com/watch?v=ZQ0QWn7Z-IQ).

Interessanterweise kennt man bis heute keine viel besseren Algorithmen für TSP. 1970 konnte man das Problem mit einem etwas cleveren Algorithmus für 120 Städten lösen. Mit dem selben Algorithmus kommt man heute auf 140 Städte, einfach durch schneller Computer. Nur zu warten bis die Maschinen schneller werden, bringt uns also nicht allzu weit.

Mittlerweile gibt es aber auch bessere Algorithmen, sodass wir auch Rundreisen mit hunderttausenden Städte finden können. Ein algorithmischer Durchbruch kann also eine Effizienzsteigerung bringen.

## Schnelle Multiplikation nach Karatsuba & Ofman
Zurück zu unserem Beispiel des *Multiplikationsalgorithmus*.
Wir wollen die Anzahl Multiplikationen unseres Algorithmus minimieren. Dabei zählen wir die Anzahl einstelliger Multiplikationen. Die Kosten der Additionen ignorieren wir für den Moment.
Kostenmodell: einstellige Multiplikationen

Die Schulmethode von oben benötigte $2 \cdot 2 = 4$ Multiplikationen. Für zwei $n$-stellige Zahlen benötigen wir mit der Schulmethode $n^2$ elementare Multiplikationen.
Geht es mit weniger?

62 * 37
----------
18
18
14
14
16
---------
2294
als dritte Multiplikation verwendeten wir dabei: $(6-2)\cdot(7-3)$.
Wir kommen also mit nur drei, statt vorher vier Multiplikationen aus.

Funktioniert das immer? Um die Korrektheit zu zeigen können wir einfach $a,b,c$ und $d$ für die vier Ziffern einsetzen und die Methode symbolisch nachprüfen.

In der Informatik braucht man heute häufig sehr grosse Zahlen (Kryptographie). Können wir mit diesem Trick auch bei mehr als zweistelligen Zahlen profitieren?

$6237\cdot 5898$ können wir interpretieren als zwei zweistelligen Zahlen mit "Ziffern" 62, 37, 58, 98 und rekursiv/induktiv die selbe Methode anwenden. In diesem Beispiel würde unsere neue Methode $9$ Operationen benötigen, während die Schulmethode $16$ (=$4*4$) benötigt. Dieses Prinzip der induktiven Anwendung kommt in der Algorithmik sehr häufig vor.

Analysieren wir die Methode systematischer:
Sei $M(n)$ = Anzahl einstelliger Multiplikationen bei zwei Zahlen mit je n Ziffern mit unserer neuen Methode. Wir haben gesehen, dass wir zwei einstellige Zahlen mit einer elementaren Multiplikation multiplizieren können und zwei zweistellige Zahlen mit drei elementaren Multiplikationen. Allgemein:
$M(2^i) = \begin{cases}
1 & \text{für } i=0\\
3 \cdot M(2^{i-1}) & \text{für } i>0.
\end{cases}$
Die Schulmethode zum Vergleich benötigt $S(n) = n^2$ viele einstellige Multiplikationen.

Was ist nun mehr?
Bei rekursiven Algorithmen ist die Analyse häufig auch rekursiv. Wir hätten aber gerne eine explizite Formel. Wie finden wir die?

Wir beginnen mit Teleskopieren, d.h. wir setzen die Rekursionsformel einige Male ein, bis wir eine Vermutung für die explizite Formel finden:
$$
M(2^i) = 3 \cdot M(2^{i-1}) = 3 \cdot 3 \cdot M(2^{i-2}) = ... = 3^i M(2^0)
$$

Das lässt uns vermuten: $M(2^i)$ =$3^i$.

Nun beweisen wir diese Vermutung mittels vollständiger Induktion:

* *Vermutung* $M(2^i)=3^i$

* *Anfang* $M(2^0) = 3^0 = 1$ ✓

* *Schritt* $M(2^k) = 3\cdot M(2^{k-1}) = 3 \cdot 3^{k-1} = 3^k$

Was ist das denn jetzt im Vergleich zu den $n^2$ der Schulmethode? Wir ersetzen $2^i$ durch $n$ in $M(2^i) = 3^i$. Dann gilt $M(n) = 3^{log_2n} = 2^{log_2 3 log_2 n} = n^{log_2 3} = n^{1.58}$.

Für grosse Zahlen ist das also deutlich schneller als die Schulmethode. Für grosse Zahlen ist unser Verfahren also rasch mal 100mal schneller als die Schulmethode. Als konkretes Beispiel: für zwei tausendstellige Zahlen ist unser neues Verfahren $\frac{1000^2}{1000^{1.58}} \approx 18$ mal schneller als die Schulmethode.

Diese Idee ist gar nicht mehr so neu sondern stammt von Karatsuba & Ofman in 1962. Und es wurde seither noch weiter an schnellen Multiplikationsalgorithmen geforscht. Noch heute gibt es viele Leute, die daran arbeiten schneller und schneller zu multiplizieren. Wenn Sie einen neuen besseren Algorithmus finden, dann kommen Sie bestimmt in der New York Times. Die besten Algorithmen sind schon sehr nahe bei $n^1$, aber eben nur fast, also eher $n^{1.001}$.[^FastMult]

[^FastMult]: Für lange Zeit war der [Schönhage-Strassen-Algorithmus](https://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm) der schnellste bekannte Algorithmus mit einer Laufzeit von $\O(n \log n \log \log n)$. 2007 hat nun aber der Schweizer Mathematiker [Martin Fürer](http://www.cse.psu.edu/~fhs/) einen noch schnelleren Algorithmus präsentiert, an dem nun intensiv weiter geforscht wird. Alle diese neuen Algorithmen sind aber nicht wirklich praktikabel [[Wikipedia]](https://en.wikipedia.org/wiki/Fürer%27s_algorithm).

Im Idealfall möchte man zusätzlich häufig gerne noch eine theoretische untere Schranke finden, um zu zeigen, dass es gar nicht mehr schneller gehen kann. Man kann sich die Frage stellen, wie viele elementare Multiplikationen mindestens notwendig sind, um zwei $n$-stellige Zahlen zu multiplizieren. Diese Frage ist noch nicht endgültig geklärt. Man weiss jedoch, dass man mindestens $n$ elementare Multiplikationen sein müssen. Ein nicht ganz präzises Argument dafür: Würden wir weniger als $\frac{n}{2}$ elementare Multiplikationen durchführen, so könnten wir gar nicht erst alle Ziffern der Eingabe anschauen.

Zusatzfrage: Was machen wir wenn die Zahlen keine Längen haben, die Zweierpotenzen sind?^[Eine Variante: Wir füllen die Zahlen mit führenden Nullen auf bis wir Zweierpotenzenlängen vor uns haben. Doch es geht auch cleverer indem wir die Teilzahlen abhängig von ihrer Länge clever kombinieren.]

## Algorithmenentwurf
Wie im Beispiel vorher gehen Algorithmenentwurf und dessen Analyse Hand in Hand. Wäre eine Übungsaufgabe gewesen "Finde ein schnelleres Verfahren für die Multiplikation", wäre es schwierig gewesen die Methode von Karatsuba einfach so zu finden. Häufiger ist der Algorithmenentwurf aber eine sehr systematische, nachvollziehbare Sache. Ein Beispiel dazu:

### Beispiel: Finde die Rektorin
Ist die ETH-Rektorin im Saal? Wer kennt sie überhaupt?
Wir wollen eine Rektorin unter uns finden. Was ist eine Rektorin? Und wie finden wir sie?

Definition: Rektorin
: - alle kennen sie
- sie kennt keinen


Als elementare Operation betrachten wir: Frage an A: Kennst du B? Antwort: (Ja/Nein)
Andere Fragen erlauben wir nicht. Wie stellen wir diese Fragen in einem Raum mit $n$ Personen am besten?

- Kann es sein, dass es keine Rektorin gibt? Ja, z.B. wenn jeden jeden kennt.
- Kann es sein, dass es genau einen Rektorin gibt? Ja, z.B. wenn Sarah Springman um die Ecke kommt.
- Kann es sein, dass es mehr als eine Rektorin gibt?[^ZweiRektorinnen]

[^ZweiRektorinnen]: Gäbe es zwei Rektorinnen, so müsste die eine die andere kennen, damit die andere alle kennen und damit eine Rektorin sein kann. Die eine kennt dann aber nicht keinen und ist daher per Definition keine Rektorin, weil sie die andere kennt. [Verwirrt?](http://dgraf.ch/d/div/handspiel.mp3)

Wir wollen also die Anzahl Fragen minimieren.
Naives Verfahren: Jeden über jeden ausfragen: $n \cdot (n-1)$ Fragen
Wir füllen das komplette Tableau mit Ausnahme der Diagonale (jeder kennt sich selbst):

| A \ B | 1 | **2** | 3 |
| ----- | ---- | -- | ---- |
| 1 | - | **Ja** | Nein |
| **2** | **Nein** | - | **Nein** |
| 3 | Ja | **Ja** | - |

Wie finden wir nun die Rektorin in dieser Tabelle? Wir suchen eine Person, sodass ihre Spalte nur *Ja* enthält (alle kennen sie) und ihre Zeile nur aus *Nein* besteht (sie kennt niemanden).

Das sind ziemlich viele Fragen, nämlich alle möglichen Fragen. Bei der Multiplikation zuvor haben wir argumentiert, dass es nicht besser gehen kann, als jede Ziffer anzuschauen. Hier ist das ein bisschen anders: Es ist nicht ausgeschlossen, dass wir die Rektorin finden können oder mit Sicherheit sagen können, dass es keine Rektorin gibt *ohne* jede mögliche Frage zu stellen.

Versuchen wir es mit Induktion:
Mit zwei Personen können wir die Aufgabe immer mit zwei Fragen lösen: F(2) = 2.
Für mehr als zwei Personen: Wir schicken jemanden raus, bestimmen rekursiv die potentielle Rektorin im Rest und holen die rausgeschickte Person wieder rein. Für diese Person müssen wir schauen, ob sie eine Rektorin ist, was 2(n-1) Fragen kosten kann.
$F(n) = 2(n-1)+F(n-1) = 2(n-1) + 2(n-2) +...+2 = n(n-1)$
Wir haben also leider nichts gespart und stellen immer noch etwa $n^2$ viele Fragen.

Wieso sparen wir keine Fragen? Da es sein kann, dass die rausgeschickte Person eine Rektorin ist, brauchen wir viele Fragen, wenn sie wieder reinkommt. Können wir garantieren, dass wir nicht die Rektorin rausschicken?
*Trick:* Wenn wir A nach B fragen: Wenn A B kennt ist A keine Rektorin, falls A B nicht kennt, dann ist B keine Rektorin. So können wir also mit nur immer einer Frage eine Nicht-Rektorin rausschicken. Wenn diese Person wieder reinkommt, können wir die potentielle Rektorin mit nur zwei Fragen überprüfen.

$F(n) = \begin{cases}
2 & \text{für } n=2\\
1 + F(n-1) + 2 & \text{für } n>2
\end{cases}$

Wir teleskopieren:

$$
F(n) = 3 + F(n-1) = 3 + 3 + F(n-2) = ... = 3(n-2) + 2 = 3n-4
$$

Beweis durch Induktion:
* Vermutung: $F(n)$ = $3n-4$
* Induktionsanfang: $F(2)$ = $2$ ✓
* Induktionsschritt: $F(n) = 3 + F(n-1) = 3 + 3(n-1) -4 = 3n-4$ ✓

Wir fassen zusammen: Wir versuchten es zuerst ohne Erfolg mit Induktion. Aber nachdem wir genau hinschauten, um herauszufinden, wo die Induktion klemmt, haben wir ein viel schnelleres Verfahren gefunden. Das Verfahren ist so schnell, dass wir nur einen kleinen Bruchteil aller möglichen Fragen stellen müssen.

Denksportaufgabe: Geht es besser?

## Kostenmodell
Für Probleme, die wir mit dem Computer lösen wollen, ist die elementare Operation nicht "eine Frage stellen" sondern eher Dinge wie eine Zahl einlesen, zwei Zahlen vergleichen, Werte zuweisen etc. Das sind alles simple Operationen. Weiter ins Detail, auf die Ebene der einzelnen Bits und Bytes, wollen wir in dieser Vorlesung meist nicht gehen. Wie lange eine einzelne Addition zweier (kleiner) Zahlen effektiv dauert hängt von vielen Faktoren ab: der Taktzahl unserer CPU, der Effizienz des Compilers, die Ausnutzung des Cache-Speichers, der Wahl der Programmiersprache usw. Der Einfachheit halber, nehmen wir an, dass jede dieser Operationen einen einzelnen Schritt bedeutet und nennen dies das *Einheitskostenmodell*. Als erste Idee wollen wir also solche konstante Faktoren ignorieren.

Das steht im Gegensatz zu unserem vorherigen Beispiel, wo eine Multiplikation zweier Zahlen mehrere Operationen bedeutete und wir gar deren Geschwindigkeit optimierten. Wenn wir nichts anderes sagen, dann analysieren wir in dieser Vorlesung immer mit dem Einheitskostenmodell. Wir nehmen also an, dass der Aufwand für arithmetische Operationen unabhängig von der Grösse der Operanden ist.

Die zweite Idee ist, dass wir uns nur für grosse Eingabewerte interessieren, bei denen der Algorithmus lange läuft. Denn bei kleinen Eingaben ist auch ein naiver Algorithmus vernünftig schnell.

Wenn wir zwei Algorithmen miteinander vergleichen wollen, dann ist derjenige besser, der auf grossen Eingaben schneller läuft. Um das mathematisch präzise zu beschreiben, machen wir Vereinfachungen:
Konstante Faktoren und Verschiebungen wollen wir weglassen. Eine lineare Wachstumskurve mit Steigung $1$ erachten wir als gleich schnell wie eine Kurve mit Steigung $20$. Damit wollen wir kompensieren, was wir uns mit dem Einheitskostenmodell eingehandelt haben, denn bereits da drin verstecken wir ja schon konstante Faktoren.

Dazu definieren wir eine Menge von Funktionen, die auch nicht schneller wachsen als eine Wachstumsfunktion $f:
\N \rightarrow \N$. Wir schreiben dies mit einem grossen, kalligraphischen 'O', als
$\O(g) = \{f: \N \rightarrow \N, \exists c_1, c_2: \forall n: f(n) \leq c_1 + c_2 \cdot g(n) \}$.

Wir sagen:

> Alle Funktionen $f$ in $\O(g)$ wachsen asymptotisch nicht schneller als $g$.

Damit können wir nun Dinge vereinfachen wie:
$3n-4 \in \O(n)$ indem wir z.B. als $c_1 = 0$ und $c_2 = 3$ wählen.
Die beiden Konstanten erlauben es uns also die eine Funktion gegenüber der anderen zu skalieren und zu verschieben.


Da man früher keine $\in$ Zeichen schreiben konnten, hat man häufig $3n-4 = \O(n)$ geschrieben, korrekt ist aber schon die $\in$ Notation, denn 3n-4 ist nur eine der vielen Funktionen, die in $O(n)$ enthalten sind.

Nun kann man das selbe auch machen mit "mindestens so schnell wachsend" als Klasse $\Omega(g)$. Oder als "weniger schnell wachsend" mit klein-O also $o(g)$.

Ist eine Funktion $f$ sowohl in $\O(g)$ also auch in $\Omega(g)$, sagen wir dass $f$ und $g$ asymptotisch gleich schnell wachsen und schreiben $f \in \Theta(g)$.

Noch ein Wort der Vorsicht: Diese $\O$-Notation sollten wir nicht in Rekursionsgleichungen drin verwenden, da man so leicht wichtige Konstanten versteckt. Wir benutzen die $\O$-Notation also meist nur ganz am Schluss.

An diese asymptotische Notation muss man sich etwas gewöhnen. In der Algorithmik ist sie allgegenwärtig und wir werden ihr in jeder Vorlesung wieder begegnen. Deshalb handelt das erste Übungsblatt ausschliesslich davon.