Kapitel 6: Komplexität, Verifikation, Terminierung

Jeden Programmierer treiben stets drei Fragen um:

1. Ist mein Programm schnell genug?
2. Arbeitet mein Programm korrekt?
3. Hört das Programm irgendwann auf?

Die Fragen 2 und 3 sind eng miteinander verwoben. Frage 2 zielt darauf ab, ob ein Programm für jede Eingabe ein valides Ergebnis liefert. Üblicherweise testen Programmierer ihre Programme mit Testdaten. Wenn ein Programm diese korrekt verarbeitet, ist das bereits ein gutes Zeichen. Damit ist jedoch nicht gezeigt, dass dies für alle möglichen Eingaben zutrifft. Dies nachzuweisen ist Aufgabe der Verifikation.

Frage 3 fragt danach, ob das Programm regulär terminiert oder ungewollt endlos lange läuft. Eine endlos lange Laufzeit kann durchaus ihre Ursache darin haben, dass ein Programm bestimmte Eingaben nicht korrekt verarbeitet. Aber auch Logikfehler können ursächlich sein. Ähnlich der Verifikation kann auch die Terminierung nachgewiesen werden.

Ob ein Programm schnell genug ist, ist wenig präzise gefragt, auch wenn umgangssprachlich oft so gesprochen wird. Die Frage ist vielmehr die: Wie kann überhaupt gemessen werden, wie schnell ein Programm arbeitet? - Die Angabe, es laufe 42 Sekunden, ist äußerst fragwürdig, denn es fehlen Angaben dazu, wie viele Daten es in der Zeit verarbeitet, wie sich die Zeit ändert, wenn beispielsweise die zu verarbeitende Datenmenge verdoppelt wird. Außerdem ist nicht klar, auf welche Art von Computer sich die Zeitangabe bezieht. Wie verändert sich die Laufzeit, wenn beispielsweise die Prozessorleistung erhöht und/oder der Hauptspeicher erweitert wird. Um Programme vergleichen zu können, bedarf es einer Messgröße, die unabhängig von CPU-Leistung, Netzwerkdurchsatz usw. ist. Und da kommt die sogenannte Big-O-Notation, geschrieben $\mathcal{O}$-Notation, ins Spiel.

Big-O-Notation

Bei der $\mathcal{O}$-Notation geht es darum, ein asymptotisches Laufzeitverhalten eines Programmes, eines Algorithmus, in Abhängigkeit von der Menge oder Größe der Eingabedaten zu beschreiben. 100 Worte zu sortieren ist beispielsweise etwas anderes als eine Million Worte sortieren zu wollen. Eine Primfaktorzerlegung einer kleinen Zahl wie 42 ist sicherlich mit weniger Schritten zu bewältigen als die einer Zahl im Milliardenbereich. Bei der ersten Aufgabenstellung ist es die Menge der Eingabedaten, die bestimmend ist, bei der zweiten die Größe des Eingabewertes. - Es ergibt sich gewöhnlich aus dem Kontext, was der bestimmende Faktor konkret ist.

$\mathcal{O}$ ist ein mathematisches Werkzeug in der Informatik, das die Wachstumsrate (Zeit- oder Speicherbedarf) eines Algorithmus beschreibt, wenn die Größe der Eingabedaten $n$ sehr groß wird, um seine Effizienz zu bewerten, indem es das Worst-Case-Szenario als obere Grenze darstellt. Es hilft zu verstehen, wie sich ein Algorithmus mit zunehmender Datenmenge verhält, unabhängig von der spezifischen Hardware, und klassifiziert ihn zum Beispiel als linear ($\mathcal{O}(n)$), quadratisch ($\mathcal{O}(n^2)$) oder konstant ($\mathcal{O}(1)$). - Die Kategorisierung ist dabei recht „grob". Benötigt ein Algorithmus für $n$ Daten $n$ Schritte und ein Vergleichsalgorithmus $2n$ Schritte, dann ist man geneigt zu sagen, der erste Algorithmus wäre doppelt so schnell wie der zweite. Bei $\mathcal{O}$ wird von konstanten Faktoren abstrahiert. Entscheidend ist vielmehr die Tatsache, dass beide Algorithmen bei einer Vervielfachung der Eingabe, beispielsweise auf das Doppelte, auch entsprechend mehr Schritte benötigen. Beide Algorithmen werden daher als $\mathcal{O}(n)$ eingestuft, sind also Linear-Algorithmen.

