Unterschiede und Beziehungen zwischen randomisierten und nicht deterministischen Algorithmen?

Welche Unterschiede und Beziehungen bestehen zwischen randomisierten und nicht deterministischen Algorithmen?

Aus Wikipedia

Ein randomisierter Algorithmus ist ein Algorithmus, der einen Zufallsgrad als Teil seiner Logik verwendet. Der Algorithmus verwendet typischerweise gleichmäßig zufällige Bits als Hilfseingabe, um sein Verhalten zu steuern, in der Hoffnung, im "Durchschnittsfall" eine gute Leistung über alle möglichen Auswahlmöglichkeiten von zufälligen Bits zu erzielen. Formal ist die Leistung des Algorithmus eine Zufallsvariable, die durch die Zufallsbits bestimmt wird. Daher sind entweder die Laufzeit oder die Ausgabe (oder beide) Zufallsvariablen.

Ein nicht deterministischer Algorithmus ist ein Algorithmus, der im Gegensatz zu einem deterministischen Algorithmus bei verschiedenen Läufen ein unterschiedliches Verhalten aufweisen kann. Es gibt verschiedene Möglichkeiten, wie sich ein Algorithmus von Lauf zu Lauf unterschiedlich verhält. Ein gleichzeitiger Algorithmus kann aufgrund einer Rennbedingung bei verschiedenen Läufen unterschiedlich ausgeführt werden. Ein probabilistischer Algorithmus ‚s Verhalten hängt von einem Zufallszahlengenerator. Ein Algorithmus, der ein Problem in der nichtdeterministischen Polynomzeit löst, kann in Abhängigkeit von der Auswahl, die er während der Ausführung trifft, in der Polynomzeit oder in der Exponentialzeit ausgeführt werden.

Sind randomisierte Algorithmen und probabilistische Algorithmen dasselbe Konzept?

Wenn ja, sind randomisierte Algorithmen nur eine Art nicht deterministischer Algorithmen?

Nicht deterministische Algorithmen unterscheiden sich stark von probabilistischen Algorithmen.

Probabilistische Algorithmen verwenden Münzwürfe und funktionieren "meistens". Beispiel: Randomisierte Varianten von Quicksort arbeiten in der Zeit in Erwartung (und mit hoher Wahrscheinlichkeit), aber wenn Sie Pech haben, können sie bis zu Θ ( n 2 ) dauern . Probabilistische Algorithmen sind praktisch und werden beispielsweise von Ihrem Computer beim Generieren von RSA-Schlüsseln verwendet (um zu testen, ob die beiden Faktoren Ihres geheimen Schlüssels Primzahlen sind). Probabilistischer Algorithmus, der keine Münzwürfe verwendet, wird manchmal als "deterministisch" bezeichnet.$\Theta(n\log n)$$\Theta(n^2)$

Nichtdeterministische Algorithmen sind solche, die "einen Hinweis brauchen", aber immer richtig sind: Sie können nicht getäuscht werden, wenn ihnen der falsche Hinweis gegeben wird. Als Beispiel ist hier ein nicht deterministischer Algorithmus, der eine ganze Zahl faktorisiert: Errate eine Faktorisierung von n und verifiziere, dass alle Faktoren Primzahlen sind (es gibt einen deterministischen Algorithmus "fast-in-theory", um dies zu tun). Dieser Algorithmus ist sehr schnell und weist falsche Hinweise zurück. Die meisten Leute denken, dass randomisierte Algorithmen Ganzzahlen nicht so schnell berücksichtigen können. Offensichtlich ist dieses Berechnungsmodell nicht realistisch.$n$$n$

Warum interessieren uns nicht deterministische Algorithmen? Es gibt eine Klasse von Problemen, bekannt als NP, die aus Entscheidungsproblemen besteht , die effiziente nicht deterministische Algorithmen aufweisen. Die meisten Leute denken, dass die schwierigsten Probleme in dieser Klasse, die sogenannten NP-vollständigen Probleme, keine effizienten deterministischen (oder sogar randomisierten) Algorithmen haben; Dies ist als P vs NP-Frage bekannt. Da viele natürliche Probleme NP-vollständig sind, ist es interessant zu wissen, ob sie im schlimmsten Fall tatsächlich nicht effizient lösbar sind (in der Praxis sind die in der Praxis auftretenden Fälle häufig tatsächlich in angemessener Zeit lösbar).

