Nicht deterministischer, aber determinierter Algorithmus Beispiel?
Ich suche Beispiele für nicht deterministische, aber determinierte Algorithmen.
Determinismus ist dabei die Eindeutigkeit als dynamische Eigenschaft, also während der Laufzeit ist klar, welcher Handlungsschritt als nächster folgt.
Determiniertheit bedeutet, dass der Algorithmus bei gleichen Voraussetzungen das gleiche Ergebnis liefert.
Vielen Dank für Beispiele!
2 Antworten
"So gibt es Algorithmen, die nicht-deterministisch, aber trotzdem determiniert sind (d. h. das gleiche Ergebnis liefern).[2] Zum Beispiel teilt der Sortieralgorithmus Quicksort eine vorgegebene Liste immer in Teillisten ein, welche in ihrer Größe zufällig gewählt werden können, das Ergebnis ist jedoch stets das Gleiche."
Quelle: https://de.wikipedia.org/wiki/Determinismus_(Algorithmus)
Es ist nur dann das gleiche Ergebnis, wenn kein Element derselben Größe doppelt vorkommt. Quicksort ist nicht stabil^^
Kuchen backen ist mir jetzt auch noch eingefallen. Da kann man schließlich auch erst vorheizen etc., selbst, wenn der Kuchen am Ende genauso schmeckt.
Vielleicht auch noch interessant in diesem Zusammenhang:
"Instabile Sortierverfahren:
- Bogosort
- Combsort
- Heapsort
- Introsort
- Quicksort
- Selectionsort
- Shellsort
- Smoothsort
- Slowsort
- Stoogesort "
Quelle: https://de.wikipedia.org/wiki/Stabilit%C3%A4t_(Sortierverfahren)
ja, da passt irgendwie das Sprichwort "viele Wege führen nach Rom" wenn man es ergänzt: "auch vom selben Ausgangsort" - denn die Eingabe soll ja gleich sein!
Merci, das ging schnell