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

Als ein Beispiel für die Problematik der Terminierung und undefinierter Funktionen betrachten wir folgenden Algorithmus:

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

Man sieht sofort, dass eine Auswertung des Tests aufgrund der Rekursion zu einer unendlichen Berechnung führt:

f(x) = ⊥für allex ∊ int

Nun könnte man auf die Idee kommen, folgenden Schluss zu ziehen: Da f(x) = ⊥, gilt etwa f(7) ≠ 0, und damit wird der zweite Zweig der Auswahl ausgewählt: f(7) = 0. Dies ist nun ein Widerspruch, den man auflösen muss.

Vorsicht beim »Rechnen« mit ⊥!

Also gilt: Vorsicht beim »Rechnen« mit ⊥! Sowohl 0 = ⊥ als auch 0 ≠ ⊥ werden beide zu ⊥ ausgewertet. Des Weiteren gilt immer die folgende Auswertung:

if ⊥ then t else u fi= ⊥

Diese Festlegung passt auch zu der Auffassung von ⊥ als »unendlich lange Berechnung«.

Bedeutung von Algorithmen

Wir hatten bisher immer ein Problem vorgegeben und dazu einen Algorithmus ausgeführt, der die Lösung des Problems als Semantik hatte. Wie ist es aber nun umgekehrt – gegeben sei ein Algorithmus, kann man einfach daraus die Bedeutung ablesen? Dieses Problem hat zwei Aspekte: Kann man die mathematische Funktion bestimmen, die berechnet wird, und kann man diese Funktion dann auch semantisch interpretieren, also mit einer sinnvollen Problemstellung verknüpfen? Wir betrachten wieder einige Beispiele.