Ein Algorithmus gibt eine Methode an, um von einer bestimmten Eingabe zu einer gewünschten Ausgabe zu gelangen, die eine bestimmte Beziehung zur Eingabe hat. Wir sagen, dass dieser Algorithmus deterministisch ist, wenn zu irgendeinem Zeitpunkt genau und eindeutig festgelegt wird, welcher nächste Schritt im Algorithmus als Teil dieser Methode ausgeführt werden muss, möglicherweise abhängig von der Eingabe oder den bisher berechneten Teildaten, aber immer eindeutig identifiziert.

Nichtdeterminismus bedeutet, dass ein Teil des Algorithmus unter oder gar nicht spezifiziert bleibt. Beispielsweise wird "int i = eine gerade Zahl zwischen 0 und n" nicht angegeben. Dies bedeutet, dass an dieser Stelle kein eindeutiges Verhalten angegeben ist.

Damit diese Unterscheidung nützlich ist, benötigen Sie das (übliche) Konzept der 'Korrektheit' für (deterministische) Algorithmen, das informell besagt, dass "der Algorithmus immer berechnet, was ich berechnen möchte". Es wird dann interessant, darüber nachzudenken, was Korrektheit für nicht deterministische Algorithmen bedeuten würde, die die Auswahlmöglichkeiten in unterbestimmten Befehlen berücksichtigen müssen.

Es gibt zwei Möglichkeiten, die Korrektheit für den Nichtdeterminismus zu definieren. Die erste ist eher einfach und weniger interessant, und für sie bedeutet Korrektheit, dass der Algorithmus für alle Folgen von Entscheidungen, die ich treffen darf, immer das berechnet, was ich berechnen möchte. Dies tritt manchmal auf, wenn ein Autor eines Pseudocode-Bits zu faul ist, um eine Zahl auszuwählen, und sagt "Wähle eine gerade Zahl zwischen 0 und n", wenn "Wähle 0" den Algorithmus deterministisch gemacht hätte. Im Wesentlichen können Sie den Algorithmus deterministisch machen, indem Sie den gesamten Nichtdeterminismus durch das Ergebnis irgendeiner Wahl ersetzen.

Dies ist auch der 'Nichtdeterminismus', auf den Sie in Ihrem zweiten Absatz Bezug genommen haben. Dies ist auch der Nicht-Determinismus bei parallelen Algorithmen: Bei diesen Algorithmen sind Sie sich nicht ganz sicher, wie die Ausführung genau aussieht, aber Sie wissen, dass sie immer funktionieren wird, egal was genau passiert (andernfalls wäre Ihr paralleler Algorithmus falsch).

Die interessante Definition der Korrektheit für nichtdeterministische Algorithmen lautet: "Der Algorithmus berechnet immer das, was ich berechnen möchte, für eine Reihe von Entscheidungen, die ich treffen darf." Dies bedeutet, dass es möglicherweise Entscheidungen gibt, die in dem Sinne falsch sind, dass der Algorithmus die falsche Antwort liefert oder sich sogar in einer Endlosschleife befindet. Im Beispiel "Wähle eine gerade Zahl zwischen 0 und n" sind vielleicht 4 und 16 die richtige Wahl, aber alle anderen Zahlen sind falsch, und diese Zahlen können abhängig von der Eingabe, den Teilergebnissen und den bisher getroffenen Entscheidungen variieren.

In der Informatik ist der Nichtdeterminismus normalerweise auf die nichtdeterministische Auswahl einer 0 oder einer 1 beschränkt. Wenn Sie jedoch viele solcher Bits nichtdeterministisch auswählen, können Sie lange nichtdeterministische Zahlen oder andere Objekte generieren und daher kaum nichtdeterministische Entscheidungen treffen (wenn überhaupt) schränkt seine Anwendbarkeit ein - wenn die Anwendbarkeit begrenzt ist, war Nichtdeterminismus an erster Stelle zu mächtig.

