Was ist eine Invariante?

129

Das Wort scheint in einer Reihe von Zusammenhängen verwendet zu werden. Das Beste, was ich herausfinden kann, ist, dass sie eine Variable bedeuten, die sich nicht ändern kann. Ist das nicht was Konstanten / Finale (verdammt noch mal Java!) Sind?

Dustman
quelle
Vielleicht hätten sie es als Nicht-Variante bezeichnen sollen?
Johnny

Antworten:

188

Eine Invariante ist eher "konzeptuell" als eine Variable. Im Allgemeinen ist es eine Eigenschaft des Programmstatus, die immer wahr ist. Eine Funktion oder Methode, die sicherstellt, dass die Invariante gilt, soll die Invariante beibehalten.

Beispielsweise kann ein binärer Suchbaum die Invariante haben, dass für jeden Knoten der Schlüssel des linken untergeordneten Knotens kleiner ist als der eigene Schlüssel des Knotens. Eine korrekt geschriebene Einfügefunktion für diesen Baum behält diese Invariante bei.

Wie Sie sehen, können Sie dies nicht in einer Variablen speichern, sondern eher eine Aussage über das Programm. Indem Sie herausfinden, welche Art von Invarianten Ihr Programm beibehalten soll, und dann Ihren Code überprüfen, um sicherzustellen, dass diese Invarianten tatsächlich beibehalten werden, können Sie logische Fehler in Ihrem Code vermeiden.

Jacob Baskin
quelle
1
Dieses großartige Beispiel wäre besser, wenn es Ceros Antwort mit dem Wikipedia-Link enthalten würde.
ablarg
2
Das Alter eines Elternteils ist höher als das Alter seiner leiblichen Kinder. Der umgebende Kontext wird sich ändern, aber die Invariante ändert sich nie. Zum Beispiel könnte es die Familie Smith sein, die zwei Kinder hat. Oder es könnte bei anderen Arten eines Säugetiers sein. Der Kontext ändert sich, aber die Invariante ändert sich nicht.
Truthadjustr
1
"... eine Eigenschaft eines Programmzustands, die immer wahr ist ..." - @jacob baskin - gut geschrieben und danke dafür.
Twknab
"... eine Eigenschaft eines Programmzustands, die immer wahr ist ..." - Ich stimme zu, dass sie gut geschrieben ist, aber irreführend sein kann. Zuerst habe ich es als boolean true verstanden, aber ich bin mir ziemlich sicher, dass es bedeutet "... ist immer konstant" (aber vielleicht nur, weil Englisch nicht meine Muttersprache ist)
dev-null
29

Es ist eine Bedingung, von der Sie wissen, dass sie an einer bestimmten Stelle in Ihrer Logik immer wahr ist und die Sie beim Debuggen überprüfen können, um herauszufinden, was schief gelaufen ist.

Mondschatten
quelle
17

Normalerweise betrachte ich sie eher als Algorithmen oder Strukturen.

Beispielsweise könnten Sie eine Schleifeninvariante haben, die bestätigt werden kann - immer zu Beginn oder am Ende jeder Iteration wahr. Das heißt, wenn Ihre Schleife eine Sammlung von Objekten von einem Stapel zum anderen verarbeiten sollte, könnten Sie sagen, dass | stack1 | + | stack2 | = c oben oder unten in der Schleife ist.

Wenn die invariante Prüfung fehlschlug, würde dies darauf hinweisen, dass ein Fehler aufgetreten ist. In diesem Beispiel kann dies bedeuten, dass Sie vergessen haben, das verarbeitete Element auf den endgültigen Stapel usw. zu verschieben.

Michael Haren
quelle
17

Die Magie von Wikipedia: Invariant (Informatik)

In der Informatik wird ein Prädikat, das, wenn es wahr ist, während einer bestimmten Folge von Operationen wahr bleibt, als (eine) Invariante dieser Folge bezeichnet.

Cero
quelle
2
Links? Fachjargon? LESEN? WTF ? ;) Im Ernst, guter Link, aber eine kleine Zusammenfassung wäre schön.
Dustman
10

Wie diese Zeile besagt:

