Diskussion:Determiniertheit (Algorithmus)

Ich denke, die einzige Bedingung, die ein determinierter Algorithmus erfüllen muss, ist das er die Eingabe im Sinne einer mathematischen Funktion auf die Ausgaben zuordnet, d.h. jeder Eingabe muss eindeutig eine Ausgabe zugeordnet werden. Die bisherige Formulierung (bijektive, lineare Abbildung) halte ich für falsch:

Bijektiv muss diese Funktion meiner Meinung nach nicht sein, da sie damit auch injektiv sein müßte. Wenn dem so wäre, dann wäre nicht jeder deterministische Algorithmus auch determiniert: Gegenbeispiel hierfür wäre ein deterministischer Sortieralgorithmus, der einer Menge von Zahlenfolge-Permutationen eine eindeutige - nämlich die sortierte Folge - zuordnet. Dieser ist nicht injektiv und damit auch nicht bijektiv.

Linearität bedeutet, dass es sich um eine homogene und additive Abbildung handelt. Die Additivität gilt zum Beispiel auch im Fall des oben beschriebenen Sortieralgorithmus nicht.

Aber muß es denn wirklich eine Funktion für einen determinierten Algorithmus geben? Wenn der Algorithmus ein komplexes System berechnet, bei dem immer nur aus dem Zustand n oder Zustand n+1 berechnet werden kann, wenn die Konfiguration des Zustandes n bekannt ist, dann gibt es doch IMHO keine Funktion dafür, aber sehr wohl könnte es möglich sein, einen determinierten Algorithmus zu schreiben. Oder nicht? --El capitan

---

Der lapidare Hinweis "Der Begriff Determiniertheit ist vom Begriff Determinismus zu unterscheiden." hilft IMHO nicht wirklich weiter, lieber den Unterschied in beiden Artikeln kurz erklären. Meinungen?

IMHO wäre es sinnvoll, den Artikel leichter verständelich zu schreiben und evtl durch ein Beispiel zu veranschaulichen. Meine das etwa so (bitte inhaltlich, typografisch und sprachlich korrigieren, ggf weitere/klarere Bsp hinzu):

deterministisch: Es gibt von jedem Zustand aus genau einen Weg, der durchlaufen werden kann (der Startzustand bestimmt genau einen Pfad). Vom Start bis zum Ende ist jeder Schritt festgelegt, systeminterne Entscheidungen sind nicht möglich, jede (auch sinnvolle) Art von Unabhängigkeit ist verboten. Bsp: Klickfolge in einer Software-Menüleiste, Abfolge der Aktivitäten in einem Motor bei gegebenem Gas, ...

determiniert: Es gibt für je einen Startpunkt genau einen Endpunkt. Der Weg zu diesem einen Endpunkt ist aber nicht fix (z.B. parallele Maschinen/Wege/...). Das Endergebnis ist festgelegt, aber der Weg offen. Bsp: Um eine Software-Funktion auszuführen, kann man das Menü via Tastatur oder Maus bedienen, das Kontextmenü eines Objekts nutzen, oder einen Hotkey drücken. Bei Internet-Übertragung ist Start und Ziel festgelegt, aber über welche Zwischenknoten Pakete wandern, ist nicht festgelegt.

--Schoschi 23:17, 13. Feb 2005 (CET)

Injektivität?

Im Artikel steht, dass Determiniertheit auf injektiv ist. Jede Eingabe hat genau eine Ausgabe. Das bedeutet aber, dass die Menge der Ausgaben auch Elemente haben kann, die durch keine Eingabe erreicht werden können.

Warum aber sollte die Ausgabemenge Elemente erhalten die man eh nicht erreichen kann? --Abdull 23:41, 27. Okt 2005 (CEST)

Na zum Beispiel kann dein Drucker doch alle möglichen Dinge drucken und vllt. sogar in Farbe, aber er druckt bei jedem Mal nur einen kleinen Teil von dem was möglich wäre. Ein Alg. verteilt sich auch so. Z. B. soll ein Alg. unseren (kleinen lateinischen) Buchstaben jeweils aufsteigend natürliche Zahlen zuordnen. Jedes (a-z) hat dann eine "Nummer", aber die Zahl 735 hat leider keinen Buchstaben mehr abbekommen. --WissensDürster 13:44, 18. Feb. 2009 (CET)

Injektivität

Ich verstehe es so:

Determiniertheit bezeichnet die Eigenschaft eines Algorithmus, bei gleichem Eingabewert stets den gleichen Ausgabewert zu liefern. Der Weg selber ist aber nicht vorgeschrieben, auch könnten verschiedene Eingabewerte den gleichen Ausgabewert liefern. Hier könnte man den Unterschied zum Determinismus klar machen, ein deterministisches Algorithmus ist determiniert, die Umkehrung aber gilt nicht.

Die Erklärung mit der injektiven Abbildung finde nicht so gut, eine verbale Definition wäre besser, injektiv muss aber die Abbildung nicht sein, verschiedene Eingabewerte könnten doch den gleichen Ausgabewert haben, das Algorithmus wäre nach wie vor determiniert. Wenn dann würde ich eher es als surjektive Abbildung bezeichnet, wie Abdull meinte, wieso sollte man Ausgabewerte zulassen die man ehe nicht erreichen kann.

Reinhard