Diskussion:Determinismus (Algorithmus)

1. Warum sind Zufallszahlen-Generatoren nichtdeterministisch? Es handelt sich doch i.d.R. um eine einfache Rechenvorschrift, bei der bei gleichen Anfangswerten immer die gleichen Zufallszahlen herauskommen?
2. Was genau an Quicksort ist nichtdeterministisch?

Es geht ja auch um einen theoretischen Zufallszahlen-Generator, der unabhängig von jeglichen physikalischen Größen immer eine andere Zufallszahl liefert. Wenn der nicht nichtdeterministisch ist, weiss ichs auch nicht ... --brunft 00:04, 23. Apr 2004 (CEST)

---

zu 2.) Quicksort ist nur dann nichtdeterministisch, falls der im Algorithmus zu bestimmende Median zufällig ausgewählt wird.

---

Also erwaehnen wir Quicksort in diesem Zusammenhang lieber nicht.

Habe

• Jedoch ist in einigen wichtigen Fällen noch ungeklärt, ob die nichtdeterministischen Automaten tatsächlich mächtiger sind als ihr deterministisches Äquivalent, so zum Beispiel bei den beiden wichtigen Klassen P und NP (siehe P/NP-Problem).

geloescht, weil falsch. Die erwaehnten Komplexitaetsklassen beziehen sich auf Turingmaschinen. Auch ist unklar, was mit "einige wichtige Faelle" gemeint ist. P=NP ist nicht nur fuer einige wichtige Faelle offen, sondern prinzipiell. Aber das wird in anderen Artikeln ausreichend gut behandelt. --Dirk 13:38, 9. Okt 2004 (CEST)

Sind Eingaben erlaubt

Angenommen, ein Algorithmus gestattet die anfängliche Eingabe von Parametern. Basierend auf diesen Eingaben verhält sich der Algorithmus unterschiedlich, jedoch für diesselben Eingaben jedes Mal gleich. Darf man einen solchen Algorithmus auch noch als deterministisch bezeichnen? Danke, --Abdull 00:10, 28. Okt 2005 (CEST)

Titel deterministischer Algorithmus anstatt Determinismus (Algorithmus)

Sollte der Artikel nicht besser unter dem Namen „deterministischer Algorithmus“ laufen? Determinismus dazu zu sagen ist vermutlich eher eine Kurzform in Fachkreisen(?). Stochastischer Algorithmus wäre ja auch in deser Form. --Michael Scheffenacker 10:42, 10. Jul. 2011 (CEST)

Der erste Satz

Der erste Satz macht mich stutzig: "Ein deterministischer Algorithmus oder auch determinierter Algorithmus" Das hört sich doch so an, als ob das eine nur ein anderer Ausdruck für das andere wäre. Im restlichen Text wird aber beides genau unterschieden. (nicht signierter Beitrag von 91.67.16.60 (Diskussion) 18:11, 25. Aug. 2011 (CEST))

Quallenwarnung / wohldefiniert?

Die Richtigkeit der Definition ist offenbar fragwürdig, denn: 1. wenn auf Zustand A mal Zustand B und mal Zustand C folgt, dann liegt das ersichtlich an anderen Eingaben... selbst wenn der Algorithmus eine kryptographisch sichere Zufallszahl nutzt, kann man die dennoch als Teil der Eingabe sehen... 2. siehe oben... alles unbeantwortet... *staun* Vorschlag: Es muss also zumindest erwähnt werden, dass die Eigenschaft eigentlich nur davon abhängt, was als Eingabe gilt, und dass somit die Eigenschaft eher etwas schwammig definiert ist... PS: die Paraphrase zu „Komplexität” hört sich auch etwas daneben an... vllt sollte man den ganzen Artikel erstmal löschen? --Heimschützenzentrum (?) 19:07, 25. Dez. 2013 (CET)

Jeder Algorithmus ist für mich deterministisch

Für mich gehört Determiniertheit zu den Eigenschaften eines Algorithmus. (In Prolog wird "deterministisch" anders gebraucht, was natürlich verwirrend ist.) -- UKoch (Diskussion) 22:05, 30. Okt. 2016 (CET)

1. in der theoretischen Informatik gibt es die Nichtdeterministische Turingmaschine, die es in der wirklichen Welt nicht gibt, und die nur für theoretische Überlegungen gebraucht wird... 2. in der angewandten Informatik ist es immer die Frage, was alles zur Eingabe eines Algorithmus dazu gehört... man kann natürlich auch die Zufallszahlen aus /dev/random als Teil der Eingabe betrachten, zumal die genauso schwer vorhersagbar sind, wie die übrigen Eingaben... in diesen Bereich gehören bei nebenläufigen Vorgängen auch die Zeitpunkte zu denen Eingaben erfolgen... 3. es gibt aber auch Menschen, die die Eingabe eines Algorithmus anders definieren und dann hinterher furchtbar herumjammern, dass sie in einer nichtdeterministischen Welt leben (das passiert auch promovierten Dipl.-Inf.s... *kicher*)... --Heimschützenzentrum (?) 06:03, 31. Okt. 2016 (CET)