In der Informatik wird ein Prädikat, das, wenn es wahr ist, während einer bestimmten Folge von Operationen wahr bleibt, als (eine) Invariante dieser Folge bezeichnet.

Um diese Hoffnung besser zu verstehen, hilft dieses Beispiel in C ++.

Stellen Sie sich ein Szenario vor, in dem Sie einige Werte abrufen und die Gesamtzahl in einer Variablen mit dem Namen as countabrufen und sie in einer Variablen mit dem Namen as hinzufügen müssensum

Die Invariante (wieder eher wie ein Konzept):

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

Der Code für das oben genannte wäre ungefähr so:

int count=0;
double sum=0,x=0;
while (cin >> x) {
++count;
sum+=x;
}

Was macht der obige Code?

1) Liest die Eingabe von cinund fügt sie einx

2) Inkrementieren Sie nach einem erfolgreichen Lesevorgang countundsum = sum + x

3) Wiederholen Sie 1-2 bis zum Ende des Lesens (dh Strg + D).

Schleifeninvariante:

Die Invariante muss IMMER wahr sein . Zunächst beginnen Sie Ihren Code damit

while(cin>>x){
  }

Diese Schleife liest Daten von der Standardeingabe und speichert sie in x. Schön und gut. Aber die Invariante wird falsch, weil der erste Teil unserer Invariante nicht befolgt (oder wahr gehalten) wurde.

// we have read count grades so far, and

Wie kann man die Invariante wahr halten?

Einfach! Inkrementanzahl.

So ++count;täte gut !. Jetzt wird unser Code so etwas,

while(cin>>x){
 ++count; 
 }

Aber

Sogar jetzt ist unsere Invariante (ein Konzept, das WAHR sein muss) falsch, weil wir jetzt den zweiten Teil unserer Invariante nicht erfüllt haben .

// sum is the sum of the first count grades

Was tun jetzt?

Fügen Sie xes hinzu sumund speichern Sie es in sum( sum+=x). Beim nächsten Mal cin>>xwird ein neuer Wert in x eingelesen.

Jetzt wird unser Code so etwas,

while(cin>>x){
 ++count; 
 sum+=x;
 }

Lass uns das Prüfen

Ob der Code mit unserer Invariante übereinstimmt

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

Code:

while(cin>>x){
 ++count; 
 sum+=x;
 }

Ah!. Jetzt ist die Schleifeninvariante immer True und der Code funktioniert einwandfrei.

Das obige Beispiel wurde aus dem Buch Accelerated C ++ von Andrew-koening und Barbara-E übernommen und modifiziert

Leere
quelle
4

Etwas, das sich innerhalb eines Codeblocks nicht ändert

Chris
quelle
2

In Anlehnung an das, was es ist, sind Invarianten sehr nützlich, um sauberen Code zu schreiben, da Sie, wenn Sie konzeptionell wissen, welche Invarianten in Ihrem Code vorhanden sein sollten , leicht entscheiden können, wie Sie Ihren Code organisieren, um diese Ziele zu erreichen. Wie bereits erwähnt, sind sie auch beim Debuggen nützlich, da die Überprüfung, ob die Invariante beibehalten wird, oft eine gute Möglichkeit ist, um festzustellen, ob die Manipulation, die Sie ausführen möchten, tatsächlich das tut, was Sie möchten.

Kaushik
quelle
2

Dies ist normalerweise eine Größe, die sich unter bestimmten mathematischen Operationen nicht ändert. Ein Beispiel ist ein Skalar, der sich bei Rotationen nicht ändert. Bei der Magnetresonanztomographie ist es beispielsweise nützlich, eine Gewebeeigenschaft durch eine Rotationsinvariante zu charakterisieren, da ihre Schätzung dann idealerweise nicht von der Ausrichtung des Körpers im Scanner abhängt.

HassanTC
quelle
2

Diese Antwort ist für mein 5 Jahre altes Kind. Stellen Sie sich eine Invariante nicht als konstanten oder festen numerischen Wert vor. Aber es kann sein. Es ist jedoch mehr als das.