Nichtdeterminismus ist ein Tool, das genau so leistungsfähig ist wie ein zertifikatsbasierter deterministischer Algorithmus, dh ein Algorithmus, der eine Eigenschaft mit einer bestimmten Instanz und ein Zertifikat für diese Eigenschaft überprüft. Sie können das Zertifikat für eine Richtung einfach nicht deterministisch erraten, und Sie können ein Zertifikat angeben, das alle "richtigen" Antworten für die nicht deterministischen Schätzungen von 0 und 1 Ihres Programms für die andere Richtung enthält.

Wenn wir die Laufzeit in die Mischung einfließen lassen, werden die Dinge noch interessanter. Die Laufzeit eines nicht deterministischen Algorithmus wird normalerweise als das Minimum für alle (richtigen) Entscheidungen angesehen. Andere Entscheidungen können jedoch zu einer dramatisch schlechteren Laufzeit (die asymptotisch schlechter oder sogar willkürlich schlechter als das Minimum sein kann) oder sogar zu einer Endlosschleife führen. Deshalb nehmen wir das Minimum: Diese seltsamen Fälle interessieren uns nicht.

Nun kommen wir zu randomisierten Algorithmen. Randomisierte Algorithmen sind wie nichtdeterministische Algorithmen, aber anstatt die Wahl zwischen 0 und 1 an bestimmten Punkten "zuzulassen", wird diese Wahl durch einen zufälligen Münzwurf zu dem Zeitpunkt bestimmt, zu dem die Wahl getroffen werden muss (der von Lauf zu Lauf unterschiedlich sein kann) (oder wenn die gleiche Auswahl später bei der Ausführung des Algorithmus erneut getroffen werden muss). Dies bedeutet, dass das Ergebnis mit gleicher Wahrscheinlichkeit 0 oder 1 ist. Die Korrektheit wird nun entweder "der Algorithmus berechnet fast immer das, was ich berechnen möchte" oder "der Algorithmus berechnet immer das, was ich berechnen möchte" (nur die deterministische Version). Im zweiten Fall ist die Zeit, die der Algorithmus benötigt, um seine Antwort zu berechnen, normalerweise "fast immer schnell", im Gegensatz zu einem deterministischen "immer schnell".

$P \subseteq ZPP \subseteq NP$

Kurz gesagt: Nichtdeterminismus bedeutet, mehrere, gleichermaßen gültige Möglichkeiten zur Fortsetzung einer Berechnung zu haben. Randomisierung bedeutet, eine externe Quelle von (zufälligen) Bits zu verwenden, um die Berechnung zu steuern.

Um den Nichtdeterminismus zu verstehen, schlage ich vor, dass Sie sich endliche Automaten (FA) ansehen. Für einen deterministischen FA (DFA) ist die Übergangsfunktion eine Funktion. In Anbetracht des aktuellen Status und des nächsten Eingabesymbols ist der nächste Status eindeutig definiert.

$(ab)^*(ac)^*$

^{[ Quelle ]}

$a$$(ab)^*$$(ac)^*$$a$

Der entscheidende Punkt hierbei ist , dass die Annahme ist definiert als „akzeptieren , wenn es eine akzeptierende run“ für NFA. Dieses Existenzkriterium kann als "immer richtig raten" interpretiert werden, obwohl es kein tatsächliches Raten gibt.

Beachten Sie, dass es hier nirgends Wahrscheinlichkeiten gibt. Wenn Sie Nichtdeterminismus in Programmiersprachen übersetzen würden, hätten Sie Anweisungen, die bei gleichem Status zu Sprüngen zu anderen Anweisungen führen können . So etwas gibt es nicht, außer vielleicht in esoterischen Programmiersprachen, die so konzipiert sind, dass es Sie um den Verstand bringt.

Randomisierung ist ganz anders. Wenn wir es aufschlüsseln, hat der Automat / das Programm keine Mehrfachauswahlmöglichkeiten, um die Ausführung fortzusetzen. Sobald die Zufallsbits gezeichnet sind, ist die nächste Anweisung eindeutig definiert:

if ( rand() > 5 )
  do_stuff();
else
  do_other_stuff();

Betrachten Sie in Bezug auf endliche Automaten Folgendes:

^{[ Quelle ]}

$\{a,b,c\}^*$$1$$0$

$\Sigma \times \Pi$$\Pi$

Ein letzter Hinweis: Wir können sehen, dass Nichtdeterminismus ein rein theoretischer Begriff ist, der nicht umgesetzt werden kann! Warum benutzen wir es also?