4. wo taucht in Prolog der Determinismus auf? da ist doch einfach nur die Reihenfolge der Auswertung der Regeln vorgeschrieben... --Heimschützenzentrum (?) 06:09, 31. Okt. 2016 (CET)

Ad 1: Klar, aber weil sie nichtdeterministisch ist, sehe ich sie nicht als Algorithmus.

Ad 2: In Algorithmus steht unter "Definition", Determinismus sei eine häufige Einschränkung des Algorithmusbegriffs "in praktischen Bereichen". Das passt zu dem, was in diesem Artikel steht, also für mich alles OK.

Ad 4: Das ist ein anderer Sprachgebrauch. Ein Prädikat wird da als deterministisch bezeichnet, wenn es nur auf eine Art bewiesen werden kann. Bsp.:

n(0).
n(X).
d(X).

In der Prolog-Sprechweise ist n nichtdeterministisch und d deterministisch. -- UKoch (Diskussion) 22:39, 31. Okt. 2016 (CET)

zu 4: oops? in Prolog gibt es doch immer nur eine einzige Art die Anfrage zu „beweisen“ (wobei „bewerten“ das bessere Wort wäre, da ja auch eine Widerlegung möglich ist...), weil doch die Reihenfolge festliegt... zu 1: aber man kann Algorithmen für ne Nichtdeterministische Turingmaschine angeben... zu 2: das ist nur dummes Zeug, was da steht... lol --Heimschützenzentrum (?) 05:50, 1. Nov. 2016 (CET)

Ad 4: Ich meine damit: Die Anfrage ?- n(Z). kann auf 2 Arten erfolgreich sein; wenn man (typischerweise durch Semikolon) nach dem ersten "Z=0, yes" eine 2. Lösung anfordert, bekommt man sie, während die Anfrage ?- d(Z). einmal mit "yes" und nach Semikolon mit "no" beantwortet wird. Zur Möglichkeit einer Widerlegung: Nur als Unmöglichkeit des Beweisens, also negation by failure.

Ad 1: Ich würde da nicht von Algorithmen sprechen, aber Algorithmus ist da anderer Meinung, also OK für mich.

Ad 2: Siehe oben. -- UKoch (Diskussion) 19:47, 1. Nov. 2016 (CET)

zu 4: das ist mir neu... davon steht auch im Artikel nix... zu 2: also sollte der Artikel nich geändert werden? ich weiß gar nich, wo das herkommt, dass man Schlamperei bei der Definition später einfach als „nicht deterministisch“ durchgehen lässt... lol --Heimschützenzentrum (?) 06:20, 2. Nov. 2016 (CET)

Zu 4: Sollte evtl. im Prolog-Artikel hinzugefügt werden. Vielleicht habe ich ja mal irgendwann Lust...

Zu 2: Nein, ich denke nicht, dass "meine" Def., die Determinismus beinhaltet, die allein seligmachende ist. Die Def., die im Artikel steht, hat wohl mehr mit der nichtdeterministischen Turing-Maschine zu tun als mit Schlamperei bei der Definition. -- UKoch (Diskussion) 20:21, 2. Nov. 2016 (CET)

zu 4: wenn's dafür ne ordentliche Quelle gibt... zu 2: nun hat ne nichtdeterministischen Turing-Maschine aber nix mit „praktischen Bereichen“ zu tun... lol --Heimschützenzentrum (?) 20:39, 2. Nov. 2016 (CET)

Zu 4: Mal sehen. Zu 2: Jo. Ich meinte: Die Def., die Nichtdeterminismus erlaubt, wird mit der nichtdeterministischen Turing-Maschine zu tun haben. -- UKoch (Diskussion) 21:22, 4. Nov. 2016 (CET)

zu 2: schön wärs, aber: es gibt wirklich welche (auch Forschungs-Assistenten an Universitäten und damit vermutlich auch Professoren...), die glauben, dass z. B. Java nicht-deterministisch ist... siehe talk:Garbage_Collection/Archiv/1#Letzter_Stand... LOL --Heimschützenzentrum (?) 21:35, 4. Nov. 2016 (CET)

Hmm, interessanter Punkt. Mir scheint, beim GC-Beispiel geht es um noch eine andere Lesart von "Determinismus", aber ich muss weiter drüber nachdenken. -- UKoch (Diskussion) 23:14, 6. Nov. 2016 (CET)