Formales Beispiel:

Seien $f, g: \mathbb{N} \rightarrow \mathbb{N}$, Abbildungen von $\mathbb{N}$ nach $\mathbb{N}$, $f$ sei höchstens von der Größenordnung $g$.

In Zeichen: $f \in \mathcal{O}(g)$, falls $n_0, c \in \mathbb{N}$ existieren mit

Statt $f \in \mathcal{O}$ sagt man auch $f = \mathcal{O}(g)$.

Wegen des konstanten Faktors $c$ ist die exakte Festlegung eines Schrittes nicht erforderlich.

Beispiel:

Sei $f(n) = 42n + 11n^2$.

Dann ist $f(n) \in \mathcal{O}(n^2)$.

Die Idee hinter $\mathcal{O}$ ist, nochmals umgangssprachlich zusammengefasst, zu beschreiben, wie sich Laufzeit/Speicherbedarf für große $n$ ($n$ gegen unendlich) verhalten. Im obigen Beispiel ist $n^2$ der dominierende Faktor, der den Verlauf einer entsprechenden Kurve, würden wir sie in einem Graphen auftragen, bestimmt.

Formal ließe sich dies mit Grenzwerten zeigen, darauf verzichten wir hier bewusst.

Wesentliche Klassen (mit Beispielen) sind:

• $\log_2(n)$: binäre Suche
• $n$: lineare Suche
• $n\cdot \log_2(n)$: „schlaues" Sortieren
• $n^2$: „dummes“ Sortieren
• $n^3$: Lösung von Gleichungssystemen
• $2^n$: alle Teilmengen
• $n!$: alle Permutationen

Bei kleinen Mengen/Größen von Eingabedaten, wie das in Seminaren üblich ist, bemerken wir die eklatanten Unterschiede im Laufzeitverhalten nicht. Wir können uns aber leicht eine Wertetabelle aufstellen, die uns einen Überblick und ein Gefühl für das Laufzeitverhalten vermittelt. Annahme: 1 Schritt dauert $1 \mu{}s = 0.000001 \text{s}$. Dann ergeben sich für die als Spalten aufgetragenen Datenmengen jeweils die folgenden Laufzeiten für die verschiedenen Laufzeitverhalten:

Tabelle 6.1: Vergleich von Laufzeitverhalten

Bei einem Algorithmus der Klasse $\mathcal{O}(2^n)$ wächst die Laufzeit um den Faktor 2, wenn auch nur ein Datenwert mehr zu verarbeiten ist. Wächst $n$ um $10$ benötigen Sie bereits einen rund 1000-fach schnelleren Computer um die Datenmenge in der gleichen Zeit verarbeiten zu können wie die vorherige Datenmenge.

Analoge Aussagen sind bezüglich des benötigten Speicherbedarfs möglich. Auch hierbei zählen wir nicht die konkrete Anzahl Bytes, sondern betrachten lediglich das Wachstum des Platzbedarfs an Speicherplätzen in Abhängigkeit von der Eingabegröße.

Aussagen über Laufzeit und Platzbedarf beziehen sich auf:

• Best Case: günstigster Fall
• Average Case: im Mittel
• Worst Case: ungünstigster Fall

Im folgenden betrachten wir einige Beispiele, die Ihnen ein Gefühl für die $\mathcal{O}$-Analyse vermitteln. Wir betrachten lediglich Code-Ausschnitte, davon ausgehend, es handle sich bei den Variablen um ganze Zahlen beziehungsweise Arrays von ganzen Zahlen.

Minimum-Suche in einem Array

min = a[0];
for (i = 1; i < n; i++)
    if(a[i] < min) min = a[i];

Unabhängig davon, das Minimum vielleicht schon im ersten Schritt gefunden zu haben, muss das gesamte Array untersucht werden, um sicher sein zu können, das Minimum der Daten im Array gefunden zu haben. Die Laufzeit beträgt $\mathcal{O(n)}$ für den schlechtesten, den mittleren und den günstigsten Fall.

Suche nach mehrfach vorkommenden Werten in einem Array