1. Oft sind kleinere Darstellungen möglich. Möglicherweise wissen Sie, dass es NFA gibt, für die der kleinste DFA exponentiell so groß ist¹. Die Verwendung der kleineren ist nur eine Frage der Vereinfachung des Automatendesigns und der technischen Beweise.

2. Die Übersetzung zwischen Modellen ist häufig einfacher, wenn im Zielmodell Nichtdeterminismus zulässig ist. Stellen Sie sich zum Beispiel vor, Sie konvertieren reguläre Ausdrücke in DFA: Die übliche (und einfache) Methode besteht darin, sie in eine NFA zu übersetzen und diese zu bestimmen. Mir ist keine direkte Konstruktion bekannt.

3. Dies mag ein akademisches Problem sein, aber es ist interessant, dass Nichtdeterminismus die Leistung eines Geräts erhöhen kann. Dies ist nicht der Fall für endliche Automaten und Turing-Maschinen, die wohl die gängigsten Maschinenmodelle sind, aber zum Beispiel können deterministische Pushdown-Automaten, Büchi-Automaten und Topdown-Baumautomaten weniger Sprachen akzeptieren als ihre nicht deterministischen Geschwister².

1. Ein Beispiel finden Sie in dieser Frage auf cstheory.SE .
2. Siehe hier , hier und hier (Satz 1.6.2) .

Sie sollten sich darüber im Klaren sein, dass es hier zwei verschiedene Definitionen von Nichtdeterminismus gibt.

1. Wie Wikipedia es definiert, so ziemlich "kein Determinismus", dh jeder Algorithmus, der nicht immer das gleiche Verhalten bei den gleichen Eingaben hat. Randomisierte Algorithmen sind ein Sonderfall von "nicht deterministischen" Algorithmen, da sie der Definition entsprechen, wie ich sie gerade angegeben habe.

2. Nichtdeterministische Rechenmodelle (wie nichtdeterministische Turingmaschinen) sind theoretische Rechenmodelle. Sie können mehrere mögliche Ausführungspfade haben und sie "akzeptieren", wenn einer dieser Pfade akzeptiert. Sie sollten beachten, dass sie nicht real sind. Es gibt keine Möglichkeit, einen Algorithmus physikalisch auszuführen, der in diesem Sinne nicht deterministisch ist, obwohl Sie ihn mit einem zufälligen oder deterministischen Algorithmus simulieren können.

In CS bedeutet Nichtdeterminismus normalerweise (2), sodass die von Ihnen angegebene Definition von Wikipedia (1) irreführend ist. Die meisten der bisher gegebenen Antworten erklären (2), nicht (1).

Wenn ich dies aufgrund einiger verwandter Forschungen, die ich mache, erneut betrachte, kann die Meinungsverschiedenheit zwischen mir und einigen der anderen, die geantwortet haben, zu einem ganzheitlichen Verständnis verarbeitet werden, in dem wir alle Recht hatten. Aber meiner Meinung nach ist die in der Informatik verwendete Terminologie "beschränkter Nichtdeterminismus" ein falsches Oxymoron (worauf ich früher eingegangen bin).

Ihr Hauptpunkt ist die Unterscheidung zwischen begrenztem und unbegrenztem Nichtdeterminismus. [1]

Nichtdeterministischen Turingmaschinen (auch bekannt als „NTMs“) haben begrenzten Nicht - Determinismus, daß jeder Zustandsübergang hat eine beschränkte Anzahl von Möglichkeiten, das heißt die Anzahl der Programme (auch bekannt als „Konfigurationen“) endlich ist . Das Band bleibt unbegrenzt, so dass der Kündigungsnachweis unentscheidbar bleibt. Bei einer bestimmten Eingabe, die angehalten wird, ist die Ausgabe jedoch deterministisch und zeitlich begrenzt. Das heißt, bei jeder Eingabe ist das Ergebnis deterministisch oder endet nicht. Außerdem führen NTMs alle möglichen Konfigurationen parallel aus, sodass sie exponentiell schneller als die Emulation von NTMs auf deterministischen Turing-Maschinen (auch als „DTMs“ bezeichnet) ausgeführt werden. [2]

