Eigenschaft eines imperativen Algo (Pseudocode) sofort erkennen

[PeterMaffay99]

Guten Morgen,
gibt es einen Trick wie man auf Anhieb erkennen kann ob ein imperativer Algorithmus (Pseudocode) Deterministisch, Determiniert oder terminierend ist? Wenn mir das jemand netterweise auch anhand der Beispiele mal kurz erläutern könnte bzw. ein Feedback zu meinen "Versuchen" abgeben könnte 🙂

FAC: var X,Y: int;
 input X;
 Y:=1;
 while X>1 do
 Y:=Y ·X; 
 X:=X-1 od 
 output Y.

Input und Output (Ergebnis) unterscheiden sich , also "Nicht-Determiniert"
Wir haben einen Output (Ergebnis), also "terminierend"

algorithm BinarySearch (F, k) ! p
Eingabe: Folge F der Länge n, Schlüsse k
u := 1, o := n;
while u <= o do
  m := (u + o)/2;
  if F[m] = k then
   return m
  else
   if k < F[m] then
     o := m − 1
   else
     u := m + 1
   fi;
  fi;
od;
return NO_KEY

Die Methode liefert am Ende entweder m-1 oder m+1 , also "Determiniert"
Wir haben keinen Output (Ergebnis), also "nicht terminierend"

FIB: var X, A, B, C: int;
 input X;
 A:=1; B:=1;
 while X>0 do
  C:=A+B; A:=B; B:=C; X:=X-1
od 
output A.

Input und Output (Ergebnis) unterscheiden sich , also "Nicht-Determiniert"
Wir haben einen Output (Ergebnis), also "terminierend"

GGT1 :var X,Y: int;
 input X,Y;
 while X ≠ Y do
  while X>Y do X:=X-Y od;
  while X<Y do Y:=Y-X od 
 od;
 output X

Input und Output (Ergebnis) identisch, also "Determiniert"
Wir haben einen Output (Ergebnis), also "terminierend"

Gibt es noch weitere Merkmale wie man was sofort erkennt?

 

[httpdigest]

gibt es einen Trick wie man auf Anhieb erkennen kann ob ein imperativer Algorithmus (Pseudocode) Deterministisch, Determiniert oder terminierend ist?

Kurz: Nein, gibt es nicht. Insbesondere die Eigenschaft, ob ein Algorithmus terminiert, ist im Allgemeinen sogar unentscheidbar. Das heißt, es gibt keinen Algorithmus (ob nun von einem Menschen oder einer Maschine ausgeführt), der für einen gegebenen Algorithmus entscheidet, ob dieser Algorithmus nun irgendwann terminiert oder für immer und ewig weiterläuft. Siehe hierzu: https://de.wikipedia.org/wiki/Halteproblem

...erstes Codesnippet...
Input und Output (Ergebnis) unterscheiden sich , also "Nicht-Determiniert"
Wir haben einen Output (Ergebnis), also "terminierend"

Zum Punkt "Nicht-Determiniert": Determiniert heißt nicht, dass am Ende der Output exakt dem Input entspricht. Das wäre dann ja auch eine ziemlich unnütze Funktion, nämlich die Identitätsfunktion, die da berechnet würde. Determiniertheit heißt nur, dass, gegeben einen Input, die Funktion für diesen Input immer dasselbe Ergebnis liefert. Und dasselbe meint hier nicht, dass das Ergebnis identisch zum Input sein soll.
Zum Punkt "terminierend": Du sagst "Wir haben einen Output (Ergebnis)". Was genau meinst du damit? Natürlich kann im Code irgendwo stehen "gebe Ergebnis/Output aus", aber das heißt ja noch lange nicht, dass diese Stelle auch jemals ausgeführt wird. Terminierend heißt nicht, dass irgendwo im Code irgendetwas ausgegeben oder zurückgegeben wird, sondern, dass die Ausführung des Algorithmus auch irgendwann beendet wird und eben diese terminierenden Stellen im Code erreicht. Das wiederum ist nur für die aller-trivialsten Algorithmen entscheidbar/beweisbar und nicht im Allgemeinen.

...zweites Codesnippet...
Die Methode liefert am Ende entweder m-1 oder m+1 , also "Determiniert"
Wir haben keinen Output (Ergebnis), also "nicht terminierend"

Woher weißt du, dass sie em Ende m-1 oder m+1 liefert? Kannst du das beweisen? Und wenn ja, wie? Deine Aussage, dass wir hier keinen Output/Ergebnis haben und somit die Funktion nicht terminiert, ist auch falsch. Der Output, bzw. das Ergebnis in diesem Fall wäre ja, dass ein Wert mittels des return-Statements an den Aufrufer der Funktion zurückgeliefert wird.

...drittes Codesnippet...
Input und Output (Ergebnis) unterscheiden sich , also "Nicht-Determiniert"
Wir haben einen Output (Ergebnis), also "terminierend"

Nein. Siehe obige Aussagen.