Bisher wurden sowohl eher informelle als auch formale Beschreibungsmethoden für Algorithmen eingeführt und der Leser hat bereits einige Erfahrungen mit der Programmierung in Java gesammelt. Ziel dieses Kapitels ist es, einige Eigenschaften von Algorithmen und damit auch von Programmen zu betrachten.
Fragestellungen betreffend Eigenschaften von Algorithmen
In Abschnitt 7.1 beschäftigt uns die Frage, welche Leistungen Algorithmen prinzipiell erbringen können. Gibt es für jedes Problem auch einen Lösungsalgorithmus – muss dieser gegebenenfalls nur noch gefunden werden? Oder gibt es Fragestellungen, die sich der algorithmischen Lösbarkeit prinzipiell entziehen?
Im folgenden Abschnitt 7.2 geht es dann um die Korrektheit von Algorithmen und damit von Programmen. Kann man ein Programm zertifizieren, also gewisse Eigenschaften garantieren? Wie kann man nachweisen, dass ein Programm tatsächlich das tut, was es soll?
Nach der Behandlung der Korrektheit beschäftigt sich Abschnitt 7.3 dann mit einem anderen Aspekt der Güte eines Algorithmus, nämlich mit der Effizienz bzw. Komplexität. Grob gesprochen geht es darum, wie schnell ein Algorithmus ein Problem, beispielsweise das Sortieren einer Liste, in Abhängigkeit von der Eingabegröße lösen kann. Hier geht es dann sowohl um die Unterscheidung »schneller« und »langsamer« Lösungen desselben Problems als auch um prinzipielle Schranken für den Zeitbedarf der Lösung gewisser Probleme.
Gibt es Problemstellungen, für die es keinen Algorithmus gibt, der sie löst? Eine auf den ersten Blick schwierige Frage – man weiß ja in einem konkreten Fall, in dem man keine Lösung gefunden hat, nicht, ob es nicht doch eine gibt, die man nur noch nicht entdeckt hat. Hier verhält es sich ähnlich wie bei mathematischen Sätzen, die oft Jahrzehnte als Problem formuliert waren, bevor ein erster Beweis geführt werden konnte.
Wir gehen daher das Problem von einer anderen Seite her an, bevor wir uns auf die Suche nach konkreten nichtberechenbaren Fragestellungen machen. Hierzu überlegen wir uns zuerst, wie viele Algorithmen es denn überhaupt geben kann.
Um über die Berechenbarkeit von Problemstellungen Aussagen treffen zu können, konkretisieren wir die Fragestellung derart, dass wir die Frage betrachten, welche mathematischen Funktionen sich überhaupt durch Algorithmen – seien es applikative, imperative oder andere – berechnen lassen. Gibt es also mathematische Funktionen, die sich nicht durch irgendeinen Algorithmus berechnen lassen?
Wir können aus den geforderten Basiseigenschaften von Algorithmen schließen, dass dies tatsächlich der Fall sein muss. Wir benutzen hierzu nur eine – sicherlich unabdingbare – Eigenschaft eines jeden Algorithmus, nämlich:
Jeder Algorithmus lässt sich durch einen endlichen Text über einem festen, endlichen Alphabet beschreiben.
Endliche Texte über einem Alphabet
Wir beginnen damit, derartige Texte mathematisch exakt zu definieren. Sei A = {a1, …, an} ein Alphabet mit der alphabetischen Ordnung a1 < a2 < … < an. Mit A* bezeichnen wir die Menge der Texte (auch Zeichenketten, endliche Folgen, Worte genannt) über A :
A* = {ε, a1, …, an, a1a1, a1a2, …, a5a3a3a1a5a2, …}
Hierbei ist ε der leere Text der Länge 0.
Wir können die Texte in A* nun in einer festen Ordnung auflisten, und zwar
b1b2 … bl < c1c2 … cl
gilt genau dann, wenn
|
b1 < c1 |
∨ |
(b1 = c1 ∧ b2 < c2) |
∨ |
(b1 = c1 ∧ b2 = c2 ∧ b3 < c3) |
… |
|
∧ |
(b1 = c1 ∧ … ∧ bl−1 = cl−1 ∧ bl < cl) |
gilt.
Hierdurch ist eine Ordnung auf A* eindeutig bestimmt, so dass wir von dem ersten, zweiten, dritten etc. Text über A (gemäß dieser Ordnung) reden können. Die derart definierte Ordnung der Texte fester Länge kann auch auf Texte unterschiedliche Länge erweitert werden und ist uns als lexikographische Ordnung etwa aus der Sortierung von Namen etwa in Telefonbüchern vertraut.
Aus der Existenz dieser lexikographischen Ordnung folgt eine mathematische Charakterisierung der Anzahl der Texte:
Die Menge A* aller Texte ist abzählbar.
Die Anzahl der Texte über einem festen Alphabet entspricht somit der Anzahl der natürlichen Zahlen. Abzählbarkeit bedeutet, dass man die Menge A* der Reihe nach durchnummerieren kann, sie also wie in einem Kinderreim »abzählen« kann. Mathematisch entspricht eine derartige Abzählung einer bijektiven Funktion von A* auf die natürlichen Zahlen.
Da es nicht mehr berechenbare Funktionen als sie berechnende Algorithmen und nicht mehr Algorithmen als sie beschreibende Texte geben kann, gilt offenbar auch folgende Aussage:
Die Menge der durch Algorithmen definierten berechenbaren Funktionen ist abzählbar.
Nicht jeder Text in A* definiert einen Algorithmus, der eine Funktion berechnet – aber es kann auch nicht mehr berechnende Algorithmen als Texte geben.
Betrachten wir nun speziell einstellige Funktionen auf 
, f : → . Wie bewiesen, gibt es nur abzählbar viele solcher berechenbaren Funktionen. Funktionen insgesamt gibt es jedoch weit mehr, wie der folgende Satz zeigt:
Die Menge F = {f | f : → } der einstelligen Funktionen auf ist überabzählbar.
Beweis: Wir nehmen an, F sei abzählbar, so dass wir nun alle f ∊ F auflisten können, F = {f0, f1, …}, d.h., jedes f hat eine Nummer i in dieser Folge. Sei nun g : → definiert durch
g(x) = fabs(x)(x) + 1
Dann ist für i = 1, 2, …, g(i) ≠ fi(i), also ist für alle i = 1, 2, … immer g ≠ fi. Die Funktion g kommt demnach in der obigen Folge nicht vor. Offensichtlich ist g aber eine einstellige Funktion auf und müsste somit in der obigen Folge aller dieser Funktionen vorkommen. Der Widerspruch lässt sich nur lösen, wenn wir die Annahme fallen lassen, F sei abzählbar.
Berechenbare Funktionen sind also unter allen Funktionen genauso »seltene« Ausnahmen wie ganze (oder natürliche oder rationale) Zahlen unter den reellen.
Cantor’sches Diagonalverfahren
Die obige Beweismethode ist unter dem Namen »Cantor’sches Diagonalverfahren« bekannt. Der Begriff Diagonalverfahren kommt von der grafischen Darstellung der fi(j) in einer (i, j)-Matrix – der Beweis konstruiert jeweils Unterschiede entlang der Diagonalen (also für i = j). Auf ähnliche Weise hat Cantor erstmals bewiesen, dass die reellen Zahlen überabzählbar sind.
Nachdem wir wissen, dass berechenbare Funktionen eher seltene Ausnahmen sind, ist die Frage nahe liegend, ob sich nichtberechenbare Funktionen konkret angeben lassen. Um zu beweisen, dass eine gegebene Funktion berechenbar ist, braucht man nur einen Algorithmus anzugeben, der sie berechnet. So schwierig dies im Einzelfall sein mag, so ist es doch prinzipiell schwieriger zu beweisen, dass eine gegebene Funktion nicht berechenbar ist. Dieses erfordert nämlich eine Beweisführung über alle denkbaren und möglichen Algorithmen!
Derartige Ergebnisse über Algorithmen lassen sich nur gewinnen, wenn man den Begriff des Algorithmus mit hinreichender mathematischer Genauigkeit definiert, wie dies im vorigen Kapitel geschah.
Nun kehren wir zu dem Problem zurück, eine nichtberechenbare Funktion konkret anzugeben. Wir benutzen dazu ein beliebiges Algorithmenmodell, welches folgenden Kriterien genügt:
Durch diese Festlegungen können Algorithmentexte wiederum als Eingaben für Algorithmen genommen werden. Diese Eigenschaft ist wichtig für die folgenden Betrachtungen.
Als Beispiel lassen sich Markov-Algorithmen leicht als Text über einem geeigneten Alphabet A kodieren, in dem auch die Eingabe- und Ausgabewerte kodiert werden können.
Gödelisierung
Alternativ kann man statt Algorithmen auf A* auch Algorithmen über den natürlichen Zahlen betrachten. Hierbei müssen dann allerdings auch die Algorithmentexte als Zahlen verschlüsselt werden. Kodierungen von Algorithmen durch natürliche Zahlen gehen auf K. Gödel (1931) zurück. Man spricht daher bei dieser Variante auch von »Gödelisierung«.
Vor der eigentlichen Konstruktion einer konkreten nichtberechenbaren Funktion legen wir einige formale Konzepte im Zusammenhang mit den betrachteten Algorithmen fest.
Sei x ∊ A* ein beliebiger Text. Dann bezeichnet ϕx die vom Algorithmus mit Text x berechnete Funktion. Ist x kein sinnvoller Algorithmentext, so sei ϕx überall undefiniert.
Natürlich sind die meisten Texte in A* keine sinnvollen Algorithmentexte – dies ist aber für die folgenden Betrachtungen nicht relevant.
Sei f : A* → A* eine partielle Funktion. Dann ist
dom f := {x ∊ A* | f(x) ist definiert}
der Urbildbereich von f (dom für »domain«).
Der Urbildbereich einer Funktion gibt uns also genau diejenigen Eingabewerte, bei der die Funktion einen Wert berechnet. Anders formuliert: Für alle Werte außerhalb des Urbildbereichs hält der Algorithmus nicht.
Nun sind wir endlich in der Lage, eine nichtberechenbare Funktion konkret anzugeben. Dazu sei a ∊ A ein fest gewählter Buchstabe.
Die (totale) Funktion h : A* → A*,
ist nicht berechenbar.
Die Werte ε, also das leere Wort, und a sind dabei willkürlich gewählt – wichtig ist, dass es sich um zwei unterschiedliche Werte aus A* handelt, die die Rolle von true und false übernehmen können.
Spezielles Halteproblem
Die obige Funktion h ist mathematischer Ausdruck des Spezialfalls eines recht anschaulichen Problems, des sogenannten Halteproblems. Die Funktion h entscheidet durch die Ausgaben ε oder a, ob x ∊ dom ϕx ist oder nicht. Nun bedeutet y ∊ dom ϕx, dass ϕx(y) definiert ist, und dies wiederum heißt, dass der Algorithmus mit Text x bei Eingabe von y irgendwann anhält. Betrachtet wird nun der Fall x = y, also die Anwendung eines Algorithmus auf die eigene Beschreibung. Die Funktion h drückt also die Frage aus:
»Hält ein Algorithmus irgendwann an, wenn man ihm seinen eigenen Text eingibt?«
Diese Frage ist auch als spezielles Halteproblem bekannt. Da die Funktion h total ist, ist sie für alle Texte von Algorithmen definiert und ihre Berechnung würde daher in allen Fällen terminieren. Diese Fragestellung sieht auf den ersten Blick etwas esoterisch aus. Ein Compiler für Java kann aber durchaus in Java programmiert sein – ein Programm, das seinen eigenen Text als Eingabe verarbeitet, ist also durchaus nicht ungewöhnlich.
Probleme, deren Entscheidungsfunktion nicht berechenbar ist, nennt man nichtentscheidbar. Es gibt eine große Fülle nichtentscheidbarer Probleme, von denen wir einige genauer betrachten werden. Das Problem x ∊ dom ϕx ist ein spezielles Entscheidungsproblem, auch Selbstanwendungsproblem oder spezielles Halteproblem genannt. Das Selbstanwendungsproblem ist nun gerade eines dieser nichtentscheidbaren Probleme.
Allgemeines Halteproblem
Um die Nichtentscheidbarkeit des speziellen Halteproblems zu zeigen, betrachten wir zuerst das allgemeine Halteproblem. Das allgemeine Halteproblem ist y ∊ dom ϕx, also:
»Hält Algorithmus x bei der Eingabe von y?«
Beweisen wollen wir nun die folgende Aussage:
Das allgemeine Halteproblem ist nichtentscheidbar.
Beweis: Gäbe es einen Entscheidungsalgorithmus für y ∊ dom ϕx, so könnte man damit auch speziell x ∊ dom ϕx entscheiden.
Bemerkung: So einfach dieser Beweis erscheint, er zeigt ein typisches Grundmuster, nämlich »Reduktion auf ein als nichtentscheidbar bewiesenes Problem«. Fast alle Nichtentscheidbarkeitsbeweise sind so konstruiert: »Wäre das (neue) Problem Y entscheidbar, so auch das (alte) Problem X«. Das Halteproblem spielt hierbei die Rolle einer Wurzel, auf die letzten Endes alle Nichtentscheidbarkeitsprobleme reduziert werden.
Wir haben uns bisher um einen wirklichen Beweis gedrückt – Satz 7.4 wurde ja noch gar nicht bewiesen und damit hängt der Beweis von Satz 7.5 noch genauso in der Luft. Diesen Beweis müssen wir jetzt natürlich nachholen.
Wegen der grundlegenden Bedeutung des Halteproblems für die Theorie der Entscheidbarkeit wollen wir zunächst einen »anschaulichen« Beweis für seine Nichtentscheidbarkeit liefern.
Angenommen, wir hätten eine Maschine (Algorithmus) STOP mit zwei Eingaben, nämlich einem Algorithmentext x und einer Eingabe y für x, sowie zwei Ausgaben:
JA: x stoppt bei Eingabe von y
NEIN: x stoppt nicht bei Eingabe von y
In Abbildung 7–1 wird diese Maschine grafisch dargestellt.
Abb. 7–1 Die Maschine STOP
Mit dieser Maschine STOP könnten wir dann eine neue Maschine SELTSAM konstruieren, die in Abbildung 7–2 dargestellt ist.
Abb. 7–2 Die Maschine SELTSAM
Bei Eingabe von x wird getestet, ob x bei Eingabe von x stoppt. Im JA-Fall wird in eine Endlosschleife gegangen. Im NEIN-Fall hält SELTSAM an mit der Anzeige OK. Eine derartige Konstruktion ist in jedem der bisher betrachteten Algorithmenmodelle leicht durchführbar.
Nun geben wir den Algorithmentext von SELTSAM als Eingabe für sich selbst ein und fragen:
Hält SELTSAM bei der Eingabe von SELTSAM?
Bei genauerer Betrachtung kommen wir zu folgenden Antworten:
Diese Widersprüche folgen allein aus der Annahme, dass eine STOP-Maschine existiert, was daher verneint werden muss.
Auch wenn diese Beweisführung für das intuitive Verständnis ausreicht, wollen wir nun doch der Vollständigkeit halber einen mathematischen Beweis »nachschieben«.
Beweis der Nichtberechenbarkeit des speziellen Halteproblems
Beweis: (formaler Beweis von Satz 7.4): Wir nehmen an, die Funktion h : A* → A* mit
sei berechenbar. Dann ist aufgrund der Church’schen These auch die Funktion g : A* → A*
berechenbar, da eine derartige Fallunterscheidung in den uns bekannten Algorithmenmodellen leicht berechnet werden kann.
Nun ist sicherlich aufgrund der Definition g(x)≠ ϕx(x) für alle x ∊ A*. Da g berechenbar ist, gibt es einen Algorithmus mit einem Text y ∊ A*, der g berechnet, d.h., es gibt ein y mit g = ϕy. Damit folgt nun:
ϕy(y) = g(y) ≠ ϕy(y)
Dies ist offenbar ein Widerspruch, der sich nur dadurch lösen lässt, dass wir die Annahme aufgeben, h sei berechenbar.
Dies ist übrigens wiederum ein Diagonalbeweis.
Das Halteproblem ist ein Beispiel für ein semantisches Problem von Algorithmen, nämlich ein Problem der Art:
Kann man anhand eines Programmtextes (Syntax) entscheiden, ob die berechnete Funktion (Semantik) eine bestimmte Eigenschaft hat?
Beim Halteproblem ist dies die Eigenschaft, ob die berechnete Funktion an einer bestimmten Stelle definiert ist. Wie steht es nun mit anderen semantischen Eigenschaften von Algorithmen?
Aus einem grundlegenden Satz der Algorithmentheorie (Satz von Rice) folgt die folgende bemerkenswerte Aussage:
Jede nichttriviale semantische Eigenschaft von Algorithmen ist nichtentscheidbar.
Dabei ist eine Eigenschaft genau dann trivial, wenn entweder jede oder keine berechnete Funktion sie hat. Nichttriviale semantische Eigenschaften sind demnach solche, die manche berechnete Funktionen haben und manche nicht.
Nichtentscheidbare semantische Eigenschaften von Algorithmen
Nicht entscheidbar sind also u.a. die folgenden Probleme:
Diese Ergebnisse bedeuten nicht, dass man solche Fragen nicht im Einzelfall entscheiden könnte! Dies ist durchaus möglich. So behandeln wir z.B. im folgenden Abschnitt 7.2 das Problem, die Korrektheit von Algorithmen nachzuweisen. Es ist jedoch prinzipiell unmöglich, eine allgemeine Methode hierfür zu finden, also z.B. einen Algorithmus, der die Korrektheit aller Algorithmen nachweist (und damit auch seine eigene!).
Man könnte nun den Eindruck gewinnen, dass die Nichtentscheidbarkeit nur semantische, eher »esoterische« Probleme betrifft. Im folgenden Abschnitt werden wir sehen, dass auch sehr konkrete und einfach klingende Probleme nichtentscheidbar sein können.
Post’sches Korrespondenzproblem
Ein besonders einfaches und verblüffendes nichtentscheidbares Problem ist das sogenannte Post’sche Korrespondenzproblem (E. Post): Gegeben seien ein Alphabet A und zwei gleich lange Listen von Worten über A:
α |
= |
(α1, α2, …, αn) |
β |
= |
(β1, β2, …, βn) |
wobei αi, βi ∊ A+ = A* − {ε} und n ≥ 1. Das Problem besteht nun darin, eine »Korrespondenz« zu finden, d.h. eine endliche Folge (i1, i2. …, ik), ij ∊ {1, …, n} für j = 1, 2, …, k, so dass gilt:
αi1 αi2 … αik = βi1 βi2 … βik
Die folgenden zwei Beispiele erläutern dies näher.
Wir betrachten ein Post’sches Korrespondenzproblem über einem zweielementigen Alphabet mit Wortlisten der Länge 3.
A = { 0, 1 } |
α = (1, 1 0 1 1 1, 1 0) |
|
β = (1 1 1, 1 0, 0) |
Lösung
Dieses Post’sche Korrespondenzproblem besitzt eine Lösung, nämlich die Korrespondenz (2,1,1,3):
1 0 1 1 1 . 1 . 1 . 1 0 = 1 0 . 1 1 1 . 1 1 1 . 0
Mit dem Finden einer Lösung hat man natürlich immer gleich unendlich viele Lösungen gefunden, indem man die Lösung iteriert.
Der positive Schluss kann einfach durch Angabe einer Lösung erfolgen. Der Nachweis des Fehlens einer Lösung muss mittels eines Beweises über alle möglichen Korrespondenzlisten erbracht werden.
Wir betrachten wieder ein Post’sches Korrespondenzproblem über einem zweielementigen Alphabet mit Wortlisten der Länge 3.
A = { 0, 1 } |
α = (1 0, 0 1 1, 1 0 1) |
|
β = (1 0 1, 1 1, 0 1 1) |
Dieses Post’sche Korrespondenzproblem besitzt keine Lösung. Gäbe es nämlich eine, so müsste sie mit dem Index 1 anfangen:
Als zweites müsste nun ein Index i mit αi = 1 … gewählt werden, also 1 oder 3. Aber (1, 1, …) ergibt
1 0 1 0 … ≠ = 1 0 1 1 0 1 …
und (1, 3, …) ergibt
Die gleiche Überlegung wie oben führt nun dazu, dass wieder der Index 3 gewählt werden muss. (1, 3, 3, …) ergibt
Wieder müsste 3 gewählt werden usw. Es ist nun zu sehen, dass niemals eine Lösung entstehen kann, da die rechte Seite der linken immer um eine Stelle voraus ist.
Während wir in diesen Beispielen die Lösbarkeit entscheiden können, ist das allgemeine Problem, nämlich zu entscheiden, ob eine Lösung für ein gegebenes Post’sches Korrespondenzproblem über einem Alphabet mit mindestens zwei Buchstaben existiert, nicht entscheidbar. Auch der Beweis dieser Aussage wird auf eine Kodierung eines speziellen Halteproblems als Post’sches Korrespondenzproblem zurückgeführt.
Wir überlassen Einzelheiten und den Beweis dieser Aussage Lehrbüchern der theoretischen Informatik – hier war es nur unser Ziel, zu zeigen, wie verblüffend einfach nichtentscheidbare Fragestellungen sein können.
Korrektheit von Algorithmen
Es ist ganz wesentlich, dass Algorithmen, die wir für eine bestimmte Aufgabe entworfen haben, korrekt sind, d.h., dass sie sich genauso verhalten, wie wir es beabsichtigt hatten. Bei einigen hochsensiblen und kritischen Anwendungen (z.B. in der medizinischen Informatik, bei der Steuerung von Robotern und Fahrzeugen, aber auch in der Baustatik) können durch nicht korrekte Algorithmen hervorgerufene Fehlfunktionen schwere Schäden anrichten oder gar Katastrophen auslösen.
Nun haben wir im vorherigen Abschnitt gesehen, dass die Korrektheit von Programmen im Allgemeinen nicht entscheidbar ist. In vielen Anwendungsfällen wird man mit pragmatischem Austesten eine hinreichende Sicherheit erreichen können. Will man jedoch die Korrektheit eines Algorithmus mit mathematischer Exaktheit und Strenge nachweisen, so ist man auf eine Beweisführung im Einzelfall angewiesen. Dies ist nicht nur bei sicherheitskritischen Anwendungen angezeigt, sondern z.B. auch bei Standardalgorithmen, die hardwaremäßig, etwa als VLSI-Chip, realisiert und in großer Serie produziert werden sollen. Ein Beispiel hierfür sind Kommunikationsprotokolle. Ein großer Aufwand bei dem Nachweis der Korrektheit lohnt sich hier, da Fehler große wirtschaftliche Verluste bewirken.
In diesem Abschnitt wollen wir einige grundlegende Konzepte und Vorgehensweisen für Korrektheitsbeweise für Algorithmen erörtern. Die Problematik kann hier nicht tief und ausführlich abgehandelt werden. Wir beschränken uns darauf, Problematik und Vorgehensweise anhand einfacher Beispiele zu demonstrieren.
Relative Korrektheit
Der Nachweis der Korrektheit eines Algorithmus bezieht sich immer auf eine Spezifikation dessen, was er tun soll. Insofern handelt es sich immer um eine relative Korrektheit. Ein Algorithmus kann also nicht als korrekt an sich bewiesen werden, sondern nur in Bezug auf eine Spezifikation des beabsichtigten Verhaltens.
Verifikation
Der Nachweis der Korrektheit kann auf verschiedene Arten erfolgen. Unter der Verifikation verstehen wir einen formalen, mathematisch rigiden Beweis, dass ein Algorithmus korrekt bezüglich einer Spezifikation ist. Verifikation erfordert eine Formalisierung der Algorithmensprache sowie eine Spezifikation in einem mathematisch exakten Formalismus. Unter Validation verstehen wir einen nichtformalen und in der Regel nicht hundertprozentig sicheren Nachweis der Korrektheit, wie er etwa durch systematisches Testen erfolgen kann.
Die für die Korrektheit eines Algorithmus wichtigen Begriffe können wir also wie folgt zusammenfassen:
Große Teilgebiete der Softwaretechnik beschäftigen sich mit Spezifikationssprachen, semiautomatischer und automatischer Verifikation und mit Testverfahren. Wir können hier nur exemplarisch einige Grundprinzipien anhand von Beispielen erläutern.
Vor- und Nachbedingungen
Wir behandeln zunächst die imperativen Algorithmen, die ja vielen kommerziellen Programmiersprachen zugrunde liegen. Eine verbreitete Methode, die gewünschten Eigenschaften von Algorithmen zu spezifizieren und die gerade für imperative Algorithmen gut eingesetzt werden kann, ist die Angabe von Vor- und Nachbedingungen :
{ VOR }ANW{ NACH }
VOR und NACH sind dabei Aussagen über den Zustand vor bzw. nach Ausführung der Anweisung ANW. Der Bezug auf den Zustand verdeutlicht, dass diese Spezifikationsform gerade für imperative Algorithmen geeignet ist, deren Semantik von uns ja als Zustandstransformation definiert wurde. Genauer bedeutet diese Aussage:
Semantik von Vor- und Nachbedingungen
Gilt die Bedingung VOR unmittelbar vor Ausführung von ANW und terminiert ANW, so gilt die Bedingung NACH unmittelbar nach Ausführung von ANW.
Terminiert die Anweisungsfolge ANW nicht, so ist eine derartige Bedingung also trivialerweise wahr, wie auch immer VOR und NACH aussehen.
Entsprechend ist die Bedingung auch trivialerweise wahr, wenn die Vorbedingung VOR nicht gilt, gleichgültig, ob ANW terminiert oder nicht und ob NACH gilt oder nicht.
Vor- und Nachbedingungen und imperative Algorithmen
Vor- und Nachbedingungen basieren auf dem Konzept eines Zustands, der durch eine Anweisung verändert wird. Der Zustand ist bei imperativen Algorithmen über die Werte der Variablen bestimmt. Vor- und Nachbedingungen können somit als logische Formeln der Prädikatenlogik unter Verwendung dieser Variablen notiert werden. Man muss dabei beachten, dass diese Variablen in der Vorbedingung einen anderen Wert annehmen können als in der Nachbedingung, da ihr Wert durch eine Wertzuweisung modifiziert worden sein kann. Wir werden dieses Konzept nun an einigen Beispielen erläutern.
Wir betrachten Anweisungen über Variablen, die Werte aus dem Bereich der ganzen Zahlen Z annehmen.
{X = 0}X := X + 1{X = 1 }
ist wahr. Diese Spezifikation entspricht genau der Bedeutung der Wertzuweisung in imperativen Algorithmen.
{true}X := Y{X = Y}
ist ebenfalls wahr.
{Y = a}X := Y{X = a ∧ Y = a}
ist wahr für alle a ∊ .
{X = a ∧ Y = b ∧ a ≠ b}X := Y; Y := X{X = b ∧ Y = a}
ist falsch für alle a, b ∊ , da nach dem ersten Schritt beide Variablen den Wert b angenommen haben (ein typischer Anfängerprogrammierfehler beim Wertetausch).
{X = a ∧ Y = b}Z := X; X := Y; Y := Z{X = b ∧ Y = a}
ist wahr für alle a, b ∊ – dies ist die korrekte Realisierung des Wertetauschs.
{false}ANW{NACH}
ist wahr für alle ANW und NACH, da eine falsche Vorbedingung die Implikation immer erfüllt.
{true}ANW{false}
ist aufgrund unserer Definition genau dann wahr, wenn ANW nicht terminiert.
{X = a}whileX ≠ 0 do X := X − 1od{X = 0}
ist wahr für alle a ∊ – insbesondere auch für a < 0, da dann die while-Schleife nicht terminiert.
Bei der Korrektheit imperativer Algorithmen bzgl. gegebener Vor- und Nachbedingungen unterscheidet man zwischen partieller und totaler Korrektheit. Zur Definition dieser Begriffe sei ein Algorithmus PROG gegeben:
PROG: |
varX,Y, ...: int; |
|
P,Q ...: bool; |
|
inputX1, …, Xn; |
|
α; |
|
outputY1, …, Ym. |
Ferner seien eine Vorbedingung VOR und eine Nachbedingung NACH für die Anweisung α von PROG gegeben. Die Vorbedingung spiegelt dabei die Belegung der Variablen mit Werten wider, während die Nachbedingung die zu beweisende Berechnung ausdrückt.
Ein Programm PROG heißt partiell korrekt bzgl. VOR und NACH gdw.
{VOR} α {NACH}
wahr ist (siehe informelle Definition der Bedeutung von Vor- und Nachbedingungen).
Totale Korrektheit
PROG heißt total korrekt bzgl. VOR und NACH gdw. PROG partiell korrekt ist bzgl. VOR und NACH, und wenn α darüber hinaus immer dann terminiert, wenn vorher VOR gilt.
Im Rahmen dieses Buches wird darauf verzichtet, ein Regelwerk zum Beweisen von Vor- und Nachbedingungen anzugeben. Es sei stattdessen auf spätere Vorlesungen und weiterführende Literatur vertröstet. Hier sei nur bemerkt, dass das Finden von geeigneten Vor- und Nachbedingungen nicht einfach ist. Für jedes Konstrukt imperativer Algorithmen muss eine Beweisvorgehensweise entwickelt werden. Wir werden dies nur für den Fall der Schleifen etwas ausführlicher demonstrieren.
Imperative Algorithmen haben vier grundlegende Anweisungstypen: Wertzuweisungen als atomare Anweisungen, Sequenz, Selektion und Iteration. Wir werden für diese vier Anweisungsmuster kurz erläutern, wie bei einem Beweis vorgegangen werden muss – auf eine intensive Diskussion werden wir wie bereits erwähnt verzichten und stattdessen anschließend zwei Beispiele vorstellen.
Transformation bei Wertzuweisung
Für eine atomare Anweisung X := t kann man eine Vorbedingung in eine Nachbedingung transformieren, indem jedes Auftreten des Terms t in der Vorbedingung V OR durch X ersetzt wird. So kann man etwa die folgende Bedingungen zeigen:
{3 > 0} X := 3{X > 0}
Beachten muss man dabei, dass die Variablen der Vorbedingung den alten Zustand betreffen, die der Nachbedingung den neuen. Daher kann man dieses Prinzip auch auf folgendes Beispiel übertragen, bei dem die Variable X in beiden Bedingungen auftaucht:
{X + 1 > 0} X := X + 1{X > 0}
Man kann sich die Korrektheit des Beispiels dadurch verdeutlichen, dass man die »neuen« Werte von X als X′ markiert:
{X + 1 > 0} X′ := X + 1{X′ > 0}
Die Ersetzung ist natürlich oft nicht direkt möglich, da der Term t in der Vorbedingung auftauchen muss, um eine geeignete Nachbedingung zu erzeugen. Dies kann man allerdings mittels logischer Tautologien und Umformungen erreichen. Als Beispiel tauchen in der Formel
{X > 0} X := X − 1 {X ≥ 0 }
keine geigneten Terme auf, aber nach Äquivalenzumformungen können wir trotzdem den Beweis führen:
{(X − 1) + 1 > 0} X := X − 1 {X + 1 > 0}
Hier haben wir die Äquivalenzen (X > 0) ((X − 1) + 1 > 0) und (X ≥ 0) ≡ (X + 1 > 0) ausgenutzt.
Korrektheit einer Sequenz
Besteht die Anweisung aus der Sequenz zweier Schritte, so muss man den Beweisschritt in zwei Schritte aufteilen. Um also
{VOR} α; β {NACH}
zu zeigen, müssen wir eine Zwischenbedingung MITTE finden, so dass
{VOR} α {MITTE}
und
{MITTE} β {NACH}
gezeigt werden kann.
Korrektheit einer Selektion
Bei der Beweisführung im Fall der Selektion ist eine Fallunterscheidung notwendig. Um die Formel
{VOR} if B then α else β fi {NACH}
{VOR ∧ B} β {NACH}
und
{VOR ∧ ¬B} β {NACH}
gezeigt werden. Wichtig ist also, dass die Nachbedingung gilt, egal welcher Zweig selektiert wurde.
Korrektheit einer Iteration
Erwartungsgemäß ist die Beweisführung für den Fall der Iteration aufwendiger. Um eine Bedingung über eine Schleife der Form
{ VOR }
while B do β od
{ NACH }
Schleifeninvariante
zu überprüfen, müssen wir eine sogenannte Schleifeninvariante P finden, die auch bei mehrfachen Schleifendurchläufen jeweils ihre Gültigkeit bewahrt. Im Einzelnen müssen wir dabei Folgendes prüfen:
VOR ⇒ P
gilt. Die Vorbedingung garantiert also die Gültigkeit von P beim ersten Eintritt in die Schleife.
{P ∧ B} β {P}
Der Schleifenrumpf bewahrt die Schleifeninvariante in den Fällen, in denen der Rumpf tatsächlich durchlaufen wird. Da uns nur dieser Fall interessiert, können wir für die Beweisführung annehmen, dass vor dem Eintritt in die Schleife sowohl die Schleifeninvariante als auch die Bedingung B gilt.
{P ∧ ¬B} ⇒ NACH
Die vorgestellten Beweismuster können direkt auf die entsprechenden Grundmuster in imperativen Programmiersprachen übertragen werden. Einige weitere verbreitete Konstrukte wie die case-, for- und until-Konstrukte können auf die vorgestellten vier Basismuster zurückgeführt werden.
Mehr Aufwand bedarf es, den Aufruf von Prozeduren oder exit- oder gar goto-Anweisungen in den Formalismus zu integrieren. Hier muss unter anderem der doch einfache Zustandsbegriff deutlich erweitert werden.
Um die Grundprinzipien der Verifikation von Vor- und Nachbedingungen zu zeigen, führen wir Beweise für zwei einfache Algorithmen. Der erste Beweis zeigt den Einsatz von Schleifeninvarianten an einem einfachen Beispiel.
Wir betrachten als Beispiel den Algorithmus MULT, der die Multiplikation nur mittels Addition und Subtraktion realisiert.
MULT: |
varW,X,Y,Z :int; |
|
inputX, Y |
|
Z:=0; |
|
W:=Y; |
|
whileW ≠ 0doZ:=Z+X;W:=W-1od; |
|
outputZ |
Der Schleifenrumpf sei wieder mit β bezeichnet. Die Spezifikation lautet wie folgt:
Um diese Spezifikationen beweisen zu können, benötigen wir eine Schleifeninvariante P. P muss durch den Schleifenrumpf erhalten bleiben, und bei Verlassen der Schleife (also im Fall W = 0) die Nachbedingung implizieren. Durch Nachdenken kommen wir auf die folgende Bedingung (leider gibt es kein automatisches Verfahren zur Bestimmung einer geeigneten Nachbedingung für alle Situationen):
P = (X · Y = Z + W · X)
Wir müssen nun die drei Aussagen beweisen, die die Bedeutung einer Schleifeninvariante ausmachen:
{Y ≥ 0}Z := 0; W := Y {X′ · Y′ = Z′ + W′ · X′}
Nun ersetzen wir die neuen Werte durch die alten Werte gemäß den Zuweisungen (X und Y wurden nicht verändert):
{X · Y = X′ · Y′ = Z′ + W′ · X′ = 0 + Y · X}
Dies ist sicherlich eine korrekte Aussage. P gilt also vor dem ersten Schleifendurchlauf.
{X · Y = Z + W · X ∧ W ≠ 0}
Z := Z + X; W := W − 1
{X′ · Y′ = Z′ + W′ · X′}
Wir ersetzen wieder in der Nachbedingung die als neu markierten Variablen durch ihre Werte basierend auf den Zuweisungen im Schleifenrumpf:
X · Y = X′ · Y′ |
= |
Z′ + W′ · X′ |
|
= |
(Z + X) + (W − 1) · X |
|
= |
Z + X + W · X − X |
|
= |
Z + W · X |
Der Rumpf erhält also die Schleifeninvariante P.
(P ∧ ¬B) ≡ (X · Y = Z + W · X ∧ W = 0) ≡ (X · Y = Z)
Dies beweist natürlich nur die partielle Korrektheit. Einen Beweis einer totalen Korrektheit zeigt das nächste Beispiel.
Als zweites Beispiel wird die Korrektheit des Algorithmus XYZ aus dem Beispiel 3.23 (Abschnitt 3.3, Seite 81) betrachtet. Um die Korrektheit von XYZ zu beweisen, müssen wir dessen Spezifikation kennen, die wir bisher verschwiegen haben. Tatsächlich berechnet XYZ den ganzzahligen Anteil der Quadratwurzel des Eingabewertes – eine Spezifikation, auf die man nur durch Anschauen des Algorithmentextes wahrscheinlich nicht so schnell gekommen wäre. Dies verdeutlicht erneut eine grundlegende Eigenschaft von Korrektheitsbeweisen: Es ist immer nur möglich, die relative Korrektheit betreffend einer gegebenen Spezifikation zu prüfen!
Der zu prüfende Algorithmus XYZ (vergleiche Beispiel 3.23 von Seite 81) ist wie folgt formuliert:
XYZ: |
var W,X,Y,Z : int; |
|
input X |
|
Z:=0; W:=1; Y:=1; |
|
while W ≤ X |
|
do Z:=Z+1; W:=W+Y+2; Y:=Y+2 od; |
|
output Z. |
Zu prüfen ist die Korrektheit bezüglich Vor- und Nachbedingungen, die die Eigenschaft ausdrücken, dass XYZ den ganzzahligen Anteil der Quadratwurzel von X berechnet. Seien also die Vorbedingung
VOR (X ≥ 0)
und die Nachbedingung
NACH (Z2 ≤ X < (Z + 1)2) ≡ (Z = 
)
gegeben. Wir wollen insgesamt beweisen, dass XYZ total korrekt ist bzgl. VOR und NACH. Hierzu beweisen wir in diesem Beispiel vorerst nur die partielle Korrektheit, der Beweis der Terminierung folgt in Beispiel 7.6.
Wir benutzen die folgenden Abkürzungen für Teile des Algorithmentextes:
α |
= |
(Z := 0; W := 1; Y := 1) |
β |
= |
(Z := Z + 1; W := W + Y + 2; Y := Y + 2) |
Wir benötigen wieder eine Schleifeninvariante P als »Zwischenbedingung«, von der wir zeigen, dass sie am Anfang jeden Durchlaufs durch die while-Schleife gilt und dass sie nach Ablauf der while-Schleife die Nachbedingung NACH impliziert.
P ≡ (Z2 ≤ X ∧ (Z + 1)2 = W ∧ 2Z + 1 = Y ∧ Y > 0)
Für die Schleifeninvariante müssen wir die folgenden drei Eigenschaften zeigen:
Haben wir diese drei Formeln bewiesen, so folgt daraus, dass XYZ partiell korrekt ist bzgl. VOR und NACH.
Im Einzelnen läuft der Beweis wie folgt ab:
(02 ≤ X ∧ (0 + 1)2 = 1 ∧ 2 · 0 + 1 = 1 ∧ 1 > 0)
{(Z + 1)2 = W ∧ W ≤ X} β {Z2 ≤ X}
{(Z + 1)2 = W ∧ 2Z + 1 = Y} β {W = (Z + 1)2}
Dass dies gilt, kann man sich an folgender Rechnung verdeutlichen, die Zuweisungen an Z und W im Schleifenrumpf berücksichtigt:
W = Z2 + 2 (Z − 1) + 1 + 2 = Z2 + 2Z + 1 = (Z + 1)2
{2Z + 1 = Y} β {Y = 2(Z − 1) + 1 + 2 = 2Z + 1}
{Y > 0} β {Y > 0}
Aus den vier Teilbeweisen folgt insgesamt {P ∧ W ≤ X} β {P}.
P ∧ W > X ⇒ Z2 ≤ X ∧ X < (Z + 1)2 ⇒ NACH
Damit ist die partielle Korrektheit bewiesen. Man beachte, dass hierfür die Bedingung Y > 0 nicht benötigt wurde. Sie ist erst zum Beweis der Terminierung erforderlich.
Terminierung von imperativen Algorithmen
Die Terminierung einer Schleife kann man zum Beispiel dadurch zeigen, dass man eine Folge von Werten u0u1u2u3u4 … derart konstruiert, dass Folgendes gilt:
Diese Bedingungen zusammen konstruieren eine garantiert terminierende Folge, da die Werte gegen 0 streben und bis ins Infinitesimale schrumpfende Differenzen ausgeschlossen sind. Im folgenden Beispiel zeigen wir nur den interessanten Teil der Beweisführung. Formal müssten wir die Folge der Werte von u+1 betrachten, um unserer Bedingung gerecht zu werden.
Um die Terminierung des Algorithmus XYZ aus Beispiel 7.5 zu beweisen, zeigen wir, dass für den Wert von u = X − W gilt:
Haben wir dies bewiesen, so folgt daraus, dass es nur endlich viele Schleifendurchläufe geben kann, dass XYZ also (bzgl. VOR) terminiert. Die beiden Bedingungen werden wie folgt bewiesen:
u |
= |
X − W |
u′ |
= |
X − (W + Y + 2) = X − W − Y − 2 |
Da Y > 0 ist (!), ist u′ < u.
Dies vervollständigt der Beweis der totalen Korrektheit von XYZ bzgl. VOR und NACH.
Korrektheit applikativer Algorithmen
Für den Nachweis von Eigenschaften – wie z.B. der Korrektheit – applikativer Algorithmen verwendet man typischerweise Induktionsbeweise, die der Struktur der rekursiven Funktionsdefinition folgen. Dies geschieht analog zu klassischen mathematischen Beweisen mit vollständiger Induktion und wird daher hier nicht vertieft. Stattdessen betrachten wir ein einfaches Beispiel für einen derartigen Beweis.
Wir betrachten die aus Beispiel 3.13 von Seite 69 bekannte McCarthys 91-Funktion:
f(x) =if x > 100 then x − 10 else f(f(x + 11)) fi
Unser Ziel ist es nun, zu beweisen, dass die Funktion f äquivalent zur folgenden Funktion g ist:
g(x) =if x > 100 then x − 10 else 91 fi
Es muss also gezeigt werden, dass f(x) = g(x) für alle x ∊ . Der Beweis folgt dem klassischen Muster der Beweise mit vollständiger Induktion:
Als Induktionsanfang betrachten wir die Werte über 100: Für x > 100 ist f(x) = x − 10 = g(x).
Die Induktion selbst verläuft nun »rückwärts«, d.h., wir zeigen:
Gilt f(y) = g(y) für alle y ≥ x, so gilt auch f(x − 1) = g(x − 1).
Die Induktionsannahme lautet somit wie folgt:
Es gelte f(y) = g(y) für alle y ≥ x.
Für den eigentlichen Induktionsschritt unterscheiden wir zwei Fälle:
f(x − 1) |
= |
f(f(x − 1 + 11)) |
|
= |
f(f(x + 10)) |
|
= |
f(x + 10− 10) |
|
= |
f(x) = g(x) = 91 = g(x − 1) |
Aufgrund der Induktionsannahme ist f(x + 10) = g(x + 10) = 91, also folgt:
f(x − 1) = f(91) = g(91) = 91 = g(x − 1)
Dies beweist f(x) = g(x) für alle x ∊.
Dieses Kapitel kann nur einen sehr oberflächlichen Eindruck von den Methoden vermitteln, die zur Verifikation von Algorithmen und damit von Programmen eingesetzt werden können. Allerdings sollte deutlich geworden sein, dass ein formaler Beweis der Korrektheit eines Programms möglich ist trotz der eher negativen Aussagen über die Entscheidbarkeit derartiger Fragestellungen im letzten Kapitel. Solche Beweise lassen sich aufgrund der Entscheidbarkeitsfrage nicht vollständig automatisieren, aber der Aufwand lohnt sich insbesondere bei sicherheitskritischen Anwendungen (bei der Software einer Sonde auf dem Weg zum Jupiter können wir Fehlersituationen, wie sie in verbreiteten PC-Betriebssystemen immer noch regelmäßig auftreten, sicher nicht tolerieren).
Komplexität
Für die algorithmische Lösung eines gegebenen Problems ist es unerlässlich, dass der gefundene Algorithmus das Problem korrekt löst. Darüber hinaus ist es natürlich wünschenswert, dass er dies mit möglichst geringem Aufwand tut. Manchmal ist dies auch unerlässlich – etwa beim automatischen Abschalten eines Kernkraftwerkes im Falle einer Havarie. Die Theorie der Komplexität von Algorithmen beschäftigt sich damit, gegebene Algorithmen hinsichtlich ihres Aufwandes abzuschätzen und – darüber hinaus – für gegebene Problemklassen zu bestimmen, mit welchem Mindestaufwand Probleme dieser Klasse gelöst werden können.
Aufwand der sequenziellen Suche
Die Bestimmung des Aufwandes wollen wir zunächst an einem einfachen Beispiel verdeutlichen: der sequenziellen Suche in Folgen. Gegeben seien hierzu
Gesucht wird der Index i = 1, 2, …, n, so dass b = ai ist, sofern ein solcher Index existiert. Sonst soll i = n + 1 ausgegeben werden.
Eine sehr einfache Lösung dieses Suchproblems ist die folgende (wobei standardmäßig an+1 = 0 gesetzt sei):
i := 1; while i ≤ n ∧ b ≠ ai do i := i + 1 od
Am Ende hat i den gesuchten Ausgabewert.
Der Aufwand der Suche, d.h. die Anzahl der Schritte, hängt von der Eingabe ab, d.h. von n, a1, …, an und b. Es gilt:
Erfolgreiche Suche
Erfolglose Suche
Die erste Aussage hängt noch von zu vielen Parametern ab, um aufschlussreich zu sein. Man ist bemüht, globalere Aussagen zu finden, die nur von einer einfachen Größe abhängen. Hier bietet sich die Länge n der Eingabeliste an und man beschränkt sich auf Fragen der Art:
Wir analysieren nun den Fall der erfolgreichen Suche:
zu A: Im schlechtesten Fall wird b erst im letzten Schritt gefunden, d.h. b = an. Also gilt:
S = n im schlechtesten Fall.
zu B: Um eine mittlere Anzahl von Schritten zu berechnen, muss man Annahmen über die Häufigkeit machen, mit der – bei wiederholter Verwendung des Algorithmus mit verschiedenen Eingaben – b an erster, zweiter, …, letzter Stelle gefunden wird. Wird b häufiger am Anfang der Liste gefunden, so ist die mittlere Anzahl von Suchschritten sicherlich kleiner, als wenn b häufiger am Ende der Liste gefunden wird. Als einfaches Beispiel nehmen wir die Gleichverteilung an. Läuft der Algorithmus N-mal, N ≫ 1, so wird b gleich häufig an erster, zweiter, …, letzter Stelle gefunden, also jeweils 
-mal.
Dann werden für alle N Suchvorgänge insgesamt
Schritte benötigt. Die Auswertung ergibt:
Für eine Suche werden im Mittel demnach 
Schritte benötigt, also:
im Mittel (bei Gleichverteilung)
Unser Algorithmus ist für das gestellte Problem keineswegs der schnellste, sondern eher einer der langsameren. Es gibt Algorithmen, die die Suche in Listen (oder Tabellen) mit n Einträgen unter speziellen Voraussetzungen i.W. mit einer konstanten, nicht von n abhängigen Anzahl von Schritten lösen! Die besten Suchverfahren für direkten Zugriff, die auch sequenzielle Verarbeitung in der Ordnung der Schlüssel zulassen, benötigen eine logarithmische Anzahl von Schritten, d.h. S = a · log2(b · n) + c, wobei a, b, c ∊ 
Konstanten sind. Konkrete Verfahren werden wir u.a. im Kapitel 14 kennen lernen.
Meist geht es bei der Analyse der Komplexität von Algorithmen bzw. Problemklassen darum, als Maß für den Aufwand eine Funktion
f : 
→
Problemgröße
Aufwand
anzugeben, wobei f(n) = a bedeutet: »Bei einem Problem der Größe n ist der Aufwand a«. Die Problemgröße n bezeichnet dabei in der Regel ein Maß für den Umfang einer Eingabe, z.B. die Anzahl der Elemente in einer Eingabeliste oder die Größe eines bestimmten Eingabewertes. Der »Aufwand« a ist in der Regel ein grobes Maß für die Rechenzeit, jedoch ist auch der benötigte Speicherplatz zuweilen Gegenstand der Analyse. Die Rechenzeit wird meist dadurch abgeschätzt, dass man zählt, wie häufig eine bestimmte Art von Operation ausgeführt wird, z.B. Speicherzugriffe, Multiplikationen, Additionen, Vergleiche etc. Auf diese Weise erhält man ein maschinenunabhängiges Maß für die Rechenzeit, wie wir es beispielsweise im Zusammenhang mit der Laufzeit einer abstrakten Maschine (siehe auch Definition 6.5 auf Seite 166) bereits vorgestellt haben.
Zur Illustration betrachten wir einige Beispiele. Wir benutzen dabei eine einfache for-Schleife, die folgendermaßen definiert ist:
for i := 1 to u do α od ≡
i := 1; while i ≤ u do α; i := i + 1 od
Wie oft wird die Wertzuweisung »x := x + 1« in folgenden Anweisungen ausgeführt?
1. |
x := x + 1 |
1mal |
2. |
for i := 1 to n do x := x + 1 od |
n-mal |
3. |
for i := 1 to n do |
|
|
for j := 1 to n do x := x + 1 od od |
n2-mal |
Die Aufwandsfunktion f : → lässt sich in den wenigsten Fällen exakt bestimmen. Vorherrschende Analysemethoden sind
Selbst hierfür lassen sich im Allgemeinen keine exakten Angaben machen. Man beschränkt sich dann auf »ungefähres Rechnen in Größenordnungen«. Das folgende Beispiel illustriert die Schwierigkeit von exakten Analysen, insbesondere bei Abschätzungen im Mittel, bereits in recht einfachen Fällen.
Gegeben: |
n ≥ 0, a1, …, an ∊ |
Gesucht: |
Der Index i der (ersten) größten Zahl |
|
unter a1, i = 1, …, n. |
Lösung |
max := 1; |
|
for i := 2 to n do |
|
if amax < ai then max := i fi |
|
od |
Am Ende enthält max den gesuchten Index (bzw. die Zahl 1, falls n=0 ist).
Diese gesuchte mittlere Anzahl sei Tn. Offenbar gilt: 1 ≤ Tn ≤ n.
Das heißt, dass bei N Durchläufen durch den Algorithmus, N ≫ 1, insgesamt 
-mal die Anweisung »max := i« ausgeführt wird für i = 1, …, n. Das heißt:
max := 1 wird N-mal, d.h. immer, ausgeführt
max := 2 wird 
-mal ausgeführt
etc.
Daraus folgt für die gesamte Anzahl N · Tn von Ausführungen von »max := i« (für irgendein i) bei N Durchläufen:
Damit erhalten wir 
, und dies ist Hn, die n-te harmonische Zahl. Für Hn ist keine exakte geschlossene Formel bekannt, jedoch eine ungefähre Abschätzung:
Tn = Hn ≈ ln n + γ
wobei γ = 0.57721566 … die Euler’sche Konstante ist.
Da der Aufwand schon vom Ansatz her ohnehin nur grob abgeschätzt werden kann, macht eine Feinheit wie »+γ« im obigen Beispiel nicht viel Sinn. Interessant ist lediglich, dass Tn logarithmisch von n abhängt, nicht so sehr, wie dieser Zusammenhang im Detail aussieht. Man schreibt dafür:
Tn = O(log n),
und dies bedeutet, dass Tn »von der Ordnung log n« ist, wobei multiplikative und additive Konstanten sowie die Basis des Logarithmus unspezifiziert bleiben.
Die O-Notation lässt sich mathematisch exakt definieren. Seien f, g : → gegeben.
f(n) = O(g(n)) 
∃c, n0 ∀n ≥ n0 : f(n) ≤ c · g(n)
Das heißt, dass 
für genügend große n durch eine Konstante c beschränkt ist. Anschaulich bedeutet dies, dass f »nicht stärker wächst« als g (Abbildung 7–3). Diese Begriffsbildung wendet man bei der Analyse von Algorithmen an, um Aufwandsfunktionen f : → durch Angabe einer einfachen Vergleichsfunktion g : → abzuschätzen, so dass f(n) = O(g(n)) gilt, also das Wachstum von f durch das von g beschränkt ist.
Asympotische Analyse
Man bezeichnet O(n) auch als asymptotische obere Schranke für f und die Beschreibung der Komplexität durch Angabe der Wachstumsgeschwindigkeit bzw. der Größenordnung mithilfe der O-Notation als asymptotische Analyse. Eine Asymptote ist eine Gerade, der sich eine Kurve bei deren immer größer werdender Entfernung vom Koordinatenursprung unbegrenzt nähert. Die Funktion f wächst damit asymptotisch nicht schneller als g.
Eigentlich ist die Angabe f = O(g) im mathematischen Sinn nicht exakt. Vielmehr müsste man f ∊ O(g) schreiben, um auszudrücken, dass f zur Klasse der Funktionen gehört, deren Wachstum asymptotisch durch das Wachstum von g beschränkt ist. Die Schreibweise mit dem »=« hat sich allerdings allgemein eingebürgert, so dass wir sie auch verwenden.
Abb. 7–3 Asymptotische obere Schranke: O-Notation
Da die O(g)-Notation eine obere Grenze für eine Klasse von Funktionen definiert, kann die Funktion g jeweils vereinfacht werden, indem konstante Faktoren weggelassen werden sowie nur der höchste Exponent berücksichtigt wird.
Für das Beipiel 7.9 gilt genauer
Tn |
= |
Hn = ln n + γ |
Tn |
= |
O(log n) |
Die Basis des Logarithmus ist unerheblich, da ein Basiswechsel gleichbedeutend ist mit der Multiplikation mit einer Konstanten: logb n = loga n · logb a.
Das folgende Beispiel verdeutlicht die Beschränkung auf den höchsten Exponenten einer Funktion, da immer ein c gefunden wird, so dass ab einem n0 die Funktion g(n) obere Schranke ist.
Es sei zu zeigen, dass
n2 + 3n − 3 = O(n2)
Demnach muss gelten, dass
n2 + 3n − 3 ≤ c · n2
Durch Umformen ergibt sich daraus
Diese Ungleichung wird für n ≥ n0 erfüllt, wenn man beispielsweise c = 2 und n0 = 1 einsetzt.
Einige Vergleichsfunktionen treten bei der Analyse von Algorithmen und Datenstrukturen recht häufig auf. Man spricht daher auch von Komplexitätsklassen. Die wichtigsten dieser Klassen sind in Tabelle 7–1 angegeben.
Tab. 7–1 Typische Komplexitätsklassen
O(1) |
konstanter Aufwand |
O(log n) |
logarithmischer Aufwand |
O(n) |
linearer Aufwand |
O(n · log n) |
|
O(n2) |
quadratischer Aufwand |
O(nk) für ein k ≥ 0 |
polynomialer Aufwand |
O(2n) |
exponentieller Aufwand |
Zur Veranschaulichung des mit diesen Funktionen verbundenen Wachstums wollen wir in Tabelle 7–2 einige Werte für ein gegebenes n betrachten, wobei (ld = log2) sei. Die eingerahmten Werte liegen dabei jenseits der Grenze der »praktischen Berechenbarkeit«.
Tab. 7–2 Wachstum für ausgewählte Komplexitätsklassen
Recht illustrativ ist es auch, sich vor Augen zu führen, welche Größenordnung ein Problem haben kann, wenn man die Zeit durch eine maximale Dauer T begrenzt (Tabelle 7–3). Wir nehmen dazu an, dass ein »Schritt« des Aufwandes genau eine Mikrosekunde (1 µs) dauert. G sei dabei das größte lösbare Problem in der Zeit T. Den Aufwand g(n) = log n lassen wir weg, da man hier praktisch unbegrenzt große Probleme in vernünftiger Zeit bearbeiten kann.
Tab. 7–3 Zeitaufwand für einige Problemgrößen
Abschließend sind in Tabelle 7–4 zu den einzelnen Komplexitätsklassen noch einige typische Klassen von Problemen genannt, die sich mit diesem Aufwand, jedoch nicht mit geringerem, lösen lassen.
Tab. 7–4 Typische Problemklassen
Aufwand |
Problemklasse |
O(1) |
einige Suchverfahren für Tabellen (Hashing) |
O(log n) |
allgemeine Suchverfahren für Tabellen (Baum-Suchverfahren) |
O(n) |
sequenzielle Suche, Suche in Texten, syntaktische Analyse von Programmen (bei »guter« Grammatik) |
O(n · log n) |
Sortieren |
O(n2) |
einige dynamische Optimierungsverfahren (z.B. optimale Suchbäume), Multiplikation Matrix-Vektor (einfach) |
O(n3) |
Matrizen-Multiplikation (einfach) |
O(2n) |
viele Optimierungsprobleme (z.B. optimale Schaltwerke), automatisches Beweisen (im Prädikatenkalkül 1. Stufe) |
P
NP
Die Werte aus Tabelle 7–2 und 7–3 deuten schon einen Grenzbereich zwischen effizient (polynomialer Aufwand) und nicht effizient (exponentieller Aufwand) lösbaren Problemen an. Die Menge aller Probleme, die mithilfe deterministischer Algorithmen in polynomialer Zeit – und damit effizient – gelöst werden können, gehören zur Klasse P (für polynomial). Diese Definition schließt die meisten der bisher betrachteten Algorithmen ein. Die Klasse von Problemen, die nur mithilfe nichtdeterministischer Algorithmen in polynomialer Zeit gelöst werden können, bezeichnet man mit NP (für nichtdeterministisch polynomial). Nichtdeterminismus bezieht sich dabei auf die Fähigkeit, bei der Entscheidung zwischen mehreren Varianten die richtige zu »erraten«. Eine Umsetzung mit deterministischen Algorithmen würde dagegen exponentiellen Aufwand erfordern.
Erfüllbarkeitsproblem
Eine bekannte Problemstellung ist das Erfüllbarkeitsproblem. Gegeben ist eine aussagenlogische Formel aus Variablen a, b, c etc. und logischen Operatoren ∧, ∪, ¬ sowie Klammern. Es ist ein Algorithmus gesucht, der prüft, ob die Formel erfüllbar ist, d.h., ob es eine Belegung der Variablen mit booleschen Werten true und false gibt, für die die Formel den Wert true liefert. Eine »einfache«, aber sicher nicht effiziente Lösung ist das Testen aller möglichen Belegungen.
Offensichtlich gehört jedes Problem aus P auch NP an, d.h., es gilt P ⊆ NP. Es gibt eine Reihe von Problemen, von denen man weiß, dass sie NP angehören, aber nicht, ob sie auch P angehören. Das bedeutet, dass sie mithilfe eines nichtdeterministischen Algorithmus gelöst werden können, aber es noch nicht gelungen ist, einen effizienten deterministischen Algorithmus zu finden.
NP-vollständig
Es ist – streng genommen – ein offenes Problem, ob sich die exponentiellen Probleme nicht doch mit polynomialem Aufwand lösen lassen, d.h., ob P=NP gilt. Es wäre jedoch eine große Überraschung, wenn sich dies herausstellen sollte. Man kann allerdings beweisen, dass es eine Klasse von verwandten Problemen aus NP gibt, die folgende Eigenschaft aufweisen: Falls eines dieser Probleme in polynomialer Zeit mit einem deterministischen Algorithmus gelöst werden könnte, so ist dies für alle Probleme aus NP möglich (demzufolge wäre P=NP). Man bezeichnet Probleme mit dieser Eigenschaft als NP-vollständig. Ein bekanntes Problem aus dieser Klasse ist das Problem des Handlungsreisenden (siehe auch Abschnitt 16.6).
Wie kann nun die Laufzeitkomplexität eines Algorithmus bestimmt werden? Die Probleme einer exakten Analyse haben wir bereits in Abschnitt 7.3.2 diskutiert. Die Bestimmung der Größenordnung ist dagegen wesentlich einfacher, da sich hierfür einige einfache Regeln angeben lassen:
Der Laufzeitaufwand einer Schleife ergibt sich aus:
Laufzeit := |
max. Laufzeit der inneren Anweisung · |
|
Anzahl der Iterationen |
So kann der Aufwand der inneren Anweisung im folgenden Beispiel als konstant (O(1)) angesehen werden:
Da die Anzahl der Iterationen n beträgt, ergibt sich der Gesamtaufwand für die obige Schleife aus n · O (1) = O(n).
Bei geschachtelten Schleifen wird für jede Iteration der äußeren Schleife ein kompletter Durchlauf der inneren Schleife durchgeführt. Demnach ergibt sich die Gesamtlaufzeit wie folgt:
Laufzeit := |
Laufzeit der inneren Anweisung · |
|
Produkt der Größen aller Schleifen |
Da im folgenden Beispiel für die innere Anweisung der Aufwand wieder O(1) beträgt, lässt sich der Gesamtaufwand aus n · n · O (1) = O(n2) bestimmen.
for i := 1 to n do
for j := 1 to n do
k := k + 1;
od
od
Bei einer Sequenz von Anweisungen werden die Laufzeiten zunächst addiert. Da konstante Faktoren weggelassen werden können und nur die jeweils höchsten Exponenten berücksichtigt werden, wird für die Gesamtlaufzeit nur die maximale Laufzeitkomponente verwendet. Im folgenden Beispiel lässt sich die Laufzeit für die erste Schleife unter Anwendung von Regel (1) mit O(n) angeben und für die zweite Schleife nach Regel (2) mit O(n2):
for i := 1 to n do
a[i] := 0;
od;
for i := 1 to n do
for j := 1 to n do
a[i] := a[i] + a[j] + i + j;
od
od
Die maximale Komponente des Ausdrucks n2 + n bestimmt den Gesamtaufwand, der danach O(n2) beträgt.
Der Laufzeitaufwand einer solchen Verzweigung ergibt sich aus der Summe des Aufwandes für den Test bedingung und dem Maximum der Aufwände beider Alternativen A1 und A2:
Laufzeit := |
Aufwand für Test + |
|
max (Aufwand für A1, Aufwand für A2) |
Im folgenden Beispiel ist der Aufwand für den Test sowie die erste Anweisung konstant (O(1)). Die zweite Anweisung ist mit einem Aufwand von O(n) verbunden, da hier eine Schleife durchlaufen wird, deren innere Anweisung wiederum einen konstanten Aufwand aufweist.
if x > 100 then
y := x;
else
for i := 1 to n do
if a[i] > y then y := a[i] fi
od
fi
Daraus ergibt sich für den Aufwand für die gesamte Anweisung entsprechend O(n).
Diese Regeln sind im Wesentlichen natürlich nur für die Aufwandsschätzung konkreter Programme gedacht. Die Abschätzung des Aufwandes für Problem klassen erfordert Techniken wie mathematische Beweise etc.