Es gibt wirklich keine nicht deterministische Beziehung zwischen Eingaben und Ergebnissen in NTMs, da das Ergebnis für jede Eingabe und jeden Anfangszustand immer das gleiche ist, was offensichtlich ist, weil sie von DTMs ohne zusätzliche Zufälligkeit emuliert werden können. [2] Unentscheidbar ist nicht das Gegenteil von deterministisch, denn nicht aufzuhalten ist auch ein deterministisches Ergebnis. Deterministische Maschinen haben immer das gleiche Ergebnis für eine bestimmte Eingabe, auch wenn dieses Ergebnis nicht zum Stillstand kommen soll. Der lokalisierte Nichtdeterminismus von NTMs ist in jedem Zustandsübergang des ausführenden Algorithmus. Es ist von vornherein unentscheidbar, welcher Pfad des Baums beim Bereitstellen des Ausgabezustands enden könnte. Aber Unentscheidbarkeit ist kein Nichtdeterminismus. Der Begriff "beschränkter Nichtdeterminismus" soll daher die lokalisierte Unbestimmtheit innerhalb der Zustandsmaschine beschreiben, nicht jedoch das Verhältnis von Eingaben zu Ergebnissen. daher der begriff „begrenzt“. Ich denke immer noch, dass der Begriff „beschränkter Nichtdeterminismus“ ein Oxymoron ist und genauer als Turing-Maschine mit „parallelisiertem Zustandsübergang“ beschrieben werden könnte.

Während unbegrenzter Nichtdeterminismus (auch „Indeterminismus“ genannt) für einen bestimmten Eingabe- oder Anfangszustand eine unbegrenzte Anzahl möglicher Zustände aufweist. Unbegrenzter Nicht-Determinismus beinhaltet nicht nur die Anzahl der möglichen Konfigurationen von Programmen, sondern auch einen unbegrenzten externen Zustand, der nicht Teil des Eingabe- oder Anfangszustands ist, wie beispielsweise unbegrenzte Verzögerungen. Daher können die Ergebnisse bei wiederholten Ausführungen für dieselbe Eingabe oder Anfangsbedingung variieren. Somit besteht keine deterministische Beziehung zwischen Input und Outcome. [3]

Randomisierte und probabilistische Algorithmen verwenden einen gewissen Nichtdeterminismus, dh eine zufällige Auswahl möglicher Konfigurationen, die möglicherweise an die Anzahl der Konfigurationen gebunden sind, führen jedoch nicht alle möglichen Konfigurationen aus, wie dies bei NTMs der Fall ist. Sie sind daher nur deterministisch, wenn die Zufälligkeit deterministisch ist (z. B. PRNG) und der Anfangszustand der Entropie für die Zufälligkeit als Teil der Eingabe betrachtet wird.

[1] https://en.wikipedia.org/w/index.php?title=Unbounded_nondeterminism&oldid=710628370#Nondeterministic_automata

[2] https://en.wikipedia.org/w/index.php?title=Non-deterministic_Turing_machine&oldid=754212081#Equivalence_with_DTMs

[3] Hewitt, Meijer und Szyperski: The Actor Model (alles, was Sie wissen wollten ...) . Springe zur 17:44 Minuten Marke.

Abgesehen von all den Antworten, die den Unterschied erklären, habe ich ein Beispiel, das Ihnen helfen kann, das zu finden, was sie sagen wollen.
Betrachten wir eine Münze werfen, Sie entweder einen bekommen H oder T . Wenn der Münzwurf zufällig ist, ist es sehr wahrscheinlich, dass von 1000 Münzwürfen 500 H sind und es ist ziemlich unwahrscheinlich, dass 999 von ihnen H sind . Aber wenn der Münzwurf nicht deterministisch ist, können wir nicht sagen, dass es sehr unwahrscheinlich ist , 999 H zu erhalten.

Randomisierte Algorithmen (Polynomialzeit, Boolesches Ergebnis) gehören zur RP-Komplexitätsklasse. Hierbei handelt es sich um eine Teilmenge von NP, in der sich nicht deterministische Algorithmen (Polynomialzeit, Boolesches Ergebnis) und eine Obermenge von P, in der deterministische Algorithmen (Polynomialzeit, Boolesches Ergebnis) befinden. Algorithmen sind vorhanden.

