Unterschied zwischen Terminierung und Finitheit (Algorithmik)?

Hallo zusammen,

ich studiere Wirtschaftsinformatik im ersten Semester und beschäftige mich momentan mit den Eigenschaften von Algorithmen. Dort bin ich im Vorlesungsskript auf 2 Definitionen zur Finitheit und Terminierung gestoßen.

• Finitheit: Der Algorithmus kann in einer endlichen Zeit beschrieben und beendet werden.

• Terminierung: Das Verfahren muss in endlich vielen Schritten abschließbar sein.

Mir erschließt sich nicht ganz der Unterschied zwischen den beiden Eigenschaften. Kann ein Algorithmus auch finit sein, aber nicht terminiert und umgekehrt?

Vielen Dank schon mal für Eure Hilfe! LG

Answer 1

[offeltoffel]

Finitheit bezieht sich auf den Aufbau des Algorithmus, Terminierung auf die Ausführung.

Finitheit bedeutet, dass der Algorithmus eine endliche Länge an Befehlen/Zeilen hat und auch auf dem Computer nur endliche Ressourcen zur Verfügung hat.

Terminierung bedeutet, dass der Algorithmus solange arbeitet, bis ein Ereignis eintritt, das ihn beendet und ein Ergebnis liefert.

Comments

[TimurHC]

Vielen Dank, das erklärt die beiden Eingeschaften nochmal einfacher :)

Answer 2

[rednblack]

Sicher, dass du da nicht die Begriffe verwechselst? Meiner Kenntnis nach bezieht sich die Terminierung darauf, dass das Programmende zeitlich definiert ist, also z.b. nicht in eine Dauerschleife geführt wird.

Finitheid bedeutet, dass das Programm das Problem in einer bestimmten Menge an Arbeitsschritten abarbeitet und ein Ergebnis erzeugt, mit dessen Ausgabe der Algorithmus beendet wird.

Comments

[TimurHC]

Also die beiden Definitionen stehen genau so im Skript. :-)

Answer 3

[surbahar53]

In der Wissenschaft kommt es immer wieder vor, dass sogenannte Experten verbrämte Sprachfloskeln erfinden, um das Ego zu steigern.

Finitheit bei einem Algorithmus meint, dass die Anzahl der Elementaranweisungen auf ein bestimmtes Maß beschränkt bleibt ("endlich"). Das gilt ebenso für die Ressourcen des Algorithmus also z.B. den Speicherplatzbedarf für Zwischenwerte. Mir ist allerdings ein nicht finiter Algorithmus unbekannt. Macht auch wenig Sinn, weil er in der Praxis nicht anwendbar wäre.

Terminierung meint, dass der Algorithmus auf jede Eingabe nach N Schritten ein Ergebnis liefert. Nun meinen viele " Algorithmiker", daß ein Algorithmus, der nicht terminiert, kein Algorithmus im eigentlichen Sinne sei. Donald Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden ('Computational Methods') zu bezeichnen.

Alles also rein theoretische Sprachblasen ohne jeden praktischen Nutzen.