Eine Invariante ist vielmehr so ​​etwas wie eine feste Beziehung zwischen verschiedenen Entitäten. Zum Beispiel wird Ihr Alter im Vergleich zu Ihren leiblichen Eltern immer geringer sein. Sowohl Ihr Alter als auch das Alter Ihrer Eltern ändern sich im Laufe der Zeit, aber die Beziehung, die ich oben erwähnt habe, ist unveränderlich.

Eine Invariante kann auch eine numerische Konstante sein. Zum Beispiel ist der Wert von piein invariantes Verhältnis zwischen dem Umfang des Kreises und seinem Durchmesser. Egal wie groß oder klein der Kreis ist, dieses Verhältnis wird immer sein pi.

trueadjustr
quelle
1

Die ADT-Invariante gibt Beziehungen zwischen den Datenfeldern (Instanzvariablen) an, die vor und nach der Ausführung einer Instanzmethode immer wahr sein müssen.

Meshal Almotairi
quelle
0

In dem Buch Java Concurrency in Practice gibt es ein hervorragendes Beispiel für eine Invariante und warum sie wichtig ist .

Obwohl Java-zentriert, beschreibt das Beispiel einen Code, der für die Berechnung der Faktoren einer bereitgestellten Ganzzahl verantwortlich ist. Der Beispielcode versucht, die zuletzt angegebene Nummer und die Faktoren, die zur Verbesserung der Leistung berechnet wurden, zwischenzuspeichern. In diesem Szenario gibt es eine Invariante, die im Beispielcode nicht berücksichtigt wurde, wodurch der Code in einem gleichzeitigen Szenario für Rennbedingungen anfällig geworden ist.

Geben Sie hier die Bildbeschreibung ein

Der Gilbert Arenas Dolch
quelle
0

Alle Antworten hier sind großartig, aber ich hatte das Gefühl, dass ich mehr Licht in die Sache bringen kann:

Aus sprachlicher Sicht unveränderlich bedeutet etwas, das sich nie ändert. Das Konzept stammt zwar aus der Mathematik, ist aber in Kombination mit der Induktion eine der beliebtesten Beweisverfahren.

So geht ein Beweis: Wenn Sie eine Invariante finden, die sich im Ausgangszustand befindet, und diese Invariante unabhängig von einer auf den Staat angewendeten [legalen] Transformation bestehen bleibt, können Sie beweisen, dass ein bestimmter Staat dies nicht hat invariant dann kann es nie auftreten, egal welche Sequenz von Transformationen auf den Ausgangszustand angewendet wird.

Die bisherige Denkweise (wieder kombiniert mit Induktion) ermöglicht es nun, die Logik von Computersoftware vorherzusagen. Besonders wichtig, wenn die Ausführung in Schleifen erfolgt, in denen eine Invariante verwendet werden kann, um zu beweisen, dass eine bestimmte Schleife ein bestimmtes Ergebnis liefert oder den Status eines Programms niemals auf eine bestimmte Weise ändert.

Wenn eine Invariante verwendet wird, um eine Schleifenlogik vorherzusagen, wird sie als Schleifeninvariante bezeichnet . Es kann außerhalb von Schleifen verwendet werden, aber für Schleifen ist es wirklich wichtig, da Sie oft viele Möglichkeiten oder unendlich viele Möglichkeiten haben.

Beachten Sie, dass ich das Wort "Prädikat" der Logik einer Computersoftware verwende und nicht beweise. Und das liegt daran, dass Invarianten in der Mathematik zwar als Beweis verwendet werden können, aber niemals beweisen können, dass die ausgeführte Computersoftware das liefert, was erwartet wird, da die Software auf vielen Abstraktionen ausgeführt wird, die niemals bewiesen werden können dass sie das liefern, was erwartet wird (denken Sie zum Beispiel an die Hardware-Abstraktion).

Während die theoretische und strenge Vorhersage der Softwarelogik nur für hochkritische Anwendungen wie medizinische und militärische Anwendungen wichtig ist. Invariant kann weiterhin verwendet werden, um den typischen Programmierer beim Debuggen zu unterstützen. Es kann verwendet werden, um zu wissen, wo an einem bestimmten Ort das Programm fehlgeschlagen ist, weil es eine bestimmte Invariante nicht beibehalten hat - viele von uns verwenden es trotzdem, ohne darüber nachzudenken.

ehab
quelle