Bei der Teilmengenkomplexität geht es darum , Probleme in einer Menge auf eine andere Menge zu reduzieren . Somit schließt RP ⊆ NP die Möglichkeit von randomisierten Algorithmen aus, die ebenfalls nicht deterministisch sind, da definitiv eine Obermenge die Untermenge enthält. Untermenge bedeutet, dass jeder RP-Algorithmus (oder ein beliebiger RP-vollständiger Algorithmus) auf einen NP-Algorithmus (oder einen beliebigen NP-vollständigen Algorithmus) reduziert werden kann. P ist eine Teilmenge von RP, da jedes Problem in P auf ein Problem in RP reduziert werden kann, bei dem der Betrag der unkontrollierten Entropie 0 ist.

_{Tangential ist dies analog dazu, wie jedes Problem in NC (parallele Berechnung) durch Simulieren der parallelen Berechnung in einer Reduktion auf ein serielles Problem in P auf ein Problem in P reduziert werden kann, aber es ist noch nicht bewiesen, dass das Gegenteil zutrifft, d. H dass jedes Problem in P auf ein Problem in NC reduzierbar ist oder sich als nicht wahr erwiesen hat, dh der unplausible Beweis, dass ein P-vollständiges Problem nicht auf ein Problem in NC reduzierbar ist. Es ist möglich, dass es Probleme gibt, die von Natur aus seriell sind und nicht parallel berechnet werden können, aber den Beweis zu erbringen, dass P ≠ NC nicht plausibel ist (aus Gründen, die in dieser Antwort nicht erörtert werden können).}

Allgemeiner (dh nicht beschränkt auf boolesche Ergebnistypen) unterscheiden sich randomisierte Algorithmen von deterministischen Algorithmen darin, dass ein Teil der Entropie von außen stammt . Randomisierte Algorithmen unterscheiden sich von nicht deterministischen Algorithmen, da die Entropie begrenzt ist und somit bewiesen werden kann, dass randomisierte (und nicht deterministische) Algorithmen immer enden.

Die Unvorhersehbarkeit von nichtdeterministischen Algorithmen ist wegen Unfähigkeit, aufzuzählen , alle möglichen Permutationen der Eingangs Entropie (die Ergebnisse in Unvorhersehbarkeit der Terminierung). Die Unvorhersehbarkeit eines randomisierten Algorithmus ist auf die Unfähigkeit zur Steuerung zurückzuführendie gesamte Eingabe-Entropie (was zu einer Unvorhersehbarkeit eines unbestimmten Ergebnisses führt, obwohl die Rate der Unvorhersehbarkeit vorhergesagt werden kann). Keines davon sind Aussagen über die Unvorhersehbarkeit der richtigen Antwort auf das Problem, sondern die Unvorhersehbarkeit manifestiert sich im Seitenkanal der Beendigung bzw. im unbestimmten Ergebnis. Es scheint, dass viele Leser Unvorhersehbarkeit in einem Bereich mit Unvorhersehbarkeit des korrekten Ergebnisses in Konflikt bringen, was eine von mir nie geschriebene Konfluenz ist (siehe Editierverlauf).

Es ist wichtig zu verstehen, dass Nichtdeterminismus immer (in jeder Wissenschaft oder Verwendung des Begriffs) die Unfähigkeit ist, universelle (dh unbegrenzte) Entropie aufzuzählen. Während sich Randomisierung auf den Zugriff auf eine andere Entropiequelle bezieht (in Programmen, deren Entropie nicht von den Eingabevariablen gesteuert wird), die möglicherweise unbegrenzt ist oder nicht.

Ich habe den folgenden Kommentar unter der derzeit beliebtesten Antwort auf den anderen Thread hinzugefügt, der eine ähnliche Frage stellt.

Alle Wissenschaften verwenden dieselbe Definition des Nichtdeterminismus, die sich auf den Begriff der unbegrenzten Entropie bezieht. Unvorhersehbare Ergebnisse in allen Wissenschaften sind auf die Unfähigkeit zurückzuführen, alle möglichen Ausgaben eines Algorithmus (oder Systems) a priori aufzulisten, da er unbegrenzte Zustände, dh NP-Komplexitätsklassen, akzeptiert. Das Angeben einer bestimmten Eingabe, um zu beobachten, ob sie anhält, und das Feststellen, dass das Ergebnis idempotent ist, entspricht in anderen Wissenschaften dem Konstanthalten des Rests der Entropie des Universums, während derselbe Zustandswechsel wiederholt wird. Computing ermöglicht diese Entropieisolation, die Naturwissenschaften dagegen nicht.