hit = 0;
for (i = 1; i < n-1; i++)
    for (j = i+1; j < n; j++)
        if(a[i] == a[j]) hit++;

Laufzeit: $(n\cdot(n-1))/2$ Schritte für $n$ Daten, also $\Rightarrow \mathcal{O}(n^2)$.

Zwei ineinander geschachtelte Schleifen bedeuten fast immer $n^2$.

Summe der Elemente einer quadratischen Matrix

Achtung: Stolperfalle

1total = 0;
2for (i = 1; i < n; i++)
3    for (j = 0; j < n; j++)
4        total += a[i][j];

Auch hier haben wir zwei ineinander geschachtelte Schleifen. Jedoch haben wir auch $n^2$ Daten.

Laufzeit: $n^2$ Schritte für $n^2$ Daten, also doch nur $\mathcal{O}(n)$.

Lineare Suche in einem Array

1i = 0;
2while ((i < n) && (a[i] != x))
3    i++;

Laufzeit: Best Case $1$ Schritt ($\mathcal{O}(1)$), Worst Case $n$ Schritte ($\mathcal{O}(n)$), Average Case $\frac{n}{2}$ Schritte, was ($\mathcal{O}(n)$) ergibt - die Halben interessieren im $\mathcal{O}$-Kalkül nicht!

Türme von Hanoi

Die Laufzeit beträgt:

Vergleichen Sie mit dem Code Hanoi.java (Listing 5.8). $f$ steht für den Aufruf der move()-Methode. Die wird in den Zeilen 14 und 16 rekursiv aufgerufen. Dazwischen, in Zeile 15 erfolgt die Ausgabe. Daraus ergibt sich $f(n-1) + f(n-1) + 1$. Das Basisfall, die Rekursionsbremse, wenn $n = 0$ ist, erfordert keinen weiteren Schritt.

Wir haben also zwei rekursive Aufrufe, in denen die Datenmenge $n$ um jeweils $1$ reduziert wird, plus einen Schritt für die Ausgabe. Eingedenk der Vergröberungen des $\mathcal{O}$-Kalküls ergibt das eine Laufzeit von $\mathcal{O}(2^n)$. Das deckt sich mit unseren Beobachtungen, die wir beim Ausführen des Programms haben machen können.

Fibonacci

Die Analyse des rekursiven Fibonacci-Algorithmus gestaltet sich geringfügig anders.

Die Laufzeit beträgt:

Wegen $n-2$ statt $n-1$, wie bei den Türmen von Hanoi, muss $f(n) \in \mathcal{O}(\alpha^2)$ liegen, mit $\alpha$ größer als $1$ und kleiner als $2$. Wir suchen also für große $n$ ein $\alpha$ für das gilt:

Teile durch $\alpha^{n-2}$:

$\Rightarrow \alpha^2 = \alpha + 1 + \frac{1}{\alpha^{n-2}}$. Für $n \rightarrow \infty$ und $\alpha > 1$ geht $\frac{1}{\alpha^{n-2}} \rightarrow 0$.
$\Rightarrow \alpha^2 = \alpha + 1 \Rightarrow \alpha = \frac{1+\sqrt{5}}{2} \approx 1.61803$

Das rekursive Fibonacci-Programm hat eine Laufzeit von $\mathcal{O}(1.62^n)$. Dabei ist $n$, wie bei den Türmen von Hanoi, der Wert der Eingabe, nicht seine Länge!

Zum Vergleich lohnt es sich, sich einmal konkret anzusehen, worin der Unterschied zwischen $2^n$ und $1.62^n$ besteht. Für $n=20$ ist $2^n$ rund eine Million, $1.62^{20}$ beträgt dagegen nur rund $15,000$. - Der Unterschied ist gewaltig!

Korrektheit und Terminierung

Durch Testen kann nachgewiesen werden, dass sich ein Programm für endlich viele Eingaben korrekt verhält. Durch eine Verifikation kann nachgewiesen werden, dass sich ein Programm für alle Eingaben korrekt verhält.

