Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 83

Algorithmen können durchaus eine «kniffelige Bedeutung« haben. Wir betrachten die folgenden beiden Funktionsdefinitionen:

f(x)	=	if x = 1 then 1 else f(g(x)) fi
g(x)	=	if even(x) then x ÷ 2 else 3x + 1 fi

Da g eine negative Zahl immer auf eine andere negative Zahl abbildet, gilt sicher für alle negativen Zahlen (und für die 0, die wieder auf 0 abgebildet wird):

f(x) = ⊥fürx ≤ 0

Betrachten wir also den Bereich der positiven ganzen Zahlen. Wenn die Berechnung überhaupt terminiert, kann als Ergebnis nur der Wert 1 herauskommen. Einige Beispielberechnungen bestätigen dies:

f(1)		1
f(2)		f(1) 1
f(3)		f(10) f(5) f(16) f(8) f(4) f(2) 1
f(4)		… 1
…

Allerdings wissen wir nicht, ob die Berechnung von f tatsächlich für alle positiven Zahlen terminiert! Es ist bisher unbewiesen, ob die folgende Äquivalenz gilt:

f(x) =if x > 0 then 1 else ⊥ fi

Dies zeigt, dass das Problem, ob man entscheiden kann, ob zwei Algorithmen äquivalent sind, d.h. dasselbe berechnen, durch die Existenz von unendlichen Berechnungen einen weiteren Schwierigkeitsgrad erhält – wenn wir im Beispiel die Terminierung gezeigt haben sollten, ist die Gleichheit der Ergebniswerte trivial.

Neben der Äquivalenz von Algorithmen wird uns später der Aufwand bei deren Berechnung intensiv beschäftigen. Der folgende Algorithmus zeigt, dass der Berechnungsaufwand bei relativ einfachen Algorithmenbeschreibungen förmlich explodieren kann.