Fügen Sie einige der besten Kommentare hinzu, um meinen Standpunkt über die einzige hervorstechende Unterscheidung zwischen randomisiert und nicht deterministisch zu verdeutlichen.

Es ist wirklich sehr elegant und leicht, die Unterscheidung zu erkennen, wenn Sie aufhören, sie durcheinander zu bringen, indem Sie versuchen, sie vom betrieblichen Standpunkt aus anstatt vom Standpunkt der hervorstechenden Entropie aus zu beschreiben.

@reinierpost Jeder verschmilzt den Unterschied zwischen randomisiert und nicht deterministisch. Dies führt dazu, dass Ihr Kommentar durcheinander gerät. Der Algorithmus reagiert auf die Interaktion der Eingabe- (Variablen-) Entropie und der (invarianten) internen Entropie des Quellcodes. Nichtdeterminismus ist unbegrenzte Entropie. Invariante Entropie kann sogar intern unbegrenzt sein, z. B. durch Erweitern der Stellen von π . Randomisiert ist, dass ein Teil der Entropie nicht wie definiert an den Eingang gekoppelt ist (dh, es kann sich um einen Systemaufruf /dev/randomoder eine simulierte Zufälligkeit handeln, z. B. NFA oder ein PRNG).

.

@Raphaels formale Definition des nicht deterministischen endlichen Automs (NFA) ist die endliche Eingabe-Entropie (Daten: das 5-Tupel). Somit kann jede NFA auf einer deterministischen Turing-Maschine ausgeführt werden, dh es ist keine nicht deterministische Turing-Komplett-Maschine erforderlich. Somit gehören NFAs nicht zu den nicht deterministischen Problemen. Der Begriff "Nichtdeterminismus" in NFA ist, dass sein Determinismus (obwohl er eindeutig vorhanden ist, da jeder NFA in einen DFA umgewandelt werden kann) nicht explizit erweitert wird - nicht dasselbe wie Nichtdeterminismus der Berechnung

.

@Raphael der behauptete "Nichtdeterminismus" in NFAs ist wirklich Zufälligkeit ist Sinn meiner Definition der Unterscheidung zwischen Zufälligkeit und Nichtdeterminismus. Meine Definition ist, dass Zufälligkeit ein Teil der Entropie ist, der nicht unter der Kontrolle, dem Wissen (oder der gewünschten nicht expliziten Erweiterung im Fall einer NFA) der Eingabe in das Programm oder die Funktion steht. Ein echter Nichtdeterminismus ist die Unfähigkeit, die Entropie in jedem Fall zu kennen, weil sie unbegrenzt ist. Genau das unterscheidet den randomisierten vom Nichtdeterminismus. NFA sollte also ein Beispiel für das erstere sein, nicht für das letztere, wie Sie behauptet haben.

.

@Raphael Wie ich bereits erklärte, verbindet der Begriff des Nichtdeterminismus in NFAs das Nichtdeterministische mit der endlichen Entropie. Somit ist der Nicht-Determinismus ein lokales Konzept, den Determinismus nicht als eine Form der Komprimierung oder Zweckmäßigkeit zu erweitern. Wir sagen daher nicht, dass NFAs nicht deterministisch sind, sondern eher den Anschein von Zufälligkeit für ein Orakel, das nicht bereit ist, die deterministische Expansion zu berechnen. Aber es ist alles ein Trugbild, weil es deterministisch erweitert werden muss, weil die Entropie nicht unbegrenzt, dh endlich ist.

Wörterbücher sind Werkzeuge. Lerne sie zu benutzen.

zufälliges Adjektiv

Statistiken. von oder Charakterisieren eines Auswahlprozesses, bei dem jeder Gegenstand einer Menge die gleiche Wahrscheinlichkeit hat, ausgewählt zu werden.

Sein oder sich auf eine Menge oder ein Element einer Menge beziehend, von denen jedes Element die gleiche Auftrittswahrscheinlichkeit hat