Bei der Zusicherungsmethode sind zwischen den Statements sogenannte Zusicherungen eingestreut, die eine Aussage über die aktuellen Beziehungen zwischen den Variablen treffen. Neben der assert-Anweisung in Java, die mit -ea in der JVM aktiviert werden muss, ist es sicherlich am einfachsten, diese Zusagen nur theoretisch durchzuspielen. Das geht mit Papier und Bleistift oder entsprechenden Kommentaren im Code. Beispiel:

// $i > 0 \land z = i^2$

Aus einer Zusicherung und der folgenden Anweisung lässt sich dann eine weitere Zusicherung ableiten:

i = i-1
// $i \geq 0 \land z = (i+1)^2$

Bei einer Schleife wird die Zusicherung $P$, die vor Eintritt und vor Austritt gilt, die Schleifeninvariante genannt.

// $P$
while($Q$) {
// $P \land Q$
...
// $P$
}
// $P \land \neg Q$

Beginnend mit einer ersten, offensichtlich richtigen Zusicherung, lässt sich als letzte Zusicherung eine Aussage über das berechnete Ergebnis ableiten (partielle Korrektheit).

Zusammen mit dem Nachweis der Terminierung ergibt sich dann die totale Korrektheit. - Auf Beispiele verzichte ich hier. Das wissen, dass in der Informatik so verfahren wird, sollte jedoch bei jedem Seminarteilnehmer vorhanden sein. Wenn Sie Informatik studieren oder beabsichtigen es zu tun, werden Sie das Thema in Ihren Vorlesungen eingehend behandeln. In der Praxis gibt man sich in der Regel mit Tests zufrieden. Zahlreiche Frameworks unterstützen das Testen.

Halteproblem

Behauptung: Es gibt kein Programm, welches in der Lage ist zu entscheiden, ob ein gegebenes Programm, angesetzt auf eine gegebene Eingabe, anhält.

Beweis durch Widerspruch

Annahme: Es gibt eine Methode checkTermination(). Diese Methode sei in einer Klasse TerminationTest implementiert, die uns im Binärcode zur Verfügung steht.

public class TerminationTest {
    public static boolean checkTermination(char[] code, char[] input) {
        // liefert true, falls das durch die Zeichenkette code 
        // dargestellte Programm bei den durch die Zeichenkette
        // input dargestellten Eingaben anhält, false sonst

        ... // hier passiert irgendwas Magisches!
    }
}

Die Implementierung der Klasse kennen wir nicht. Gar nicht dumm, schreiben wir das folgende Java-Programm (Battle.java), um die Klasse TerminationTest „herauszufordern“:

import de.pakad.udemy.StdIn

public class Battle {
    public static void main(String[] args) {
        char[] code = StdIn.readChars();
        if (TerminationTest.checkTermination(code, code))
            while (true)
                ;  // Endlosschleife mit leerer Anweisung
    }
}

Unser Programm sieht seltsam aus, stellt aber, wenn die Klasse TerminationTest vorhanden ist, validen Java-Code dar. Wir setzen unser Programm auf den eigenen Quellcode an.

$ java Battle < Battle.java    

Das ist kein üblicher Fall, aber machbar. Wenn die Klasse TerminationTest hält, was sie verspricht, kann unser Experiment zwei mögliche Ausgänge haben:

1. Fall: checkTermination() kommt zum Ergebnis false. D. h., Battle auf sich selbst angesetzt hält nicht an. Beobachtung: Battle hält an, weil die while-Schleife in diesem Fall nicht betreten wird. $\Rightarrow$ Widerspruch!
2. Fall: checkTermination() kommt zum Ergebnis true. D. h., Battle auf sich selbst angesetzt hält an. Beobachtung: Battle hält nicht an, weil die while-Schleife in diesem Fall betreten wird. $\Rightarrow$ Widerspruch!

Formal handelt es sich hierbei um einen Widerspruchsbeweis: Wir nehmen an, dass eine bestimmte Eigenschaft gilt, und zeigen, dass diese Annahme zu einem logischen Widerspruch führt.

Schlussfolgerung: Eine Methode checkTermination() kann es nicht geben! - Das mag frustrierend sein, weil es bedeutet, dass wir uns selbst um die Nachweise von Korrektheit und Terminierung kümmern müssen. Auf der anderen Seite können wir als Informatiker nicht durch Programme wegrationalisiert werden, wodurch wir auch morgen noch unser Brot verdienen können!