Die Randomisierung erfordert daher nur, dass ein Teil der Eingabe-Entropie gleich wahrscheinlich ist, was mit meiner Definition übereinstimmt, dass ein Teil der Eingabe-Entropie nicht vom Aufrufer der Funktion gesteuert wird. Beachten Sie, dass für die Randomisierung nicht erforderlich ist, dass die Eingabe-Entropie für die Beendigung unentscheidbar ist.

In der Informatik ist ein deterministischer Algorithmus ein Algorithmus, der bei einer bestimmten Eingabe immer dieselbe Ausgabe erzeugt, wobei die zugrunde liegende Maschine immer dieselbe Folge von Zuständen durchläuft.

Formal berechnet ein deterministischer Algorithmus eine mathematische Funktion; Eine Funktion hat einen eindeutigen Wert für jede Eingabe in ihrer Domäne, und der Algorithmus ist ein Prozess, der diesen bestimmten Wert als Ausgabe erzeugt.

Deterministische Algorithmen können als Zustandsmaschine definiert werden: Ein Zustand beschreibt, was eine Maschine zu einem bestimmten Zeitpunkt tut. Zustandsautomaten gehen auf diskrete Weise von einem Zustand in einen anderen über. Kurz nachdem wir die Eingabe eingegeben haben, befindet sich die Maschine in ihrem Ausgangszustand oder Startzustand. Wenn die Maschine deterministisch ist, bedeutet dies, dass ab diesem Zeitpunkt der aktuelle Zustand den nächsten Zustand bestimmt. sein Verlauf durch die Menge der Zustände ist vorbestimmt. Beachten Sie, dass eine Maschine deterministisch sein und dennoch niemals anhalten oder enden kann und daher kein Ergebnis liefern kann.

Dies sagt uns also, dass deterministische Algorithmen vollständig durch den Eingangszustand der Funktion bestimmt werden müssen, dh wir müssen nachweisen können, dass die Funktion beendet wird (oder nicht beendet wird) und das kann nicht unentscheidbar sein. Trotz des durcheinandergebrachten Versuchs von Wikipedia, nicht deterministisch zu beschreiben, sind Algorithmen, deren Eingabezustand (Entropie) schlecht definiert ist, die einzige Antithese zur Deterministik, wie sie oben von Wikipedia definiert wurde. Und der einzige Weg, wie der Eingabezustand falsch definiert werden kann, ist, wenn er nicht begrenzt ist (daher kann er nicht deterministisch voranalysiert werden). Dies ist genau das, was eine nicht deterministische Turing-Maschine (und viele reale Programme, die in gängigen Turing-Komplettsprachen wie C, Java, Javascript, ML usw. geschrieben sind) von deterministischen TMs und Programmiersprachen wie HTML, Tabellenkalkulationsformeln unterscheidet. Coq, Epigramm,

In der Theorie der rechnerischen Komplexität sind nichtdeterministische Algorithmen solche, die bei jedem möglichen Schritt mehrere Fortsetzungen ermöglichen können (stellen Sie sich einen Mann vor, der auf einem Waldweg geht, und jedes Mal, wenn er weitergeht, muss er die gewünschte Weggabelung auswählen nehmen). Diese Algorithmen finden nicht für jeden möglichen Rechenweg eine Lösung; Es wird jedoch garantiert, dass sie zu einer korrekten Lösung für einen bestimmten Pfad gelangen (dh der Mann, der durch den Wald geht, findet möglicherweise nur dann seine Hütte, wenn er eine Kombination von "richtigen" Pfaden auswählt). Die Auswahl kann als Vermutung in einem Suchprozess interpretiert werden.

Wikipedia und andere versuchen, Randomisierung mit Nichtdeterminismus zu verbinden, aber wozu sind die beiden Konzepte gut, wenn Sie sie nicht eloquent voneinander unterscheiden wollen?

Bei Determinismus geht es eindeutig um die Fähigkeit zu bestimmen. Bei der Randomisierung geht es eindeutig darum, einen Teil der Entropie gleich wahrscheinlich zu machen.

Die Einbeziehung der Zufallsentropie in den Zustand eines Algorithmus macht ihn nicht unbedingt unbestimmbar. Zum Beispiel kann ein PRNG die geforderte gleichwahrscheinliche statistische Verteilung haben, aber auch vollständig deterministisch sein.

Orthogonale Konzepte zu konflationieren, ist das, was Menschen mit niedrigem IQ tun. Ich erwarte mehr von dieser Community!